Collision Graph based Communication Scheduling for Parallel Systems

Applications such as image processing, fluid mechanics, and geophysical data analysis are examples of problems that require the high computing performance provided by multi-processor systems. Such performance depends highly on the interprocessor communication time resulting from allocating tasks to the individual processors. This research focuses on the development of techniques that reduce the communication overhead by intelligently scheduling message transmissions within a tightly-coupled processor network. Using a collision graph to model the system message traffic, static scheduling algorithms are developed to reduce the communication overhead. Since a priori knowledge about the network, required in static approaches, may not always be available or accurate, dynamic scheduling is also considered. A novel hybrid static-dynamic scheduling approach is presented which operates in a dynamic environment, yet uses known communication pattern information. Results show improvement over base..