DEVELOPMENT OF AN EFFICIENT TASK SCHEDULING ALGORITHM FOR RECONFIGURNBLE COMPUTING SYSTEMS

Abstract

Reconfigurable Computing (RC) is an emerging paradigm of research that offers cost-effective solutions for computationally intensive applications through hard-ware reuse. To fulfill the gap between Application Specific Integrated Circuit (ASIC) and Application Specific Instruction Processor (ASIP) reconfigurable com-puting has been introduced. In reconfigurable computing environment one can have performance like ASIC while having general-purpose processor flexibility. There is a growing demand in this domain for techniques exploiting inherent par-allelism in the target application and scheduling the parallelized application. There arises the need for scheduling and mapping of the tasks on to hardware resources. The Reconfigurable Logic Units (RLUs) i.e., hardware resources represent recon-figurable hardware modules on a reconfigurable System-on-Chip (rSoC). In this thesis, the problem of scheduling and mapping of the tasks onto the several RLUs for a given application task graph is considered, where the RLUs vary in terms of chip area (henceforth referred as variable area RLUs) and each task can have multiple versions of implementations (configuration bit streams) having corresponding execution time. An efficient scheduling algorithm dealing with the above mentioned problem is developed using dynamic programming approach, with the objective of minimizing the total execution time. The algorithm takes into account the reconfiguration delay when assigning task to the RLU in addition to the task execution time. On the similar lines, another algorithm using the Greedy Heuristic approach is developed for performance comparison. The comparison studies are carried out, which show that our algorithm always performs better. The algorithm is implemented using SystemC environment to support hardware as well as software co-simulation. The development of algorithms is done keeping in view the Virtex II Pro XUP FPGA development kit standards.