Research On Online Task Placement Algorithm For Heterogeneous Reconfigurable Architectures

Employing a finer task placement algorithm, reconfigurable computing system can place more tasks onto reconfigurable device at the same time, which can speed up the execution of tasks, make better utilization of the limited reconfigurable resource and improve the performance of system. With the development of reconfigurable device manufacture, the scale and kinds of resources provided by device increase, and the architecture of device becomes heterogeneous. The placement algorithms based on homogeneous model are not suit for the reconfigurable system which uses heterogeneous device, so they just can be applied in few situations. While hardware tasks are placed and removed dynamically, the available resources of device split into many scattered fragments, which makes against to the placement of subsequent tasks. Therefore, it is significant to research the online task placement algorithm and defragmentation algorithm based on heterogeneous architecture.After analyzing the architecture of main reconfigurable devices, this dissertation establishes heterogeneous models for reconfigurable device and hardware tasks, and proposes corresponding online task placement algorithm and defragmentation algorithm. In the end, a blue print of heterogeneous reconfigurable hardware task processing system (HRHTPS) which supports online defragmentation is proposed. Main work and contributions of this dissertation are outlined as follows:The models of reconfigurable device and hardware tasks with heterogeneous architecture are established, and a data structure is designed to describe the status of reconfigurable resource. Consequently, groundwork for researching task placement algorithm is established. After analyzing the interior structure of main reconfigurable devices and partial reconfigurable technology supplied, considering hardware task's different needs of resource, heterogeneous models of device and tasks are established. Using well-designed different numeric identifiers to describe the status of different resources, reconfigurable resource can be managed effectively.An online heterogeneous task placement algorithm named ARTC-PW is proposed. A concept of relative task coverage (RTC) is put forward. The algorithm establishes a placement window (PW) for task queue, and places the foremost task according to the RTC matrix generated by all tasks in PW. So the placement of subsequent tasks is taken into consideration in advance, whole efficiency of task placement increases accordingly. The experiments show the algorithm can gain less average waiting time for tasks and higher utilization ratio of device than those of First Fit algorithm.An online partial defragmentation algorithm named MPDC is proposed, which is based on task priority. The MPDC algorithm searches the least task relocation cost to execute partial defragmentation, assembles the resource fragments to be coherent area. Therefore the placement of task with high priority is expedited, and the work efficiency of system increases accordingly. Some new evaluating indicators are presented. Two static placement algorithms named DARTC and DDARTC is proposed for the tasks those needs to be relocated, which support the defragmentation effectively.A blue print of heterogeneous rconfigurable hardware task processing system (HRHTPS) is proposed, which supports defragmentation. Without an effectively scheduling algorithm, HRHTPS can support processing real-time task.