PBD系统的模块选择算法研究  

The Analysis of the Patterns Selection Algorithm in PBD System

作　　者：郎荣玲[1] 夏煜[1] 戴冠中[1] 

机构地区：[1]西北工业大学控制与网络研究所,西安710072

出　　处：《计算机工程与应用》2003年第30期9-12,40,共5页Computer Engineering and Applications

基　　金：国家部委基础研究项目资助

摘　　要：随着集成电路复杂度的提高以及产品投放市场的周期要求越来越短,传统的集成电路设计方法不再满足要求。因此需要开发基于硬件平台的系统,此系统通过可逻辑编程以及结构重组可以完成同一领域的一系列操作。同一领域的各个功能存在共性,可以通过研究这一领域的功能的共性,找出一些固定模块嵌入在系统中,从而在芯片面积有限的条件下提高芯片的利用率。这些模块的数量可能非常多,并且功能之间可能还有重复,因此模块选择问题成为设计者关注的焦点。直接求解此优化问题非常困难,需借助图论这一有利的数学工具解决此问题。但此问题是NP完备的,因此提出了针对两种特殊情况的算法,并分析了求解一般问题的一启发式算法,此算法的计算复杂性为O(N2s×k)。The increase in the complexity of integrated circuits and shorter time-to-market results to develop hardware platforms based system to share across multiple applications in the same domain.The system combine programmability with reconfigurable in it.There is regularity among the applications in the same domain,so we can build some patterns to be embed in the system by exploiting the regularly among the applications.The number of to be embed in the sys-tem can be large and can exit overlap between the pattern,so the problem of patters selection is put forward.The prob-lem is hard to be solved directly,so it is transformed to a problem in graph theory.The problem of pattern selection is NP-complete,so two algorithms of special condition are proposed and a heuristic algorithm is introduced.The complexity of the algorithm is O(N 2s ×k).

关 键 词：SOC 效益 交叉图 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]