Title :
Optimal partitioning of random workloads in homogeneous multiprocessor and distributed systems
Author :
Haddad, Emile K.
Author_Institution :
Dept. of Comput. Sci., Virginia Polytech. Inst. & State Univ., Falls Church, VA, USA
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 :
computational complexity; concurrency control; distributed processing; multiprocessing programs; optimisation; scheduling; storage allocation; computational complexity; concurrency; distributed systems; execution time; load distributions; multiprocessor systems; optimisation; random workloads; task scheduling; Computational complexity; Computer science; Concurrent computing; Delay effects; Heuristic algorithms; Multiprocessing systems; Parallel processing; Partitioning algorithms; Random variables; Stochastic processes;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143571
