Scheduling algorithms for coarse grain reconfigurable architectures

Coarse grain reconfigurable architecture is a promising platform. It is expected to fill the gap between microprocessors that are flexible but power inefficient and custom hardwired architectures that are efficient but non-programmable. However, it is also known to be a notoriously difficult platform to program because of its distributed resources and scarce communication resources.This dissertation presents scheduling algorithms that target architectures based on a coarse grain reconfigurable template.This first algorithm schedules a function of an application using a list scheduling algorithm modified to simultaneously place and schedule an operation and route its communications with other operations. Four ideas are presented that contribute to shortening the length of the generated schedule.An aggregate improvement over the baseline approach of up to 23 percent in schedule length was achieved when all four techniques were used. Additionally, it generated schedules that were up to 36.9 percent faster than those generated by an implementation of an approach based on Dominant Sequence Clustering.The second scheduling algorithm presented in this dissertation is an iterative modulo scheduling algorithm for coarse grain reconfigurable architectures. The algorithm is based on simulated annealing and repeatedly places and removes operations from processing elements until a feasible solution is found. It uses a compact three-dimensional graph that represents the target architecture to find a route that is free of resource conflicts for a communication edge. Also, a throughput constrained scheduling algorithm is presented.Experimental results showed that the proposed modulo scheduling algorithm finds a feasible solution faster than a previous approach when both approaches targeted architectures with similar interconnection networks.The last algorithm schedules streaming applications onto architectures with multiple independent coarse grain reconfigurable cores. The algorithm consists of two successive steps, the partitioning and scheduling steps, both of which are formulated as MILP problems. Its goal is to find a schedule of kernels in the application that minimizes the largest amount of buffers needed. Experimental results show large reduction in maximum buffer size when compared with past works, nearing 70 percent for some of the combinations of architecture configuration and application.In addition to the three scheduling algorithms mentioned above, this dissertation presents an architecture description language specific to the architectures targeted for this work.