A Caltech Library Service

Time-Multiplexed FPGA Overlay Networks on Chip


Mehta, Nikil (2006) Time-Multiplexed FPGA Overlay Networks on Chip. Master's thesis, California Institute of Technology. doi:10.7907/WZTS-XR26.


How do we design a communication network for processing elements (PEs) on a single chip that minimizes application communication time and area? In designing such a network it is essential to use a network communication pattern that matches application communication and area requirements. This report characterizes the design space of a particular communication pattern for networks on chip: Time-Multiplexed Interconnect. In contrast to more commonly used packet-switched networks, which route communication dynamically, time-multiplexed networks schedule all possible communication prior to runtime with an offline router. We describe how to build well engineered, highly scalable time-multiplexed FPGA networks in terms of topology selection, routing algorithm design and hardware design that operate on a Xilinx XC2V6000-4 at 166MHz. To benchmark our networks we use real, communication rich applications instead of generating synthetic traffic. We show that over all areas (10K–10M slices) and over all applications the best "one topology fits all" is Butterfly Fat Tree (BFT) with c = 1, p = 0.5, which requires, in the worst case, 6.1x as many cycles to route communication than the optimal topology. We compare time-multiplexing to packet-switching, and show that on average, over all applications for all equivalent topologies, online packet-switched communication requires 1.5x as many cycles to route as offline time-multiplexed scheduling. When applying designs to equivalent area, for areas <100K slices packet-switching typically outperforms time-multiplexing, but at >100K slices packet-switching requires up to 3.4x as many cycles to route as time-multiplexing in the worst case. Finally, for equivalent, large networks (>100 PEs) time-multiplexing outperforms packet-switching for communication loads where greater than 10% of all logical links are active. This demonstrates that well designed time-multiplexed FPGA overlay networks can deliver performance and area efficiency exceeding that of packet-switched networks.

Item Type:Thesis (Master's thesis)
Subject Keywords:FPGA; Graph Machine; Network on Chip; Overlay Network; Reconfigurable Computing; Time Multiplexed; Topology
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • DeHon, Andre
Thesis Committee:
  • Unknown, Unknown
Defense Date:31 May 2006
Record Number:CaltechETD:etd-05312006-164103
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2335
Deposited By: Imported from ETD-db
Deposited On:05 Jun 2006
Last Modified:27 Mar 2020 00:09

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page