Code Optimization of Parallel ProgramsParallel Software Challenges & Focus Area for this TalkOutlineOur Current Paradigm for Code Optimization has served us well for Fifty Years ….… and has been adapted to meet challenges along the way …… but is now under siege because of parallelismParadigm ShiftsKuhn’s History of ScienceSome Well Known Paradigm ShiftsSlide 10What anomalies do we see when optimizing parallel code?1. Control Flow Rules from Sequential Code OptimizationDominator ExampleAnomalies in Control Flow Rules for Parallel Code2. Data Flow Rules from Sequential Code OptimizationAnomalies in Data Flow Rules for Parallel Code3. Load Elimination Rules from Sequential Code OptimizationAnomalies in Load Elimination Rules for Parallel Code (Original Version)Anomalies in Load Elimination Rules for Parallel Code (After Load Elimination)Slide 20Incremental Approaches to coping with Parallel Code OptimizationMore Comprehensive Changes will be needed for Code Optimization of Parallel Programs in the FutureProgram Dependence Graphs [Ferrante, Ottenstein, Warren 1987]PDG ExamplePDG restrictionsViolation of the Predecessor-Ancestor Condition can lead to “non-serializable” PDGs [LCPC 1993]PDG restrictions (contd)Limitations of Program Dependence GraphsAnother Limitation: no Parallel Execution Semantics defined for PDGsParallel Program Graphs: A Comprehensive Representation that Subsumes CFGs and PDGs [LCPC 1992]PPG ExampleRelating CFGs to PPGsRelating PDGs to PPGsExample of Transforming PPGsAbstract Interpreter for PPGsAbstract Interpreter for PPGs (contd)Abstract Interpreter for PPGs: ExampleWeak (Deterministic) Memory Model for PPGsSoundness PropertiesReaching Definitions Analysis on PPGs [LCPC 1997]Reaching Definitions Analysis on PPGsPPG LimitationsIssues in Modeling Synchronized/Atomic Blocks [LCPC 1999]Slide 44Habanero Project (habanero.rice.edu)2) Habanero Static Parallelizing & Optimizing CompilerHabanero Target Applications and PlatformsHabanero Research TopicsHabanero Research Topics (contd.)Opportunities for Broader ImpactHabanero Team (Nov 2007)Other Challenges in Code Optimization of Parallel CodeRelated Work (Incomplete List)PLDI 2008 Tutorial (Tucson, AZ)ConclusionsCode Optimization of Parallel ProgramsCode Optimization of Parallel ProgramsVivek SarkarRice [email protected] SarkarRice [email protected] Directory/ControlL2L2L2LSU LSUIFUBXUIDU IDUIFUBXUFPU FPUFXUFXUISU ISU2Parallel Software Challenges & Focus Area for this TalkParallel Software Challenges & Focus Area for this TalkMiddlewareParallel Runtime & System LibrariesOS and HypervisorsLanguagesProgramming ToolsParallelism in middleware e.g., transactions, relational databases, web services, J2EE containersExplicitly parallel languages e.g., OpenMP, Java Concurrency, .NET Parallel Extensions, Intel TBB, CUDA, Cilk, MPI, Unified Parallel C, Co-Array Fortran, X10, Chapel, FortressParallel Debugging and Performance Tools e.g., Eclipse Parallel Tools Platform, TotalView, Thread CheckerCode partitioning for accelerators, data transfer optimizations, SIMDization, space-time scheduling, power managementParallel runtime and system libraries for task scheduling, synchronization, parallel data structuresVirtualization, scalable management of heterogeneous resources per core (frequency, power)Static & Dynamic Optimizing CompilersDomain-specific Programming ModelsDomain-specific implicitly parallel programming models e.g., Matlab, stream processing, map-reduce (Sawzall), Application LibrariesParallel application libraries e.g., linear algebra, graphics imaging, signal processing, securityParallel intermediate representation, optimization of synchronization & data transfer, automatic parallelizationMulticore Back-ends3OutlineOutlineParadigm ShiftsAnomalies in Optimizing Parallel CodeIncremental vs. Comprehensive Approaches to Code Optimization of Parallel CodeRice Habanero Multicore Software project4Our Current Paradigm for Code Optimization has served us well for Fifty Years ….Our Current Paradigm for Code Optimization has served us well for Fifty Years ….TranslationTranslationTranslationFortranAutocoder IIALPHAILOPTIMIZERREGISTER ALLOCATORILILASSEMBLERSTRETCHSTRETCH-HARVESTOBJECT CODEStretch – Harvest Compiler Organization(1958 - 1962) Source: “Compiling for Parallelism”,Fran Allen, Turning Lecture, June 20075… and has been adapted to meet challenges along the way … … and has been adapted to meet challenges along the way … Interprocedural analysisArray dependence analysisPointer alias analysisInstruction scheduling & software pipeliningSSA formProfile-directed optimizationDynamic compilationAdaptive optimizationAuto-tuning. . .6… but is now under siege because of parallelism … but is now under siege because of parallelism Proliferation of parallel hardwareMulticore, manycore, accelerators, clusters, …Proliferation of parallel libraries and languagesOpenMP, Java Concurrency, .NET Parallel Extensions, Intel TBB, Cilk, MPI, UPC, CAF, X10, Chapel, Fortress, …7Paradigm ShiftsParadigm Shifts"The Structure of Scientific Revolutions”, Thomas S. Kuhn (1970)A paradigm is a scientific structure or framework consisting of Assumptions, Laws, Techniques Normal science is a puzzle solving activity governed by the rules of the paradigm. It is uncritical of the current paradigm, Crisis sets in when a series of serious anomalies appear“The emergence of new theories is generally preceded by a period of pronounced professional insecurity”Scientists engage in philosophical and metaphysical disputes. A revolution or paradigm shift occurs when an an entire paradigm is replaced by another8Kuhn’s History of ScienceKuhn’s History of ScienceNormal ScienceImmature ScienceAnomaliesCrisisRevolutionRevolution: A new paradigm emergesOld Theory: well established, many followers, many anomaliesNew Theory: few followers, untested, new concepts/techniques, accounts for anomalies, asks new questionsSource: www.philosophy.ed.ac.uk/ug_study/ ug_phil_sci1h/phil_sci_files/L10_Kuhn1.ppt9Some Well Known Paradigm ShiftsSome Well Known Paradigm ShiftsNewton’s Laws to Einstein's Theory of RelativityPtolemy’s geocentric view to Copernicus and Galileo’s heliocentric viewCreationism to Darwin’s Theory of Evolution10OutlineOutlineParadigm ShiftsAnomalies in Optimizing Parallel CodeIncremental