Parallel Computation on a Network of Workstations

• IIS members:
  • Tsan-sheng Hsu, IIS, Academia Sinica.
• Outside members:
  • Dian Rae Lopez, Computer Science Discipline, Division of Science and Mathematics, University of Minnesota - Morris.

This problem studies the scheduling of parallel tasks with precedence constraints on a distributed memory parallel processing environment. There has been a lot of work in this area, however, we feel that those work suffer from several drawbacks which include over emphasizing empirical studies, and over simplifying machine models used to achieve meaningful theoretical results. Another drawback is the lack of a good model to address important issues in nowadays machines, e.g., pipe-lined communication, message transmission and receiving overhead, and communication latency.

• Tsan-sheng Hsu, Joseph C. Lee, Dian Rae Lopez and William A. Royce, "Task Allocation on a Network of Processors," IEEE Transactions on Computers, volume 49, number 12, pages 1339--1353, 2000.
  • In this paper, we not only provide more approximation algorithms, but also give performance evaluation data for the practical problem of image compressing. We find that our theoretical model nicely predict the behavior of a real network of workstations. We are still working in the area, hoping to get good average case performances by better heuristic algorithms and to get more approximation algorithms for lesser constraints or more restricted real cases.
• Tsan-sheng Hsu and Dian Rae Lopez, "Executing Divisible Jobs on a Network with a Fixed Number of Processors (Extended Abstract)," Proc. 4th International Computing and Combinatorics Conf. (COCOON), Springer-Verlag LNCS# 1449, pages 241--250, 1998.
  • In this paper we attempt to study the frequently encountered class of task graphs where jobs can be evenly divided in several ways. We have provided algorithms to find the best partition of data considering the latency and process speed.
• Lisa Hollermann, Tsan-sheng Hsu, Dian Rae Lopez, and Keith Vertanen, ``Scheduling Problems in a Practical Allocation Model,'' Journal of Combinatorial Optimization, volume 1, number 2, Pages 129--149, 1997.
  • In this paper, we provide several approximation algorithms and non-trivial analysises and proofs for several important classes of task graphs.
• Tsan-sheng Hsu and Dian Rae Lopez, ``Bounds and Algorithms for a Practical Task Allocation Model,'' Proc. 7th International Symposium on Algorithms and Computation (ISAAC), Springer-Verlag LNCS# 1178, pages 397--406, 1996.
  • This is our first paper to set up the foundations of this series of research. We describe the theory model and studies various complexity issues. It turns out obtaining an optimal scheduling under this model is NP-complete even for very simple instances.