Prof. Saman Amarasinghe, MIT. 1 6.189 IAP 2007 MIT6.189 IAP 2007Lecture 12StreamIt Parallelizing Compiler2 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Common Machine Language● Represent common properties of architectures Necessary for performance● Abstract away differences in architectures Necessary for portability● Cannot be too complex Must keep in mind the typical programmer● C and Fortran were the common machine languages for uniprocessors Imperative languages are not the correct abstraction for parallel architectures.● What is the correct abstraction for parallel multicore machines?3 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Common Machine Language for Multicores● Current offerings: OpenMP MPI High Performance Fortran ● Explicit parallel constructs grafted onto imperative language● Language features obscured: Composability Malleability  Debugging● Huge additional burden on programmer: Introducing parallelism Correctness of parallelism Optimizing parallelism4 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Explicit Parallelism● Programmer controls details of parallelism!● Granularity decisions: if too small, lots of synchronization and thread creation  if too large, bad locality● Load balancing decisions Create balanced parallel sections (not data-parallel)● Locality decisions Sharing and communication structure● Synchronization decisions barriers, atomicity, critical sections, order, flushing● For mass adoption, we need a better paradigm: Where the parallelism is natural Exposes the necessary information to the compiler5 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Unburden the Programmer● Move these decisions to compiler! Granularity Load Balancing Locality Synchronization● Hard to do in traditional languages Can a novel language help?6 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.● Regular and repeating computation● Synchronous Data Flow● Independent actors with explicit communication● Data items have short lifetimesBenefits:● Naturally parallel● Expose dependencies to compiler● Enable powerful transformationsAdderSpeakerAtoDFMDemodLPF1DuplicateRoundRobinLPF2LPF3HPF1HPF2HPF3Properties of Stream Programs7 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Outline● Why we need New Languages?● Static Schedule ● Three Types of Parallelism● Exploiting Parallelism8 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { }pop=3push=1pop=2…ABC9 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A }pop=3push=1pop=2…ABC10 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A, A }pop=3push=1pop=2…ABC11 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A, A, B }pop=3push=1pop=2…pop=3push=1ABC12 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A, A, B, A }pop=3push=1pop=2…ABC13 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2Steady-State Schedulepop=3push=1pop=2…pop=3push=1ABC● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A, A, B, A, B }14 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.…push=2Steady-State Schedule● All data pop/push rates are constant● Can find a Steady-State Schedule # of items in the buffers are the same before and the after executing the schedule There exist a unique minimum steady state schedule● Schedule = { A, A, B, A, B, C }pop=3push=1pop=2…pop=2…ABC15 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Initialization Schedule● When peek > pop, buffer cannot be empty after firing a filter ● Buffers are not empty at the beginning/end of the steady state schedule● Need to fill the buffers before starting the steady state execution peek=4pop=3push=116 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Initialization Schedule● When peek > pop, buffer cannot be empty after firing a filter ● Buffers are not empty at the beginning/end of the steady state schedule● Need to fill the buffers before starting the steady state execution peek=4pop=3push=1peek=4pop=3push=117 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Outline● Why we need New Languages?● Static Schedule ● Three Types of Parallelism● Exploiting Parallelism18 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Types of ParallelismTask Parallelism Parallelism explicit in algorithm Between filters without producer/consumer relationshipData Parallelism Peel iterations of filter, place within scatter/gather pair (fission) parallelize filters with statePipeline Parallelism Between producers and consumers Stateful filters can be parallelizedScatterGatherTask19 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Types of ParallelismTask Parallelism Parallelism explicit in algorithm Between filters without producer/consumer relationshipData Parallelism Between iterations of a stateless filter  Place within scatter/gather pair (fission) Can’t parallelize filters with statePipeline Parallelism Between producers and consumers