VLSI Routing and Estimation Intern

Peter Yoon, Trinity College

Usage Details

As part of the Blue Waters Undergraduate internship Program, the undergraduate intern will work with the mentor to design and implement a parallel algorithm for Group Steiner Problem (GSP) on the Blue Waters system. The student will then use the procedure in the global routing phase of VLSI chip design, where an optimal routing and wiring estimation of transistors (typically in the order of billions) is desired. The global routing phase of modern VLSI design can be modeled by the GSP: Given an undirected weighted graph and a set of disjoint groups of nodes, find a minimum-cost tree which contains at least one node from each group. The solution to the GSP can lead to an optimal routing and wiring estimation of transistors during the global routing phase. However, typical modern high-performance chips contain billions of transistors, each with multi-port terminals, making the whole procedure computationally challenging. This research is focused on developing an efficient parallel algorithm, amenable to parallel architectures such as the Blue Waters system. The undergraduate intern will help develop and implement an approximation algorithm for the GSP on the Blue Waters. The student will also conduct a comparative analysis with other global routing algorithms. In addition to working with the mentor, the intern will collaborate with a faculty member of engineering department to verify the effectiveness of the developed parallel procedure in the VLSI chip design.