《VLSI计算理论与并行算法》求取 ⇩

第一章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.3VLSI电路的抽象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.5VLSI计算模型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.5VLSI布局理论68

3.5.1 平面图的分离定理68

3.5.2 圈的交叉点数69

3.5.3 布局下界定理71

参考文献71

第四章VLSI并行结构与并行算法72

4.1VLSI并行结构及其特点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.4VLSI并行算法设计基础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.2VLSI计算模型上的排序算法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.3VLSI并行计算中的数据传输算法214

7.3.1 置换选路算法214

7.3.2 超立方网络上的选路算法215

7.3.3 数据分布算法216

7.3.4 多到-选路算法219

7.4VLSI模型上的词典操作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

附录DLipton-Tarjan平面图分离集定理289

D.1 平面图的同心圆表示289

D.2 平面图的分离集定理291

算法索引293