Optimal sharing of bags of tasks in heterogeneous clusters

ABSTRACT

We prove that "FIFO" worksharing protocols provide asymptotically optimal solutions to a problem related to sharing a bag of identically complex tasks in a heterogeneous network of workstations (HNOW) n. In the HNOW-Exploitation Problem, one seeks to accomplish as much work as possible on n during a prespecified fixed period of L time units. The worksharing protocols we study are crafted within an architectural model that characterizes n via parameters that measure workstations' computational and communicational powers. The protocols are self-scheduling, in that they determine completely both an amount of work to allocate to each of n's workstations and a schedule for all related interworkstation communications. A protocol observes a FIFO regimen if it has n's workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes. Simulation experiments indicate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes' duration.

REFERENCES

• 1: Micah Adler , Ying Gong , Arnold L. Rosenberg, Asymptotically Optimal Worksharing in HNOWs: How Long is "Sufficiently Long?", Proceedings of the 36th annual symposium on Simulation, p.39, March 30-April 02, 2003
• 2: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
• 3: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 4: M.J. Atallah, C.L. Black, D.C. Marinescu, H.J. Siegel, T.L. Casavant (1992): Models and algorithms for coscheduling compute-intensive tasks on a network of workstations. J. Parallel Distr. Comput. 16, 319--327.
• 5: M. Banikazemi and D.K. Panda (2000): Efficient collective communication on heterogeneous networks of workstations. Tech. Rpt., Ohio State Univ.
• 6: Olivier Beaumont , Arnaud Legrand , Yves Robert , Larry Carter , Jeanne Ferrante, Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.79, April 15-19, 2002
• 7: V. Bharadwaj , D. Ghose , V. Mani, Optimal Sequencing and Arrangement in Distributed Single-Level Tree Networks with Communication Delays, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.968-976, September 1994 [doi>10.1109/71.308534]
• 8: V. Bharadwaj, D. Ghose, V. Mani (1995): Multi-installment load distribution in tree networks with delays. IEEE Trans. Aerospace and Electron. Systs. 31, 555--567.
• 9: Prashanth B. Bhat , Viktor K. Prasanna , C. S. Raghavendra, Adaptive Communication Algorithms for Distributed Heterogeneous Systems, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.310, July 28-31, 1998
• 10: Efficient Collective Communication in Distributed Heterogeneous Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.15, May 31-June 04, 1999
• 11: Franck Cappello , Pierre Fraigniaud , Bernard Mans , Arnold L. Rosenberg, HiHCoHP: Toward a Realistic Communication Model for Hierarchical HyperClusters of Heterogeneous Processors, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.42, April 23-27, 2001
• 12: Y.C. Cheng and T.G. Robertazzi (1990): Distributed computation for tree networks with communication delays. IEEE Trans. Aerospace and Electron. Systs. 26, 511--516.
• 13: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 14: Tsan-Sheng Hsu , Joseph C. Lee , Dian Rae Lopez , William A. Royce, Task Allocation on a Network of Processors, IEEE Transactions on Computers, v.49 n.12, p.1339-1353, December 2000 [doi>10.1109/12.895858]
• 15: Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
• 16: Ram Kesavan , Kiran Bondalapati , Dhabaleswar K. Panda, Multicast on Irregular Switch-based Networks with Wormhole Routing, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.48, February 01-05, 1997
• 17: Pangfeng Liu , Tzu-Hao Sheng, Broadcast scheduling optimization for heterogeneous cluster systems, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.129-136, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341816]
• 18: Reduction Optimization in Heterogeneous Cluster Environments, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.477, May 01-05, 2000
• 19: Gregory F. Pfister, In search of clusters (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 20: Ravi Prakash , Dhabaleswar K. Panda, Designing communication strategies for hetereogeneous parallel systems, Parallel Computing, v.24 n.14, p.2035-2052, Dec. 1998 [doi>10.1016/S0167-8191(98)00089-1]
• 21: David A. Reimann , Vipin Chaudhary , Ishwar K. Sethi, Modeling Cone-Beam Tomographic Reconstruction Using LogSMP: An Extenced LogP Model for Clusters of SMPs, Proceedings of the 6th International Conference on High Performance Computing, p.77-83, December 17-20, 1999
• 22: Arnold L. Rosenberg, Needed: a theoretical basis for heterogeneous parallel computing, Developing a computer science agenda for high-performance computing, ACM Press, New York, NY, 1994 [doi>10.1145/197912.198003]
• 23: Arnold L. Rosenberg, Sharing Partitionable Workloads in Heterogeneous NOWs: Greedier Is Not Better, Proceedings of the 3rd IEEE International Conference on Cluster Computing, p.124, October 08-11, 2001
• 24: A.S. Tosun and A. Agarwal (2000): Efficient broadcast algorithms for heterogeneous networks of workstations. Tech. Rpt., Ohio State Univ.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance, Theory

Keywords:
bags of tasks workloads, cluster computing, heterogeneous NOW, network of workstations (NOW), worksharing