A novel online hardware task scheduling and placement algorithm for 3D partially reconfigurable FPGAs

Abstract

The recent emergence of 3D partially reconfigurable FPGAs implies that we need efficient online hardware task scheduling and placement algorithms for such architectures. However, the algorithms available in the literature for 3D FPGAs create a blocking-effect. That is, these algorithms tend to make a wrong decision in finding a location of each arriving hardware task during runtime scheduling and placement on 3D partially reconfigurable FPGAs. This leads to currently scheduled tasks blocking future hardware tasks from being scheduled and satisfying their deadlines. We need to solve this problem to maximize the performance of partially reconfigurable runtime systems implemented using 3D chip technology. We propose a novel placement and scheduling algorithm with a blocking-aware heuristic to make better decisions at runtime. Based on evaluation using both synthetic and real workloads, our algorithm reduces deadline miss rate by 61% with 15% longer runtime overhead compared to state-of-the-art algorithms. © 2011 IEEE.