High-Level Parallel Programming of Computation-Intensive Algorithms on Fine-Grained Architecture

Computation-intensive algorithms require a high level of parallelism and programmability, which make them good candidate for hardware acceleration using fine-grained processor arrays. Using Hardware Description Language (HDL), it is very difficult to design and manage fine-grained processing units and therefore High-Level Language (HLL) is a preferred alternative. This thesis analyzes HLL programming of fine-grained architecture in terms of achieved performance and resource consumption. In a case study, highly computation-intensive algorithms (interpolation kernels) are implemented on fine-grained architecture (FPGA) using a high-level language (Mitrion-C). Mitrion Virtual Processor (MVP) is extracted as an application-specific fine-grain processor array, and the Mitrion development environment translates high-level design to hardware description (HDL). Performance requirements, parallelism possibilities/limitations and resource requirement for parallelism vary from algorithm to algorithm as well as by hardware platform. By considering parallelism at different levels, we can adjust the parallelism according to available hardware resources and can achieve better adjustment of different tradeoffs like gates-performance and memory-performance tradeoffs. This thesis proposes different design approaches to adjust parallelism at different design levels. For interpolation kernels, different parallelism levels and design variants are proposed, which can be mixed to get a well-tuned application and resource specific design