Parallel Algorithm For Network Traffic Scheduling In Application-Specific Architectures
Ronald P. Bianchini, John Paul Shen · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1988
For many application-specific and mission-oriented multiple processor systems, the interprocessor communication is deterministic and can be specified at system inception. This specification can be automatically mapped onto a physical system using a network traffic scheduler. An iterative network traffic scheduler is presented which, given the arbitrary topology of the communication network, translates the deterministic communication into a network traffic routing pattern. Previous work has shown the existence of a network traffic scheduling algorithm based on a fluid-flow model that converges to an optimal solution. However, this algorithm assumes an external host that performs centralized scheduling. This paper presents a parallel version of the algorithm which can be executed in a parallel fashion by the network switching nodes themselves without requiring an external host. Hence, using such an algorithm a communication network can perform self scheduling of interprocessor traffic. Furthermore, with the self-scheduling capability, a network will be able to perform traffic routing and scheduling concurrently and on-line network reconfiguration.