Impact of interconnection networks in a massively parallel FPGA architecture on a parallel reduction algorithm

As the size, hardware complexity, and programming diversity of parallel systems continue to evolve, the range of alternatives for implementing a task on these systems grows. Choosing a parallel algorithm and implementation becomes an important decision, and the choice has a significant impact on the execution time of the application. This paper focuses on the implementation of a SIMD parallel reduction algorithm in a massively parallel architecture on FPGA. In fact, parallel reduction is a common and important data parallel primitive. The impact of the interconnection network topology on the number of data transfers required to perform the computations is studied. This paper introduces also two flexible and parametric communication networks, integrated in a SIMD SoC architecture, to manage both regular and irregular communications. The programmer can choose one or both networks when configuring his architecture in order to choose the most appropriate one for a given application. The performance of executing the reduction algorithm on the proposed architecture is finally evaluated. The goal of this work is to highlight some implementation decisions that influence the overall performance of a parallel algorithm. We conclude that the massively parallel interconnection network used has a great impact on the performance of a data parallel algorithm.