Algorithms for Scheduling with Applications to Parallel Computing
Y. F. Hu and R. J. Blake
Daresbury Laboratory, CCLRC, Warrington WA4 4AD, UK
Scheduling of message passing for synchronous communication is found to
be equivalent to colouring the edges of a graph without conflict.
The graph edge-colouring
problem, which has other applications, is studied. An algorithm which
colours the graph with no more than
is the degree of
the graph, is implemented. The problem of minimising the sum of the largest
weight for each colour is also investigated and an algorithm suggested.
These algorithms are used to organise the communication
as part of a finite element
Different communication schemes and their effect on the performance of the flow
solver are compared.