部分可重构系统布局的一种新算法

针对动态部分可重构系统的瓶颈,即布局算法必须在保证运行速度的基础上,尽可能增加可重构芯片利用率的问题,提出了一种布局算法KVIT(keeping the vertexes information of tasks).其核心思想是尝试将新到达的硬件任务放置在已布局硬件任务的顶点处,并通过对可重构芯片内部计算单元进行编码迅速判断新任务是否可放置在该顶点.该算法的时间复杂度为O(N),N是可重构系统中当前运行的硬件任务的数目.仿真实验结果表明,KVIT算法的布局质量与现有的O(N2)时间复杂度布局算法基本一致,而其执行速度则明显高于已有算法.

A new methodology for placement on partial reconfigurable devices

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.