Dynamic Reconfigurable Hardware Acceleration Technology Based On Runtime Computation Pattern

Dynamic Reconfigurable Computing based hardware acceleration exploited the a-bility from Field Programmable Gate Array (FPGA) chips of performing computationin hardware logic to gain processing speed boost. In reconfigurable computing, com-putations of original application are partitioned onto generic CPU and reconfigurablehardware in an optimized pattern to achieve the best overall performance gain.Existing approaches are almost based on statistical source code analyze, locatinghot-spot of application software, optimizing the partition solution, and patching and re-compile to generate corresponding executable codes that deploy into either generic pro-cessor or reconfigurable hardware. However, this procedure involves too many human in-tervention, thus rendering the design procedure of low efciency. Without the knowledgeabout dynamic behavior, previous approaches sufers from broken integrity of computa-tion logic and heavy overhead that originated from control and data dependency.Targeting these problems, this thesis focuses on automatical HW/SW partitioningfor reconfigurable computing. With dynamic analysis on runtime characteristics of targetapplication, HW/SW partitioning is performed and optimized in realtime. HW/SW par-titioning in this thesis used unified model to balance the resource cost and performancegain. Contributions inside this thesis can be summarised as:(1) Runtime Basic Block (RBBL) model is proposed to analyze the dynamic behav-ior patterns of target application program. This model enables high efciency recordingand analyzing of the runtime control flow and data dependency. The result program mes-sages can be used as a guide to automatical software-hardware partition.(2) Based on description from RBBL model, a partitioning and scheduling algorith-m is proposed to select the best set of computation patterns to convert into the hardwarelogic. A computation pattern is defined in this paper as a set of operations connectedlogically, which consists of consistent or inconsistent sequences of operations and com-mitted to certain calculation task. A typical computation pattern can be exemplified bylast few steps of recursive calculation. Since operations inside one computation patternare logically connected, the control and data dependency between computation patternscan be optimized more easily when partitioning into hardware.(3) Based on the analyzing model and the automatic partitioning algorithm, a Su- per Massive Parallel Processing (SMPP) hardware based SAT accelerator is proposed tospeed up the solving procedure. Runtime characteristics and computation patterns arediscovered by automatic analyzing tool set. Computation patterns of SAT solver are im-plemented by hardware in a specially designed parallel processing scheme. Experimentalresults show the high efciency of proposed approach when tackling complex SAT prob-lems.