《互连网络结构分析》求取 ⇩

第一章并行处理系统与互连网络1

1.1 并行处理——提高计算机系统性能的重要途径1

1.1.1 推动并行处理技术发展的因素1

1.1.2 并行性的概念及其实现途径3

1.2 并行处理系统的系统结构6

1.2.1 流水线处理机的工作原理与特点6

1.2.2 阵列处理机的功能结构与性能7

1.2.3 多处理机的系统结构与控制10

1.2.4 计算机系统的分类12

1.3 互连网络在并行处理系统中的地位和作用14

1.3.1 互连网络的作用与功能模型14

1.3.2 互连网络的连接通路15

1.4 互连网络与互连函数16

1.4.1 互连函数的表示形式17

1.4.2 几种基本互连函数17

1.4.3 FUB互连函数24

1.4.4 BPC互连函数26

1.5 映射和置换的初步知识27

1.5.1 映射27

1.5.2 置换31

1.6 互连网络的结构分类36

1.6.1 静态互连网络36

1.6.2 动态互连网络41

参考文献47

2.1.1 单总线48

第二章静态互连网络结构分析48

2.1 总线型网络48

2.1.2 多总线49

2.1.3 多级总线50

2.1.4 多维总线52

2.1.5 分割总线53

2.2 环形网络54

2.2.1 单环网络的结构特征与寻径算法55

2.2.2 带弦环形网络的特性和分布控制算法59

23 立方体网络64

2.3.1 立方体网络的结构与特性64

2.3.2 带环立方体网络的组成与特点65

2.3.3 一般化的超立方体网络67

2.4 树形网络72

2.4.1 二叉树和半环、全环二叉树网络72

2.4.2 超树形网络的构成与特性75

2.4.3 多树网络的结构分析78

2.5 网孔形、星形和全连接网络80

2.5.1 网孔形网络80

2.5.2 星形网络81

2.5.3 全连接网络82

2.6 静态互连网络的生成方法82

参考文献85

3.1.1 SIMD机器的两种基本组态87

第三章单级互连网络87

3.1 SIMD机器的结构模型87

3.1.2 STMD机器的结构模型88

3.2 单级互连网络93

3.2.1 单级互连网络的概念模型94

3.2.2 网孔连接的Illiac网络95

3.2.3 加减2？网络99

3.2.4 洗牌交换网络103

3.2.5 立方体网络106

3.3 单级互连网络的划分110

3.3.1 网络划分的原理112

3.3.2 立方体网络的划分114

3.3.3 Illiac网络的划分116

3.3.4 PM2I网络的划分116

3.3.5 洗牌交换网络的划分119

3.4 单级互连网络的相互模拟119

3.4.1 单级互连网络相互模拟原理119

3.4.2 PM2I网络模拟其它网络121

3.4.3 立方体网络模拟其它网络127

3.4.4 Illiac网络模拟其它网络134

3.4.5 SE网络模拟其它网络146

参考文献150

4.1 STARAN网络152

4.1.1 STARAN网络的作用152

第四章动态多级阻塞互连网络152

4.1.2 拓扑结构154

4.1.3 控制方式与连接特性155

4.2 间接二进制n方体网络160

4.2.1 拓扑结构及其控制160

4.2.2 容许通过的置换163

4.3 Ω网络172

4.3.1 并行存储器的无冲突访问172

4.3.2 Ω网络的结构与控制176

4.3.3 连接特性与应用179

4.4 数据变换网络188

4.4.1 DM网络的构成与变换功能188

4.4.2 ADM网络及其控制191

4.5 榕树网络195

4.5.1 榕树网络195

4.5.2 SW榕树网络197

4.6 Delta网络203

4.6.1 工作原理与网络组成203

4.6.2 性能分析与交叉开关的比较208

4.7 基准网络213

4.7.1 基准网络213

4.7.2 基准网络与位序颠倒交换网络215

4.7.3 一次通过网络的容许置换216

4.7.4 二次通过网络实现任意置换218

4.8.1 拓扑等价219

4.8 多级互连网络的拓扑与功能等价219

4.8.2 功能等价226

4.9 多级互连的网络划分233

4.9.1 多级互连网络的划分233

