Task Scheduling And Floorplanning Algorithm In Dynamically Reconfigurable Systems

Field-Programmable Gate Array(FPGA)is a type of programmable integrated cir-cuit with the feature of reconfiguration,which can efficiently implement circuit design and flexibly change the architecture of circuit.Dynamically reconfigurable system is based on the character of dynamic reconfiguration in FPGA,which can accommodate different computing requirements under the resource constraints.Thus,it is the effec-tive solution for hardware acceleration.Using dynamically reconfigurable design,all tasks in a large scale computing ap-plication can dynamically reuse reconfiguration resource with time multiplexing.Un-fortunately,the reconfiguration ordering and location of tasks will influence the running time of the system,the usage efficiency of resource and the communication overhead.So effective scheduling and floorplanning is anticipated.For existing FPGA architec-ture,the problem of partitioning,scheduling and floorplanning,which is coupling each other in dynamically reconfigurable system,is studied in this dissertation.Therefore the problem model for scheduling and floorplanning is formulated and then a corresponding optimization algorithm is proposed.In order to represent the task scheduling and floorplanning in dynamically recon-figurable system,the sequence triple(ST)is proposed,which is composed of three task nested sequences PS,MS,RS that integrating temporal and spatial partitioning simulta-neously.(PS,MS)is a hybrid nesting sequence pair(HNSP)to represent the floorplan of tasks in all reconfiguration regions at every scheduling time.And position coordi-nates of tasks can be calculated by solving longest common sequence in HNSP.RS is a reconfiguration sequence to represent the configuration ordering of tasks in all reconfig-uration regions.Combining the reconfiguration sequence with data dependencies,the reconfigurable constraints graph(RCG)is constructed,which can depict precedence constraints during dynamic reconfiguration process.And the start time of task config-uration and execution can be calculated by solving longest path to vertex in RCG.The task scheduling and floorplanning must satisfy the resource constraints in hardware and data dependencies among tasks during the reconfiguration process.To determine the complete feasible solution space of ST,a sufficient and necessary condition is provided to ensure the feasibility of task scheduling and floorplanning.The optimization algorithm in this dissertation is elaborated with a simulated an-nealing based search engine,which can optimize scheduling and floorplanning simul-taneously.According to the feature of ST,a perturbation method named insertion after remove is used,where a randomly chosen task is removed from the sequence triple and then inserted back into a proper position.Different inserting positions correspond to dif-ferent solutions of scheduling and floorplanning.Through enumerating and evaluating feasible insertion positions,many bad solutions are skipped.For accelerating the per-turbation process,an incremental method is proposed,which can evaluate all inserting positions in linear time complexity.The experimental results demonstrate the efficiency and effectiveness of the pro-posed algorithm.The results show that the proposed algorithm can optimize scheduling and floorplanning simultaneously,which can ensure well scheduling results and im-prove the success rate of floorplanning.And for the low task parallelism application in the experiment,the proposed algorithm can obviously decrease the reconfiguration latency in dynamic reconfiguration process.Compared with the results without opti-mizing communication overhead,the proposed algorithm can achieve the optimization of communication overhead and the solve time will increase,accordingly.Using the proposed algorithm,the consequence of communication overhead will be better with the increasing of dependencies between tasks.