''Configuring the Circuit Switched Tree for Multiple Width Communications''
Krishnendu Roy
Ramachandran Vaidyanathan
Jerry L. Trahan
Proc. Workshop on Advances in Parallel and Distributed Computational Models (APDCM 2005)
Abstract:
Dynamically reconfigurable architectures offer extremely fast solutions
to various problems. The Circuit Switched Tree (CST) is an important
interconnect 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.
This work was supported in part by
the National Science Foundation under grant numbers CCR-0310916 and CCR-0073429.