Andrew B. Kahng - US grants

Kahng The unifying theme of this research is that the underlying geometries, embedding dimensions and topological representations of CAD designs, together afford a perspective for effective algorithm design. The research is in three areas. 1. Performance-driven synthesis at various levels of design, including clustering for problem decomposition and fast hierarchical placement, and estimation of intrinsic resource requirements via topological criteria. 2. Assessment of design problem complexity based on the interaction between topology of neighborhood structures and scaling geometry in the associated cost surfaces. This includes time-bounded stochastic optimizations, and a non-monotone class of annealing methods. 3. Capturing the underlying physics of high-speed devices and interconnects while maintaining algorithmically tractable formulations. Examples are a unified routing tree optimization and the separation of the interconnect topology from subsequent geometric embedding.

9303148 Kleinrock This award provides support for the investigation of collective behavior of a collection of autonomous, communicating mobile robots (mobots). Ths study will be accomplished through the establishment of a laboratory to study distributed robotics involving researchers form computer science, electrical engineering, and mechanical engineering. The award also provides support for the acquisition of mobots and for the support of technical staff to maintain the laboratory. The main research topic pursued is distributed algorithms for collective behavior. The specific topics to be pursued are communication improvements and protocols for wireless communication between improvements and protocols for wireless communication between robots, distributed motion planning studies for the robots, and the application of maximum utility theory to the implementation of collective behavior.

Prediction and predictability of optimization heuristics are at the foundation of convergent, top-down system synthesis. Not knowing how a heuristic behaves on various types of relevant instances makes accurate modeling, and hence predictability, difficult. This project is exploring basic ideas that can lead to improved understanding of predictability of heuristic algorithm behavior within top-down physical design. The project first develops a new methodology and criteria for characterizing the operation of given (iterative, combinatorial) heuristic functions, and how the application context and use model define requirements for the design, implementation and evaluation of the heuristic. The project also explores principles for developing predictors of a given heuristic's output, based on understanding of the heuristic and its context. Finally, in the context of a multi-stage optimization ("design flow"), the project addresses means of abstracting objectives that can be effectively optimized from downstream parameters of the design state.

Proposal ID: 0429630
PI/coPI: Gabriel Robins (UVA), Andrew Kahng (UCSD), Aleksandr Zelikovskiy (GA state)
Title: Collaborative Research: New Directions for Advanced VLSI Manufacturability

Abstract:
As VLSI technology advances into ever shrinking design regimes and growing complexity, it is increasingly difficult to maintain adequate verification, process windows, and manufacturing yields. This project will investigate several newly critical issues at the interface between layout design and manufacturability, including automatic
layout flows for phase-shifting masks, area fill synthesis for yield improvement, gate-length biasing for leakage variability control, and principled methodologies for exploring restricted design rules. The Intellectual merit of our proposed research stems from its broad conceptualization of a future integrated design-to-manufacturing flow, coupled with its selective focus on several key design technology goals. This work will help alleviate some of the challenges that now threaten Moore's Law and the Semiconductor Technology Roadmap.

Proposal IDs: 0811832 & 0811866
PI names: Andrew Kahng & Puneet Gupta
Title: Collaborative Research: Research on Benchmarking and Robustness of VLSI Sizing Optimizations
Inst: UCSD & UCLA


ABSTRACT
The proposed research will investigate the ?sizing? optimizations that underlie all practical tradeoffs of integrated-circuit area, delay and power metrics. The intellectual merit of our proposed research stems from its broad and multi-pronged attack on a fundamental type of design optimization. The PIs will investigate core aspects of optimization including technology strategy based on fast estimation of achievable solution quality, benchmarking of optimization heuristics and strengthening of iterative optimization heuristics by use of stronger move ?operators?. The PIs will also address fundamental changes to the optimization context such as the potential need for statistical optimization in a regime of uncontrollable manufacturing variability and the need for incremental optimization under the regime of evolving process models.

The broader impact of the proposed research lies in helping chip designers and manufacturers reduce design turnaround time in addition to IC area, delay and power metrics. This will enable the design of more complex and functional products within a given cost and power envelope; as such, our proposed research will have very substantial research and commercial impact. Other impacts will include open-source tools that will establish a baseline and foundation for further work by other research groups, preventing the wasted effort of reinventing the wheel that is endemic to experimental research today.

One of the most critical challenges in todays nanoscale VLSI design is the lack of predictability in analysis and optimization. As VLSI technology continues scaling in the nanometer domain, VLSI systems are subject to increasingly significant parametric variations coming from not only the manufacturing process but also the system runtime environment. Increasingly significant parametric variations lead to increasingly significant variations in IC timing performance, power consumption, and other product metrics. Existing VLSI statistical analysis techniques cannot accurately and efficiently capture such variations; this greatly compromises design optimization and design convergence, affecting product quality and time-to market.

