Datapath电路的布局概述

总结国内外现有的设计流程和算法，大致可以分为两种类型，一类是综合工具，一类是提取工具。

Terry Tao Ye提出的抽象物理模型算法属于综合工具：该算法对电路综合前的逻辑设计信息进行整理，对其中的功能块进行建模，对每一种运算单元建立相应的标准单元组，并抽象成具有不同I/O数量和类型的矩形，然后在布局前预处理网表，采用匹配的方法决定标准单元的归属，并把这些单元在布图区域里进行映射从而完成布局。A.Chowdhary提出的一个自动模板匹配法也属于综合工具，该算法同样是根据电路逻辑设计的结果自动生成一些模板，然后对网表中的单元进行匹配，不同的是，他建立的单元组是树状的。上述这两种方法拥有“综合工具”类方法的共同点，就是在提取规则性信息时要求回溯到综合阶段以前的硬件描述语言中，从中得到大多数信息。但是，在大多数实际情况中，布局算法的输入是纯粹的综合后的电路网表，并没有初始硬件描述，原有的规则性信息在综合后都丢失了，这类算法在这种情形下几乎不再适用。“提取工具”类算法恰好相反，它是在电路网表中通过一定的提取算法进行规则性信息的提取，而不需要电路综合前的硬件描述信息，因而特别适用于一般意的datapath单元布局。R.X.T. Nijssen提出了一种基于单元连接关系分析的提取算法，该算法通过分析单元连接度和数据流向等电路属性来判断单元之间的关系，并据此提取规则单元。国内清华大学的博士也提出了一种基于单元规则排列的datapath布局算法（DPP）能够保持bit slice结构，并且能够提高功率和减小布局面积，还可以结合到任何P&R工具当中，算法提出了一个新的不规则度（irregularity degree）模型来衡量单元之间连接关系的规则性，并根据这个模型提出了规则提取算法，由提取算法抽取的规则单元排列成矩阵，最后算法把规则矩阵转化为并行约束并通过二次布局算法实现了datapath单元布局。

2 datapath结构特点

Datapath是并行进行多位数操作的数字集成电路，其在逻辑上和物理结构上具有规则性，与随机逻辑单元（即控制逻辑单元）不同，它经常用于算术逻辑单元，每一个操作会和一个功能块相关，如图1所示。客户的要求不同，功能块就不同，一般有加法器、寄存器族、触发器、多路选择和多路控制器、译码器、解码器、比较器等。位之间的连接是由操作定义的，因此，电路中存在两种意义上的互连流，一种是数据流，一种是控制流。数据流一般是并行的多位数据。控制流可以是全局的控制信号，对每一位同时产生作用；也可以是局部的控制信号，控制相邻几位，如图2所示。

在标准单元模式的布局背景下，根据操作的数据位数，datapath的功能块被设计成相应个数的标准单元，每个单元负责一个数据位上的操作，相同功能块的单元形成列状排列的叫“列（word-line）”；一个列中的单元之间多通过控制线相连，不同功能块里对相同的位进行操作的单元可以排列成行叫“行（slice）”，相同行中的单元之间多通过数据线相连。这样，datapath电路在设计时就被看成是按行和列结构规则排列的单元矩阵，这个矩阵称为“规则矩阵”，矩阵中的单元称为“规则单元”，而datapath电路中规则单元成矩阵排列的这种特殊结构被称为bit-slice结构。图1为一个datapath电路的逻辑设计结构，图2为相应的成矩阵状排列的物理布局结构，这也是datapath电路最理想的布局结果。

如图3所示，正因为datapath电路的bit-slice结构具有高度的规则化和结构化，吸引了设计者们想要以规则化的布局方式达到高性能、布局面积小的目的。每一组功能相近的组件被称为datapath的一个stage，如图3，顶部的一组datapath组件也可以分为几个stage，电路的数据流向一般与stage顺序方向一致，但是stage内部也可以有自己的数据流向，如stage3，在位列之间也会有数据流，如stage2，一个stage到下一个stage之间，可以有一对多或多对一的输入输出关系。这种规则化的原理图一般可以整体转化为一个规则化的布局。在特殊情况下，数据流可能会很长，以至于无法形成一个简单规则的bit-slice结构，我们在布图当中就会解决这个问题。

3 datapath电路的布局要求

