Title page for ETD etd-0410103-215703

Type of Document Dissertation
Author El-Boghdadi, Hatem Mahmoud El-Sayed
Author's Email Address helbog1@lsu.edu
URN etd-0410103-215703
Title On Implementing Dynamically Reconfigurable Architectures
Degree Doctor of Philosophy (Ph.D.)
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
R.Vaidyanathan Committee Chair
J. Ramanujam Committee Member
J. Trahan Committee Member
S. Rai Committee Member
S.Kundu Committee Member
R. Litherland Dean's Representative
  • dynamic reconfiguration
  • segmentable bus
  • circuit switched tree
  • self reconfiguration
  • reconfigurable mesh
Date of Defense 2003-04-08
Availability unrestricted
Dynamically reconfigurable architectures have the ability to change their structure at each step of a computation. This dissertation studies various aspects of implementing dynamic reconfiguration, ranging from hardware building blocks and low-level architectures to modeling issues and high-level algorithm design.

First we derive conditions under which classes of communication sets can be optimally scheduled on the circuit-switched tree (CST). Then we present a method to configure the CST to perform in constant time all communications scheduled for a step. This results in a constant time implementation of a step of a segmentable bus, a fundamental dynamically reconfigurable structure.

We introduce a new bus delay measure (bends-cost) and define the bends-cost LR-Mesh; the LR-Mesh is a widely used reconfigurable model. Unlike the (idealized) LR-Mesh, which ignores bus delay, the bends-cost LR-Mesh uses the number of bends in a bus to estimate its delay. We present an implementation for which the bends-cost is an accurate estimate of the actual delay. We present algorithms to simulate various LR-Mesh configuration classes on the bends-cost LR-Mesh. For "semimonotonic configurations," a Θ(N)*Θ(N) bends-cost LR-Mesh with bus delay at most D can simulate a step of the idealized N*N LR-Mesh in O((log N/(log D-log Δ))2) time (where Δ is the delay of an N-element segmentable bus), while employing about the same number of processors. For some special cases this time reduces to O(log N/(log D-log Δ)). If D=Nε, for an arbitrarily small constant ε > 0, then the running times of bends-cost LR-Mesh algorithms are within a constant of their idealized counterparts. We also prove that with a polynomial blowup in the number of processors and D=Nε, the bends-cost LR-Mesh can simulate any step of an idealized LR-Mesh in constant time, thereby establishing that these models have the same "power."

We present an implementation (in VHDL) of the "Enhanced Self Reconfigurable Gate Array" (E-SRGA) architecture and perform a cost-benefit study for different dynamic reconfiguration features. This study shows our approach to be feasible.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  El-Boghdadi_dis.pdf 1.40 Mb 00:06:27 00:03:19 00:02:54 00:01:27 00:00:07

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.