An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints

CHEN Nai-jin; JIANG Jian-hui; CHEN Xin; ZHOU Zhou; XU Ying

doi:10.3969/j.issn.0372-2112.2012.05.032

您当前的位置：

首页 >

文章列表页 >

An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints

更新时间：2025-07-16

- An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints
- Acta Electronica Sinica Vol. 40, Issue 5, Pages: 1055-1066(2012)
- 作者机构：
  
  1. 同济大学软件学院,上海,201804
  2. 安徽工程大学计算机与信息学院,安徽,芜湖,241000
  3. 同济大学电子与信息工程学院,上海,201804
  4. 同济大学软件学院,上海,201804
  5. 安徽工程大学计算机与信息学院,安徽,芜湖,241000
  6. 同济大学电子与信息工程学院,上海,201804
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2012.05.032
  CLC：
- Published：2012
- 稿件说明：
移动端阅览
CHEN Nai-jin, JIANG Jian-hui, CHEN Xin, et al. An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints[J]. Acta Electronica Sinica, 2012, 40(5): 1055-1066.
DOI：

CHEN Nai-jin, JIANG Jian-hui, CHEN Xin, et al. An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints[J]. Acta Electronica Sinica, 2012, 40(5): 1055-1066. DOI： 10.3969/j.issn.0372-2112.2012.05.032.

摘要

本文提出了一种改进的层划分算法.该算法充分考虑了划分块的最小执行延迟和尽可能充分利用可重构资源

能够跟踪层划分算法节点分配过程并进行调整

消除了经典层划分算法不能动态更新就绪节点列表选取节点进行划分的缺陷.实验结果表明

与层划分算法相比

所提出的改进层划分算法在模块数、执行延迟和跨模块间的I/O边数等三个方面均获得了改进.与现有的簇划分、增强静态列表、多目标时域划分、簇层次敏感等四种划分算法相比

新算法能获得最少的执行延迟

并且随着可重构处理单元面积的增大

模块数的均值也是最小的.

Abstract

This paper presents an improved level based partitioning (ILBP) algorithm that considers sufficiently minimum execution delay and make good use of reconfigurable resources as soon as possible.ILBP can trace and adjust the node allocation process of level based partitioning (LBP) algorithm.ILBP can eliminate the disadvantage of LBP that can not update dynamically the ready list nodes for partitioning node selection.Experiment results show that the proposed ILBP algorithm can improve number of modules

execution delay and number of input-output edges crossing modules by comparing with LBP.By comparing with cluster based partitioning

enhanced static list

multi-objective temporal partitioning and level sensitive cluster based partitioning algorithms

the proposed algorithm can get the least execution delay

and it can also obtain the least average number of modules with increase of the area of reconfigurable processing unit.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Data-Driven Uniform Programming Model for Reconfigurable Computing

Reconfigurable Resource Assignment Based on a Type-Location Model

A Fine Grain Parallel Computer Architecture Model Based on Free Space Optical Interconnection

Related Author

ZHOU Xue-hai

LUO Sai

WANG Feng

QI Ji

ZHANG Hui-zhen

XIE Wei-bo

LI Xi

HONG Xin

Related Institution

Department of Computer Science and Technology,University of Science and Technology of China

School of Computer Science and Technology, Huaqiao University

Department of Computer Science,National University of Defense Technology

⁰