1 of 31

�

Jinkwon Kim Mincheol Kang Jeongkyu Hong Soontae Kim

High Performance Computer Architecture (HPCA) 2022

Exploiting Inter-block Entropy �to Enhance the Compressibility �of Blocks with Diverse Data

2 of 31

Executive Summary

2

Ideal Hardware-based Compression Algorithm

High Compression Coverage
Low Decompression Latency

High Compression Coverage

✔

Low Decompression Latency

✔

Inter-block Similarity Approach

Low Decompression Latency

✔

Low Compression Coverage

🗶

Intra-block Similarity Approach

Slide Title

3 of 31

3

1. Background

2. Motivation and Design Challenges

3. Algorithm: Entropy-based Pattern Compression Technique

4. Architecture: EPC-support DRAM System

5. Evaluation

Slide Title

4 of 31

Memory Compression Architecture

Attaché Framework

Inline-metadata to eliminate metadata overhead
The bandwidth is doubled when accessing two compressed blocks.

For maximum performance gain

High Compression Coverage
Low Decompression Latency

Subrank 0

Subrank 1

Uncompressed C

Compressed B

Meta.

Compressed A

Slide Title

Here is a conventional memory system architecture.

Typically, main memory consists of 8 chips and

[Click] thus a memory block is stored into 8 chips.

[Click] To improve memory bandwidth, attache framework for hardware-based memory compression architecture has been proposed.

[Click] In this framework, the main memory is divided into a smaller group, called a subrank,

[Click] and then compressed blocks are stored into only one subrank.

[Click] In addition, metadata for storing compression status is stored into block itself and is handled by inline-metadata handler to eliminate metadata overheads and the additional hardware units are implemented in the memory controller.

So, in this framework, the memory bandwidth can be doubled when two compressed blocks are accessed because each subrank can operate independently.

[Click] Thus, To maximize performance gain, we need a compression technique that has high compression coverage to maximize bandwidth benefits and low decompression latency to avoid an increase in the memory latency.

5 of 31

5

1. Background

2. Motivation and Design Challenges

3. Algorithm: Entropy-based Pattern Compression Technique

4. Architecture: EPC-support DRAM System

5. Evaluation

Slide Title

6 of 31

Limitations of the intra-block Approach

Previous compression techniques (BDI, FPC, C-Pack, BPC) build upon

1) intra-block similarity and 2) narrow-width value property.
Cannot handle blocks with diverse data (e.g., blocks with both pointer and primitive data types).

6

(Above 0x7FFF_0000_0000)

(Above 0x40000)

Slide Title

Since previous compression techniques utilize intra-block similarity and narrow width value property, they cannot handle blocks that have diverse data.

One of the examples is a block that has both pointer and primitive data types.

[Click] Unlike primitive data types, a pointer stores the virtual address of the pointed object.

[Click] Typically, a pointer points to the heap memory segment.

In the heap segment, depending on the allocation size, the small heap or memory mapping segment (i.e., large heap) is allocated. Each heap allocation assigns a new chunk in the particular segment.

Thus, a pointer value is higher than a narrow-width value and different from the typical data, but only determined by the pointed object address.

[Click] For example, Xalancbmk(잴런스) consists of countless small heap chunks and many memory blocks are derived from XalancSourceTreeText class and thus have 7 pointers which point to different chunks.

[Click] In mcf, two large heap chunks are allocated and almost memory blocks are derived from arc struct and thus have 4 pointers where two pointer points to the first chunk and the others point to the second chunk.

As shown in this example, pointers in a single memory block do not have a similar value because each pointer points to a distinct address.

7 of 31

Limitations of the intra-block Approach

Previous compression techniques (BDI, FPC, C-Pack, BPC) build upon

1) intra-block similarity and 2) narrow-width value property.
Cannot handle blocks with diverse data (e.g., blocks with both pointer and primitive data types).

7

High Compression Coverage

✔

Low Decompression Latency

✔

Inter-block Similarity Approach

Low Decompression Latency

✔

Low Compression Coverage

🗶

Intra-block Similarity Approach

Slide Title

8 of 31

Challenges of the inter-block Approach

Two key challenges, especially in the main memory with the multi-core system.

1) Block Grouping: How to group similar blocks (Block Grouping)
2) Block Managing: How to choose and manage block groups (w/o additional metadata overhead)

8

Deduplication Technique [DATE ’20 for Cache; ASPLOS ’21 for Cache+Memory]

Block Grouping (Good), Block Managing (Bad; Additional Metadata Overhead for indirection)

MORC [MICRO ’15 for Cache]

Block Grouping (Bad), Block Managing (Bad; Additional Metadata Overhead for time-ordering)

Thesaurus [ASPLOS ’20 for Cache]

Block Grouping (Bad), Block Managing (Good)

Our goal

Block Grouping (Good), Block Managing (Good)

Slide Title

There are two key challenges to support the inter-block approach in the main memory with the multi-core system.

The first is block grouping and the second is block managing.

Block grouping is the way to group similar blocks while block managing is which candidate block groups is selected for compression, and managing the block groups.

[Click]

There are some previous works that leverage inter-block similarity.

However, these techniques are proposed for the cache memory system, which can hide the additional metadata overhead and has a small footprint.

So, when applying these techniques to the GB main memory system, they cause additional huge metadata overheads or cannot find similar blocks because of the large footprint in the main memory system.

[Click]

Thus, our goal is to support efficient block grouping without additional block managing metadata overheads.

9 of 31

Key Idea

1) Block Grouping

Leverage two kinds of low-entropy among blocks

1) The naturally observed low-entropy
2) The artificially generated low-entropy by our techniques.

9

2) Block Managing

Frequently-used patterns are discovered by our selection methods.

Pattern metadata are seamlessly stored along with the inline-metadata (No additional metadata overhead).

Selected patterns are stored in a dedicated table within the memory controller.

Slide Title

Let’s talk about our key idea.

[click] Our key idea for block grouping is to leverage two kinds of low-entropy among blocks. The first one is natural low-entropy and the second one is the artificially generated low-entropy by our techniques.

[Click] For example, our technique investigated the data in the block.

[Click] and then properly discover the low-entropy region (the red one) and the high-entropy region (the gray one). Based on the low-entropy region, we group the blocks that have the same low-entropy region.

[click] For block managing, the frequently-used patterns are discovered by our proposed techniques

[click] and then the selected patterns are stored in a dedicated table within the memory controller.

[click] After the block is compressed,

[click] the pattern metadata is stored along with the inline-metadata, which eliminates the additional metadata overheads.

By doing these, our paper can support efficient block grouping without additional block managing metadata overheads.

10 of 31

10

1. Background

2. Motivation and Design Challenges

3. Algorithm: Entropy-based Pattern Compression Technique

4. Architecture: EPC-support DRAM System

5. Evaluation

Slide Title

11 of 31

Naturally Observed Low-entropy

1) bulk memory allocations (e.g., large heap allocation) are dominant

11

Slide Title

12 of 31

Naturally Observed Low-entropy

1) bulk memory allocations (e.g., large heap allocation) are dominant

Arrays of structure, primitive type array, and pointer type array

12

node size 104 arc size 64

malloc for nodes 4 MB

malloc for dummy arcs 3 MB

malloc for arcs 1668 MB

------------------------------

heap about 1675 MB

Slide Title

13 of 31

Naturally Observed Low-entropy

1) bulk memory allocations (e.g., large heap allocation) are dominant

Arrays of structure, primitive type arrays, and pointer type arrays

13

Slide Title

14 of 31

Naturally Observed Low-entropy

2) Each word among the same layout blocks have low-entropy

14

1. Integer Primitive type

Mostly zero or narrow-width values.
Most MSBs are “0” or “1”

2. Floating-point primitive Type

Similar Floating-point values have similar MSBs (sign and exponent bit field)

3. Pointer Type

Each pointer in the same layout tends to point to the adjacent heap chunk.
Most MSBs are the similar.

Slide Title

15 of 31

Artificially Generated Low-entropy

Can address blocks with diverse data

15

Slide Title

16 of 31

Artificially Generated Low-entropy

Limitations of the natural low-entropy

16

To overcome the limitation of natural low-entropy, we propose three optimization techniques to generate artificial low-entropy

Slide Title

17 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

17

Slide Title

18 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

18

Decreases the entropy between narrow-width values with opposite signs.

Slide Title

19 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

19

Decreases the entropy between narrow-width values with opposite signs.

Transforms the low-entropy region.

Slide Title

20 of 31

20

1. Background

2. Motivation and Design Challenges

3. Algorithm: Entropy-based Pattern Compression Technique

4. Architecture: EPC-support DRAM System

5. Evaluation

Slide Title

21 of 31

Overall Architecture

21

Slide Title

22 of 31

Pattern Selection and Deletion Operations

Pattern Selection Method

1. Profiling-based Static Pattern Selection

Selects the most frequently-used patterns based on the profiling.
Patterns are static during the program execution.

22

Total Dynamic Instructions

0%

20%

40%

60%

80%

100%

1B

2. Hardware-based Dynamic Pattern Selection

