Hybrid static-dynamic communication scheduling for parallel systems

Parallel processing techniques have become widespread in applications requiring very high throughput or which have real-time deadlines. However, the potential gains from parallel processing can be diminished by the communication overhead inherent in these systems. With tightly-coupled architectures being used as the platform, an optimal way of scheduling the messages in a network is addressed. Static scheduling, while being able to utilize a priori information, is found to be lacking when this information is unavailable or inaccurate. Dynamic scheduling can adjust to changes within the network at run-time but suffers from not having any knowledge of the network traffic environment. To solve this problem, we introduce a hybrid scheduling technique which seeks to extract the best from each of these approaches. This hybrid scheduling technique incorporates a priority scheme derived from using the newly developed Collision Graph model. The determination of an optimal schedule is an NP-complete problem. Therefore, heuristics are used in the development of a priority mapping algorithm to deal with a general case model of message traffic. Experiments performed show a significant improvement over baseline approaches.