EECC756 EECC756 --ShaabanShaaban#1 lec # 3 Spring2008 3-20-2008Parallel Program IssuesParallel Program Issues••Dependency Analysis:Dependency Analysis:––Types of dependencyTypes of dependency––Dependency GraphsDependency Graphs––Bernstein’s Conditions of ParallelismBernstein’s Conditions of Parallelism••Asymptotic Notations for Algorithm Complexity AnalysisAsymptotic Notations for Algorithm Complexity Analysis• Parallel Random-Access Machine (PRAM)––Example: sum algorithm on P processor PRAMExample: sum algorithm on P processor PRAM••Network Model of MessageNetwork Model of Message--Passing Passing MulticomputersMulticomputers– Example: Asynchronous Matrix Vector Product on a Ring••Levels of Parallelism in Program ExecutionLevels of Parallelism in Program Execution••Hardware Vs. Software ParallelismHardware Vs. Software Parallelism••Parallel Task Grain Size Parallel Task Grain Size ••Software Parallelism Types: Data Vs. Functional ParallelismSoftware Parallelism Types: Data Vs. Functional Parallelism••Example Motivating Problem With high levels of concurrencyExample Motivating Problem With high levels of concurrency••Limited Parallel Program Concurrency: Amdahl’s LawLimited Parallel Program Concurrency: Amdahl’s Law••Parallel Performance Metrics: Degree of Parallelism (DOP)Parallel Performance Metrics: Degree of Parallelism (DOP)––Concurrency ProfileConcurrency Profile••Steps in Creating a Parallel Program: Steps in Creating a Parallel Program: ––Decomposition, Assignment, Orchestration, Mapping Decomposition, Assignment, Orchestration, Mapping ––Program Partitioning Example (handout)Program Partitioning Example (handout)––Static Multiprocessor Scheduling Example (handout)Static Multiprocessor Scheduling Example (handout)PCA Chapter 2.1, 2.2EECC756 EECC756 --ShaabanShaaban#2 lec # 3 Spring2008 3-20-2008Parallel Programs: Definitions• A parallel program is comprised of a number of tasks running as threads (or processes) on a number of processing elements that cooperate/communicate as part of a single parallel computation.• Task: – Arbitrary piece of undecomposed work in parallel computation– Executed sequentially on a single processor; concurrency in parallel computation is only across tasks.• Parallel or Independent Tasks:– Tasks that with no dependencies among them and thus can run in parallel on different processing elements.• Parallel Task Grain Size: The amount of computations in a task.• Process (thread):– Abstract entity that performs the computations assigned to a task– Processes communicate and synchronize to perform their tasks• Processor or (Processing Element): – Physical computing engine on which a process executes sequentially– Processes virtualize machine to programmer• First write program in terms of processes, then mapto processors• Communication to Computation Ratio (C-to-C Ratio): Represents the amount of resulting communication between tasks of a parallel programIn general, for a parallel computation, a lower C-to-C ratio is desirable and usually indicates better parallel performanceOther Parallelization Overheads CommunicationComputationParallel Execution TimeThe processor with max. execution time determines parallel execution timeEECC756 EECC756 --ShaabanShaaban#3 lec # 3 Spring2008 3-20-2008• Dependency analysis is concerned with detecting the presence and type of dependency between tasks that prevent tasks from being independent and from running in parallel on different processorsand can be applied to tasks of any grain size.– Represented graphically as task dependency graphs.• Dependencies between tasks can be 1- algorithm/program related or 2- hardware resource/architecturerelated.• Algorithm/program Task Dependencies:– Data Dependence:• True Data or Flow Dependence• Name Dependence: – Anti-dependence– Output (or write) dependence– Control Dependence• Hardware/Architecture Resource DependenceDependency Analysis & Conditions of ParallelismConditions of Parallelism12Down to task = instructionA task only executes on one processor to which it has been mapped or allocatedEECC756 EECC756 --ShaabanShaaban#4 lec # 3 Spring2008 3-20-2008Conditions of Parallelism: Conditions of Parallelism: Data & Name DependenceData & Name DependenceAssume task S2 follows task S1 in sequential program order1 True Data or Flow Dependence: Task S2 is data dependent on task S1 if an execution path exists from S1 to S2 and if at least one output variable of S1 feeds in as an input operand used by S2 Represented by S1 ⎯→ S2 in task dependency graphs2 Anti-dependence: Task S2 is antidependent on S1, if S2 follows S1 in program order and if the output of S2 overlaps the input of S1 Represented by S1 ⎯→ S2 in dependency graphs3 Output dependence: Two tasks S1, S2 are output dependent if they produce the same output variableRepresented by S1 ⎯→ S2 in task dependency graphsS1....S2ProgramOrderNameDependenciesEECC756 EECC756 --ShaabanShaaban#5 lec # 3 Spring2008 3-20-2008• Assume task S2 follows task S1 in sequential program order• Task S1 produces one or more results used by task S2, – Then task S2 is said to be data dependent on task S1• Changing the relative execution order of tasks S1, S2 in the parallel program violates this data dependence and results in incorrect execution.(True) Data (or Flow) Data (or Flow) DependenceTask S2 is data dependent on task S1Task Dependency Graph RepresentationS1S2Data DependenceS1....S2ProgramOrderS1 (Write)SharedOperandsS2 (Read)i.e. Produceri.e. ConsumerS1 ⎯→ S2EECC756 EECC756 --ShaabanShaaban#6 lec # 3 Spring2008 3-20-2008Name Dependence Classification: Classification: Anti-DependenceTask S2 is anti-dependent on task S1• Assume task S2 follows task S1 in sequential program order • Task S1 reads one or more values from one or more names (registers or memory locations)• Instruction S2 writes one or more values to the same names (same registersor memory locations read by S1)– Then task S2 is said to be anti-dependent on task S1• Changing the relative execution order of tasks S1, S2 in the parallel program violates this name dependence and may result in incorrect execution.Task Dependency Graph RepresentationS1S2Anti-dependenceS1....S2ProgramOrderName: Register or Memory LocationS1 (Read)SharedNamesS2 (Write)S1 ⎯→