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

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

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.