Fine grain algorithm parallelization on a hybrid control-flow and dataflow processor

The execution time of a high-performance computing algorithm is influenced by various factors, including the algorithm's scalability, the selected hardware for processing elements, and the communication speed between these elements. This study utilizes a hybrid architecture that integrates both control-flow and dataflow hardware. Specifically, the control-flow hardware encompasses both multicore and manycore architectures. Guidance for dataflow programmers is provided to enable them to anticipate the level of acceleration achievable with a hybrid control-flow and dataflow architecture before developing dataflow hardware algorithms. Furthermore, the methodology developed is introduced, offering a structured approach for programmers to decompose algorithms and optimize each segment by leveraging the most suitable architectural type. The prerequisite for a programmer is not to know hardware description languages, but he must be well-versed in estimating the complexity of an algorithm. This study represents the culmination of over a decade of expertise in hybrid control-flow and dataflow architectures. It provides a detailed methodology for decomposing a control-flow algorithm into segments optimized for dataflow architectures and those better suited to control-flow architectures. The Lattice-Boltzmann method is employed as a representative example, implemented on both control-flow and dataflow hardware. The estimated total acceleration factor of the decomposed Lattice-Boltzmann method on the hybrid architecture, relative to execution times using control-flow and dataflow hardware, is approximately two for a given matrix dimension. The findings underscore the advantages of employing a hybrid architecture, demonstrating significant acceleration potential even for algorithms traditionally optimized for dataflow architectures. The primary benefit of the hybrid architecture lies in its capacity to accelerate algorithms where only specific portions are suitable for dataflow hardware.