4.9.2 STARAN网络的划分234

4.9.3 间接二进翻n方体网络的划分235

4.9.4 Ω网络的划分238

4.9.5 数据变换网络的划分239

参考文献240

第五章动态多级非阻塞互连网络243

5.1 开关连接系统与互连网络243

5.1.1 连接系统的一般特性243

5.1.2 互连网络的连接能力244

5.1.3 多级非阻塞网络的研究概况247

5.2 交叉开关网络250

5.3 多级非阻塞网络252

5.3.1 非阻塞Clos网络252

5.3.2 非对称Clos网络的某些术语及符号258

5.3.3 非对称严格非阻塞Clos网络260

5.3.4 严格非阻塞Cantor网络263

5.4 可重排非阻塞网络266

5.4.1 可重排三级Clos非阻塞网络266

5.4.2 非对称的可重排非阻塞网络268

5.4.3 二进制置换网络274

5.4.4 二项网络279

5.4.5 细胞结构的可重排网络286

5.5 一般化的连接网络294

5.5.1 一般化的连接网络及其图的表示294

5.5.2 GCN的构造方法296

5.5.3 信息播送与开关设置算法300

5.6 非阻塞网络复杂度的边界值303

5.6.1 严格非阻塞网络的边界值303

5.6.2 可重排非阻塞网络的边界值305

5.6.3 单边互连网络的边界值307

附录 定理5.2α的证明308

参考文献311

6.1 多级互连网络的控制314

第六章多级互连网络的控制314

6.2 可重排网络的路径控制算法316

6.2.1 方阵分解算法316

6.2.2 循环控制算法321

6.2.3 并行设置算法327

6.2.4 递归分治算法335

6.2.5 改进的终端标记算法341

6.2.6 一般控制算法345

6.3 多级阻塞网络的路径控制算法349

6.3.1 Ω网络的简化控制法349

6.3.2 π网络的改进终端标记法354

6.3.3 洗牌-交换网络多次通过实现任意置换的控制算法357

参考文献365

7.1 排序网络和互连网络367

7.1.1 排序和互连网络的关系367

第七章排序和选择网络367

7.1.2 排序网络的非自适应和非阻塞特性368

7.1.3 用排序网络实现任意的互连函数369

7.1.4 用洗牌交换函数构造排序网络371

7.2 Batcher归并和排序网络371

7.2.1 比较器网络和［0-1原理］371

7.2.2 Batcher奇-偶归并网络376

7.2.3 Batcher双调归并网络381

7.2.4 Batcher排序网络386

7.3.1 布尔对称函数及其性质392

7.3 布尔排序网络和Preparata枚举排序网络392

7.3.2 布尔对称函数在分析和综合排序网络时的应用396

7.3.8 Muller和Preparata的枚举排序网络401

7.4 Ajtai O(nlogn)排序网络404

7.4.1 Aitai排序网络的基本原理404

7.4.2 扩展图405

7.4.3 ε-对分和ε-准排序407

7.4.4 寄存器的分配和划分409

7.4.5 Ajtai算祛的形式描述411

7.5 分组选择网络412

7.5.1 次第选择和区分选择412

7.5.2 分组原理在选择算法中的应用414

7.5.3 分组选择网络417

7.5.4 平衡分组选择网络420

7.6 递归选择网络425

7.6.1 分离原理在递归算法中的应用425

7.6.2 关于选择网络边界值的研究427

7.6.3 Yao的递归选择网络430

7.6.4 平衡递归选择网络的工程设计435

参考文献441

第八章互连网络的设计和应用444

8.1 多级互连网络的图分析与设计法444

8.1.1 多级互连网络的图模型444

8.1.2 多级互连网络的图分析法447

3.1.3 多级互连网络的图设计法453

8.2 开关元件的设计与实现455

8.2.1 2×2交换开关的设计与实现455

8.2.2 4×4交叉开关的设计与实现461

8.3 互连网络在数值运算中的应用470

8.3.1 多项式计算471

8.3.2 矩阵运算472

8.3.3 快速傅里叶变换477

8.4 互连网络在非数值运算中的应用482

8.4.1 并行排序482

8.4.2 图象数据的不规则展开与压缩490

参考文献492