第一章 VLSI电路设计基础及计算模型 1
1.1 集成电路和Mead-Conway设计规则 1
1.1.1 涂层及晶体三极管的形成 1
1.1.2 Mead-Conway设计规则 2
1.2 逻辑电路及其电气特性 3
1.2.1 上拉晶体管 3
1.2.2 传送晶体管 4
1.2.3 恢复器 5
1.2.4 上拉和下拉逻辑 5
1.2.5 定时计算 6
1.3 VLSI电路的抽象 7
1.3.1 模型在算法设计中的作用 8
1.3.2 电路的栅格模型 8
1.3.3 凸面假定 9
1.3.4 定时 9
1.3.5 层的数目 10
1.4 芯片制造过程及VLSI设计系统 11
1.4.1 电路图到掩模图的映射 11
1.4.2 芯片版图制作的主要阶段 12
1.4.3 用符号布局设计语言进行版图的人工布局 13
1.4.4 人机交互式布局设计系统 15
1.4.5 VLSI布局设计语言 16
1.4.6 VLSI设计系统中的算法问题 17
1.5 VLSI计算模型 17
1.5.1 面积和时间假定 18
1.5.2 信号传播的数学模型及时延分析 18
1.5.3 结语 20
参考文献 21
第二章 VLSI面-时下界理论及其应用 22
2.1 引言 22
2.1.1 VLSI算法复杂性度量 22
2.1.2 问题和问题实例 22
2.1.3 时-空确定性 23
2.2 三种基本的下界论点 24
2.2.1 基于信息存储的面积下界(A-理论) 24
2.2.2 基于输入/输出流的面-时下界(AT-理论) 25
2.2.3 基于内部信息流的面-时下界(AT2-理论) 26
2.3 信息流和穿越序列 26
2.3.1 信息的概念 27
2.3.2 穿越序列 29
2.3.3 电路外形和焊点位置对下界的影响 31
2.3.4 AT2下界的几何证明法 32
2.4 基于计算摩擦的面-时下界 33
2.5 左移位的下界 34
2.5.1 左移位芯片的AT2下界 34
2.5.2 归约和传递函数 36
2.6 两个矩阵相乘的下界 38
2.7 整数加法的下界 40
2.8 排序问题的下界 42
2.8.1 VLSI排序的面积下界 42
2.8.2 VLSI排序的AT2下界 43
2.8.3 VLSI排序的AT/logA下界 44
参考文献 45
第三章 VLSI布局 46
3.1 引言 46
3.2 典型计算图的结构布局法 46
3.2.1 树的布局 46
3.2.2 网孔和树网的布局 48
3.2.3 洗牌-交换网的布局 49
3.2.4 立方环的布局 52
3.2.5 ？形网络的布局 54
3.3 典型计算图的布局下界 55
3.3.1 树的布局下界 55
3.3.2 树网的布局下界 57
3.3.3 洗牌-交换网的布局下界 60
3.3.4 ？形网络的布局下界 60
3.4 分治布局法 61
3.4.1 分离集 61
3.4.2 强分离集 63
3.4.3 通道生成 65
3.4.4 分治布局法 66
3.5 VLSI布局理论 68
3.5.1 平面图的分离定理 68
3.5.2 圈的交叉点数 69
3.5.3 布局下界定理 71
参考文献 71
第四章 VLSI并行结构与并行算法 72
4.1 VLSI并行结构及其特点 72
4.1.1 VLSI并行计算机系统结构 72
4.1.2 VLSI并行结构的特点 74
4.2 心动阵列及波前阵列 75
4.2.1 心动阵列 75
4.2.2 波前阵列 78
4.3 VLSI并行结构设计的层次与阶段 80
4.4 VLSI并行算法设计基础 81
4.4.1 VLSI并行算法的评估参数 81
4.4.2 数据相关及其对并行性的影响 83
4.4.3 对串行程序发掘并行性的基本方法 84
4.4.4 VLSI并行算法的表达 87
参考文献 88
第五章 基本数值计算的并行算法 90
5.1 数学表达式的并行计算 90
5.1.1 求两个多项式的最高公因式 90
5.1.2 多项式求值 96
5.1.3 k阶递推问题的并行计算 99
5.2 矩阵相乘 101
5.2.1 矩阵与向量相乘 101
5.2.2 二维正方形阵列上的矩阵乘法 105
5.2.3 二维六角形阵列上的矩阵乘法 108
5.2.4 立方体连接的阵列上的矩阵乘法 111
5.3 方阵的分解与求逆 114
5.3.1 方阵的LU分解 114
5.3.2 对称方阵的Cholesky分解 118
5.3.3 方阵求逆 121
5.3.4 六角形阵列的设计 123
5.4 线性方程组求解与矩阵的三角化 125
5.4.1 三角方程组的求解 125
5.4.2 用Gauss消去法进行三角化 129
5.4.3 正交三角化方法 133
5.4.4 超定线性方程组的最小二乘解 135
5.5 进行矩阵运算的多功能阵列 135
5.5.1 Faddeev算法 136
5.5.2 实现Faddeev算法的阵列 138
5.5.3 Faddeev算法在向量运算中的应用 138
5.5.4 改进的Faddeev算法 140
5.6 在固定大小的阵列上解决大型计算问题 141
5.6.1 模拟方法 141
5.6.2 分解方法 145
参考文献 152
第六章 数字信号处理中数值计算的并行算法 154
6.1 卷积 154
6.1.1 一维卷积 154
6.1.2 二维卷积 157
6.2 数字滤波 160
6.2.1 无限冲激响应(IIR)滤波器 160
6.2.2 中值滤波器 162
6.3 傅里叶变换 164
6.3.1 离散傅里叶变换(DFT) 164
6.3.2 快速傅里叶变换(FFT) 165
6.4 用Hough变换检测曲线 171
6.5 Toeplitz方阵的分解 173
6.6 方阵的特征值与特征向量 177
6.6.1 并行QR算法 178
6.6.2 并行Jacobi方法 179
6.7 矩阵的奇异值分解 186
6.7.1 并行Jacobi方法 186
6.7.2 并行Hestenes方法 189
参考文献 197
第七章 VLSI计算模型上的非数值计算的并行算法 198
7.1 基本的VLSI电路模块 198
7.1.1 Batcher比较器 198
7.1.2 程控单元 199
7.1.3 心动单元 199
7.1.4 处理器 199
7.2 VLSI计算模型上的排序算法 200
7.2.1 Batcher双调排序网络的VLSI实现 200
7.2.2 二维方阵上奇偶排序算法 202
7.2.3 树网上的枚举排序算法 204
7.2.4 立方环结构上的双阅排序算法 206
7.2.5 ？形网络上的奇偶排序算法 210
7.2.6 洗牌-交换和超立方网络上的算法 213
7.3 VLSI并行计算中的数据传输算法 214
7.3.1 置换选路算法 214
7.3.2 超立方网络上的选路算法 215
7.3.3 数据分布算法 216
7.3.4 多到-选路算法 219
7.4 VLSI模型上的词典操作 220
7.4.1 词典机和词典操作 220
7.4.2 心动搜索树上的词典操作 221
7.4.3 网孔结构上的词典操作 223
7.4.4 洗牌-交换网上的词典操作 224
7.4.5 立方环上的词典操作 226
7.5 心动阵列上的字符串模式匹配 229
7.5.1 字符比较器阵列实现的模式匹配 229
7.5.2 位比较器阵列实现的模式匹配 231
参考文献 231
第八章 VLSI计算模型上的图论算法 233
8.1 图的传递闭包算法 233
8.1.1 传递闭包问题 233
8.1.2 Guibas-Kung-Thompson传递闭包算法 234
8.1.3 算法的正确性和复杂度 235
8.2 图的连通分量算法 236
8.2.1 Hirschberg用顶点合并法找连通分量 236
8.2.2 一维心动阵列上的Savage连通算法 237
8.2.3 树机上的Lipton-Valdes连通算法 239
8.2.4 树网结构上的连通算法 242
8.2.5 M？yr-Siegel连通算法 244
8.2.6 二维心动阵列上的连通与强连通算法 247
8.3 图的最短路径算法 249
8.3.1 利用GKT算法求顶点间最短路径 249
8.3.2 利用矩阵乘法求点对间最短路径 249
8.4 图的生成树算法 250
8.4.1 广度优先生成树算法 250
8.4.2 Bentley最小生成树算法 251
8.5 图的求桥算法 253
叁考文献 254
第九章 VLSI阵列算法的自动生成 256
9.1 引言 256
9.2 算法映射问题的理论基础 256
9.2.1 计其集 257
9.2.2 时空集 257
9.2.3 心动阵列的性质 259
9.3 变换方法 260
9.3.1 VLSI阵列的数学模型 260
9.3.2 算法的数学模型 261
9.3.3 选择正确的变换 262
9.4 几何方法 265
9.5 代数方法 266
9.5.1 算法的Z图表示 268
9.5.2 Z图的代数表示 269
9.5.3 Z图间的等价变换 270
9.5.4 k-延迟Z图 271
9.5.5 代数方法的一般过程 272
9.6 参数方法 275
9.6.1 心动阵列中的参数 275
9.6.2 心动阵列设计的优化 276
9.6.3 参数方法的一般过程 277
参考文献 280
附录A 复杂度表示符号——“大-O”、“大-Ω”和“大-Θ” 282
A.1 大-O及其运算 282
A.2 大-Ω和大-Θ 282
附录B 具有重复输入的面-时下界 283
B.1 关于重叠划分的信息流 283
B.2 基于信息流的面积和时间 284
附录C 概率芯片的面-时下界 286
附录D Lipton-Tarjan平面图分离集定理 289
D.1 平面图的同心圆表示 289
D.2 平面图的分离集定理 291
算法索引 293