Treffer: Scheduling algorithms for data redistribution and load-balancing on master-slave platforms
Title:
Scheduling algorithms for data redistribution and load-balancing on master-slave platforms
Authors:
Source:
Clusters and computational grids for scientific computingParallel processing letters. 17(1):61-77
Publisher Information:
Singapore: World Scientific Publishing, 2007.
Publication Year:
2007
Physical Description:
print, 15 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Electronics, Electronique, Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme glouton, Greedy algorithm, Algoritmo glotón, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Complétude, Completeness, Completitud, Equilibrage charge, Load balancing, Equilibrio de carga, Modélisation, Modeling, Modelización, Mémoire répartie, Distributed memory, Memoria compartida, Méthode polynomiale, Polynomial method, Método polinomial, Ordonnancement, Scheduling, Reglamento, Parallélisme, Parallelism, Paralelismo, Relation maître esclave, Master slave relationship, Relación maestro esclavo, Topologie, Topology, Topología, Master-slave platform, data redistribution, divisible load theory, independent tasks, one-port model, scheduling
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
LIP, ENS Lyon, 46 allée d'Italie, 69364 Lyon, France
ISSN:
0129-6264
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18702952
Database:
PASCAL Archive
Weitere Informationen
In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We considei the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We assume that the data consists of independent and identical tasks. We prove the NP completeness of the problem for fully heterogeneous platforms. Also, we present optimal polynomial algorithms for special important topologies: á simple greedy algorithm for homogeneous star-networks, and a more complicated algorithm for platforms with homogeneous communication links and heterogeneous workers.