Type of Document Dissertation Author Roy, Krishnendu Author's Email Address kroy1@ece.lsu.edu URN etd-07032009-232128 Title Scheduling and Reconfiguration of Interconnection Network Switches Degree Doctor of Philosophy (Ph.D.) Department Electrical & Computer Engineering Advisory Committee
Advisor Name Title Trahan, Jerry Lee Committee Co-Chair Vaidyanathan, Ramachandran Committee Co-Chair Koppelman, David M Committee Member Ramanujam, Jagannathan Committee Member Ullmer, Brygg A Committee Member Sengupta, Ambar N Dean's Representative Keywords
- Logarithmic Delay Bound
- Circuit Switched Tree
- Fat-Tree
- Reconfigurable Algorithms
- Packet Delay
- Switch Scheduling
- Interconnection Network
- Network Switch
- Reconfigurable-Mesh
- Maximal Bipartite Matching
Date of Defense 2009-06-25 Availability unrestricted Abstract Interconnection networks are important parts of modern computing systems, facilitating communication between a system's components. Switches connecting various nodes of an interconnection network serve to move data in the network. The switch's delay and throughput impact the overall performance of the network and thus the system. Scheduling efficient movement of data through a switch and configuring the switch to realize a schedule are the main themes of this research. We consider various interconnection network switches including (i) crossbar-based switches, (ii) circuit-switched tree switches, and (iii) fat-tree switches.
For crossbar-based input-queued switches, a recent result established that logarithmic packet delay is possible. However, this result assumes that packet transmission time through the switch is no less than schedule-generation time. We prove that without this assumption (as is the case in practice) packet delay becomes linear. We also report results of simulations that bear out our result for practical switch sizes and indicate that a fast scheduling algorithm reduces not only packet delay but also buffer size. We also propose a fast mesh-of-trees based distributed switch scheduling (maximal-matching based) algorithm that has polylog complexity.
A circuit-switched tree (CST) can serve as an interconnect structure for various computing architectures and models such as the self-reconfigurable gate array and the reconfigurable mesh. A CST is a tree structure with source and destination processing elements as leaves and switches as internal nodes. We design several scheduling and configuration algorithms that distributedly partition a given set of communications into non-conflicting subsets and then establish switch settings and paths on the CST corresponding to the communications.
A fat-tree is another widely used interconnection structure in many of today's high-performance clusters. We embed a reconfigurable mesh inside a fat-tree switch to generate efficient connections. We present an R-Mesh-based algorithm for a fat-tree switch that creates buses connecting input and output ports corresponding to various communications using that switch.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access RoyDiss.pdf 878.78 Kb 00:04:04 00:02:05 00:01:49 00:00:54 00:00:04
If you have questions or technical problems, please Contact LSU-ETD Support.