Optimum divisible load scheduling on heterogeneous stars with limited memory
| Autor: | Maciej Drozdowski, Pawel Wolniewicz |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Information Systems and Management
General Computer Science Computer science Computation Parallel algorithm A* search algorithm Parallel computing Management Science and Operations Research Telecommunications network Industrial and Manufacturing Engineering Scheduling (computing) law.invention Exact algorithm law Modeling and Simulation Heuristics Time complexity |
| Zdroj: | European Journal of Operational Research. 172:545-559 |
| ISSN: | 0377-2217 |
| Popis: | Scheduling divisible application on a set of heterogeneous processors with limited memory sizes is analyzed in this paper. Divisible loads are computations which allow for dividing computations into several parts of arbitrary sizes, and the parts can be processed independently in parallel. Though the model originated in the parallel computing context, it has strong links with other applications of operations research. A star communication network is assumed. Each processing element of the network is characterized by the processing speed, memory size, speed and startup time of its communication link. The goal is to find a distribution of the load whose schedule length is minimum. The problem is established to be computationally hard. Therefore, two types of algorithms are proposed, and evaluated: an exact algorithm whose execution time may be exponential, and polynomial-time heuristics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect