Title :
General non-approximability results in presence of hierarchical communications
Author :
Giroudeau, R. ; König, J.C.
Author_Institution :
LIRMM, Montpellier, France
Abstract :
We investigate the problem of minimizing the makespan (resp. the sum of the completion time) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in connected clusters. We propose general non-approximability results for the case where all the tasks of the precedence graph have unit execution times, where the multiprocessor is composed of an unrestricted number of machines with ℓ ≥ 4 identical processors each.
Keywords :
hierarchical systems; message passing; minimisation; multiprocessing systems; multiprocessor interconnection networks; processor scheduling; resource allocation; hierarchical communications; intercluster communication; interprocessor communication; makespan minimization; multiprocessor scheduling problem; nonapproximability; precedence graph; Algorithm design and analysis; Computer networks; Concurrent computing; Delay; History; Parallel processing; Power system modeling; Processor scheduling; Scheduling algorithm; Workstations; hierarchical communications; nonapproximability; scheduling;
Conference_Titel :
Parallel and Distributed Computing, 2004. Third International Symposium on/Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, 2004. Third International Workshop on
Print_ISBN :
0-7695-2210-6
DOI :
10.1109/ISPDC.2004.27
