Memory Specialization for Processors

This content delves into stream-based memory specialization and computation patterns for general-purpose processors. It discusses a new ISA memory abstraction, stream characteristics, ISA extensions, and opportunities for microarchitecture advancements. Explore conventional memory abstractions, prefetch mechanisms, and opportunities for efficient memory access patterns.

• Memory Specialization
• General Processors
• Stream-based Computing
• ISA Abstraction
• Microarchitecture

brynly Follow

Uploaded on Feb 15, 2025 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Stream-based Memory Specialization for General Purpose Processors Zhengrong Wang Prof. Tony Nowatzki 1

2. Computation & Memory Specialization SIMD Dataflow + + - + - + - + - + - New ISA abstraction for certain computation pattern. / Core Acc. + b[i] b[0] b[1] b[2] a[b[0]] a[b[1]] a[b[2]] New ISA abstraction for memory access pattern? Mem Acc. a[b[i]] Stream 2

3. Stream: A New ISA Memory Abstraction Stream: A decoupled memory access pattern. Higher level abstraction in ISA. Decouple memory access. Enable efficient prefetching. Leverage stream information in cache policies. 60% memory accesses streams. 1.37 speedup over a traditional O3 processor. Core Acc. b[i] b[0] b[1] b[2] a[b[0]] a[b[1]] a[b[2]] a[b[i]] Stream Mem Acc. 3

4. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 4

5. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 5

6. Conventional Memory Abstraction O3 Core L1 Cache L2 Cache while (i < N) { if (cond) v += a[i]; i++; } Overhead 3: Assumption on reuse. if Overhead 2: Similar address computation/loads. addr if Addr. load addr Miss Hit Addr. load Miss Hit Overhead 1: Hard to prefetch with control flow. Val. add Resp. Resp. Val. br add Resp. Resp. 6 br

7. Opportunity 1: Prefetch with Ctrl. Flow O3 Core L1 Cache L2 Cache cfg(a[i]); while (i < N) { if (cond) v += a[i]; i++; } Prefetch. cfg. SE. Miss Hit Before loop. if Resp. Resp. addr if Addr. load addr Miss Hit Hit Addr. load Miss Hit Hit Overhead 1: Hard to prefetch with control flow. control flow. Opportunity 1: Prefetch with Val. add Resp. Resp. Val. br add Resp. Resp. 7 br

8. Opportunity 2: Semi-Binding Prefetch s_a = cfg(); while (i < N) { if (cond) v += s_a; i++; } O3 Core L1 Cache L2 Cache Prefetch. cfg. SE. Miss Hit Before loop. if Resp. Resp. addr if Opportunity 2: Semi-binding Overhead 2: Similar address computation/loads. prefetch. FIFO Addr. load addr Hit Addr. Opportunity 1: Prefetch with control flow. load Hit add Resp. Val. br add Resp. br 8

9. Opportunity 3: Stream-Aware Policies O3 Core L1 Cache L2 Cache s_a = cfg(); while (i < N) { if (cond) v += s_a; } Prefetch. cfg. SE. Miss Hit Before loop. if Resp. Resp. Overhead 2: Repeated address computation/loads. prefetch. Opportunity 2: Semi-binding if add FIFO Opportunity 3: Overhead 3: Assumption on reuse. Better policies, e.g. bypass a cache level if no locality. br add Opportunity 1: Prefetch with control flow. br 9

10. Related Work Decouple access execute. Outrider [ISCA 11], DeSC [MICRO 15], etc. Ours: New ISA abstraction for the access engine. Prefetching. Stride, IMP [MICRO 15], etc. Ours: Explicit access pattern in ISA. Cache bypassing policy. Counter-based [ICCD 05], LLC bypassing [ISCA 11], etc. Ours: Incorporate static stream information. 10

11. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 11

12. Stream Characteristics Stream Type Trace analysis on CortexSuite/SPEC CPU 2017. 51.49% affine, 10.19% indirect. Indirect streams can be as high as 40%. 100% 90% 80% 70% 60% Support indirect stream. 50% 40% 30% 20% 10% 0% Affine Indirect PC Unqualified Outside 12

13. Stream Characteristics Stream Length 51% stream accesses from stream longer than 1k. Some benchmarks contain short streams. 100% 90% 80% Support longer stream to capture long term behavior. 70% Low overhead to support short streams. 60% 50% 40% 30% 20% 10% 0% pca rbm disparity lbm_s >1k sphinx srr svm >0 xz_s avg. >100 >50 13

14. Stream Characteristics Control Flow 53% stream accesses from loop with control flow. 100% 90% 80% 70% Decouple from control flow. 60% 50% 40% 30% 20% 10% 0% >3 3 2 1 Execution Paths within the Loop 14

15. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 15

