2013-3-1 1
第八章
2013-3-1 2
§ 1 全定制电路的结构化设计特征
结构化设计是由 Mead和 Conway首先提出来
的, 其目的是让设计者能够直接参加芯片
设计以实现高性能系统 。 在结构化设计中
采用以下几方面的技术 。
2013-3-1 3
一、层次性,
? 原因：由于系统规模很大，设计复杂性
很高，层次式设计可以降低设计复杂性。
? 层次式设计分类,
自底向上（ bottom-up)
自顶向下 (top-down)
两者结合
? 层次式设计方法：系统划分与布图规划
2013-3-1 4
? 系统划分,在功能设计与寄存器级设计完成后，
将模块划分成合适的单元组合，然后分别对单元电
路进行逻辑级、电路级乃至版图级的设计。划分的
关键是评价函数的确定。
? 布图规划,与全定制设计功能级并行的工作是芯
片面积的规划，称为布图规划，其目的是为每个模
块确定一个布图面积的大小及在芯片上的相对位置。
在布图规划中，只是在较高层次上完成了对软模块
的形状和大小的估计，以及它们的引线端的分配。
2013-3-1 5
二, 模块性
? 模块有明确定义的物理接口：模块名称, 功
能, 层类, 尺寸与外部互连端点的数目, 名
称及位置等 。
? 模块性有助于设计人员明确问题并做出文件
接口 。 每个人只设计芯片的一部分 。
2013-3-1 6
三, 规则性
? 规则化：是指模块内部可以随功能不同而不同, 但
模块间的接口如电源, 地线, 时钟线, 总线等是公
共的 。
? 方法及优点：采用单元重复的方法是结构化设计的
一种好方法, 这样既简化设计, 又减少错误, 同时
使结构规则化 。
? 规则化的层次：规则化可以在设计层次的所有级别
上存在 。
2013-3-1 7
四, 局部性
通过对模块接口的很好定义, 可以有效
地使该模块的内容变得对任何外部接口
不再重要, 可以将每个模块看作一个黑
盒子 。 设计时不关心模块内部的情况,
这样减少了模块表现的复杂性 。
2013-3-1 8
五, 手工参与
? 全定制设计中往往需要手工参与：由于
设计系统的复杂性, 结构灵活性, 性能
的约束性 。
? 手工参与设计的实质是在各个设计层次
上, 人工干预和协调各种 EDA工具的应
用, 目的是取得设计的最高效率和最好
结果 。
2013-3-1 9
全定制设计流程
设计说明
功能设计
单元版图设计与验证
寄存器传输级设计
寄存器模块的逻辑设
计
逻辑单元的电路设计
芯片版图验证
芯片版图设计
布图规
划
设计规则
电学参数
功能设计要求
掩膜版数据输出
测试图形生成
测试数据输出
2013-3-1 10
§ 2 几种全定制设计方法
?基于几何图形的交互版图编辑
?符号法
?积木块自动布图
2013-3-1 11
一, 交互图形编辑,
交互图形编辑方法是一种人工设计方法,
? 绘图、显示、插入、移动、删除、复制、
拉伸等命令。
? 联机的的设计规则检查功能 。
? 开窗, 缩放, 窗口移动 。
? 设计性能高, 版图质量高, 效率低, 设
计周期长 。
2013-3-1 12
交互图形编辑产品
? Cadence,Mentor等都有功能完善, 性
能良好的编辑工具 。
? 我国自行开发的 PANDA系统也包括有
一个交互图形编辑工具 。 除了工作站版
本外, 有些公司还专门提供微机上的版
本 。
? Tanner公司的 L-Edit是一个广泛使用的微
机上的交互图形编辑器 。
2013-3-1 13
设计检查
? 由于手工设计方法不可避免地会产生错
误。因此，必须在版图编辑后进行版图
验证。
? 版图验证包括：设计规则检查、电学规
则检查、版图与原理图对照检查以及电
路网表提取，版图寄生参数提取和后模
拟。
2013-3-1 14
设计检查工具
CAD公司在提供交互图形编辑软件的同
时，也提供版图验证软件。 Cadence的
Dracula就是一个十分著名的版图验证软
件。一个性能良好的版图验证软件可以
将设计错误消灭在芯片制造之前，确保
芯片的正确性和一定的成品率。
2013-3-1 15
二, 符号法版图设计方法
符号法版图设计方法 （ symbolic layout
approach） 是一种半自动设计方法,
（ 1） 使用晶体管, 通孔和连线的符号进行
输入和编辑并产生一个拓扑版图 。
（ 2） 根据给定的设计规则将拓扑版图转换
成物理版图 。
（ 3） 版图压缩, 以优化版图面积 。
2013-3-1 16
符号法版图设计的特点
符号法版图设计方法保持了交互图形编
辑方法所具有的较高布图密度和灵活性
的优点, 且由于设计规则是由符号法版
图编辑器维持的, 用户在操作时不需要
考虑, 因而大大降低了设计工作量 。
2013-3-1 17
符号法版图设计产品
? Magic是一个著名的符号法版图编辑器,
它是由美国加州大学 Berkeley分校开发的 。
有些实用系统把符号法和交互图形编辑
集成在一个系统中 。
? 我国 PNADA系统中, 用户可以用几何图
形, 也可以用器件符号进行版图编辑 。
2013-3-1 18
三, 积木块自动设计
积木块自动布图 （ Building Block Layout）
又称为任意形状单元布图, 简称作 BBL。
它是基于单元库的一种最为灵活的设计方
式 。 限于实现的困难, 大部分的 BBL模式
单元版图都为矩形, 它们可被安置在芯片
的任何位置上 。
2013-3-1 19
积木块自动布图
R O M /
R A M
A / D
P L A
I / O
转换
数据通路
压焊块 第一层金属 第二层金属
通
孔
随
机
逻
辑
2013-3-1 20
BBL布图分类
? 有通道,BBL模式下的布线区域比较复杂,
未被模块占用的芯片空间为布线区 。 通
常要先把它们划分成矩形的通道区, 然
后再按一定次序逐个进行布线, 此时模
块上面不能走线 。
? 无通道：随着多层布线工艺的出现, 模
块上允许有三层以上的走线, 出现了
,跨单元布线, （ Over the Cell
Routing） 技术 。 它使得布线区域大大减
小 。
2013-3-1 21
BBL设计模型实例
2013-3-1 22
BBL布图设计特点
? 优点：布图密度高, 布图灵活, 设计性
能高, 它是一种很理想的设计方法 。
? 难点,BBL的布图算法和布图系统较其
它设计方法复杂, 目前还没有一个很成
功的实用系统 。 但是, 目前从 SOC设计
的需要出发, 必须要研究这种基于各种
IP模块的设计方法 。
2013-3-1 23
BBL自动设计工具
? Cadence推出过一个叫 SYMBED的 BBL系
统。
? 美国加州大学 Berkeley分校的 BEAR系统
是一个著名的 BBL系统。它在算法、数
据结构和系统构思方面都有很多创新。
? 我国的 PANDA系统中的 FRACT系统是一
个 BBL设计工具，它是在 BEAR的基础上
改进而成的 。
2013-3-1 24
BBL布图方法的改进
? 目前可以有非矩形的模块, 如 L型, T型
的形状 。
? 问题的表示方法, 布图规划, 布局, 布
线算法的研究也在不断进行 。
? 考虑延迟, 功耗, 噪声串扰等约束以及
将布局与布线同时考虑的算法等 。
2013-3-1 25
BBL自动设计的算法复杂性
由于 VLSI电路的规模和复杂性, 一次设计
成功的难度太大, 通常,
? 布局的复杂性在 O（ n2） 到 O（ n4） 之间
? 布线在 O（ n logn） 到 O（ n2） 之间当 n（ 问
题的规模 ） 很大时, 计算时间会相当长 。
2013-3-1 26
采用分级设计策略可有效地降低复杂性
以布局为列，若原来复杂性为 S=O(n2)，
分级后先对模块内进行布局，然后对整
个芯片进行布局，则总的复杂性为,
两者工作量之比为,
由于 m<<n,所以其工作量大约是原来的
1/m。 分级设计会损失掉一些布图变量 。
)/())/((' 2222 cmmnOcmmnmOS ????
2)/(/1/' nmCmSS ??
2013-3-1 27
§ 3 不同设计方法比较
? 设计方法的选择与芯片性能要求、产品上
市时间以及产品产量有关。
? 用户可以根据自己对产品性能、批量大小
和上市时间的要求，选择相应的设计方法。
表 1设计模式在版图结构上的差别。
表 2设计模式芯片面积、性能及制造方法上的不同。
2013-3-1 28
表一 各种设计模式的版图结构
设计模式
全定制 标准单元 门阵列 FPGA
单元外形 可变 固定高度 不变 不变
单元类型 可变 可变 固定 可编程
单元布局 可变 按行 固定 固定
连 线 可变 可变 可变 可编程
2013-3-1 29
表二 不同的设计模式的芯片面积、性能和掩膜制作方式
设计模式
全定制 标准单元 门阵列 F P G A
芯片面积 小 较小 中等 大
芯片性能 高 较高 中等 低
制作掩膜 全部 全部 金属连线及孔 不需要
2013-3-1 30
定制电路的设计
定制电路是指一些通用电路的设计, 由
半导体生产厂家按标准规格生产出来的
一 系 列 电 路, 如 ROM,EPROM、
EEPROM,PLA,PLD及 FPGA等等 。 这
些芯片已经制好, 只需将信息写入即可
工作 。
2013-3-1 31
定制电路的种类
这种电路的特点是结构非常规则, 对于这
类通用电路的设计, 通常有以下的方法,
1.面向规则的 ROM集成电路版图设计语言
编译 。
2.面向随机的组合逻辑 PLA,PLD方法 。
3.面向总线结构的栅陈列 （ gate matrix） 方
法 。
2013-3-1 32
设计模式的选择
? 大批量的产品, 如微处理器, 存储器等
宜采用全定制设计方法 。
? 小批量 ASIC产品则采用半定制的门阵列
或宏单元阵列设计方法 。
? 单件, 批量很小的产品, 试验电路则采
用 FPGA设计方法 。
? 电性能要求较高, 而批量较小的产品,
或中批量产品则采用标准单元设计方式 。
2013-3-1 33
设计成本、质量、效率
设计成本、效率、质量是相互制约的。如
果设计一个高质量的版图，需要付出较高
的成本，同时使设计效率下降。反之，如
果要求低成本和较高效率，那么往往要在
设计质量上作出某些让步。
2013-3-1 34
设计的产量与成本
芯片生产中平均每个管子的成本 C可用下
式表示,
当产量很低时, 第一项设计成本起主要
作用, 当产量很高时, 单个芯片生产成
本起主要作用 。
总产量芯片上晶体管数
总产量单个芯片生产成本芯片设计成本
?
??? )()(C
2013-3-1 35
设计方法、设计规模与成本
图中给出设计成本与集成度的关系。当
规模较小时，人工设计质量高，但成本
并不高。但当规模大时，人工设计成本
迅速增加而显示出自动设计的优越性。
而半动设计在 a0,a1区显示出其低成本的
优越性。
2013-3-1 36
设计方法与设计成本、集成度的关系
设计成本
集成度
a0 a1
人工
半自动
全自动
2013-3-1 37
第五节 BBL布图规划与布局
八十年代中的 BBL问题
? 典型系统是 BEAR
-- 采用模板枚举匹配和启发式算法
-- 限于复杂性只能枚举 4个模块
? 首次提出用解析法求解布局问题
? 边勾链数据结构和另一种解析法（势能函数）
? FRACT -- 基于 BEAR的 BBL系统
? 布图表示成为关键
2013-3-1 38
Slicing 结构 和 Non-Slicing 结构
? Slicing 结构
? 数据表示容易
? 通道定义方便
? 计算复杂性较低
? Non-Slicing 结构
? 布图密度更高
? 处理特殊问题较方便
? 日益受到重视
2013-3-1 39
各种不同模型的比较
? 计算复杂性
binary tree SP BSG O-tree CBL
O(n) O(n2) O(n2) O(n)* O(n)
? 搜索空间
binary tree SP BSG O-tree CBL
O(n!2) C(n2,n) O(n!22n-2/n1.5) O(n!23n-7)
? 存储量 (bits)
binary tree SP BSG O-tree CBL
n(6+[lgn]) 2n[lgn] n(n-1+[lgn]) n(2+[lgn]) n(3+[lgn])
2013-3-1 40
新一代的 BBL问题
? 九十年代中针对甚大规模和分级设计的需要提
出，希望优化时延、面积、噪声和功耗。
? 考虑 插入缓冲单元的互连规划的布局。
? 满足多种约束：芯片宽长比、多边形模块、多
边形芯片外框、固定方位模块、固定位置模块、
固定障碍等。
? 可应用于晶体管级的布局问题（另加约束）
? 多采用随机优化方法：模拟退火、遗传进化等
? 可分为 Slicing和 Non-slicing两大类
2013-3-1 41
基于阶梯网格结构的布局算法
ami33布局结果
test3布局结果
2013-3-1 42
考虑面积、线长和宽高比目标的 BBL布局算法
2013-3-1 43
带有软模块的布图规划算法
不同宽长比目标下的布图规划效果图
2013-3-1 44
带预置模块和多边形区域上的布图规划
带预置模块的布图规划 多边形区域上的布图规划
2013-3-1 45
含多边形模块的布局
2013-3-1 46
同时进行布局和总体布线算法
第八章
2013-3-1 2
§ 1 全定制电路的结构化设计特征
结构化设计是由 Mead和 Conway首先提出来
的, 其目的是让设计者能够直接参加芯片
设计以实现高性能系统 。 在结构化设计中
采用以下几方面的技术 。
2013-3-1 3
一、层次性,
? 原因：由于系统规模很大，设计复杂性
很高，层次式设计可以降低设计复杂性。
? 层次式设计分类,
自底向上（ bottom-up)
自顶向下 (top-down)
两者结合
? 层次式设计方法：系统划分与布图规划
2013-3-1 4
? 系统划分,在功能设计与寄存器级设计完成后，
将模块划分成合适的单元组合，然后分别对单元电
路进行逻辑级、电路级乃至版图级的设计。划分的
关键是评价函数的确定。
? 布图规划,与全定制设计功能级并行的工作是芯
片面积的规划，称为布图规划，其目的是为每个模
块确定一个布图面积的大小及在芯片上的相对位置。
在布图规划中，只是在较高层次上完成了对软模块
的形状和大小的估计，以及它们的引线端的分配。
2013-3-1 5
二, 模块性
? 模块有明确定义的物理接口：模块名称, 功
能, 层类, 尺寸与外部互连端点的数目, 名
称及位置等 。
? 模块性有助于设计人员明确问题并做出文件
接口 。 每个人只设计芯片的一部分 。
2013-3-1 6
三, 规则性
? 规则化：是指模块内部可以随功能不同而不同, 但
模块间的接口如电源, 地线, 时钟线, 总线等是公
共的 。
? 方法及优点：采用单元重复的方法是结构化设计的
一种好方法, 这样既简化设计, 又减少错误, 同时
使结构规则化 。
? 规则化的层次：规则化可以在设计层次的所有级别
上存在 。
2013-3-1 7
四, 局部性
通过对模块接口的很好定义, 可以有效
地使该模块的内容变得对任何外部接口
不再重要, 可以将每个模块看作一个黑
盒子 。 设计时不关心模块内部的情况,
这样减少了模块表现的复杂性 。
2013-3-1 8
五, 手工参与
? 全定制设计中往往需要手工参与：由于
设计系统的复杂性, 结构灵活性, 性能
的约束性 。
? 手工参与设计的实质是在各个设计层次
上, 人工干预和协调各种 EDA工具的应
用, 目的是取得设计的最高效率和最好
结果 。
2013-3-1 9
全定制设计流程
设计说明
功能设计
单元版图设计与验证
寄存器传输级设计
寄存器模块的逻辑设
计
逻辑单元的电路设计
芯片版图验证
芯片版图设计
布图规
划
设计规则
电学参数
功能设计要求
掩膜版数据输出
测试图形生成
测试数据输出
2013-3-1 10
§ 2 几种全定制设计方法
?基于几何图形的交互版图编辑
?符号法
?积木块自动布图
2013-3-1 11
一, 交互图形编辑,
交互图形编辑方法是一种人工设计方法,
? 绘图、显示、插入、移动、删除、复制、
拉伸等命令。
? 联机的的设计规则检查功能 。
? 开窗, 缩放, 窗口移动 。
? 设计性能高, 版图质量高, 效率低, 设
计周期长 。
2013-3-1 12
交互图形编辑产品
? Cadence,Mentor等都有功能完善, 性
能良好的编辑工具 。
? 我国自行开发的 PANDA系统也包括有
一个交互图形编辑工具 。 除了工作站版
本外, 有些公司还专门提供微机上的版
本 。
? Tanner公司的 L-Edit是一个广泛使用的微
机上的交互图形编辑器 。
2013-3-1 13
设计检查
? 由于手工设计方法不可避免地会产生错
误。因此，必须在版图编辑后进行版图
验证。
? 版图验证包括：设计规则检查、电学规
则检查、版图与原理图对照检查以及电
路网表提取，版图寄生参数提取和后模
拟。
2013-3-1 14
设计检查工具
CAD公司在提供交互图形编辑软件的同
时，也提供版图验证软件。 Cadence的
Dracula就是一个十分著名的版图验证软
件。一个性能良好的版图验证软件可以
将设计错误消灭在芯片制造之前，确保
芯片的正确性和一定的成品率。
2013-3-1 15
二, 符号法版图设计方法
符号法版图设计方法 （ symbolic layout
approach） 是一种半自动设计方法,
（ 1） 使用晶体管, 通孔和连线的符号进行
输入和编辑并产生一个拓扑版图 。
（ 2） 根据给定的设计规则将拓扑版图转换
成物理版图 。
（ 3） 版图压缩, 以优化版图面积 。
2013-3-1 16
符号法版图设计的特点
符号法版图设计方法保持了交互图形编
辑方法所具有的较高布图密度和灵活性
的优点, 且由于设计规则是由符号法版
图编辑器维持的, 用户在操作时不需要
考虑, 因而大大降低了设计工作量 。
2013-3-1 17
符号法版图设计产品
? Magic是一个著名的符号法版图编辑器,
它是由美国加州大学 Berkeley分校开发的 。
有些实用系统把符号法和交互图形编辑
集成在一个系统中 。
? 我国 PNADA系统中, 用户可以用几何图
形, 也可以用器件符号进行版图编辑 。
2013-3-1 18
三, 积木块自动设计
积木块自动布图 （ Building Block Layout）
又称为任意形状单元布图, 简称作 BBL。
它是基于单元库的一种最为灵活的设计方
式 。 限于实现的困难, 大部分的 BBL模式
单元版图都为矩形, 它们可被安置在芯片
的任何位置上 。
2013-3-1 19
积木块自动布图
R O M /
R A M
A / D
P L A
I / O
转换
数据通路
压焊块 第一层金属 第二层金属
通
孔
随
机
逻
辑
2013-3-1 20
BBL布图分类
? 有通道,BBL模式下的布线区域比较复杂,
未被模块占用的芯片空间为布线区 。 通
常要先把它们划分成矩形的通道区, 然
后再按一定次序逐个进行布线, 此时模
块上面不能走线 。
? 无通道：随着多层布线工艺的出现, 模
块上允许有三层以上的走线, 出现了
,跨单元布线, （ Over the Cell
Routing） 技术 。 它使得布线区域大大减
小 。
2013-3-1 21
BBL设计模型实例
2013-3-1 22
BBL布图设计特点
? 优点：布图密度高, 布图灵活, 设计性
能高, 它是一种很理想的设计方法 。
? 难点,BBL的布图算法和布图系统较其
它设计方法复杂, 目前还没有一个很成
功的实用系统 。 但是, 目前从 SOC设计
的需要出发, 必须要研究这种基于各种
IP模块的设计方法 。
2013-3-1 23
BBL自动设计工具
? Cadence推出过一个叫 SYMBED的 BBL系
统。
? 美国加州大学 Berkeley分校的 BEAR系统
是一个著名的 BBL系统。它在算法、数
据结构和系统构思方面都有很多创新。
? 我国的 PANDA系统中的 FRACT系统是一
个 BBL设计工具，它是在 BEAR的基础上
改进而成的 。
2013-3-1 24
BBL布图方法的改进
? 目前可以有非矩形的模块, 如 L型, T型
的形状 。
? 问题的表示方法, 布图规划, 布局, 布
线算法的研究也在不断进行 。
? 考虑延迟, 功耗, 噪声串扰等约束以及
将布局与布线同时考虑的算法等 。
2013-3-1 25
BBL自动设计的算法复杂性
由于 VLSI电路的规模和复杂性, 一次设计
成功的难度太大, 通常,
? 布局的复杂性在 O（ n2） 到 O（ n4） 之间
? 布线在 O（ n logn） 到 O（ n2） 之间当 n（ 问
题的规模 ） 很大时, 计算时间会相当长 。
2013-3-1 26
采用分级设计策略可有效地降低复杂性
以布局为列，若原来复杂性为 S=O(n2)，
分级后先对模块内进行布局，然后对整
个芯片进行布局，则总的复杂性为,
两者工作量之比为,
由于 m<<n,所以其工作量大约是原来的
1/m。 分级设计会损失掉一些布图变量 。
)/())/((' 2222 cmmnOcmmnmOS ????
2)/(/1/' nmCmSS ??
2013-3-1 27
§ 3 不同设计方法比较
? 设计方法的选择与芯片性能要求、产品上
市时间以及产品产量有关。
? 用户可以根据自己对产品性能、批量大小
和上市时间的要求，选择相应的设计方法。
表 1设计模式在版图结构上的差别。
表 2设计模式芯片面积、性能及制造方法上的不同。
2013-3-1 28
表一 各种设计模式的版图结构
设计模式
全定制 标准单元 门阵列 FPGA
单元外形 可变 固定高度 不变 不变
单元类型 可变 可变 固定 可编程
单元布局 可变 按行 固定 固定
连 线 可变 可变 可变 可编程
2013-3-1 29
表二 不同的设计模式的芯片面积、性能和掩膜制作方式
设计模式
全定制 标准单元 门阵列 F P G A
芯片面积 小 较小 中等 大
芯片性能 高 较高 中等 低
制作掩膜 全部 全部 金属连线及孔 不需要
2013-3-1 30
定制电路的设计
定制电路是指一些通用电路的设计, 由
半导体生产厂家按标准规格生产出来的
一 系 列 电 路, 如 ROM,EPROM、
EEPROM,PLA,PLD及 FPGA等等 。 这
些芯片已经制好, 只需将信息写入即可
工作 。
2013-3-1 31
定制电路的种类
这种电路的特点是结构非常规则, 对于这
类通用电路的设计, 通常有以下的方法,
1.面向规则的 ROM集成电路版图设计语言
编译 。
2.面向随机的组合逻辑 PLA,PLD方法 。
3.面向总线结构的栅陈列 （ gate matrix） 方
法 。
2013-3-1 32
设计模式的选择
? 大批量的产品, 如微处理器, 存储器等
宜采用全定制设计方法 。
? 小批量 ASIC产品则采用半定制的门阵列
或宏单元阵列设计方法 。
? 单件, 批量很小的产品, 试验电路则采
用 FPGA设计方法 。
? 电性能要求较高, 而批量较小的产品,
或中批量产品则采用标准单元设计方式 。
2013-3-1 33
设计成本、质量、效率
设计成本、效率、质量是相互制约的。如
果设计一个高质量的版图，需要付出较高
的成本，同时使设计效率下降。反之，如
果要求低成本和较高效率，那么往往要在
设计质量上作出某些让步。
2013-3-1 34
设计的产量与成本
芯片生产中平均每个管子的成本 C可用下
式表示,
当产量很低时, 第一项设计成本起主要
作用, 当产量很高时, 单个芯片生产成
本起主要作用 。
总产量芯片上晶体管数
总产量单个芯片生产成本芯片设计成本
?
??? )()(C
2013-3-1 35
设计方法、设计规模与成本
图中给出设计成本与集成度的关系。当
规模较小时，人工设计质量高，但成本
并不高。但当规模大时，人工设计成本
迅速增加而显示出自动设计的优越性。
而半动设计在 a0,a1区显示出其低成本的
优越性。
2013-3-1 36
设计方法与设计成本、集成度的关系
设计成本
集成度
a0 a1
人工
半自动
全自动
2013-3-1 37
第五节 BBL布图规划与布局
八十年代中的 BBL问题
? 典型系统是 BEAR
-- 采用模板枚举匹配和启发式算法
-- 限于复杂性只能枚举 4个模块
? 首次提出用解析法求解布局问题
? 边勾链数据结构和另一种解析法（势能函数）
? FRACT -- 基于 BEAR的 BBL系统
? 布图表示成为关键
2013-3-1 38
Slicing 结构 和 Non-Slicing 结构
? Slicing 结构
? 数据表示容易
? 通道定义方便
? 计算复杂性较低
? Non-Slicing 结构
? 布图密度更高
? 处理特殊问题较方便
? 日益受到重视
2013-3-1 39
各种不同模型的比较
? 计算复杂性
binary tree SP BSG O-tree CBL
O(n) O(n2) O(n2) O(n)* O(n)
? 搜索空间
binary tree SP BSG O-tree CBL
O(n!2) C(n2,n) O(n!22n-2/n1.5) O(n!23n-7)
? 存储量 (bits)
binary tree SP BSG O-tree CBL
n(6+[lgn]) 2n[lgn] n(n-1+[lgn]) n(2+[lgn]) n(3+[lgn])
2013-3-1 40
新一代的 BBL问题
? 九十年代中针对甚大规模和分级设计的需要提
出，希望优化时延、面积、噪声和功耗。
? 考虑 插入缓冲单元的互连规划的布局。
? 满足多种约束：芯片宽长比、多边形模块、多
边形芯片外框、固定方位模块、固定位置模块、
固定障碍等。
? 可应用于晶体管级的布局问题（另加约束）
? 多采用随机优化方法：模拟退火、遗传进化等
? 可分为 Slicing和 Non-slicing两大类
2013-3-1 41
基于阶梯网格结构的布局算法
ami33布局结果
test3布局结果
2013-3-1 42
考虑面积、线长和宽高比目标的 BBL布局算法
2013-3-1 43
带有软模块的布图规划算法
不同宽长比目标下的布图规划效果图
2013-3-1 44
带预置模块和多边形区域上的布图规划
带预置模块的布图规划 多边形区域上的布图规划
2013-3-1 45
含多边形模块的布局
2013-3-1 46
同时进行布局和总体布线算法