Can select the temporarily (dynamic) frequently-used patterns for a particular phase.
Dedicated sampler hardware samples patterns.
Sampling patterns are replaced based on the LRU policy.
Promote sampling patterns (>= Threshold)

Pattern Deletion Method

The pattern can be removed when the pattern count reaches zero.

Slide Title

To fill the inter-block pattern table, we propose two pattern selection methods.

[Click] The first one is profiling-based static pattern selection.

[Click] In the profiling method, we select the most frequently-used patterns based on the profiling. Thus, selected patterns are not changed during the program execution.

[Click] The second one is hardware-based dynamic pattern selection.

The hardware method uses dedicated sampler hardware to select the temporarily frequently-used patterns for a particular phase.

[Click] In brief, the sampler uses LRU replacement policy and promotes sampling patterns to the inter-block pattern if the sampling count exceeds the threshold.

Please refer to our paper for more detailed operation in the sampler

[Click] For the pattern deletion method, we remove the pattern when the pattern count reaches zero.

23 of 31

Hybrid Approach

An application with weak inter-block similarities.

Needs more inter-block patterns (i.e., High Hardware Overhead)

23

Hybrid Approach

Intra-block compression -> inter-block compression
Improve compression coverage and reduce the number of inter-block patterns.

Slide Title

24 of 31

24

1. Background

2. Motivation and Design Challenges

3. Algorithm: Entropy-based Pattern Compression Technique

4. Architecture: EPC-support DRAM System

5. Evaluation

Slide Title

25 of 31

Methodology

Simulator:

Ramulator with CPU-trace-driven mode
CPU traces from PinTool

25

100%

Total Dynamic Instructions

0%

20%

40%

60%

80%

1B

2B

Energy Consumption Estimation:

Micron DDR4 system power calculator
CACTI-P and Synopsys Design Compiler with 45nm

Hardware Configuration:

BDI, FPC, C-Pack, and BPC: 1,5,8, and 11 decompression CPU cycles.
Thesaurus: 12-bit Hash size and 4096 base cache size (256KB SRAM), 3 decompression CPU cycles.
EPC: 256 entry inter-block pattern table / 512 entry sampling pattern table, 3 decompression CPU cycles.

Workloads:

SPEC 2006, SPEC 2017, GAP: 12 mix and 4 rate-mode.
Five program phases: First 2B, 1B after 20%, 40%, 60%, 80%

Slide Title

We use ramlator with CPU-trace mode and CPU traces are generated from PinTool. The left table shows the system configuration. Since our focus is main memory with multicore-system, we use 16GB main memory with 8 core configuration.

[Click] We use Micron DDR4 calculator for DRAM power consumption, and CACTI-P and Synopsys design compiler for additional hardware unit for compression technique.

[Click] We compare BDI, FPC, C-Pack, and BPC in intra-block compression techniques and Thesaurus in inter-block compression technique.

We use the decompression latency and detailed configuration presented in each paper.

For our EPC configuration, we use 256 inter-block pattern table size and 512 sampling pattern table size for the hardware-based pattern selection method.

[Click] We randomly combine benchmarks from SPEC 2006, SPEC 2017, ad GAP suite to create 12 eight-core mix workloads and we choose 4 rate-mode applications.

Since compressibility is highly changed on the prgoram running, we use five program phases: The first 2B instructions, and 1B instructions after 20%, 40%, 60,% ad 80% program instructions are finished.

26 of 31

Results

26

13%

7%

25%

31%

13% 11%

7x 163x

Slide Title

27 of 31

More Results in the Paper

Detailed architecture of DSD, SC, XOR transformation

Detailed operation of Sampler in hardware-based EPC.

Compression coverage and pattern usage in each application

Sampler configuration sensitivity results

Pattern replacement results

Inter-block pattern table sensitivity results

Channel number sensitivity results

27

Slide Title

28 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

28

The below seven cases are determined by five detectors in DSD.

(1) an 8-byte pointer / (2) an 8-byte INT (and character/bool/etc. with padding)
(3) an 8-byte FP / (4) two 4-byte INT / (5) two 4-byte FP
(6) one 4-byte / (7) one 4-byte FP and one 4-byte INT

Slide Title

29 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

29

Decreases the entropy between narrow-width values with opposite signs.

Slide Title

30 of 31

Artificially Generated Low-entropy

Detect whether an 8-byte word consist of one 8-byte data or two 4-byte data

30

Decreases the entropy between narrow-width values with opposite signs.

Transforms the low-entropy region.

Slide Title

31 of 31

Overall Architecture

31

Slide Title