16. Stream ISA Extension Basic Example Original C Code int i = 0; while (i < N) { sum += a[i]; i++; } Stream Decoupled Pseudo Code Stream Dependence Graph stream_cfg(s_i, s_a); while (s_i < N) { sum += s_a; stream_step(s_i); } stream_end(s_i, s_a); s_i s_a Stream a[i] Step. User Pseudo-Reg Iter. 0 1 2 Memory 0x400 Memory 0x404 s_a i++ i++ Memory 0x408 16

17. Stream ISA Extension Control Flow Original C Code Stream Decoupled Pseudo Code Stream Dependence Graph int i = 0, j = 0; while (cond) { if (a[i] < b[j]) i++; else j++; } stream_cfg(s_i, s_a, s_j, s_b); while (cond) { if (s_a < s_b) stream_step(s_i); else stream_step(s_j); } stream_end(s_i, s_a, s_j, s_b); s_i s_j s_a s_b Stream a[i] Step User Iter. Pseudo-Reg Memory 0x400 Memory 0x404 0 1 2 i++ s_a Memory 0x408 i++ 17

18. Stream ISA Extension Indirect Stream Original C Code Stream Decoupled Pseudo Code Stream Dependence Graph stream_cfg(s_i, s_a, s_b); while (s_i < N) { sum += s_a; stream_step(s_i); } stream_end(s_i, s_a, s_b); int i = 0; while (i < N) { sum += a[b[i]]; i++; } s_i s_b s_a Iter. Step User a[b[i]] b[i] Pseudo-Reg Pseudo-Reg 0 1 2 Memory 0x888 Memory 0x668 Memory 0x400 Memory 0x404 i++ s_a s_b i++ Memory 0x86c Memory 0x408 18

19. Stream ISA Extension ISA Semantic New architectural states: Stream configuration. Current iteration s data. New speculation in ISA: Stream elements will be used. Streams are long. Maintain the memory order. Load first use of the pseudo-register after configured/stepped. Store every write to the pseudo-register. 19

20. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 20

21. Stream-Aware Policies Rich Information Better Policies Memory Footprint Reuse Distance Prefetch Throttling Modified? Cache Replacement Compiler (ISA) /Hardware Conditional Used? Cache Bypassing Indirect Sub-Line Transfer 21

22. Stream-Aware Policies Cache Bypass Stream: Access Pattern Precise Memory Footprint. Core while (i < N) while (j < N) while (k < N) sum += a[k][i] * b[k][j]; L1$ s_b s_a L2$ s_b s_a Reuse Dist. ? Reuse Dist. ? ? a[N][N] b[N][N] 22

23. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Stream-Aware Policies. Microarchitecture Extension. Evaluation. 23

24. Microarchitecture Memory 0x400 Memory 0x404 Pseudo-Reg Memory 0x408 Memory 0x40c Memory 0x410 Stream 24

25. Microarchitecture Misspeculation Control misspeculated stream_step. Decrement the iteration map. No need to flush the FIFO and re-fetch data (decoupled) ! Other misspeculation. Revert the stream states, including stream FIFO. Memory fault delayed until the use of the element. 25

26. Outline Insight & Opportunities. Stream Characteristics. Stream ISA Extension. Microarchitecture Extension. Stream-Aware Policies. Evaluation. 26

27. Methodology Compiler in LLVM: Identify stream candidates. Generate stream configuration. Transform the program. Gem5 + McPAT simulation. 33 Benchmarks: SPEC2017 C/CPP benchmarks. CortexSuite. SimPoint: 10 million instructions simpoints. ~10 simpoints per benchmark. 27

28. Configurations Stream Specialized Processor. SSP-Non-Bind: Prefetch only. SSP-Semi-Bind: + Semi-binding prefetch. SSP-Cache-Aware: + Stream-Aware cache bypassing. Baseline. Baseline O3. Pf-Stride: Table-based prefetcher. Pf-Helper: SMT-based ideal helper thread. Requires no HW resources (ROB, etc.). Exactly 1k instruction before the main thread. 28

29. Results Overall Performance 7 6 5 4 3 2 1 0 Pf-Stride SSP-Non-Bind SSP-Semi-Bind SSP-Cache-Aware Pf-Helper 29

30. Results Semi-Binding Prefetching Speedup of Semi-Binding Prefetch vs. Non-Binding Prefetch 1.5 1 1 0.8 0.6 0.4 0.2 0 Remain Insts Added Insts 30

31. Results Design Space Interaction OOO[2,6,8] Pf-Stride[2,6,8] Pf-Helper[2,6,8] SSP-Cache-Aware[2,6,8] 1.1 1.1 1 1 0.9 0.9 Energy Energy 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 1 1.5 CortexSuite Speedup 2 2.5 3 1 1.5 2 2.5 3 SPEC CPU 2017 Speedup 31

32. Conclusion Stream as a new memory abstraction in ISA. ISA/Microarchitecture extension. Stream-aware cache bypassing. New paradigm of memory specialization. New direction for improving cache architectures. Combine memory and computation specialization. 32