Graph-Theoretically Optimal Memory Banking for Stencil-Based Computing Kernels
Graph-Theoretically Optimal Memory Banking for Stencil-Based Computing Kernels
复制标题
基于模板的计算内核的图论最优内存银行
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mingjie Lin
中科院分区：
文献类型：
--
作者：
Juan Escobedo;Mingjie Lin
高级合成（HLS）在将高级“软»»»程序编译成有效的寄存器 - 转移级别（RTL）”中已有明显的进步。为了有效地优化合成的内存子系统的访问性能，就开发和实施自动化的内存优化技术进行了广泛的研究，其中存储器银行是一种关键技术，但仍有几个关键问题。回答：给定一个基于模具的计算内核，什么构成了最佳的内存银行方案，可以最大程度地减少无冲突访问所需的内存库数？最后，在本文中，任何基于模板的内核都有最佳的银行计划吗？计算任何给定模具的最小内存分区因子，但还利用着色整个内存访问冲突图的重复性，从而大大提高了硬件效率。
High-Level Synthesis (HLS) has advanced significantly in compiling high-level "soft»» programs into efficient register-transfer level (RTL) "hard»» specifications. However, manually rewriting C-like code is still often required in order to effectively optimize the access performance of synthesized memory subsystems. As such, extensive research has been performed on developing and implementing automated memory optimization techniques, among which memory banking has been a key technique for access performance improvement. However, several key questions remain to be answered: given a stencil-based computing kernel, what constitutes an optimal memory banking scheme that minimizes the number of memory banks required for conflict-free accesses? Furthermore, if such an optimal memory banking scheme exists, how can an FPGA designer automatically determine it? Finally, does any stencil-based kernel have the optimal banking scheme? In this paper we attempt to optimally solve memory banking problem for synthesizing stencil-based computing kernels with well-known theorems in graph theory. Our graph-based methodology not only computes the minimum memory partition factor for any given stencil, but also exploits the repeatability of coloring entire memory access conflict graph, which significantly improves hardware efficiency.