Li-Shiuan Peh

PhD (August 2001)

Department of Computer Science

Stanford University


Research

I was a member of the Concurrent VLSI Architecture Group in the Computer Systems Laboratory, led by Professor William J. Dally.

My research focuses on interconnection networks, the networks which traditionally connect multiprocessors, but have recently been deployed as fabrics of high-speed routers in system-area networks, storage networks and the Internet. At the same time, chips have grown in complexity to the point that interconnection networks are beginning to be used for on-chip communication in addition to system-level communication.

More specifically, my research has been largely concerned with the flow control of interconnection networks, i.e., how buffers and channels are allocated. Unlike current flow control methods which reserve buffers and channels on-the-fly, I propose flit-reservation flow control, where control flits traverse the network in advance of data flits, reserving buffers and channel bandwidth ahead of time. When data flits come along, they are simply forwarded or buffered according to this prior reservation. This advance scheduling brings about two advantages. First, it allows routing and arbitration latency to be hidden, when the destination is known beforehand. For instance, in response to a memory read request, control flits can traverse the network and reserve resources for data flits while the DRAM is being accessed, so when the data flits are ready, they can simply move through the network at the minimal wire speed. Second, scheduling ahead of data arrival enables buffers to be immediately re-used, unlike current flow control methods which idles each buffer for a considerable period after each flit departure. While flit-reservation flow control spawns new dependencies between the control and data layers, I proved through a detailed deadlock analysis of the protocol, that these dependencies can be reduced to that of virtual-channel flow control, and solved with current deadlock avoidance techniques.

Motivated by the need to evaluate a flit-reservation router which takes into account implementation details, I researched and proposed a delay model for pipelined routers. The model takes as input the clock cycle time, flow control method, and router parameters, and returns a suitable router pipeline. By defining canonical router micro-architectures tailored to each flow control method, and deriving technology-independent delay equations based on detailed gate-level design, the model facilitates accurate comparisons of different flow control methods. Application of the model to a virtual-channel router uncovers the use of speculation to further improve the performance of virtual-channel flow control. While previous router models claim virtual channels are expensive, our model showed that a speculative virtual-channel router can have the same 0-load latency as a wormhole router while extending its throughput significantly.

Application of the model to a flit-reservation router demonstrates that a flit-reservation router can fit within the same 3-stage pipeline as a wormhole and speculative virtual-channel router, thus attaining the same 0-load latency even when control flits cannot be launched ahead of time. Detailed Verilog simulations of a flit-reservation router showed it is able to attain the throughput that can only be achieved by a speculative virtual-channel router with approximately twice the number of buffers, due to its ability to immediately turn-around buffers.


Thesis

Li-Shiuan Peh, "Flow Control and Micro-Architectural Mechanisms for Extending the Performance of Interconnection Networks.", PhD Thesis, Stanford University, August 2001.


Publications

Li-Shiuan Peh and William J. Dally, "A Delay Model for Router Micro-architectures." In IEEE Micro Jan/Feb Special Issue for Hot Interconnects 8, 2001.

Li-Shiuan Peh and William J. Dally, "A Delay Model and Speculative Architecture for Pipelined Routers." , In Proceedings of the 7th International Symposium on High-Performance Computer Architecture, Jan. 22-24, 2001, Monterrey, Mexico, pp. 255-266. (Best Student Paper Award)

Li-Shiuan Peh and William J. Dally, "A Delay Model for Router Micro-Architectures.", In Proceedings of Hot Interconnects 8, Stanford, CA, August 2000.

Li-Shiuan Peh and William J. Dally, "Flit-Reservation Flow Control.", In Proceedings of the 6th International Symposium on High-Performance Computer Architecture, Toulouse, France, January 10-12, 2000. pp. 73-84.

 


Office: Gates 212
Address: Gates Building 2A, Room 212, Stanford University, CA94305
Phone: 1-650-725-8086
E-mail: lspeh@cva.stanford.edu


"Einstein's space is no closer to reality than Van Gogh's sky. The glory of science is not in a truth more absolute than the truth of Bach or Tolstoy, but in the act of creation itself. The scientist's discoveries impose his own order on chaos, as the composer or painter imposes his; an order that always refers to limited aspects of reality, and is based on the observer's frame of reference, which differs from period to period as a Rembrant nude differs from a nude by Manet." - Arthur Koestler, The Act of Creation, London, 1970, p. 253


Last edited: August 20, 2001