Datapath对布局的要求源于其自身的电学性能的要求。由于datapath电路一般由几百至几千个标准单元组成，规模较小，较一般芯片来说单元数量少，所以对线长的要求并不十分高。但由于datapath模块在整个芯片里承担主要的计算任务，因此对最大时延、串扰、信号时延平衡等性能指标的要求相对较高。其中时延是指信号到达一个单元的时间与要求时间的最大延迟，信号时延平衡则指同一信号到达同一功能块中不同位上的单元的时延差异，可以通过计算信号到达同一列上不同单元的延迟的最大、最小值的比值来大致衡量。对于最大时延的优化有已经很多文献研究，但对于信号时延平衡到目前并没有找到很好的数学模型，解决起来比较困难。但是，人们在长期的设计实践中发现：如果datapath单元的布局能够参考设计时给出的规则化的bit-slice结构，那么线网互联的延时将会得到改善，这是由于布局的过程从很大程度上借鉴了datapath电路本身的特点，datapath电路中比例最大的数据线（比如Bus线网）将最大程度的分布在行内，减少了线网在行与行之间的交叠；同时，由于行与行之间的相似性，类型相同的线网在长度和信号方向上都相差无几，这对减少信号偏差、降低串扰无疑十分有利，由此得到的布局结果往往能在最大时延和时延平衡性方面都获得良好的效果。另一方面，由于布局结果与datapath设计的拓扑结果十分一致，这将有利于设计者在综合阶段就能对datapath电路的时延等性能指标做出比较精确的估计，从设计的整体过程上提高电路的质量。也就是说：datapath电路特殊的结构和性能要求我们在布局过程中要使datapath电路能够很好的实现单元的规则化排列。

4 datapath电路布局的基本方法

Datapath电路的布局方法一般分为两个步骤，第一部是提取规则单元，第二布是规则单元布图规划。

4.1 规则单元的提取

实现单元规则化排列首先要掌握单元的规则性信息，即如何区分规则单元和自由单元，以及区分规则单元与在规则矩阵中相邻的其他单元之间的位置关系等。正常情况下，结构规则的逻辑单元一般都出现在datapath组件里，目前主要有两种提取规则单元的方法：一是覆盖，在所有可能要用的模块当中提取所有功能和结构相似的模块，然后选出最好的映射在电路当中。二是膨胀，发现相邻位块之间有相似的逻辑或结构的一部分逻辑门作为模板，再将周围电路与之前的模板进行比较，看是否具有相似的规则化，如果不规则度小于一定阈值的，则可以把模板扩大，继续膨胀找到相似结构，如果不规则度太大，则停止膨胀，得到最后相关的规则电路。

4.2 规则电路的布图规划

Datapath的布图规划就是要给datapath组件找到合适的相对位置，同时依据数据流的方向。其目的就是要实现在没有重叠布局的前提下，布图面积和互连线长达到最优化的结果。Datapath的布图规划最大的特点是线网的大多数是总线并且与数据流的方向一致。当数据流长度过大时，有两种方法解决，一种方法是把较长的为线分为几个部分然后把他们依次布局在电路中，以最大宽度和高度为约束，找到最优的分解办法和布图方式，如图4（a）；另一种方法是用般的模块封装的算法并且把数据流方向的约束加上，确保每一级的操作都是按顺序的，如图4（b）。

参考文献

[1]Terry Tao Ye and Giovanni De Micheli.Data Path Placement with Regularity[C].In Proceedings of ICCAD 2000.

[2]A. Chowdhary，S.Kale，P.Saripella，N. Sehgal and R.Gupta.A General APProach for Regularity Extraction in DatapathCircuits[C].International Conference on Computer-Aided Design，1998.

[3]R.X.T.Nijssen and C.A.J.vanEijk， “GreyHound：A methodology for utilizing datapath regularity in standard design flows”，Integration， the VLSI Journal 25，1998：111-135.

[4]杨长旗.超大规模集成电路混合模式布局算法研究和系统设计[D].清华大学博士论文，2004.

[5]L.Scheffer， L.Lavagno and G.Martin，eds.，EDA for IC Implementation， Circuit Design， and Process Technology[M]， CRC Press， Boca Raton，2006.

[6]Ulf Jälmbrant and MattiasWinsten.Structured Digital Design.CiteSeerx， Scientific Literature Digital Library and Search Engine[J].version 1.02，2007：1-4.

作者简介

郝燕芳（1990-），女，山西省晋中市人。现为中国矿业大学（北京）硕士研究生。研究方向为计算机系统结构、集成电路。

作者单位

中国矿业大学（北京） 北京市 10083

推荐访问： 概述 布局 电路 Datapath