''Routing Multiple Width Communications on the Circuit Switched Tree''
Jerry L. Trahan
International Journal of Foundations of Computer Science,
vol. 17, no. 2, pp. 271-285, 2006
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 has a binary tree structure with processing elements (PEs) as
leaves and switches as internal nodes.
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 necessitate multiple rounds of
routing to perform all communications.
The paper also explains how to apply the algorithm to an important class
of communications, well-nested, 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 number CCR-0310916 and CCR-0073429.