Time-Multiplexed FPGA Overlay Networks on Chip

Citation

Mehta, Nikil (2006) Time-Multiplexed FPGA Overlay Networks on Chip. Master's thesis, California Institute of Technology. doi:10.7907/WZTS-XR26. https://resolver.caltech.edu/CaltechETD:etd-05312006-164103

Abstract

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.

Thesis Files