Symbolic parallelization of nested loop programs / Alexandru-Petru Tanase, Frank Hannig, Jürgen Teich.

Intro; Contents; Acronyms; List of Symbols; 1 Introduction; 1.1 Goals and Contributions; 1.2 Symbolic Outer and Inner Loop Parallelization; 1.3 Symbolic Multi-level Parallelization; 1.4 On-demand Fault-tolerant Loop Processing; 1.5 Book Organization; 2 Fundamentals and Compiler Framework; 2.1 Invasive Computing; 2.2 Invasive Tightly Coupled Processor Arrays; 2.2.1 Processor Array; 2.2.2 Array Interconnect; 2.2.3 TCPA Peripherals; 2.3 Compiler Framework; 2.3.1 Compilation Flow; 2.3.2 Front End; 2.3.3 Loop Specification in the Polyhedron Model; 2.3.3.1 Iteration Space; 2.3.4 PAULA Language

2.3.5 PARO2.3.5.1 High-level Transformations; 2.3.5.2 Localization; 2.3.5.3 Static Loop Tiling; 2.3.5.4 Static Scheduling; 2.3.6 Space-Time Mapping; 2.3.7 Code Generation; 2.3.8 PE Code Generation; 2.3.9 Interconnect Network Configuration; 2.3.10 GC and AG Configuration Stream; 3 Symbolic Parallelization; 3.1 Symbolic Tiling; 3.1.1 Decomposition of the Iteration Space; 3.1.2 Embedding of Data Dependencies; 3.2 Symbolic Outer Loop Parallelization; 3.2.1 Tight Intra-Tile Schedule Vector Candidates; 3.2.2 Tight Inter-tile Schedule Vectors; 3.2.3 Parametric Latency Formula

3.2.4 Runtime Schedule Selection3.3 Symbolic Inner Loop Parallelization; 3.3.1 Tight Intra-Tile Schedule Vectors; 3.3.2 Tight Inter-tile Schedule Vector Candidates; 3.3.3 Parametric Latency Formula; 3.3.4 Runtime Schedule Selection; 3.4 Runtime Schedule Selection on Invasive TCPAs; 3.5 Experimental Results; 3.5.1 Latency; 3.5.2 I/O and Memory Demand; 3.5.3 Scalability; 3.6 Related Work; 3.7 Summary; 4 Symbolic Multi-Level Parallelization; 4.1 Symbolic Hierarchical Tiling; 4.1.1 Decomposition of the Iteration Space; 4.1.2 Embedding of Data Dependencies; 4.2 Symbolic Hierarchical Scheduling

4.2.1 Latency-Minimal Sequential Schedule Vectors4.2.2 Tight Parallel Schedule Vectors; 4.2.3 Parametric Latency Formula; 4.2.4 Runtime Schedule Selection; 4.3 Experimental Results; 4.3.1 Latency; 4.3.2 I/O and Memory Balancing; 4.3.3 Scalability; 4.4 Related Work; 4.5 Summary; 5 On-Demand Fault-Tolerant Loop Processing; 5.1 Fundamentals and Fault Model; 5.2 Fault-Tolerant Loop Execution; 5.2.1 Loop Replication; 5.2.2 Voting Insertion; 5.2.3 Immediate, Early, and Late Voting; 5.2.3.1 Immediate Voting; 5.2.3.2 Early Voting; 5.2.3.3 Late Voting; 5.3 Voting Functions Implementation

5.4 Adaptive Fault Tolerance Through Invasive Computing5.4.1 Reliability Analysis for Fault-Tolerant Loop Execution; 5.5 Experimental Results; 5.5.1 Latency Overhead; 5.5.2 Average Error Detection Latency; 5.6 Related Work; 5.7 Summary; 6 Conclusions and Outlook; 6.1 Conclusions; 6.2 Outlook; Bibliography; Index