Divisible Load Scheduling: A Tutorial on Computational Load Partitioning

1. Divisible Load Scheduling Divisible Load Scheduling A Tutorial A Tutorial Thomas Robertazzi University at Stony Brook

2. What is a Divisible Load? What is a Divisible Load? b A computational & networkable load that is arbitrarily partitionable (divisible) amongst processors and links. b A computational & networkable load that is arbitrarily partitionable (divisible) amongst processors and links. b There are no precedence relations. b There are no precedence relations.

3. Simple Application Example Simple Application Example b Problem: Sum 1000 trillion numbers b Problem: Sum 1000 trillion numbers b Approach: Partition the numbers among 100 processors b Approach: Partition the numbers among 100 processors b But how? b But how?

4. Simple Application Example Simple Application Example b To optimize solution time (maximize speedup) one needs to take into account heterogeneous link and processor speeds, computation and communication intensities, interconnection topology and scheduling policy. b To optimize solution time (maximize speedup) one needs to take into account heterogeneous link and processor speeds, computation and communication intensities, interconnection topology and scheduling policy. b Divisible Load Scheduling Theory Can Do This! b Divisible Load Scheduling Theory Can Do This!

5. Applications (Generic) Applications (Generic) b Grid Computing/Meta-computing b Grid Computing/Meta-computing b Data Intensive Computing b Data Intensive Computing b Sensor Processing b Sensor Processing b Image Processing b Image Processing b Scientific/Engineering Computing b Scientific/Engineering Computing b Financial Computing b Financial Computing

6. Applications (Specific) Applications (Specific) b Pattern Searching b Pattern Searching b Database Computation b Database Computation b Matrix-Vector Computation b Matrix-Vector Computation b E&M Field Calculation (CAD) b E&M Field Calculation (CAD) b Edge Detection b Edge Detection

7. DLT Modeling Advantages DLT Modeling Advantages b Linear and Deterministic Modeling b Linear and Deterministic Modeling b Tractable Recursive/Linear Equation Solution b Tractable Recursive/Linear Equation Solution b Schematic Language b Schematic Language b Equivalent Elements b Equivalent Elements b Many Applications b Many Applications

8. Interconnection Topologies Interconnection Topologies b Linear Daisy Chain b Linear Daisy Chain b Bus b Bus b Single Level and Multilevel Trees b Single Level and Multilevel Trees b Mesh b Mesh b Hypercube b Hypercube

9. Directions: Scalability Directions: Scalability 1 3 2 1 1 1 Sequential Distribution (Saturation) Simultaneous Distribution (Scalable) Hung & Robertazzi Cheng & Robertazzi

10. An Example An Example b Model Specifications: b Model Specifications: A star network( single level tree network), and multi-level tree. A star network( single level tree network), and multi-level tree. Computation and transmission time is a linear function of the size of load. Computation and transmission time is a linear function of the size of load. Level to Level: Store and Forward Switching Level to Level: Store and Forward Switching Same Level: Concurrent Load Distribution. Same Level: Concurrent Load Distribution.

11. b Children without Front End: b Children without Front End: b After receiving the assigned data, each child proceeds to process the data. b After receiving the assigned data, each child proceeds to process the data.

12. b Timing Diagram (single level tree) : b Timing Diagram (single level tree) : b Children without Front End b Children without Front End

13. m+1 unknows vs. m+1 Eqs. m+1 unknows vs. m+1 Eqs. b Recursive equations: b Recursive equations: b Normalization equation: b Normalization equation:

14. b Distribution Solution: b Distribution Solution:

15. b The load distribution solution is similar to the solution of the state-dependent M/M/1 queuing system. b The load distribution solution is similar to the solution of the state-dependent M/M/1 queuing system.

16. Similarities to Queueing Theory Similarities to Queueing Theory b Linear model and tractable solutions b Linear model and tractable solutions b Schematic Language b Schematic Language b Equivalent Elelements b Equivalent Elelements b Infinite Size Networks b Infinite Size Networks

