This book focuses on the acceleration of emerging irregular sparse workloads, posed by novel artificial intelligent (AI) models and sparse linear algebra. Specifically, the book outlines several co-optimized hardware-software solutions for a highly promising class of emerging sparse AI models called Probabilistic Circuit (PC) and a similar sparse matrix workload for triangular linear systems (SpTRSV). The authors describe optimizations for the entire stack, targeting applications, compilation, hardware architecture and silicon implementation, resulting in orders of magnitude higher performance and energy-efficiency compared to the existing state-of-the-art solutions. Thus, this book provides important building blocks for the upcoming generation of edge AI platforms.

lgli/Efficient_Execution_of_Irregular_Dataflow_Graphs_2023.pdf

lgrsnf/Efficient_Execution_of_Irregular_Dataflow_Graphs_2023.pdf

zlib/no-category/Nimish Shah, Wannes Meert, Marian Verhelst/Efficient Execution of Irregular Dataflow Graphs. Hardware/Software Co-optimization for Probabilistic AI and Sparse Linear Algebra_25655465.pdf

Springer Nature Switzerland AG

Switzerland, Switzerland

155

{"isbns":["3031331354","3031331362","9783031331350","9783031331367"],"last_page":2023,"publisher":"Springer"}

415ycu+1gnL._SX320_BO1,204,203,200_
1
Preface
Contents
List of Abbreviations
List of Symbols
List of Figures
List of Tables
978-3-031-33136-7_1
1 Irregular Workloads at Risk of Losing the Hardware Lottery
1.1 Domain Specialization and the Hardware Lottery
1.2 Recent Trends and Irregular Workloads
1.3 Introduction to Graphs
1.4 Target Workloads
1.4.1 Probabilistic Circuit (PC)
1.4.2 Sparse Matrix Triangular Solves (SpTRSV)
1.4.3 Comparison of PC and SpTRSV
1.5 Open Research Questions for Efficient Execution of Irregular DFGs
1.5.1 Q1: What Type of Data Representation Is Suitable?
1.5.2 Q2: How Can We Parallelize Irregular DFGs Effectively?
1.5.3 Q3: How Can We Improve the Throughput and Energy Efficiency Through a Custom Processor Architecture?
1.5.4 Q4: How Can We Improve the Hardware Further Through a Dedicated Datapath Design?
1.6 Book Contributions
1.6.1 ProbLP and the Custom Posit Representation
1.6.2 GraphOpt: A Tool for Effective Parallelization of DFGs
1.6.3 DAG Processing Unit: Version 1 (DPU)
1.6.4 DAG Processing Unit-Version 2 (DPU-v2)
978-3-031-33136-7_2
2 Suitable Data Representation: A Study of Fixed-Point, Floating-Point, and PositTM Formats for Probabilistic AI
2.1 Error-Bound Analysis
2.1.1 Fixed-Point Error Models
2.1.2 Floating-Point Error Models
2.1.3 Ensuring That All the Intermediate Values of a PC Are Within the Range
2.1.4 Error Propagation from PC Inputs to the Output
2.2 ProbLP
2.2.1 Bounds for Probabilistic Queries
Marginal Probability and MPE
Conditional Probability
2.2.2 Selecting Optimal Representation
2.2.3 Automatic Hardware Generation
2.2.4 Experimental Results
Validation of Bounds
Overall Performance
2.3 Beyond Fixed and Floating Point: Posit Representation
2.4 Conclusions
978-3-031-33136-7_3
3 GraphOpt: Constrained-Optimization-Based Parallelization of Irregular Workloads for Multicore Processors
3.1 Graph Partitioning for Parallelization
3.2 GraphOpt
3.2.1 Recursive Two-Way Partitioning (M1)
Optimization Model for the Two-Way Partitioning
Example
3.2.2 Workload Balancing (M2)
3.2.3 Scale to Large Graphs (S1, S2, S3)
Consider Limited Layers (S1)
Independent Connected Components (S2)
Heuristic Coarsening (S3)
3.3 Performance Evaluation
3.3.1 Experimental Setup
3.3.2 Analysis of Super Layers
How Large Are the Super Layers?
Workload Balancing
Throughput Scaling
Impact of the Scalability Techniques
3.3.3 Comparison with State-of-the-Art Libraries
Sparse Matrix Triangular Solves
Probabilistic Circuits
3.4 Discussion and Related Work
3.4.1 Sparse Triangular Solves
3.4.2 Probabilistic Circuits
3.4.3 Graph Partitioning
3.4.4 DAG Scheduling
3.5 Conclusion
978-3-031-33136-7_4
4 DAG Processing Unit Version 1 (DPU): Efficient Execution of Irregular Workloads on a Multicore Processor
4.1 Challenges Due to Irregularity
4.1.1 SIMD Unfriendly
4.1.2 Frequent Synchronizations
4.1.3 Inefficient Use of Caches
4.1.4 Data Prefetching
4.2 DPU Architecture
4.2.1 Compute Units (CUs)
4.2.2 Global Scratchpad and Asymmetric Crossbar
4.2.3 Global Sync Unit
4.3 Compute Unit (CU) Architecture
4.3.1 Local Scratchpad
4.3.2 Data Prefetching Using Decoupled Instruction Streams
4.4 Precision-Scalable Custom Posit Unit
4.5 Implementation and Experiments
4.5.1 Physical Implementation
4.5.2 Peak Performance and Voltage Scaling
4.5.3 Workloads
4.5.4 Throughput Scaling with Different Active CUs
4.5.5 Comparison with CPU and GPU
4.5.6 DPU's Performance for a Regular DAG
4.6 Related Work
4.7 Conclusion
978-3-031-33136-7_5
5 DAG Processing Unit Version 2 (DPU-v2): Efficient Execution of Irregular Workloads on a Spatial Datapath
5.1 Designing a Processor with a Spatial Datapath for Large Irregular DAGs
5.1.1 Which Spatial Datapath Topology Should Be Used?
5.1.2 How to Read/Write the Inputs/Outputs?
5.1.3 How to Handle Bank Access Conflicts?
5.2 DPU-v2 Architecture Template
5.2.1 Parallel Tree of PEs
5.2.2 Register File Architecture
5.2.3 Datapath-Register Banks Connections
5.2.4 Load, Store, and Copy of Data
5.2.5 Long, Variable-Length Instructions
5.3 Compiler for DAG
5.3.1 Block Decomposition (Step 1)
5.3.2 PE and Register Bank Mapping (Step 2)
5.3.3 Pipeline-Aware Reordering (Step 3)
5.3.4 Spilling from Register File (Step 4)
5.3.5 Reduction in Memory Footprint
5.4 Design Space Exploration
5.4.1 The Most-Efficient Design Configuration
5.5 State-of-the-Art Comparison
5.5.1 Comparison Using PC and SpTRSV
5.5.2 Comparison Using large PCs
5.5.3 Detailed Comparison of DPU-v2 and DPU
5.6 Additional Related Works
5.7 Conclusion
978-3-031-33136-7_6
6 Conclusions and Future Work
6.1 Contributions and Conclusions
6.2 Suggestions for Future Works
6.3 Closing Remarks
1 (1)
A The Two-Way Partitioning Model of GraphOpt
Bibliography
Index

2023-08-07