【作者】 李光顺；

【导师】 马光胜；

【作者基本信息】 哈尔滨工程大学 ， 计算机应用技术， 2008， 博士

【摘要】 芯片设计的高速化和复杂化对VLSI基础理论和设计方法提出了新的挑战。以超深亚微米和纳米工艺及IP核重用为基础的系统芯片是VLSI的发展趋势。传统的设计方法已经难以应付，出现了许多新的设计技术，如有效的高层次综合技术、验证技术及纳米工艺带来的一系列关键技术等。高层次综合是连接系统行为和结构之间的纽带，它能够缩短设计、布局和验证的时间。高层次综合阶段对电路功耗有巨大的优化空间，而物理设计阶段的功耗优化空间则急剧减少。本文就高层次综合中的调度、分配和多电压低功耗设计等问题展开研究，主要工作如下：1)提出了基于遗传算法与蚂蚁算法相融合的时间约束和资源约束下的高层次调度方法。在充分研究遗传算法和蚂蚁算法独立解决约束条件下的高层次调度问题的基础上，提出了遗传算法的编码方案、交叉算子、变异算子和评估函数及蚂蚁算法的信息素更新规则，并讨论了两个算法之间的动态切换条件。当遗传算法的子代进化率低于事先设定的最小子代进化率或超过最大迭代次数时，结束遗传算法，切换到蚂蚁算法，并由遗传算法得到的优化解产生蚂蚁算法的初始信息素分布。这样避免了蚂蚁算法在初期由于信息素匮乏而做的大量盲目搜索，提高了算法的效率。实验结果表明，与遗传算法和蚂蚁算法相比，本文资源约束的调度方法能明显减少调度长度，本文时间约束的调度方法能明显减少所用资源总数目。2)在充分研究复杂高层次数据流特性的基础上，提出一种适合高层次复杂数据流分解和设计空间搜索的多项式新模型K~*TDG。首先根据复杂数据流多项式中各参数之间的关系，对TDG中的边权值重新进行定义。然后讨论了K~*TDG模型的两种基本运算：加法和乘法。K~*TDG模型充分利用了TDG模型的思想，克服了TDG模型的缺点。在此基础上，借助于Maple中的Simplify函数和Factor函数，提出复杂数据流分解匹配算法。在此过程中定义关于面积和关键路径时延的代价函数，使上述过程始终向代价函数更优的方向进行。为了进一步降低算法复杂度，还提出了根据复杂元件多项式次数进行分组的策略，使每次搜索时的空间由整个设计空间变成与K~*TDG中分支次数相等的元件组成的局部空间。实验结果表明，在保持面积和延迟近优的前提下，本文方法能明显缩小设计空间。3)提出了基于网络流的多电压高层次低功耗设计方法。定义了一种新的系统功耗模型，同时考虑了功能单元功耗、互连功耗和电压转换功耗。首先进行单电压高层次综合，然后迭代地对单电压高层次综合结果进行局部多电压调度和分配调整。只有当某个操作与其前驱节点或后继节点有分配到同一电压簇器件的可能时，才执行该调整。提取每次迭代时需要调整的网络流子图，对该子图运行最小费用最大流增量算法。该方法充分利用前面迭代中得到的优化解，避免了对整个网络流的重复计算，节省了大量时间。最后，在讨论电路拓扑结构的基础上提出了一种门控填充值算法，能进一步减少电路设计中的伪开关跳变功耗。实验结果表明，本文方法对电路的互连功耗，电平转换功耗和总功耗均有明显的优化。更多还原

【Abstract】 The high-speed and complexity of chip design put forward new challenges to thefundamental theories and design methods of VLSI (Very Large Scale Integration).SoC (system on chip), based onthe technology of VDSM (very deep submicron),nanometer and IP (intelligent property) core reuse, is the main development trend ofVLSI. However it is difficult for traditional design methods to handle such problems.Therefore many new design techniques have emerged, such as efficient high levelsynthesis, verification technology and series of key technologies brought about bynanometer technology. Among them, high level synthesis (HLS) bridges systembehaviors and system architectures. HLS can shorten time of design, layout andverification. There is huge optimization space of power dissipation at the stage ofHLS; however the optimization space of power dissipation is smaller at the stage ofphysical design. Scheduling, allocation and multi-voltages low power design of HLSare studied in this paper. The major contributions are as follows:1) The high level scheduling methods based on the combination of geneticalgorithm and ant algorithm with latency constraints and resource constraints areproposed. After an abundant investigation of the capabilities of genetic algorithm andant algorithm to solve high level scheduling independently, the coding scheme,crosstalk operator, mutation operator, evolution function of genetic algorithm and thepheromone updating rules of ant algorithm are presented. And the dynamic switchingconditions of genetic algorithm and ant algorithm are also explored: when thesub-generation evolution ratio is less than the min sub-generation evolution ratio setbeforehand or the iteration times exceed the given maximum iteration times ofgenetic algorithm, genetic algorithm terminates and switches to ant algorithm. Theinitial pheromone distribution of ant algorithm can be generated by theoptimizational solutions of genetic algorithm, thus many blind searches in the earlystage of ant algorithm for deficiency of pheromone can be avoided, and the algorithmefficiency can also be improved greatly. Experimental results indicate that, the resource constrained scheduling method in this paper can reduce scheduling lengthand the latency constrained scheduling method in this paper can reduce the totalresource numbers, compared with genetic algorithm and ant algorithm.2) A new polynomial model K*TDG is presented after an intensive study on thecharacteristic of complex high level data flow, which is suitable for complex highlevel data flow decomposition and design space exploration. First, the arc weights ofTDG are redefined according to the relationship between the parameters of complexdata flow polynomial. Then two basic operations of K*TDG are discussed: additionand multiplication. The new model K*TDG makes the best of model TDG fully, andovercomes the disadvantages of TDG as well. On this basis, a complex data flowdecomposition method is proposed by applying the Simplify function and Factorfunction in Maple. A cost function regarding area and critical path delay is defined inthis process in order to move the decomposition to a more optimal direction. In orderto reduce the algorithm complexity further, a grouping strategy based on the degreesof component polynomials is proposed. The search space is transformed from thewhole space into the local one that share the same degree with the K*TDG branch ineach iteration. Experimental results indicate that the method in this paper can reducesearch space greatly on the precondition of keeping area and delaying approximateoptimal.3) A high level low power multi-voltages design method based on network flow isdeveloped. A new system power dissipation model isdefined, in which function unitpower, interconnection power and voltages converting power are taken intoconsideration. Single voltage high level synthesis methods run first, and thenmulti-voltages local adjustments are done iteratively on the single voltage high levelsynthesis results. Only when one operation node can be allocated to the componentwhich has the same voltage cluster with its previous operation nodes or successoroperation nodes, can the adjustment be executed. In the following, the network flowsub-graph needed to adjust is extracted from the previous network flow graph andthe min-cost max-flow incremental algorithm is run on it. At last, the topologystructure used in this paper is discussed. A gated filler value computation algorithm is proposed at last to further reduce the power dissipation of spurious switchingactivity. Experimental results indicate that, the interconnection power, voltageconverting power and total power can be optimized greatly by using the methods.更多还原