A strategy for scheduling partially ordered program graphs onto multicomputers

The issue of scalability is key to the success of massively parallel processing. Due to their distributed nature, message-passing multicomputers are appropriate for achieving scalar performance. However, the message-passing programming model lacks programmability due to difficulties encountered by the programmers to partition and schedule the computation over the processors and to establish efficient inter-processor communication in the user code. Therefore, this paper presents a compile-time scheduling heuristic, called BLAS, that maps programs onto the processors of a message-passing multicomputer. In contrast to other methods proposed in the literature, BLAS takes a more global approach in attempt to balance the tradeoff between exploitation of parallelism and reducing communication overhead. To evaluate the effectiveness of BLAS, detailed simulation studies of scheduling SISAL programs are presented