Collision graph based communication scheduling and applications
David R. Surma, Edwin H.‐M. Sha · 1998
Multiprocessor systems are increasingly being used to meet the high performance and intense computation needs of today's applications. While such systems provide a reduction in the required computation time, the communication overhead caused by the allocation of tasks to multiple processors can be significant. To alleviate this problem, scheduling of the messages needed to move data and control information between processors is studied. Static scheduling techniques are developed which reduce the contention for common resources and provide a subsequent reduction in the overall completion time. At the center of these approaches is a new graph model called a collision graph. Because static scheduling is sensitive to the accuracy of the information used at compile time to determine the schedule, a hybrid static-dynamic approach is developed. This approach uses a priori information about the processing environment known at compile time to determine priorities for each message. At run-time these priorities are used to arbitrate the message transmissions. This research uses such a scheme as its base form of routing. However, to obtain further communication overhead reduction, a form of restricted re-routing is developed. Communication scheduling is done for both messages sent between a single source and a single destination, a unicast, and for multicasts where a single source transmits a message to many destinations. The scheduling techniques are used to reduce the latency incurred in simultaneous multiple multicasts by up to 70% compared to existing approaches. Additionally, the collision graph model is used to improve the loop scheduling done in multiprocessor systems. Together, the collision graph model and communication scheduling builds a new framework to study many existing and new problems.