Research On Reconfigurable Computing Technologies

Reconfigurable computing technology combines the advantages of GeneralPurpose Processor and Application Specific Integrated Circuit. It has become a hot topicin research because reconfigurable computing system can provide the hardwiredfunctional efficiency and software programmability at the same time. Reconfigurablesystems are suitable for computation-intensive tasks, but due to diversity of applications,it is very important to design an optimal architecture for some dedicated applications.On the other hand, the development of EDA tools for reconfigurable systems is still ahurdle on the road to success. So far the existing programming models forreconfigurable systems are too complicated and the automation level of developmenttools is too low. It is very important to research automatic task partitioning, algorithmmapping and design optimization techniques for reconfigurable systems.In this paper, we studied five techniques of reconfigurable systems, including taskpartitioning, algorithm mapping, configuration space exploration, architecture design,and reconfigurable system application. The main research work and conclusions are asfollows:(1) In order to improve the execution efficiency of dynamically reconfigurablesystem, a temporal task partitioning algorithm was proposed. The task data flow graphwas partitioned into several sub-modules under hardware resource constraint. The delaycost of sub-modules and the communication cost among sub-modules were abstractedinto one general cost by different weights. Trade-off between delay and communicationoptimization can be made by this general cost. A ready list was also built to avoiddeadlock among sub-modules. Experiment results showed a better performance thanother partitioning algorithms and the time complexity of this algorithm is o(|V|~2+|V||E|)(|V|and |E| are the numbers of vertices and edges in DFG, respectively).(2) A task mapping algorithm based on simulated annealing for coarse-grainedreconfigurable architecture was proposed. In order to make algorithm mapping methodindependent on any concrete reconfigurable architecture, we firstly defined PRAM-aparameterized reconfigurable architecture model, which has powerful flexibility and candescribe different 2-dimensional reconfigurable mesh architectures to facilitateapplication mapping. PRAM not only can describe the system architecture, but also candescribe the architecture's hierarchy. Based on this model, a task mapping algorithm forcoarse-grained reconfigurable system was designed. This algorithm takes DFG andsystem model as its input, and produces an initial placement. Then it employs simulatedannealing to generate a better placed and routed mapping result.(3) A configuration space exploration algorithm was proposed to reduce the time oftask switch and reconfiguration on partially reconfigurable systems. By partitioning theapplication into grouped tasks, a task execution model and a cost evaluation function forpartially reconfigurable systems were introduced. Based on the similarity of two configurations, the reconfiguration cost between two tasks was determined. Accordingto the reconfiguration cost, dynamic programming methodology was applied to explorean optimal configuration sequence for a seres of tasks. The time complexity of theexploration algorithm is O(nm2), where n is the number of tasks and m is the number ofconfigurations of each task. Results showed that reasonable selection of configurationsfor a task sequence can effectively improve the performance of partially reconfigurablesystems.(4) The architecture of reconfigurable system was studied, and we designed aprototype system-Asynchronous Reconfigurable Cryptographic Engine (ARCEN).Different from synchronous systems, it routes signals asynchronously between adjacentcells through Neighbor-to-Neighbor wires with 4-phase handshaking protocol. We alsodesigned and implemented a simulator called JRSim for mesh-based reconfigurablearchitectures. The purpose of this simulator is to provide a platform to evaluate newarchitectures, and to assist in analysis of algorithms as well as the visualization of theirbehavior. JRSim is a platform-independent tool which is implemented by Java. Itsupports flexible bus structure, user-defined function unit and dynamic reconfiguration.(5) To evaluate the performance of reconfigurable system in high performancecomputing applications, we also carried out some case studies which include: ECCmodular multiplication algorithm implementation based on ARCEN platform; matricesmultiplication algorithm implementation based on JRSim simulator; and FPGA basedfast implementation of RS steganalytic algorithm. All these work covered theapplication research of application-specific system (ARCEN), coarse-grained system(JRSim) and fine-grained general purpose system (FPGA). The implementation resultsshowed that the solutions based on reconfigurable hardware have a far betterperformance than software.