Temporal partitioning algorithms for reconfigurable systems proposed in recent 20 years are analyzed in the paper. They are classified as netlist-level class and behaviour-level class. The netlist-level temporal partitioning algorithms are mainly based on network flow techniques. They target minimization of the area and the number of cutting nets of the circuit to get less time delay and communication cost. Behaviour-level partitioning algorithms including level-based partitioning (LBP), cluster based partitioning (CBP), enhanced static list (ESL) and multi-objective temporal partitioning (MOTP) are qualitatively analyzed. Measures for the evaluation include the number of partitioned modules, the number of input/output edges acrossing modules and the total delay of all modules. Experimental results show that the LBP has the smallest total delay in four algorithms; the CBP has less inter-module's input/output edges, and the ESL and MOTP achieve a good compromise among three measures. However, four algorithms do not consider the shape and the cost of cross-layer mapping of partitioned modules.%对近20年来可重构系统的时域划分算法进行了分析,把它们分为网表级和行为级算法两大类.网表级时城划分算法主要采用网络流方法,使电路的面积、割网的个数等最小化,并使电路获得较小的时延和通信代价.我们对层划分、簇划分、增强静态列表调度、多目标时城划分等四种行为级时域划分算法进行了定量分析和比较,评价指标体系包括划分后的模块数、跨模块的输入/输出边数、划分后所有模块的执行总延迟.实验结果表明,层划分是四个算法划分后所有模块执行总延迟最小的;簇划分算法获得较少的跨模块的输入/输出边数;增强的静态列表调度和多目标时城划分两个算法在三个指标之间获得了一个好的折中,然而,这四个算法均没有考虑划分后的模块形状及模块的跨层映射成本.
展开▼