SHF: EAGER: Deep High Level Synthesis Via Simultaneous Optimization across Multiple Domains of the VLSI CAD Flow

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Modern chip or Very Large Scale Integrated Circuit (VLSI) design is an enormously complex technical endeavor, so much so, that it is done in 7-8 stages ranging from high-level synthesis to logic synthesis to verification to placement and routing. Each stage is performed using sophisticated computer-aided design (CAD) software tools. Chip design entails considerations of many metrics like power consumption, chip-area/cost, performance/speed, reliability in terms of, say, avoiding temperature hot spots that can ruin chip functionality, and chip yield (percentage of chips correctly functioning in the presence of fabrication variability that can throw off specifications on metrics like speed). Generally, one of the metrics, typically power or cost, needs to be optimized, and specifications or constraints satisfied on the others. In current methodology, CAD tools for different stages work in silos, considering only a small subset of the metrics, and unaware of the possible effect of later stages on these metrics. This results in sub-optimal or even incorrect decisions in earlier stages with regard to some metrics. These in turn lead to final chip designs that are significantly less optimal than what they can be or that violate specifications. The latter requires redesign that wastes precious person hours of highly technical work. The goal of this project is to remedy these problems by taking various late-stage design decisions (possibly approximately) in one of the earliest stages, high-level synthesis (HLS), so that: a) there are reasonably accurate estimations of almost all metrics of interest for better HLS decisions, and b) there is optimization across a richer space of simultaneously considered multi-stage/domain design points. Such an HLS stage is called “deep HLS”. A broader impact of this project can be the development of many thousands of environmentally friendly electronic products that use significantly lower power-consuming and higher quality chips designed using deep HLS tools. Furthermore, the new optimization algorithms developed for deep HLS will be general and sophisticated enough to tackle other complex problems in science, technology and business applications. Students will be exposed to the practical utilities of our work in existing graduate courses on optimization and VLSI CAD, and via undergraduate research. Besides the traditional design points of scheduling and binding in HLS, other design points from later domains to be simultaneously acted on during HLS include floorplanning, dynamic voltage scaling, and effective power-island formation for power-gating via idle-time clustering in functional units. However, deep HLS is an extremely complex discrete optimization problem (DOP) that is beyond the reach of current approaches such as branch-and-cut and simulated annealing. To enable effective and efficient realization of deep HLS, a recent discrete optimization technique called "discretized network flow" (DNF) designed in the PI's lab will be leveraged. DNF solves DOPs by iteratively executing classical min-cost network flow (NF), a continuous and hence fast solver, augmented by some discretization requirements that the flow needs to satisfy in order to obtain legal solutions to DOPs. The DNF method is a good choice due to its time efficiency, and its ability to model several design points, multiple constraints and the optimization function in a unified network flow structure. It can thus optimize the chosen objective under multiple constraint satisfaction by considering all relevant design points simultaneously across the entire design. However, it will be necessary to augment DNF for solving a highly complex problem such as deep HLS for both better efficiency and near-optimality. This project will thus develop: a) needed significant algorithmic advances in DNF, and b) DNF graph models of various complex deep HLS sub-problems that can then be stitched together to form a full deep-HLS representation. A successful completion of this project is expected to push final chip designs to higher levels of efficacy in multiple metrics. 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.