Research On Technology Of Place And Route Of Hardware Task In Reconfigurable System

In reconfigurable computing system, a better hardware task placement and route algorithm can place more tasks onto reconfigurable device at the same time and route tasks which need communicational connections, thus it can speed up the proceeding of reconfigurable computing system executes tasks, making higher utilization of reconfigurable device's logic resource. With the improvement of chip technics, the mushroom of kinds and scales of logic resource reconfigurable device FPGA provides enables its architecture become heterogeneous. However, task placement and route algorithms, which based on homogeneous device model, are not suitable for heterogeneous device structure; meanwhile tasks are added onto and deleted off reconfigurable device dynamically, consequently unoccupied resources in device are fragmented and the placement and route of other succedent tasks are influenced. Hence, it is of significance to research task placement and route algorithm and fragment quantifying method under heterogeneous reconfigurable device model.Based on the analysis of internal architecture of reconfigurable FPGA, heterogeneous reconfigurable device model and hardware task model, which have already existed, are improved, and this dissertation proposes an algorithm named DRS-TCW, which can place and route multi-kind tasks simultaneously. At last, a task placement disposal scheme which supports FCTD fragment concatenation quantifying method is proposed. Main work and contributions of this dissertation are outlined as follows:This dissertation improves heterogeneous device model and task model, and then numerical value matrix and adjacency matrix are utilized to describe device and tasks. Based on the deep analysis of FPGA architecture and DPR technology, heterogeneous device model and hardware task model are improved, and tasks are classified based on the communicational need between them. Using well-designed data structure, numerical value matrix and adjacency matrix are utilized to describe the status of resources and communications between tasks, and numerical management towards different resources and tasks is realized effectively. Consequently, groundwork for latter task placement and route research is established.An algorithm named DRS-TCW, which can place and route multi-kind tasks simultaneously is proposed. The needs of task placement and route are deeply analyzed, and tasks are classified into sub queues after setting task-classify window on task waiting queue. Planned as a whole, the needs of different tasks are balanced and different place strategies are adopted, and then connections between correlative tasks are routed by direction of routable search method. Experiment results show that the algorithm can gain higher resource utilization compared to FF algorithm, and of high route connectivity ratio.A fragment concatenation quantifying method named FCTD is proposed, which based on three-dimensional packing model also supports task placement. This method abstracts and quantifies fragments in three-dimension, and the quantifying results are used to support task placement. Experiments show that this method can reduce fragment production and improve resource utilization effectively. A task placement disposal scheme which supports FCTD fragment quantifying is proposed. Method FCTD is used during tasks'placement and tasks are quantified differently according to their types, consequently resource utilization of system is improved much more higher.