Algorithms acceleration by a reconfigurable computing platform of FPGA

Process technology's continual shrinking trend following Moore's Law will enable Field Programmable Gate Array (FPGA) to pack billions of smaller and faster transistors on the same chip by the end of this decade. Enormous capacity of this FPGA chip increases parallel processing power for algorithms. But that alone is not enough for performance boost of algorithms. We need innovative on-chip application configuration architecture design and efficient algorithms to transform the application originally meant for microprocessor for alternative hardware implementation.; Bringing data from external memory to the hardware accelerator through bandwidth limited bus limits the acceleration power of the hardware itself. In this dissertation we analyze the cache memory requirements of many data intensive streaming applications. Accordingly we design on-chip memory architecture and memory interface with larger external off-chip memory depending on input data rate and required throughput of output data.; The first contribution of this dissertation is an application configuration architecture called Memory-Aware Run-Time Reconfigurable Embedded System (MARTRES) for modern FPGAs like Xilinx's Virtex-4 and Virtex-5 devices to provide balanced amount of logic, memory blocks and interconnect bandwidth. The goal of the configuration architecture is to provide flexibility, performance improvement and increased resource utilization in the era of applications convergence on small battery powered mobile handsets.; The second contribution of this dissertation is an online task placement algorithm based on bin packing for mapping a dynamic task list onto MARTRES configuration architecture, called Hierarchical Best Fit Ascending (HBFA) algorithm, which is more efficient than Best Fit (BF) algorithm. The time complexity of the proposed online placement algorithm, HBFA, is reduced to O(n) compared to BF algorithm's time complexity of O(n2), when the quality of the placement solution by HBFA is better than that of BF algorithm.; The third contribution of this dissertation is a novel partitioning and scheduling algorithm for MARTRES configuration architecture, whose goal is to optimize hardware resource usage and execution time of streaming applications. We reduce the execution time of applications by exploiting the temporal parallelism in streaming applications to reduce the reconfiguration cost of the hardware.