ACA2_02 New

Views:
 
Category: Education
     
 

Presentation Description

Advanced Computer Architecture - 2

Comments

Presentation Transcript

CSE539: Advanced Computer Architecture Chapter 2 Program and Network Properties Book: “Advanced Computer Architecture – Parallelism, Scalability, Programmability”, Hwang & Jotwani : 

CSE539: Advanced Computer Architecture Chapter 2 Program and Network Properties Book: “Advanced Computer Architecture – Parallelism, Scalability, Programmability”, Hwang & Jotwani Sumit Mittu Assistant Professor, CSE/IT Lovely Professional University sumit.12735@lpu.co.in

In this chapter…: 

In this chapter… CONDITIONS OF PARALLELISM PROBLEM PARTITIONING AND SCHEDULING PROGRAM FLOW MECHANISMS SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 2

Conditions of Parallelism: 

Conditions of Parallelism Key areas for significant progress in parallel processing: Computational Models for parallel computing Inter-processor communication for parallel architectures System Integration for incorporating parallel systems into general computing environment Various forms of parallelism can be attributed to: Levels of Parallelism Computational Granularity Time and Space Complexities Communication Latencies Scheduling Policies Load Balancing Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 3

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Data Dependence Flow Dependence Anti-dependence Output Dependence I/O Dependence Unknown Dependence Control Dependence Control-dependence and control-independence Resource Dependence ALU Dependence, Storage Dependence, etc. Bernstein’s Conditions for Parallelism Dependence Graph Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 4

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 5 Consider the following examples and determine the types of dependencies and draw corresponding dependence graphs Example 2.1(a): S1: R1  M[A] S2: R2  R1 + R2 S3: R1  R3 S4: M[B]  R1 Example 2.1(b): S1: Read array A from file F S2: Process data S3: Write array B into file F S4: Close file F

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 6

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 7 Example 2.2: Determine the parallelism embedded in the following statements and draw the dependency graphs. P1: C = D x E P2: M = G + C P3: A = B + C P4: C = L + M P5: F = G + E Also analyse the statements against Bernstein’s Conditions.

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 8

CONDITIONS OF PARALLELISM Data and Resource Dependencies: 

CONDITIONS OF PARALLELISM Data and Resource Dependencies Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 9

CONDITIONS OF PARALLELISM Hardware and Software Parallelism: 

CONDITIONS OF PARALLELISM Hardware and Software Parallelism Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 10 Hardware Parallelism Cost and Performance Trade-offs Resource Utilization Patterns of simultaneously executable operations k-issue processors and one-issue processor Representative systems: Intel i960CA (3-issue), IBM RISC System 6000 (4-issue) Software Parallelism Algorithm x Programming Style x Program Design Program Flow Graphs Control Parallelism Data Parallelism Mismatch between Software Parallelism and Hardware Parallelism Refer to example 2.3 on Page 50 Role of Compilers in resolving the mismatch

CONDITIONS OF PARALLELISM Hardware and Software Parallelism: 

CONDITIONS OF PARALLELISM Hardware and Software Parallelism Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 11

CONDITIONS OF PARALLELISM Hardware and Software Parallelism: 

CONDITIONS OF PARALLELISM Hardware and Software Parallelism Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 12 2

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 13 Fundamental Objectives To partition program into parallel branches, program modules, micro-tasks or grains to yield shortest possible execution time Determining the optimal size of grains in a computation Grain-size problem To determine both the size and number of grains in parallel program Parallelism and scheduling/synchronization overhead trade-off Grain Packing approach Introduced by Kruatrachue and Lewis (1988) Grain size measured by number of basic machine cycles (both processor and memory) needed to execute all operations within the node

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 14 Example 2.4: Consider the following program VAR a, b, c, d, e, f, g, h, I, j, k, l, m, n, o, p, q BEGIN a = 1 10) j = e x f b = 2 11) k = d x f c = 3 12) l = j x k d = 4 13) m =4 x 1 e = 5 14) n = 3 x m f = 6 15) o = n x i g = a x b 16) p = o x h h = c x d 17) q = p x q i = d x e END

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 15

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Grain Packing and Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 16

PROGRAM PARTITIONING AND SCHEDULING Static Multiprocessor Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Static Multiprocessor Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 17 Node Duplication scheduling To eliminate idle time and further reduce communication delays among processor, nodes can be duplicated in more than one processors Grain Packing and Mode duplication are often used jointly to determine the best grain size and corresponding schedule. Steps involved in grain determination and process of scheduling optimization: Step 1: Construct a fine-grain program graph Step 2: Schedule the fine-grain computation Step 3: Perform grain packing to produce the coarse grains Step 4: Generate a parallel schedule based on the packed graph

PROGRAM PARTITIONING AND SCHEDULING Static Multiprocessor Scheduling: 

PROGRAM PARTITIONING AND SCHEDULING Static Multiprocessor Scheduling Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 18

PROGRAM FLOW MECHANISM: 

PROGRAM FLOW MECHANISM Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 19 Control Flow v/s Data Flow Control Flow Computer Data Flow Computer Example: The MIT tagged-token data flow computer ( Arvind and his associates), 1986 Demand-Driven Mechanisms Reduction Machine Demand-driven computation Eager Evaluation and Lazy Evaluation Reduction Machine Models – String Reduction Model and Graph Reduction Model Comparison of Flow Mechanisms Refer to Table 2.1 (Page 66 of textbook) for comparison of Control Flow (Control-driven), Data Flow (Data-driven) and Reduction (Demand-driven) computers

PROGRAM FLOW MECHANISM: 

PROGRAM FLOW MECHANISM Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 20

PROGRAM FLOW MECHANISM: 

PROGRAM FLOW MECHANISM Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 21

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 22 Direct Networks for static connections Indirect Networks for dynamic connections Network Properties and Routing Static Networks and Dynamic Networks Network Size Node Degree (in-degree and out-degree) Network Diameter Bisection Width Channel width (w ), Channel bisection width (b) , wire bisection width (B = b.w ) Wire length Symmetric networks

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 23 Network Properties and Routing Data Routing Functions Shifting Rotation Permutation Broadcast Multicast Shuffle Exchange Hypercube Routing Functions

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 24

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 25

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 26 Network Performance Functionality Network Latency Bandwidth Hardware Complexity Scalability Network Throughput Total no. of messages the network can handle per unit time Hot spot and Hot spot throughput

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 27 Static Connection Networks Liner Array Ring and Chordal Ring Barrel Shifter Tree and Star Fat Tree Mesh and Torus Systolic Arrays Hypercubes Cube-connected Cycles K- ary n-Cube Networks Summary of Static Network Characteristics Refer to Table 2.2 (on page 76) of textbook

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 28

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 29

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 30

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 31

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 32

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 33 Dynamic Connection Networks Bus System – Digital or Contention or Time-shared bus Switch Modules Binary switch, straight or crossover connections Multistage Interconnection Network (MIN) Inter-Stage Connection (ISC) – perfect shuffle, butterfly, multi-way shuffle, crossbar, etc. Omega Network Baseline Network Crossbar Network Summary of Dynamic Network Characteristics Refer to Table 2.4 (on page 82) of the textbook

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 34

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 35

SYSTEM INTERCONNECT ARCHITECTURES: 

SYSTEM INTERCONNECT ARCHITECTURES Sumit Mittu, Assistant Professor, CSE/IT, Lovely Professional University 36