Graph-Theoretically Optimal Memory Banking For Stencil-Based Computing Kernels

Keywords

Chromatic Number; Graph coloring; Memory Banking

Abstract

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.

Publication Date

2-15-2018

Publication Title

FPGA 2018 - Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Volume

2018-February

Number of Pages

199-208

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/3174243.3174251

Socpus ID

85052762080 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85052762080

This document is currently not available here.

Share

COinS