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

现代芯片或超大规模集成电路（VLSI）设计是一项极其复杂的技术工作，以至于它需要在7-8个阶段完成，从高级合成到逻辑合成，再到验证，再到放置和路由。每个阶段都使用复杂的计算机辅助设计（CAD）软件工具进行。芯片设计需要考虑许多指标，如功耗、芯片面积/成本、性能/速度、可靠性（例如，避免可能破坏芯片功能的温度热点）和芯片成品率（在制造可变性的情况下，芯片正确运行的百分比，可能会偏离速度等指标的规格）。通常，需要对其中一个指标（通常是功率或成本）进行优化，并满足其他指标的规格或约束。在当前的方法中，用于不同阶段的CAD工具在筒仓中工作，只考虑指标的一小部分，并且不知道后期阶段对这些指标的可能影响。这将导致在早期阶段关于某些指标的次优甚至错误的决策。这反过来又会导致最终的芯片设计明显不如它们所能达到的最佳效果，或者违反规范。后者需要重新设计，浪费了宝贵的技术工作时间。该项目的目标是通过在早期阶段之一的高级综合（HLS）中采取各种后期设计决策（可能近似）来纠正这些问题，以便：a)对几乎所有感兴趣的指标进行合理准确的估计，以获得更好的HLS决策，b)在同时考虑的多阶段/领域设计点的更丰富的空间中进行优化。这样的HLS阶段被称为“深HLS”。该项目的更广泛影响可能是开发数千种环保电子产品，这些产品使用使用深度HLS工具设计的功耗显着降低且质量更高的芯片。此外，为深度HLS开发的新优化算法将具有通用性和复杂性，足以解决科学、技术和商业应用中的其他复杂问题。学生将在现有的优化和VLSI CAD研究生课程以及本科生研究中接触到我们工作的实际应用。除了HLS中传统的调度和绑定设计点外，HLS过程中需要同时作用的其他设计点还包括布局规划、动态电压缩放以及通过功能单元的空闲时间聚类形成有效的功率岛以实现功率门控。然而，深度HLS是一个极其复杂的离散优化问题（DOP），超出了现有方法如分支-切割和模拟退火的范围。为了有效和高效地实现深度HLS， PI实验室将利用最近设计的离散优化技术“离散网络流”（DNF）。DNF通过迭代执行经典的最小成本网络流（NF）来求解DOPs，这是一个连续的、因此是快速的求解器，并增加了一些离散化要求，这些要求是流需要满足的，以便获得DOPs的合法解。DNF方法具有时间效率高、能够在统一的网络流结构中对多个设计点、多个约束和优化函数进行建模等优点，是一个很好的选择。通过在整个设计过程中同时考虑所有相关的设计点，可以在满足多个约束条件下对所选目标进行优化。然而，为了提高效率和接近最优性，有必要增强DNF来解决深度HLS等高度复杂的问题。因此，该项目将发展：a)需要DNF的重大算法进步，b)各种复杂深度HLS子问题的DNF图模型，然后可以将其拼接在一起形成完整的深度HLS表示。该项目的成功完成预计将推动最终芯片设计在多个指标上达到更高的效率水平。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.