Abstract |
---|
This paper investigates the effect of communication overheads on the scheduling problem. We present a scheduling algorithm, based on LogP-type models, for allocating task graphs to networks of processors. The makespans of schedules produced by our Multi-stage Scheduling Approach (MSA) are compared with other well-known scheduling heuristics.The results indicate that new classes of scheduling heuristics are required to generate efficient schedules for realistic abstractions of today's parallel computers. The scheduling strategy of MSA can also be used to generate BSP-structures programs from more abstract representations. The performance of such programs are compared with "conventional" versions. |
Contact |
Cristina Boeres Departamento de Ciencia da Computacao,Universidade Federal Fluminense (UFF),Inst. de Matematica - 4 andar,Praca do Valonguinho s/n, Centro,Niteroi 24210-130 RJ,BRAZIL boeres@urbi.com.br |