A new methodology for placement on partial reconfigurable devices
Ligang Wang · 2007
The fact that placement algorithm has to obtain high total chip utilization and low time complexity simultaneously constitutes a bottleneck in partially reconfigurable systems.A KVIT(keeping the vertexes information of tasks) algorithm with time complexity O(N) is thus presented,where N is the number of hardware tasks currently running on the chip.The main idea is to put newly arrived tasks on the vertexes of the already running tasks,and then quickly validate this placement using an encoding scheme of the reconfigurable hardware.Simulation results show that the KVIT algorithm is obviously more efficient,while providing almost the same task rejection ratio compared with the other O(N2) algorithms.