''On the Communication Capability of the Self-Reconfigurable Gate Array Architecture''

Hatem M. El-Boghdadi

Ramachandran Vaidyanathan

Jerry L. Trahan

Suresh Rai

Proc. 2002 Reconfigurable Architectures Workshop (RAW'02)


To exploit the benefits of run-time reconfiguration in an FPGA-like setting, a self-reconfigurable gate array (SRGA) architecture has been proposed by Sidhu et al. This architecture consists of an array of PEs connected by row and column trees. In this paper, we study the communication capability of this tree-based interconnection fabric. We derive a necessary condition for any set of k one-to-one communications to be performed in t steps, for any 1 <= t <= k. Next, we identify a property of the communication set, called partitionability, for which the above necessary condition is sufficient as well. Then we show two classes of communication sets to possess this property. As a special case of one of these results, we show that the set of communications that can be performed in one step on a segmentable bus can be performed in two steps on the SRGA architecture. This result implies that the communication ability of the bit model HV-R-Mesh, a special case of the bit model R-Mesh, can be emulated by the SRGA architecture without significant overhead.

This work was supported in part by the National Science Foundation under grant number CCR-0073429.