Nested Loop Parallelization Using Polyhedral Optimization in High-Level Synthesis

Akihiro SUDA  Hideki TAKASE  Kazuyoshi TAKAGI  Naofumi TAKAGI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.12   pp.2498-2506
Publication Date: 2014/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.2498
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: High-Level Synthesis and System-Level Design
Keyword: 
high-level synthesis,  array partitioning,  buffer management,  Polyhedral Optimization,  

Full Text: PDF(1.2MB)
>>Buy this Article


Summary: 
We propose a synthesis method of nested loops into parallelized circuits by integrating the polyhedral optimization, which is a state-of-the-art technique in the field of software, into high-level synthesis. Our method constructs circuits equipped with multiple processing elements (PEs), using information generated by the polyhedral optimizing compiler. Since multiple PEs cannot concurrently access the off-chip RAM, a method for constructing on-chip buffers is also proposed. Our buffering method reduces the off-chip RAM access conflicts and further enables burst accesses and data reuses. In our experimental result, the buffered circuits generated by our method are 8.2 times on average and 26.5 times at maximum faster than the sequential non-buffered ones, when each of the parallelized circuits is configured with eight PEs.