Some models for scheduling parallel programs with communication delays. (English) Zbl 0863.68015
Summary: The aim of this paper is to present and analyze models for designing parallel programs. In the context of some extensions of the most popular execution models (precedence graphs, dataflow, PRAM), we describe scheduling techniques which take into account the communication delays. We illustrate all these models by two families of representative precedence graphs, namely, grids and complete trees.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68N99 | Theory of software |
References:
| [1] | Afrati, F.; Papadimitriou, C. H.; Papageorgiou, G., Scheduling DAGs to minimize time and computation, (Proceedings of the Aegian Workshop on Computing (AWOC) (1988)), 134-138 |
| [2] | Anderson, R. J.; Beame, P.; Ruzzo, W., Low overhead parallel schedules for task graphs, (Proceedings of SPAA (1990)), 66-75 |
| [3] | Aggarwal, A.; Chandra, A. K.; Snir, M., Communication complexity of PRAMs, Theoret. Comput. Sci., 71, 3-28 (1990) · Zbl 0699.68054 |
| [4] | Bampis, E., L’impact des communications sur la complexité des algorithmes parallèles, (Ph.D Thesis. (1993), University of Paris-Sud: University of Paris-Sud France) |
| [5] | E. Bampis, C. Delorme and J-C. König, Optimal schedules for dD-grid graphs with communication delays, in: C. Puech, R. Reischuk eds., STACS’96 LNCS No. 1046, 655-666.; E. Bampis, C. Delorme and J-C. König, Optimal schedules for dD-grid graphs with communication delays, in: C. Puech, R. Reischuk eds., STACS’96 LNCS No. 1046, 655-666. · Zbl 1379.68027 |
| [6] | Bampis, E.; König, J-C.; Trystram, D., Impact of communications on the complexity of the parallel Gaussian elimination, Parallel Comput., 17, 55-61 (1991) · Zbl 0725.65030 |
| [7] | Bampis, E.; König, J-C.; Trystram, D., A low overhead schedule for a 3D-Grid Graph, Parallel Process. Lett., 2, 363-372 (1992) |
| [8] | Bampis, E.; König, J-C.; Trystram, D., Optimal parallel execution of complete binary trees and grids into most popular interconnection networks, Theoret. Comput. Sci., 147, 1-18 (1995) · Zbl 0873.68156 |
| [9] | E. Bampis, J.-C. König and D. Trystram, Minimizing the schedule length for a parallel 3D-grid precedence graph, European J. Oper. Res., to appear.; E. Bampis, J.-C. König and D. Trystram, Minimizing the schedule length for a parallel 3D-grid precedence graph, European J. Oper. Res., to appear. · Zbl 0947.90575 |
| [10] | Coffman, E. G.; Denning, P. J., Operating Systems Theory (1972), Prentice Hall: Prentice Hall Englewood Cliffs, NJ |
| [11] | Colin, J.-Y.; Chrétienne, P., CPM scheduling with small interprocessor communication delays, Oper. Res., 39, 680-684 (1991) · Zbl 0793.68012 |
| [12] | Cosnard, M.; Ferreira, A., Designing parallel non numerical algorithms, (Evan, D. J.; etal., Parallel Computing ’91 (1991), North-Holland: North-Holland Amsterdam), 3-18 · Zbl 0798.68053 |
| [13] | De Rumeur, J., Communications dans les réseaux de processeurs, Masson, collection ERI (1994) |
| [14] | Gao, L.; Rosenberg, A. L.; Sitaraman, R. K., Optimal architecture-independent scheduling of fine-grain tree-sweep computations, (Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing (1995)), 620-629 |
| [15] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [16] | Guinand, F., Ordónnancement avec communications pour architectures multiprocesseurs dans divers modèles d’exécution, (Ph.D Thesis (1995), INPG, Grenoble: INPG, Grenoble France) |
| [17] | Guinand, F.; Trystram, D., Optimal scheduling of UECT trees on two processors, (Technical Report APACHE, \(n\)° 3 (1993), LMC-IMAG: LMC-IMAG Grenoble, France) |
| [18] | Jakoby, A.; Reischuk, R., The complexity of scheduling problems with communication delays for trees, (Proceedings of the Scandinavian Workshop of Algorithmic Theory. Proceedings of the Scandinavian Workshop of Algorithmic Theory, Lecture Notes in Computer Science, Vol. 621 (1992), Springer: Springer Berlin), 165-177 · Zbl 1502.68048 |
| [19] | Jung, H.; Kirousis, L.; Spirakis, P., Inform. Comput., 105, 94-104 (1993) · Zbl 0781.68070 |
| [20] | Lageweg, B. J.; Lenstra, J. K.; Veltman, B., Multiprocessor scheduling with communication delays, Parallel Comput, 16, 173-182 (1990) · Zbl 0711.68017 |
| [21] | Lawler, E. L., Scheduling trees on multiprocessors with unit communication delays, Workshop on Models and Algorithms for Planning and Scheduling Problems, ((June 1993), Villa Vigoni: Villa Vigoni Lake Como, Italy), 14-18 |
| [22] | Leighton, T., Methods for message routing in parallel machines, (Proceedings of the 24th Annual ACM Symposium on Theory Comput. (1992)), 77-96 |
| [23] | Norman, M. G.; Thanisch, P.; Chang, K.-F., Partitioning DAG computations: a cautionary note, (Joosen, W.; Milgrom, E., Parallel Computing: From Theory to Sound Practice (1992), IOS Press), 360-363 |
| [24] | Papadimitriou, C.; Ullman, J., A communication time tradeoff, SIAM J. Comput., 16, 639-646 (1987) · Zbl 0649.68048 |
| [25] | Papadimitriou, C.; Yannakakis, M., SIAM J. Comput., 9, 322-328 (1990) · Zbl 0692.68032 |
| [26] | Picouleau, C., Elude des Problèmes d’Optimisation dans les Systèmes Distribués, (Ph.D Thesis (1993), University of Paris VI: University of Paris VI France) |
| [27] | Rayward-Smith, V. J., UET scheduling with unit interprocessor communication delays, Discrete Appl. Math., 18, 55-71 (1987) · Zbl 0634.90031 |
| [28] | Varvarigou, T.; Roychowdhury, V. P.; Kailath, T., Scheduling in and out forests in the presence of communication delays, (Proceedings of International Parallel Processing Symp. (IPPS’93) (1993)), 173-182 |
| [29] | T. Varvarigou, V.P. Roychowdhury and T. Kailath, E. Lawler, Scheduling in and out forests in the presence of communication delays, IEEE Tran. Parallel Distributed Systems, to appear.; T. Varvarigou, V.P. Roychowdhury and T. Kailath, E. Lawler, Scheduling in and out forests in the presence of communication delays, IEEE Tran. Parallel Distributed Systems, to appear. |
| [30] | Veldhorst, M., A linear time algorithm to schedule trees with communication delays optimally on two machines, (Technical Report RUU-CS-93-04 (January 1993), Department of Computer Science: Department of Computer Science Utrecht) |
| [31] | Veltman, B., Multiprocessor scheduling with communication delays, (Ph.D Thesis (1993), CWI-Amsterdam: CWI-Amsterdam Holland) · Zbl 0711.68017 |
| [32] | Veltman, B.; Lageweg, B. J.; Lenstra, J. K., Multiprocessor scheduling with communication delays, Parallel Comput., 16, 173-182 (1990) · Zbl 0711.68017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
