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开发的新优化算法将足够通用和复杂，可以解决科学、技术和商业应用中的其他复杂问题。学生将在现有的优化和VLSI CAD研究生课程中，以及通过本科生的研究，接触到我们工作的实际效用。除了HLS中传统的调度和绑定设计点外，在HLS过程中要同时作用的其他更后域的设计点包括布局规划、动态电压调整以及通过功能单元中的空闲时间聚类来形成有效的功率门控的功率岛。然而，深度混合最小二乘问题是一个极其复杂的离散优化问题，目前的方法如分枝切割法和模拟退火法都无法解决。为了能够有效和高效地实现深度HLS，将利用PI实验室设计的最新离散优化技术“离散化网络流”(DNF)。DNF通过迭代执行经典的最小成本网络流来求解DOPS，这是一种连续的快速求解器，并增加了流需要满足的一些离散化要求，以便获得DOPS的合法解。DNF方法是一个很好的选择，因为它具有时间效率，能够在一个统一的网络流结构中模拟多个设计点、多个约束和优化函数。通过同时考虑整个设计中的所有相关设计点，可以在多个约束满足的情况下对所选目标进行优化。然而，为了获得更好的效率和接近最优性，有必要对DNF进行扩充以解决像深度HLS这样的高度复杂的问题。因此，该项目将开发：a)在DNF方面需要显著的算法进步，以及b)各种复杂的深层HLS子问题的DNF图模型，这些模型然后可以被缝合在一起以形成完整的深层HLS表示。该项目的成功完成预计将推动最终的芯片设计在多个指标上达到更高的效率水平。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.