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

摘要

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