Graduate Exam Abstract

Mugdha Puranik

M.S. Final

October 13, 2015, 3:30 pm - 5:00 pm

CSB 425

Optimal Design Space Explration for FPGA-based Accelerators: A Case Study on 1-D FDTD

Abstract: Hardware accelerators are optimized functional blocks designed to offload specific tasks from the CPU, speed up them up and reduce their dynamic power consumption. It is important to develop a methodology to efficiently implement critical algorithms on the hardware accelerator and do systematic design space exploration to identify optimal designs. In this thesis, we design, as a case study, a hardware accelerator for 1-D Finite Difference Time Domain (FDTD) algorithm, an important technique for modeling electromagnetic behavior that involves a large number of computations requiring huge data storage and several off-chip memory accesses. Memory limitations and bandwidth constraints result in long run times on large problems. Hence, an approach which increases the speed of the FDTD method and reduces bandwidth requirement is necessary. To achieve this, we design an FPGA based hardware accelerator that efficiently implements the FDTD method. We implement the accelerator based on time-space tiling. In our design, p processing elements (PEs) execute p parallelogram shaped tiles in parallel, which constitutes one tile pass. Our design uses a small amount of redundant computation to enable all PEs to start “nearly” concurrently, thereby fully exploiting the available parallelism. A further optimization allows us to reduce the main memory data transfers of this design by a factor of two, yielding a PE that delivers a throughput of one “iteration (i.e., two results) per cycle”. These optimizations are integrated in hardware, and implemented in Verilog in Altera’s Quartus II. To explore the feasible design space systematically, we formulate an optimization problem with the objective of minimizing the total execution time for given resource constraints. The results of the optimization problem for different problem sizes reveal that the optimal design may not always match the common sense intuition.

Adviser: Sanjay Rajopadhye
Co-Adviser: N/A
Non-ECE Member: Yashwant Malaiya, Computer Science
Member 3: Sudeep Pasricha, ECE
Addional Members: N/A


Program of Study: