Visit ShanghaiTech University | 中文 | How to find us
HOME > News and Events > Events
Towards Scalable Spectral Sparsification of Graph Laplacians and Integrated Circuits
Date: 2016/9/8             Browse: 595

Towards Scalable Spectral Sparsification of Graph Laplacians and Integrated Circuits

Speaker: Zhuo Feng

Time: Sept. 8, 10:00am - 11:00am.

Location: Room 410, Teaching Center


Present-day nanoscale integrated circuits (ICs) are integrating billions of transistors into a single chip, while even key subsystems, such as clock distribution networks, power delivery networks (PDNs), embedded memory arrays, as well as analog and mixed-signal systems, may reach an unprecedented complexity of hundreds of millions of circuit components. As a result, it becomes extremely difficult and even intractable to model, simulate, optimize and verify future nanoscale ICs at large scale with existing design methodologies. On the other hand, emerging spectral graph sparsification techniques allow to construct ultra-sparse subgraphs (a.k.a. graph sparsifiers) that can well approximate the spectra of the original graph, leading to the development of much faster numerical and graph-based algorithms. For instances, spectrally sparsified transportation networks allow to develop much faster navigation (routing) algorithms in large transportation systems, spectrally sparsified social networks allow to more efficiently understand and predict information propagation phenomenon in large social networks, spectrally sparsified circuit networks allow to more efficiently simulate, optimize and verify large circuit systems, etc. 


In this talk, I will first describe our recent spectral perturbation based approach for scalable spectral sparsification of large graphs and integrated circuits, and its role in designing nearly-linear time numerical algorithms for solving large symmetric, diagonally dominant (SDD) matrices, as well as scalable design automation algorithms that are critical for designing future nanoscale microprocessors, 3D-ICs, analog/mixed-signal circuits, as well as RF and microwave ICs. In the last, I will discuss how to leverage graph sparsification techniques for optimally solving large sparse matrices on emerging heterogeneous parallel CPU-GPU computing platforms.  


Dr. Zhuo Feng received the Ph.D. degree in Computer Engineering from Texas A&M University, College Station, TX in 2009. He is currently an associate professor in the Department of Electrical and Computer Engineering of Michigan Technological University. His current research interests include VLSI design and computer-aided design (CAD), heterogeneous parallel computing as well as graph-theoretic algorithms for solving sparse matrices. He received a Faculty Early Career Development (CAREER) Award from the National Science Foundation (NSF) in 2014, a Best Paper Award from ACM/IEEE Design Automation Conference (DAC) in 2013, and two Best Paper Award Nominations from IEEE/ACM International Conference on Computer-Aided Design (ICCAD) in 2006 and 2008. He is the principle investigator of the CUDA Research Center at Michigan Technological University named by Nvidia Corporation. He has served on the technical program committees of major international conferences in the areas of electronic design automation (EDA) and VLSI design, including DAC, ICCAD, ASP-DAC, ISQED, etc. He has been a technical reviewer for many leading IEEE/ACM journals as well as a panelist for NSF and DoE proposals.  


SIST-Seminar 16066