Partition And Schedule Algorithms For Dynamic Partial Reconfiguration On FPGA

FPGA technology provides the flexibility of an on-site programming andre-programming without going through re-fabrication with a modified design.Dynamic Partial Reconfiguration (DPR) designs based on FPGA takes this flexibilityone step further, which could reuse the same hardware for different tasks at differentphases during the execution of an application. Though DPR can improve the resourceutilization, there are still some critical bottlenecks which are the configurationoverhead caused by the online-reconfiguration and the static power consumptioncaused by the leakage power from LUTs, interconnections, SRAM cells and so on.Partial Reconfiguration Modules (PR Modules) and partition them into groups sothat the hardware modules can be swapped in and out during the run time. The designof PR Modules also impacts reconfiguration latency and resource utilization greatly.In this thesis, we formulate the PR Module generation problem into a standardMaximum-Weight Independent Set Problem so that the original manual explorationcan be solved optimally and automatically.To overcome the performance degradation of DPR, configuration prefetchingtechnique could be used by parallelizing the reconfiguration periods with theexecution of other tasks. However, the prefetching scheme should be constrained bythe data dependency relations between tasks, which makes the design of theprefetching schedule quite complicated. Thus, in this thesis, we formulate theoptimization of configuration scheduling with module-based data dependency graph,and proposed a shortest critical path finding algorithm so that the reconfigurationoverhead could be minimized efficiently. Our experiments show that our algorithmperforms significantly better than the state-of-art prefetching algorithms with areduction of the execution time of PR regions. Compared with the enumerationmethod which should provide the optimal solutions, our approach could obtainsimilar results with significant speed-up.Some techniques could save dynamic power consumption, such as clock gatingwhich selectively turn on/off specific branches of the on-chip clock distributionnetwork could be used to reduce clock distribution power, clock scaling which scaledown clock frequency when high performance was not necessary could be used to reduce the runtime power consumption. For DPR systems, it could take this runtimepower consumption saving further through saving the runtime static power.Considering lack of power model for DPR, we proposed a power model with feasibleexperiment method for DPR power consumption. In this thesis, we formulate theruntime energy consumption reduction problem as a hardware tasks schedule problem,and propose an power-aware schedule algorithm to optimize the power and theperformance. In our experiments, we develop a real experiments flow to show theefficiency and optimization of our approach.