Efficient Execution of Irregular Dataflow Graphs: Hardware/Software Co-optimization for Probabilistic AI and Sparse Linear Algebra

Description

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. Preface Contents List of Abbreviations List of Symbols List of Figures List of Tables 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) 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 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 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 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 6 Conclusions and Future Work 6.1 Contributions and Conclusions 6.2 Suggestions for Future Works 6.3 Closing Remarks A The Two-Way Partitioning Model of GraphOpt Bibliography Index