Offset Pipelining for Coarse Grain Reconfigurable Arrays

Thesis (Ph.D.)--University of Washington, 2017-06This dissertation presents an execution model and compilation algorithms to advance the utility of coarse-grained reconfigurable arrays (CGRAs). These time multiplexed, spatial architectures can provide improved energy efficiency and performance compared to FPGAs or commodity processor systems. Conventional CGRAs are generally modulo scheduled for efficiently pipelining computationally intensive code. However, as the control complexity of an application increases, the performance of modulo scheduled CGRAs is diminished. An application composed of a series of phases and complex control flow may yield poor device utilization and limited performance on conventional CGRAs. In this work, I present Offset Pipelining, a new execution model, along with supporting Offset Pipelined Scheduling and EveryTime routing algorithms for improved application mapping to CGRAs. Offset Pipelining provides a mechanism to support different phases of application execution. The approach increases the flexibility of CGRAs by supporting independent initiation intervals for the different phases and interleaving loop iterations across the device, similar to modulo scheduling. This allows portions of an application to be optimized in isolation and also maximize resource sharing on the device. It is particularly effective in cases where an application requires infrequent setup or teardown steps around a shorter inner loop that executes for many iterations. I also introduce pipelined program counter CGRAs in order to support the proposed execution style. The new algorithms presented perform the scheduling and routing for an Offset Pipelined CGRA. The Offset Pipelining Scheduling algorithm creates a schedule in the Offset Pipelining style. It takes an iterative approach to adjusting the schedule, balancing the needs of each phase by positioning operations and issue slots to maximize performance. The proposed EveryTime router manages new complexity resulting from the Offset Pipelining execution model. This includes signals with run time dependent paths and variable flight time. The Offset Pipelined Scheduling and EveryTime routing algorithms are joined by a more conventional simulated annealing placement phase to form a prototype tool chain to demonstrate the feasibility of Offset Pipelining for CGRAs. These components provide improvements to the utility of CGRAs compared to existing techniques. The Offset Pipelining execution model increases the flexibility of CGRAs on a practical hardware architecture. It offers better performance by allowing each phase to execute independently rather than fused into a single monolithic schedule for the entire application. This work hopefully advances the development of CGRA architectures and tools