Optimal partitioning of random workloads in homogeneous multiprocessor and distributed systems
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 386-393
- https://doi.org/10.1109/spdp.1990.143571
Abstract
The problem of distributing M interacting program modules of a given homogeneous random workload over P identical processors for optimizing execution time is examined. The execution time modeling allows full concurrency of activities among different processors but cascades for each processor its computation time, internal communications, external communications, and synchronization/contention delays. The results obtained express the optimality conditions in terms of the various statistical and deterministic parameters of the problem: number of modules; number of processors; mean value of module run time; probabilities and mean values of intraprocessor, interprocessor, and synchronization/contention communications overheads. Optimal load distributions are found to be either even or single-processor assignments, albeit for different conditions than stipulated in previous results.Keywords
This publication has 10 references indexed in Scilit:
- Optimal partitioning of random programs across two processorsIEEE Transactions on Software Engineering, 1989
- Heuristic algorithms for task assignment in distributed systemsIEEE Transactions on Computers, 1988
- Partitioning problems in parallel, pipeline, and distributed computingIEEE Transactions on Computers, 1988
- Assignment Problems in Parallel and Distributed ComputingPublished by Springer Nature ,1987
- Optimal partitioning of randomly generated distributed programsIEEE Transactions on Software Engineering, 1986
- Modeling Algorithm Execution Time on Processor ArraysComputer, 1984
- A Task Allocation Model for Distributed Computing SystemsIEEE Transactions on Computers, 1982
- Assignment of Tasks in a Distributed Processor System with Limited MemoryIEEE Transactions on Computers, 1979
- Critical Load Factors in Two-Processor Distributed SystemsIEEE Transactions on Software Engineering, 1978
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977