Scheduling Parallel Computations with Successive CPM Domains
Richard J. Schmidt, Dennis Horning · Computer-Aided Civil and Infrastructure Engineering · 1990
This paper describes a functional procedure for implementation of structural engineering applications in an asynchronously scheduled multi-processor environment. A modification to the classical critical path method is proposed that permits scheduling of networks that contain conditional branching or loops. A general outline is presented, describing the functional requirements of two utility procedures that generate a priority list for scheduling tasks for the particular algorithm of interest. These list-generating utilities, operating with a driver program, work with a modified version of SCHEDULE (a list scheduler) to allocate tasks to processors in an order determined using the weighted-priority heuristic. Programming difficulties inherent in schedule implementation for both shared memory systems and loosely coupled systems (with emphasis on hypercubes) are discussed. The approach is demonstrated on the subspace iteration algorithm.