Parallel System Performance: Evaluation & ScalabilityParallel Program PerformanceFactors affecting Parallel System PerformanceParallel Performance Metrics RevisitedExample: Concurrency Profile of A Divide-and-Conquer AlgorithmParallel Performance Metrics RevisitedPhase Parallel Model of An ApplicationHarmonic Mean Speedup for n Execution Mode Multiprocessor systemParallel Performance Metrics Revisited: Amdahl’s LawEfficiency, Utilization, Redundancy, Quality of ParallelismCost, Utilization, Redundancy, Quality of ParallelismA Parallel Performance measures ExampleApplication Scaling Models for Parallel ComputingProblem Constrained (PC) Scaling : Fixed-Workload SpeedupAmdahl’s Law for Fixed-Load SpeedupTime Constrained (TC) Workload Scaling Fixed-Time SpeedupGustafson’s Fixed-Time SpeedupMemory Constrained (MC) Scaling Fixed-Memory SpeedupImpact of Scaling Models: 2D Grid SolverImpact on Grid Solver Execution CharacteristicsScalabilityParallel Scalability FactorsRevised Asymptotic Speedup, EfficiencyParallel System ScalabilityExample: Scalability of Network Architectures for Parity CalculationEvaluating a Real Parallel MachinePerformance Isolation: MicrobenchmarksTypes of Workloads/BenchmarksThree Desirable Properties for Parallel WorkloadsDesirable Properties of Workloads: Representative of Application DomainsDesirable Properties of Workloads: Coverage: Stressing FeaturesCoverage: Levels of OptimizationDesirable Properties of Workloads: ConcurrencyEffect of Problem Size Example: OceanEECC756 - ShaabanEECC756 - Shaaban#1 lec # 9 Spring2008 4-29-2008Parallel System Performance: Parallel System Performance: Evaluation & ScalabilityEvaluation & Scalability•Factors affecting parallel system performance:–Algorithm-related, parallel program related, architecture/hardware-related. •Workload-Driven Quantitative Architectural Evaluation:–Select applications or suite of benchmarks to evaluate architecture either on real or simulated machine.–From measured performance results compute performance metrics:•Speedup, System Efficiency, Redundancy, Utilization, Quality of Parallelism.–Resource-oriented Workload scaling models: How the speedup of an application is affected subject to specific constraints:•Problem constrained (PC): Fixed-load Model.•Time constrained (TC): Fixed-time Model.•Memory constrained (MC): Fixed-Memory Model.•Performance Scalability:–Definition.–Conditions of scalability.–Factors affecting scalability.Parallel Computer Architecture, Chapter 4Parallel Programming, Chapter 1, handoutInformally:The ability of parallel system performance to increase with increased problem and system size. For a given parallel system and parallel problem/algorithm: 123EECC756 - ShaabanEECC756 - Shaaban#2 lec # 9 Spring2008 4-29-2008Parallel Program Performance•Parallel processing goal is to maximize speedup:•By:–Balancing computations/overheads (workload) on processors (every processor has the same amount of work/overheads). – Minimizing communication cost and other overheads associated with each step of parallel program creation and execution.Sequential WorkMax (Work + Synch Wait Time + Comm Cost + Extra Work)Speedup = <Time(1)Time(p)Max for any processorParallel Performance Scalability:Achieve a good speedup for the parallel application on the parallel architecture as problem size and machine size (number of processors) are increased. OrContinue to achieve good parallel performance "speedup"as the sizes of the system/problem are increased.(More formal treatment of scalability later)For a given parallel system and parallel computation/problem/algorithm 12Parallelizing OverheadsEECC756 - ShaabanEECC756 - Shaaban#3 lec # 9 Spring2008 4-29-2008Factors affecting Parallel System PerformanceFactors affecting Parallel System Performance•Parallel Algorithm-related: –Available concurrency and profile, dependency graph, uniformity, patterns.–Complexity and predictability of computational requirements–Required communication/synchronization, uniformity and patterns.–Data size requirements.•Parallel program related:–Partitioning: Decomposition and assignment to tasks•Parallel task grain size.•Communication to computation ratio.–Programming model used.–Orchestration•Cost of communication/synchronization.–Resulting data/code memory requirements, locality and working set characteristics.–Mapping & Scheduling: Dynamic or static.•Hardware/Architecture related:–Total CPU computational power available.–Parallel programming model support:•e.g support for Shared address space Vs. message passing support.•Architectural interactions, artifactual “extra” communication–Communication network characteristics: Scalability, topology ..–Memory hierarchy properties.i.e Inherent ParallelismRefined from factors in Lecture # 1C-to-C ratio (measure of inherent communication)EECC756 - ShaabanEECC756 - Shaaban#4 lec # 9 Spring2008 4-29-2008Parallel Performance Metrics RevisitedParallel Performance Metrics Revisited •Degree of Parallelism (DOP): For a given time period, reflects the number of processors in a specific parallel computer actually executing a particular parallel program.•Average Parallelism, A: –Given maximum parallelism = m –n homogeneous processors –Computing capacity of a single processor –Total amount of work (instructions or computations): or as a discrete summationW iiimt .1W DOP t dttt ( )12A DOP t dtt ttt12 112( )A iiimiimt t  .1 1iimt t t 12 1Where ti is the total time that DOP = i andThe average parallelism A:In discrete formComputations/secDOP AreaExecutionTimeExecutionTimeFrom Lecture # 3i.e concurrency profileEECC756 - ShaabanEECC756 - Shaaban#5 lec # 9 Spring2008 4-29-2008Example: Concurrency Profile of Example: Concurrency Profile of A Divide-and-Conquer AlgorithmA Divide-and-Conquer Algorithm•Execution observed from t1 = 2 to t2 = 27 •Peak parallelism m = 8 •A = (1x5 + 2x3 + 3x4 + 4x6 + 5x2 + 6x2 + 8x3) / (5 + 3+4+6+2+2+3) = 93/25 = 3.72Degree of Parallelism (DOP)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 271110 9 8 7 6 5 4 3 2 1Timet1t2A iiimiimt t  .1 1Area equal to total # of