Title page for ETD etd-07032009-232128


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

Browse All Available ETDs by ( Author | Department )

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