The International Conference for High Performance Computing, Networking, Storage and Analysis
A Synthesis Approach for Mapping Irregular Applications on Reconfigurable Architectures.
Authors: Vito Giovanni Castellana (Pacific Northwest National Laboratory), Antonino Tumeo (Pacific Northwest National Laboratory), Fabrizio Ferrandi (Politecnico di Milano)
Abstract: Emerging applications such as bioinformatics and knowledge discovery algorithms are irregular. They generate unpredictable memory accesses and are mostly memory bandwidth bound. Several efforts are looking at accelerating these applications on hybrid architectures, which integrate general purpose processors with reconfigurable devices. Some solutions include custom-hand tuned accelerators on the reconfigurable logic. Hand crafted accelerators provide great performance benefits, but their development time often discourages their adoption. We propose a novel High Level Synthesis approach, for the automatic generation of adaptive custom accelerators, able to manage multiple execution flows. Our approach supports multiple, multi-ported and distributed memories, and atomic operations. It features a memory interface controller, which maps unpredictable memory access requests to the corresponding memory ports, while managing concurrency. We present a case study on a typical irregular kernel, the Graph Breadth First search, evaluating performance tradeoffs when varying the number of memories and the number of concurrent flows.