Research In Strategies Of Online Tasks Scheduling And Placement For Reconfigurable Computing

Reconfigurable computing system effectively integrated the advantages ofGeneral Purpose Processor (GPP) and Application Specific Integrated Circuit (ASIC).For its high flexibility, excellent computing performance and reconfiguration,reconfigurable computing is increasingly gaining the focus of all communities, whichmainly involves the research into reconfigurable computing hardware/softwareplatforms, reconfigurable operating systems, programming languages, compilingenvironment, the related algorithms and applications.In the found of thoroughly discussing and analyzing the characteristics ofreconfigurable hardware platforms and hardware tasks, the significance of taskscheduling and placement in reconfigurable computing system are elaborated.Hardware task scheduling, on the purpose of reducing the reconfiguration overheadfor FPGA and the overall execution time for tasks, is mainly dedicated to schedulingtask to the given reconfigurable regions, which generally restrained by the number ofreconfigurable resources and the timing between tasks. While, task placement aims toimprove the utilization of reconfigurable chips and advances the acceptance ratio ofhardware tasks, which usually more takes the management for reconfigurableresources into account. But its efficiency has direct bearing with the size of freespaces as well as the strategy for placing tasks.By scrutinizing the influence to the system performance, which is caused by thedependencies and communication between tasks, the heterogeneity of reconfigurableplatforms, plus the concurrency of hardware tasks, the task scheduling mechanism arediscussed and modeled. Further, a Finite State Machine(FSM) was introduced todescribe the transformation of task in reconfigurable system, and the Directed AcyclicGraph(DAG) was utilized to present the dependencies between tasks, and a clusteringstrategy-based scheduling algorithm(CSS) was proposed, which not only effectivelycontributed to the improvement of whole execution time for task and reconfigurationoverhead, but also gained a good balance between scheduling performance and timecomplexity. Additionally, researches and experiments indicate that the serialization ofhardware tasks will impact the performance of reconfigurable systems severiously,which should be well studied and settled in future.Then, based on analyzing the existing system model, task model and resource model, as well as their relating hypothesizes, the generally used task placementalgorithms are discussed, such as Horizon Placement, Stuffing, BestFit and FirstFit.Further, the related improving approaches for these algorithms are proposed, whichprovides a firm foundation for the implementation of future algorithms. With respectto the high defragments, and long task execution time of Horizon and Stuffingplacement, a length-height aware placement strategies was proposed, which cancontribute to lower overall task execution time and less defragments.Finally, based on the Xilinx Virtex-II Pro platform, under the support of severalsoftware tools provided by Xilinx, the partial dynamical reconfiguration for DES wasimplemented, and the results of it were verified.