Algorithms for Scheduling with Applications to Parallel Computing

Y. F. Hu and R. J. Blake

Daresbury Laboratory, CCLRC, Warrington WA4 4AD, UK

Abstract:

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 $deg+1$ colours, where $deg$ 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 Euler solver. Different communication schemes and their effect on the performance of the flow solver are compared.

Hosted by www.Geocities.ws