Abstract
dc:descriptionThe crossbar is the most popular switch for digital systems such as Internet routers, clusters, andmultiprocessors (on-chip, as well asmultichip). However, because the cost of the crossbar grows withthe square of the radix thereof, and because of past implementations in various technologies, it iswidely believed that the crossbar is not scalable to radices beyond 32 or 64, and that for higher radicesmore complicated networks are needed, where the crossbar is the basic building block. In this thesis,we scale the crossbar to radices well beyond 100 by crafting novel VLSI micro-architectures and theirdetailed CMOS layouts.As a case study, we laid out a 128×128×24Gb/s crossbar, interconnecting 128 1mm2 “user tiles” in asingle hop, using just 16mm2 of silicon in 90nm CMOS. The crossbar is 32bi t s wide, runs at 750MHz,and consumes 7Wat t s.In router systems, the user tiles will containmemory implementing combined queueing at the inputsand outputs of the crossbar, plus a small part of logic for port control. We show that this architectureis the best among a range of known router memory architectures (e.g. totally shared memory, solelyinput queueing, or crosspoint queueing), for two reasons: (i) It gives top performance using only amodest speedup on either the crossbar or the memories, independent of radix; and (ii) it partitionsthe memory space only linearly with the radix, thus yielding: (a) High SRAM density by using few,large, and area efficient blocks; and (b) highmemory space utilization through flexible sharing amongflows. In chip multiprocessors, the user tiles will contain cache or local memory, plus a small part oflogic for the processor. When traffic is global and heavy, such a system is competitive to the popularmesh-centric systems, owing to the simplified routing and load balancing of the crossbar.We made high radix crossbars feasible by developing novel VLSI micro-architectures for both theirdatapath and their control path. We implement the datapath using trees of multiplexor gates, as tristatebuses are slowed down by intrinsically large parasitic capacitances, and we show that highly concentratedtrees are more area efficient by further reducing the parasitic capacitance of their internalwires. Moreover, we contribute an experimental analysis showing that: (i) The area of the crossbar isgate limited for all practical values of its radix N and its width W, thus growing as O(N2W), not asO(N2W2), which would have been the case had area been wire limited, as is commonly believed inthe literature; and (ii) the delay of the crossbar is dominated by the parasitics of wires, and becausewire length grows with the perimeter of the crossbar, delay grows as O(NpW), not asO(logN), whichwould have been the case had delay been gate limited, as is commonly believed in the literature. Next,we propose novel pipelines to cope with the delay of the interconnect. Finally, we demonstrate thatmodern EDA tools can be guided to exploit the abundance of wiring resources through custom, butalgorithmic placement of gates.For the control path, we study the architecture of iSLIP, which is the most popular parallel matchingcrossbar scheduler. In particular, we study a traditional iSLIP architecture that implements thematching decision of each input and each output of the crossbar in a separate arbiter block, and communicatesthe matching decisions between the input and the output arbiters through global arbiterto-arbiter links. First, we show that this architecture is expensive because the arbiter-to-arbiter linkstake up O(N4) area. Thus, a r adi x-128 iSLIP scheduler occupies 14mm2, where the arbiter-to-arbiterlinks account for more than 50%. Next, by observing that the wiring of an arbiter fits in O(NlogN)area, we propose a novel architecture that inverts the locality of wires by orthogonally interleaving theinput with the output arbiters, thus lowering the wiring area of the scheduler down to O(N2log 2N).Using this architecture, the r adi x-128 iSLIP scheduler becomes gate limited, fitting in 7mm2, whichis a 50% reduction compared to the traditional. For a higher radix of 256, area is reduced by almostan order of magnitude. Finally, the running time of the proposed scheduler is less than 10ns, thusallowing operation with aminimum packet as small as 30By tes at a 24Gb/s line rate.
Degree
thesis:*- Grantor dc:publisher
- University of Crete (UOC)
- Year dc:date
- 2012
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Passas, Georgios
- Πασσάς, Γεώργιος
Subjects
dc:subject × 20- Δίκτυα διασύνδεσης
- Σταυραγωγοί
- Χρονοπρογραμματιστής
- Ολοκληρωμένα κυκλώματα ειδικού σκοπού
- Υψηλή κλίμακα ολοκλήρωσης
- Εργαλεία ηλεκτρονικού αυτοματισμού
- Πολυεπεξεργαστές στο ίδιο σπίτι
- Δρομολογητές ίντερνετ
- Interconnection network
- Crossbar
- Scheduler
- Application specific integrated circuits (ASICS)
- VLSI
- Electronic design automation
- Chip multiprocessors
- Internet routers
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26898