Topic 8 Optimization for Parallel Computation 5 8 2008 CPEG421 08S Topic 8 1 Reading List Slides Topic 8x Other readings as assigned in class or homework 5 8 2008 CPEG421 08S Topic 8 2 Outline Basic Concepts Parallelism Locality Loop Nest Optimization Summary 5 8 2008 CPEG421 08S Topic 8 3 Parallelism What is Parallelism Parallelism in Computer Architecture Instruction Level Parallelism ILP Thread Level Thread Level Parallelism TLP Parallelism in Programs Applications Statement Level Parallelism Loop Level Parallelism Task Level Parallelism 5 8 2008 CPEG421 08S Topic 8 4 General Compiler Framework Source Loop Nest Optimization LNO ME Global Optimization OPT Innermost Loop scheduling BE CG Global inst scheduling Reg alloc 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 Inter Procedural Optimization IPA Arch Models Local inst scheduling Executable 5 8 2008 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 5 8 2008 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 5 8 2008 CPEG421 08S Topic 8 7 Loop Nest Tansformation and Optimization Simple Loop Transformation Unimodular Loop Transformations Beyond Unimodular Transformations Combining Loop Transformation Summary 5 8 2008 CPEG421 08S Topic 8 8 Simple Loop Transformation Loop unrolling Loop peeling 5 8 2008 CPEG421 08S Topic 8 9 Unimodular Loop Transformation Loop interchange Loop reversal Loop skewing 5 8 2008 CPEG421 08S Topic 8 10 Loop 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 5 8 2008 CPEG421 08S Topic 8 11 Safety of Loop 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 5 8 2008 CPEG421 08S Topic 8 12 Legality of Loop Interchange DO J 1 M DO I 1 N A I J 1 A I 1 J B ENDDO ENDDO Note Interchange here is Illegal 5 8 2008 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 J 1 S 1 1 S 2 1 S 3 1 S 4 1 I 2 I 3 I 4 I 1 CPEG421 08S Topic 8 13 Loop Reversal An Example S 5 8 2008 I DO I 1 N DO J M 1 1 A I 1 J A I J 1 B ENDDO ENDDO I CPEG421 08S Topic 8 2 1 2 M J 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 5 8 2008 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 An Example J 4 S 1 4 J 3 S 1 3 J 2 S 1 2 J 1 S 1 1 I 1 S 2 4 S 2 3 S 2 2 S 3 4 S 3 3 S 3 2 S 4 4 S 4 3 S 4 2 S 2 1 S 3 1 S 4 1 I 2 I 3 I 4 j 4 j 3 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 5 8 2008 I 1 Skew j J I j 2 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 An Example Cont d 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 I 3 I 2 I 1 S 1 1 j 2 j 3 j 4 j 5 j 6 j 7 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 5 8 2008 CPEG421 08S Topic 8 17 Disadvantage of Loop Skewing Recompute loop bounds Loop bounds changes average vector length changes 5 8 2008 CPEG421 08S Topic 8 18 Unimodular Transformations Motivation Easy to represent compound transformations Elegant formulation of objective functions under compound loop transformations 5 8 2008 CPEG421 08S Topic 8 19 Beyond Unimodular Loop Trasformation Loop Loop Loop Loop 5 8 2008 Strip Mining Tiling Fusion Fission CPEG421 08S Topic 8 20 Advanced Topics Toward A Framework of Combining Loop Transformations 5 8 2008 CPEG421 08S Topic 8 21 An 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 5 8 2008 CPEG421 08S Topic 8 Unimodular e g permutation Loop unrolling Both Others 22 Motivating 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 j i c j a j a j b j i 1 c j a j a j b j i 2 c j a j a j b j i 3 c j END DO END DO end Question Is the …