Synthesis of Approximated Hardware Accelerators with Monte-Carlo Tree Search (AxMCTS)

近似计算（AxC）的中心思想是权衡计算精度，以显著减少运行应用程序所需的能量和/或执行时间和/或芯片面积。在过去的几年中，AxC已经获得了强烈的兴趣，并提出了解决设计层次结构的各个层次的方法。在数字元件的水平上，近似技术的研究已经产生了现成的近似算术电路库。当试图用这些近似的组件设计完整的硬件加速器时，我们面临着非常巨大的设计空间。这使得硬件加速器的自动合成在合成运行时和结果质量方面非常具有挑战性。我们的科学假设是，新的蒙特-卡罗树搜索（MCTS）技术将导致大大提高效率，探索巨大的设计空间，在近似硬件加速器综合。AxMCTS项目是原始的，除了在我们自己的初始工作MCTS既没有被应用到近似硬件合成，也没有硬件合成一般。然而，在过去的几年里，MCTS在其他领域取得了巨大的成功，最突出的是在玩游戏方面。通过将MCTS技术转移到AxC，我们的目标是创建合成方法和工具，这些方法和工具提供近似加速器，其精度比AxC更高。在比目前可能的运行时间短得多的时间内实现能量/性能权衡。关键研究问题是：（i）哪些MCTS原则和技术可以从MCTS非常成功的领域转移，以及我们必须在哪里开发新颖的AxC特定技术来创建近似硬件加速器合成的框架？(ii)什么是非常适合的方法和途径来提高搜索过程的效率和运行时间，例如通过控制搜索树的宽度，通过将搜索引导到搜索空间中最有希望的区域，以及通过并行化搜索。(iii)如何定量评估基于MCTS的近似硬件加速器综合的优点和局限性？在方法上，我们将研究成功的MCTS技术，创建一个基于MCTS的合成框架，并设计算法方法，以实现更有效的搜索。特别是，我们将应用深度神经网络来加速MCTS中的关键步骤。此外，我们将开发并行搜索技术，用于在高性能计算集群上执行。对于实验评估，我们将针对FPGA后端和标准单元库进行合成实验，实现将利用和扩展我们以前的开源框架CIRCA进行近似硬件合成。

The central idea of Approximate Computing (AxC) is to trade-off computational accuracy for a significant reduction in energy and/or execution time and/or chip area required to run an application. In the last years, AxC has strongly gained interest and approaches addressing various levels of the design hierarchy have been presented. At the level of digital components, the investigation of approximation techniques has already resulted in readily available libraries of approximated arithmetic circuits. When trying to design complete hardware accelerators out of such approximated components, we are faced with an extraordinarily huge design space. This makes an automated synthesis of hardware accelerators very challenging in terms of synthesis runtimes and quality of results. Our scientific hypothesis is that novel Monte-Carlo Tree Search (MCTS) techniques will lead to greatly improved efficiency for exploring the huge design space in approximate hardware accelerator synthesis. The AxMCTS project is original as-besides in our own initial work-MCTS has neither been applied to approximate hardware synthesis nor to hardware synthesis in general. However, in the last years MCTS has brought about great success in other domains, most prominently in playing games. By transferring MCTS techniques to AxC, we aim at creating synthesis methods and tools that deliver approximate accelerators with improved accuracy vs.~energy/performance trade-offs in much shorter runtime than possible today. The key research questions are: (i) Which MCTS principles and techniques can be transferred from domains where MCTS is highly successful, and where do we have to develop novel AxC-specific techniques to create a framework for approximate hardware accelerator synthesis? (ii) What are well-suited approaches and methods to improve the efficiency and runtime of the search process, for example by controlling the breadth of the search tree, by steering the search to the most promising regions of the search space, and by parallelizing the search. (iii) How to quantitatively evaluate the benefits and limitations of MCTS-based approximate hardware accelerator synthesis? Methodologically, we will study successful MCTS techniques, create an MCTS-based synthesis framework, and devise algorithmic methods for a more efficient search. In particular, we will apply deep neural networks for speeding up key steps in MCTS. Further, we will develop parallelized search techniques for execution on high-performance compute clusters. For the experimental evaluation we will conduct synthesis experiments targeting both FPGA backends and standard cell libraries, and the implementation will leverage and extend our previous open source framework CIRCA for approximate hardware synthesis.