17. b Speedup Analysis b Speedup Analysis

18. b Speedup Analysis (continued) b Speedup Analysis (continued)

19. b Tree Network b Tree Network b (Children without Front Ends) b (Children without Front Ends)

20. Collapsing single level trees Collapsing single level trees

21. Bandwidth of Fat Tree Bandwidth of Fat Tree b Definition: The bandwidth of level j in a fat tree can be defined as p j-1 z. b Definition: The bandwidth of level j in a fat tree can be defined as p j-1 z.

22. Directions: Sequencing and Installments Directions: Sequencing and Installments b Daisy Chain Surprise b Daisy Chain Surprise b Efficiency Rule b Efficiency Rule Ghose, Mani & Bharadwaj

23. Directions: Sequencing and Installments Directions: Sequencing and Installments b Multi-installment for Sequential Distribution b Multi-installment for Sequential Distribution 1 2 3 4 5 6 Ghose, Mani & Bharadwaj

24. Directions: Sequencing and Installments Directions: Sequencing and Installments Diminishing returns in using multi-installment distribution. Ghose, Mani & Bharadwaj

25. Directions: Sequencing and Installments Directions: Sequencing and Installments Drozdowski

26. Directions: Time Varying Modeling Directions: Time Varying Modeling Can be solved with integral calculus. Sohn & Robertazzi

27. Directions: Monetary Cost Optimization Directions: Monetary Cost Optimization Min C Total n c n w n T cp Min C Total n c n w n T cp n=1 N Bus Processors Optimal Sequential Distribution if: c n-1 w n-1 less than c n w n for all n Sohn, Luryi & Robertazzi

28. Directions: Monetary Cost Optimization Directions: Monetary Cost Optimization b 2 US Patents: b 2 US Patents: Patent 5,889,989 (1999): Processor Cost Patent 5,889,989 (1999): Processor Cost Patent 6,370,560 (2001): Processor and Patent 6,370,560 (2001): Processor and Link Cost Link Cost Enabling technology for an open e-commerce Enabling technology for an open e-commerce market in leased proprietary computing. market in leased proprietary computing. Sohn, Charcranoon, Luryi & Robertazzi

29. Directions: Database Modeling Directions: Database Modeling Expected time to find multiple records in flat file database Ko & Robertazzi

30. Directions: Realism Directions: Realism Finite Buffers (Bharadwaj) Finite Buffers (Bharadwaj) Job Granularity (Bharadwaj) Job Granularity (Bharadwaj) Queueing Model Integration Queueing Model Integration

31. Directions: Experimental Work Directions: Experimental Work Database Join (Drozdowski)

32. Directions: Future Research Directions: Future Research b Operating Systems: b Operating Systems: Incorporate divisible load scheduling Incorporate divisible load scheduling into (distributed) operating systems into (distributed) operating systems b Measurement Process Modeling: b Measurement Process Modeling: Integrate measurement process Integrate measurement process modeling into divisible scheduling modeling into divisible scheduling

33. Directions: Future Research Directions: Future Research b Pipelining (Dutot) b Pipelining (Dutot) Concept: Distribute load to Concept: Distribute load to further processors first for further processors first for speedup improvement speedup improvement Improvement reported for daisy chains Improvement reported for daisy chains

34. Directions: Future Research Directions: Future Research b System Parameter Estimation (Ghose): b System Parameter Estimation (Ghose): Concept: Send small probing loads across Concept: Send small probing loads across links and to processors to estimate links and to processors to estimate available effort available effort Challenge: Rapid change in link & processor Challenge: Rapid change in link & processor state state

35. DLT has a Good Future DLT has a Good Future b Many Applications including b Many Applications including wireless sensor networks wireless sensor networks b Tractable (Modeling & Computation) b Tractable (Modeling & Computation) b Rich Theoretical Basis b Rich Theoretical Basis

36. Thank you! Thank you! Questions??? Questions???