Topic 8 Optimization for Parallel Computation 01 14 19 CPEG421 08S Topic 8 1 Reading List Slides Topic 8x Other readings as assigned in class or homework 01 14 19 CPEG421 08S Topic 8 2 Outline Basic Concepts Parallelism Locality Loop Nest Optimization Summary 01 14 19 CPEG421 08S Topic 8 3 Parallelism What is Parallelism Parallelism in Computer Architecture Instruction Level Parallelism ILP Thread Level Parallelism TLP Parallelism in Programs Applications Statement Level Parallelism Loop Level Parallelism Task Level Parallelism 01 14 19 CPEG421 08S Topic 8 4 General Compiler Source Framework Inter Procedural Optimization IPA Loop Nest Optimization LNO ME Global Optimization OPT Innermost Loop scheduling BE CG Global inst scheduling Reg alloc Arch Models Local inst scheduling Good IPO Good LNO Good global optimization Good integration of IPO LNO OPT Smooth information passing between FE and CG Complete and flexible support of inner loop scheduling SWP instruction scheduling and register allocation Executable 01 14 19 CPEG421 08S Topic 8 5 A Multiprocessor Architecture A generic modern multiprocessor Network Communication assist CA Mem P Node processor s memory system plus communication assist Network interface and communication controller Scalable network 01 14 19 CPEG421 08S Topic 8 6 Locality Temporal Locality the same data is used several times within a short time period Spatial Locality when different data elements that are located near to each other are used within a short period of time 01 14 19 CPEG421 08S Topic 8 7 Loop Nest Tansformation and Optimization Simple Loop Transformation Unimodular Loop Transformations Beyond Unimodular Transformations Combining Loop Transformation Summary 01 14 19 CPEG421 08S Topic 8 8 Simple Simple Loop Loop Transformation Transformation Loop unrolling Loop peeling 01 14 19 CPEG421 08S Topic 8 9 Unimodular Unimodular Loop Loop Transformation Transformation Loop interchange Loop reversal Loop skewing 01 14 19 CPEG421 08S Topic 8 10 Loop Loop Interchange Interchange do j 1 N do i 1 N X i j X i 1 j B i end do end do do i 1 N do j 1 N X i j X i 1 j B i end do end do Why we wish to perform loop interchange 01 14 19 CPEG421 08S Topic 8 11 Safety Safety of of Loop Loop Interchange Interchange DO J 1 M DO I 1 N A I J 1 A I 1 J B ENDDO ENDDO Is it legal to do interchange of I J 01 14 19 CPEG421 08S Topic 8 12 Legality Legality of of Loop Loop Interchange Interchange DO J 1 M DO I 1 N A I J 1 A I 1 J B ENDDO ENDDO J 4 S 1 4 S 2 4 S 3 4 S 4 4 J 3 S 1 3 S 2 3 S 3 3 S 4 3 J 2 S 1 2 S 2 2 S 3 2 S 4 2 S 1 1 S 2 1 S 3 1 S 4 1 I 1 I 2 I 3 I 4 Note Interchange here isJ 1 Illegal 01 14 19 CPEG421 08S Topic 8 13 Loop Loop Reversal Reversal An An Example Example S 01 14 19 DO I 1 N DO J M 1 1 A I 1 J A I J 1 B ENDDO ENDDO CPEG421 08S Topic 8 I 2 1 2 M J I 2 S DO I 1 N DO J 1 M A I 1 J A I J 1 B ENDDO ENDDO J 1 M 1 M 14 Loop Reversal An Example Cont d Interchange DO J M 1 1 DO I A I 1 J A I J 1 B ENDDO ENDDO 01 14 19 CPEG421 08S Topic 8 DO J M 1 1 A 2 N 1 J A 1 N J B 15 S 4 4 j 8 S 3 4 S 4 3 j 7 S 2 4 S 3 3 S 4 2 j 6 S 1 4 S 2 3 S 3 2 S 4 1 j 5 S 1 3 S 2 2 S 3 1 S 1 2 S 2 1 Skewing Skewing An An Example Example J 4 S 1 4 J 3 S 1 3 S 2 4 S 2 3 S 3 4 S 3 3 S 4 4 S 4 3 J 2 S 1 2 S 2 2 S 3 2 S 4 2 J 1 S 1 1 S 2 1 S 3 1 S 4 1 I 2 I 3 I 4 I 1 j 4 j 3 j 2 S 1 1 DO I 1 N DO J 1 N A I J A I 1 J A I J 1 1 0 0 1 01 14 19 I 1 Skew j J I I 2 I 3 I 4 DO I 1 N DO j I 1 I N S A I j I A I 1 j 1 A I j I 1 CPEG421 08S Topic 8 16 Skewing Skewing An An Example Example I 4 Interchange S 4 1 S 4 2 S 4 3 S 3 1 S 3 2 S 3 3 S 3 4 S 2 1 S 2 2 S 2 3 S 2 4 S 1 2 S 1 3 S 1 4 j 3 j 4 j 5 I 3 I 2 I 1 S 1 1 j 2 j 6 j 7 Cont d S 4 4 j 8 DO j 2 N N DO I max 1 j n min N j 1 A I j 1 A I 1 j 1 A I j I 1 END END 01 14 19 CPEG421 08S Topic 8 17 Disadvantage Disadvantage of of Loop Loop Skewing Skewing Recompute loop bounds Loop bounds changes average vector length changes 01 14 19 CPEG421 08S Topic 8 18 Unimodular Unimodular Transformations Transformations Motivation Easy to represent compound transformations Elegant formulation of objective functions under compound loop transformations 01 14 19 CPEG421 08S Topic 8 19 Beyond Unimodular Loop Trasformation Loop Loop Loop Loop 01 14 19 Strip Mining Tiling Fusion Fission CPEG421 08S Topic 8 20 Advanced Advanced Topics Topics Toward Toward A A Framework Framework of of Combining Combining Loop Loop Transformations Transformations 01 14 19 CPEG421 08S Topic 8 21 An An Example Example Subroutine nest a b c Real 8 a 1000 Real 8 b 1000 1000 c 1000 Do j 1 1000 DO i 1 1000 a j a j b j i c j END DO END DO end Assume a multi issue architecture with resource constraints to be considered 1 caches 2 registers 3 instruction scheduling Question What loop transformations to apply and in what order Objective performace code size energy 01 14 19 CPEG421 08S Topic 8 Unimodular e g permutation Loop unrolling Both Others 22 Motivating Motivating Example Example Subroutine nest a b c Real 8 a 1000 Real 8 b 1000 1000 c 1000 Do j 1 1000 DO i 1 1000 a j a j b j i c j END DO END DO end Cont d Do i 1 1000 4 DO j 1 1000 a j a j b …