Configuring the Circuit Switched Tree for Multiple Width Communications
K. Roy, Ramachandran Vaidyanathan, Jerry L. Trahan · 2005
Dynamically reconfigurable architectures offer extremely fast solutions to various problems. The circuit switched tree (CST) is an important interconnects used to implement such architectures. A CST consists of processing elements (PEs) and switches. PEs communicate among themselves using the links of the tree. A key component for successful communication is scheduling individual communications and the configuration of the CST switches. This paper presents a scheduling and configuration algorithm for communications on a CST where conflicts force multiple rounds of routing to perform all communications. The paper also explains how to apply the algorithm to two important classes of communications, well-nested and monotonic, for which the algorithm is optimal and efficient. The algorithm is distributed and requires only local knowledge, yet it captures the global picture to ensure proper communication.