Interprocessor Traffic Scheduling Algorithm for Multiple-Processor Networks

Recent research on parallel systems has shown that the most difficult problem for system designers and users is interprocessor connection and communication. A methodology for the automated design and implementation of interprocessor communication for certain multiple-processor systems has been developed and is presented in this paper. For many application- specific and mission-oriented systems, the interprocessor communication is deterministic and can be specified at system inception. This specification can then be automatically mapped or complied onto a physical multiple-processor system using a network traffic scheduler. An algorithm for such a scheduler, which is capable of obtaining optimal network traffic patterns, has been developed. It is shown that the order of complexity of network scheduler components is polynomial, rather than expopential as in classical solutions.