一种面向部分可重构结构的配置空间搜索方法

Configuration exploration algorithm for partially reconfigurable architecture

研究了配置序列对部分可重构系统性能的影响,提出了在部分可重构系统配置空间中搜索最优配置序列的算法.在应用算法分割成多个任务的前提下,通过建立部分可重构系统任务执行模型,给出了任务在系统上执行代价的目标函数.根据部分可重构系统中,任务执行和配置可重叠的特性,给出了配置切换代价计算方法.在此基础上,设计了基于动态规划的配置空间搜索算法,算法可在O(nm2)(n为任务数,m为每个任务最大可选配置数)时间内搜索出执行代价最小的配置序列.结果表明,合理选择配置序列可有效提高算法在部分可重构系统上执行的效率.

By studying the effect of configuration sequence on the performance of partially reconfigurable system, a configuration space exploration algorithm was proposed to reduce the time of task switch and reconfiguration on partially reconfigurable systems. By partitioning an application into grouped tasks, a task execution model and a cost evaluation function for partially reconfigurable systems were introduced. Based on the similarity of two configurations, the reconfiguration cost between two tasks was determined. According to the reconfiguration cost, a dynamic programming methodology was applied to explore an optimal configuration sequence for a series of tasks. The time complexity of the exploration algorithm is O（nm2）, where n is the number of tasks and rn is the number of configurations of each task. Results showed that reasonable selection of configurations for a task sequence can effectively improve the performance of partially reconfigurable systems.