In this work the PIs plan to develop techniques for signal probability-based statistical timing analysis (SPSTA), which would achieve accurate performance estimates for different inputs, rather than input-oblivious pessimistic delay bounds. In this project, the PIs propose to build on the foundation of SPSTA to enable a new, predictive and less-pessimistic VLSI implementation methodology. Core techniques will span VLSI statistical analysis, delay test ATPG, and optimization techniques that exploit improved predictability. Specifically, there are three thrust areas in this project, and it is expected that that these techniques will outperform existing alternative techniques.

The outcome of this project is critical to the cost-effective continuation of semiconductor technology scaling (i.e., Moore's Law), and to maintaining growth of the semiconductor industry's economic engine in the coming years. The broader impacts of the proposed project can be further measured by a strong education program including curriculum development and research training which incorporate statistical VLSI analysis and optimization techniques into the computer engineering programs at the PIs? institutions, and into course infrastructure that is broadly and openly available to others online.

Following their established practices of well over a decade, the PIs will broadly disseminate their research results by publication, industry collaboration, and online posting of open-source software. This project will also allow the PIs to broaden participation of students from under-represented groups based on the minority institute status of UT San Antonio; it will help educational initiatives that are aimed at preparing the San Antonio regional economy to transform into a technology-oriented one.

Networks-on-chip (NoCs) are an on-chip interconnection fabric of choice for general-purpose chip multiprocessors and application-specific multiprocessor systems-on-chip. This project focuses on network-on-chip modeling and optimization to enable early-stage design exploration that fully elaborates the achievable envelope of NoC power, area, speed, reliability and cost. An architectural estimation thrust develops new architecture-level estimation methods that are portable to different router microarchitectures and that can accurately capture implementation effects. The thrust addresses the automatic generation of architectural estimation models, the modeling of chip design implementation flow choices and their impacts, and new trace-aware and workload-dependent estimations. An architectural optimization thrust develops new methodologies for trace-driven optimization of router configurations, packet routing and network topology, with consideration of runtime network resource contentions.

Successful completion of this project will help network-on-chip and multiprocessor system-on-chip designers reduce design effort while improving chip area, delay and power metrics. This will be enabling to the efficient design of more complex, higher-functionality integrated-circuit products within given cost and power limits. The research will also produce software tools to establish a foundation for further work by other research groups. Through research participation, both graduate and undergraduate students will be trained in this emerging aspect of system-on-chip design.

The objective of this research is to develop a state-of-the-art photonic chip-scale probing solution for integrated Si-photonics testing and to enable new multidisciplinary collaborative projects in nano-photonics and opto-electronics. The approach exploits a universal electronic-photonic probing station that integrates electrical, optical far-field, and optical near-field probes for electrical and optical interfacing to integrated circuits and to individual elements within such circuits, together with a full set of external optical and electronic instrumentation to provide an affordable, zero-capital-investment testing capability for Research and Development by academic, industry and government laboratories.

The intellectual merit of this versatile and user friendly Si-Photonics testing instrument includes basic research to identify new phenomena, inventing new photonic technology and creating new applications, as well as providing tremendous benefit to small businesses, various research institutions and government laboratories in their product development efforts. Moreover, it can serve as a testbed for development and reduction to practice of new approaches for efficiently probing and testing Si-photonic chips, gradually evolving to become industry standards.

The broader impact of the instrument spans multiple fields, including information systems, high speed electronics and photonics, and future computer science and engineering to create wealth for 21st century economy by advancing integration of nanoscale photonic, electronic and biomedical science and technology. It will provide service to industry in Southern California and play a significant role in the education and development of human resources in science and engineering at the graduate and undergraduate levels helping to train future engineers.

The dramatic improvements in electronic devices in the last 40 years have substantially drawn on Moore's law which predicts a steady increase in transistor density in semiconductor chips, with implied improvements in cost and power. But Moore's law is now slowing, while cost improvements now rely on very large production volumes to justify billion-dollar in investments in manufacturing infrastructure. Among alternative chip design methodologies, three-dimensional chip design currently shows significant momentum and promise for commercial products. Three-dimensional chips can be produced by vertical stacking of conventional two-dimensional chips and connecting them with through-silicon vias. Despite a number of unsolved technical problems, such three-dimensional chips reduce the form-factor and interconnect, while improving yield. This research explores heterogeneous 3D chip design seeking the flexibility to combine different types of two-dimensional chips (different types of memories, fast logic, low-power logic, FPGAs, analog circuits, micro- and nano-electromechanical components, etc.), which cannot be reliably manufactured on a single conventional die. This research will reduce cost of 3D designs and make them more practical by exploiting heterogeneity in all its aspects: (1) from dies fabricated in different process nodes to interconnects realized with TSVs, silicon interposers and wire bonds; (2) from system performance (macro blocks with different frequency requirements) to system activity (blocks that are standby-dominant vs. actively-switching); and (3) at the physical design level, from criticality (performance slack) to connectivity (bisection bandwidths or netcuts) across the physical hierarchy from block-level down to gate-level. Our research scope spans three main axes -- 3D IC implementation architectures, technology and design aspects of heterogeneity, and algorithmic optimizations.

Being able to combine heterogeneous semiconductor dies in a working electronic system promises significant competitive advantage in price, performance and functionality. Such ability facilitates new types of electronic products, with clear benefits to design and manufacturing companies, as well as to the society. An example application here is a cellular phone, which integrated several micro-processors, analog circuit components and antennas, signal-processing units, accelerometers etc. Being able to revise one of these blocks without altering the supply chain for other blocks reduces the risk and cost of improvements to successful designs. Students will be trained to contribute to the design and revision of such designs, and to perform further research on alternative chip design techniques.

Design tools and methods for electronic components need to ensure that they are low-cost, low-energy, last longer, deliver better performance, and operate correctly across a diverse range of conditions. To guarantee this, engineers need analysis tools that understand mechanical shock, temperature, aging and in addition to electrical phenomena - in short, many different "physics" that are all wrapped up into a single analysis question. The analysis must also span time scales from nanoseconds to years, and spatial scales from nanometers to centimeters. Such tools do not exist today. This project will develop the "multiphysics" analysis methods that aims to address such questions for future electronic system designers. Researchers will bring together techniques from chip design, thermal and reliability analysis, mechanical simulation and other domains learning each other?s fields of expertise, and creating new analysis tools that will be used in both industry and teaching contexts. The outreach aspects of the project involve training undergraduate and graduate students for the electronic design automation industry.

The project will have three main technical goals. The first goal is to come up with fast algorithms to simulate and predict the physics of heat propagation, mechanical stress, and electrical signaling in extremely complex structures. The second goal is to enable computer codes to span multiple scales in space and in time. This will allow system design tools to correctly analyze propagation of electrical signals through nanoscale devices as the larger system is subjected to heating or mechanical shocks occurring at much longer time scales. The third goal is to develop new ways of efficiently understanding "multiphysics", e.g., the interaction between electrical, thermal and mechanical, along with temporal phenomena, when analyzing an electronic system.

Improved optimizations of energy-efficiency, safety, robustness, and other criteria in engineered systems offer the promise of incalculable societal benefits. However, challenges of scale and complexity keep many real-world optimization needs beyond our reach. The mission of The National Artificial Intelligence (AI) Institute for Learning-enabled Optimization at Scale (TILOS) is to make impossible optimizations possible, at scale and in practice. The institute (a partnership of University of California, San Diego, Massachusetts Institute of Technology, National University, University of Pennsylvania, University of Texas at Austin and Yale University) will pioneer learning-enabled optimizations that transform chip design, robotics, communication networks, and other use domains that are vital to our nation’s health, prosperity and welfare. In TILOS, research, education, outreach and translation are holistically driven by what makes the nexus of AI/ML and optimization uniquely challenging at the leading edge of practice. Industry partners will interact closely with TILOS on both foundational research and its use-domain application. TILOS will build an openly accessible program of continuing education with long-term, lifelong learning and skills renewal as its central tenet. This institute will also broaden participation, building on the visible successes at its partner institutions that have reached underserved demographics from K-12 onward. Through these efforts, TILOS will discover, educate, and translate into real-world practice a new nexus of AI, optimization, and use.

TILOS is organized around multiple virtuous cycles that unify AI and optimization, use domains, and the translation of AI-optimization breakthroughs into practice. A first virtuous cycle of AI and optimization, where each enables and amplifies the other, is at the heart of TILOS. Foundational research will pursue five main pillars: (i) bridging discrete and continuous optimization; (ii) distributed, parallel, and federated optimization; (iii) optimization on manifolds; (iv) dynamic decisions under uncertainty; and (v) nonconvex optimization in deep learning. A second virtuous cycle of challenges, inspirations and data-enabled validations connects the foundational research in AI-optimization with use-domain expertise. The initial use-domain foci bring diverse optimization challenges but inspire shared solutions with commonalities such as physical embeddedness, hierarchical-system context, underlying graphical models, safety and robustness as first-class concerns, and the bridging of human-guided and autonomous systems. A third virtuous cycle is one of translation and ever-tighter connections to the leading edge of practice. TILOS will leverage industry partnerships to accelerate impact via open standards, data sets and “data virtual reality”, and open source that democratize access to research enablement. Roadmaps of optimization formulations and progress metrics will draw researchers together and toward shared research goals. A fourth virtuous cycle with industry and the institutional partners spans both workforce development and the broadening of participation. Workforce development will identify and teach the skills and mindsets needed at the nexus of learning, optimization and practice, so as to provide skills renewal for the existing workforce as well as onramps for underserved demographics such as veterans or those seeing a career change. Broadening of participation will be pursued via the institute’s partnerships with community organizations and middle and high school educators, via tiers of engagement that span exposure, experience and environment.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.