《并行程序设计语言和模型》

目 录1

第一章绪论1

§1.1并行处理计算机1

1.1.1并行处理1

1.1.2并行处理计算机2

§1.2并行程序设计语言和模型4

1.2.1并行程序设计存在的问题4

1.2.3新的并行程序设计语言5

1.2.2传统串行语言的扩展5

1.2.4独立于结构的并行程序设计模型6

第二章并行程序设计语言7

§2.1 Occam语言7

2.1.1 Transputer简介7

2.1.2 Occam语言8

2.1.3 Occam并行程序设计实例16

§2.2并行C语言19

2.2.1概述19

2.2.2并行C语言20

2.2.3并行C程序设计实例24

§2.3 并行FORTRAN语言27

2.3.1并行FORTRAN语言27

2.3.2并行FORTRAN程序设计实例29

§2.4 并行关系LISP语言（PARALATION LISP）32

2.4.1 COMMON LISP简介32

2.4.2并行关系LISP代码33

2.4.3并行关系LISP词汇39

3.1.1什么叫并行关系模型46

3.1.2为什么要提出并行关系模型46

第三章并行关系模型46

§3.1 引言46

3.1.3并行关系模型简介47

§3.2数据结构与域49

3.2.1域——新的顺序数据结构49

3.2.2域的性质51

3.2.3并行关系的性质51

3.2.5域的读入52

3.2.4索引52

3.2.6局部性53

§3.3逐元求值53

3.3.1副作用54

3.3.2同步54

3.3.3 elwise错误55

3.3.4 elwise变量的词法指定57

3.3.5 elwise和λ表达式58

§3.4通信59

3.4.1匹配与映象60

3.4.2 目标结点之间的相互作用64

§3.5词典查询代码与术语65

3.5.1词典查询代码65

3.5.2库函数：vref66

3.5.3库函数：choose68

3.5.4 elwise的约束缩写69

3.5.5把“域”作为序列处理70

3.6.1筛选质数71

§3.6程序设计实例71

3.6.2集合上的操作72

§3.7并行关系模型的通用性74

3.7.1提高并行关系模型通用性的策略74

3.7.2处理中的问题及其解决方法74

3.7.3通信中的问题及其解决方法75

3.7.4增强精确性75

3.8.1什么是形状76

§3.8形状76

3.7.5进程间的同步76

3.8.2并行关系模型的形状79

3.8.3应用84

第四章基于并行关系模型的程序设计87

§4.1引言87

§4.2层次结构88

4.2.1嵌套循环88

4.2.2搜索状态空间89

4.2.3模型与欲解问题的结构97

§4.3程序设计风格98

4.2.4局部性的继承98

4.3.1副作用实例99

4.3.2作用式风格100

4.3.3语言对程序设计风格的影响101

§4.4程序设计的其他原则102

4.4.1简明性、规范性和正交性102

4.4.2零－壹－无穷103

4.4.3信息保护103

4.4.4费用局部化104

4.4.7信息隐蔽105

4.4.5可移植性105

4.4.6结构105

4.4.8标号106

4.4.9自动化和抽象106

§4.5程序复杂性107

4.5.1并行复杂性108

4.5.2并行关系程序的复杂性109

§4.6传统程序设计的困境111

4.7.1质数生成器112

§4.7并行关系模型的应用实例112

4.7.2快速分类算法114

4.7.3在I/O系统中的应用122

4.7.4最短路径算法125

§4.8形式化的描述128

4.8.1概述128

4.8.2操作语义130

4.8.3为提供方便而设置的语义141

5.1.1为什么需要描述实现145

§5.1 引言145

第五章并行关系模型的实现策略145

5.1.2何种语言为基语言146

5.1.3虚拟处理器146

§5.2数据结构和域的实现147

5.2.1嵌套域148

5.2.2可继承的局部性149

5.2.3映象表示150

5.3.1 SIMD elwise151

§5.3逐元求值的实现151

5.3.2 MIMD elwise152

5.3.3信息传递152

5.3.4共享内存154

5.3.5并行关系结点间的干扰154

§5.4匹配与移动的实现155

5.4.1 匹配155

5.4.2利用标准映象实现高效串行移动158

5.4.4并行硬件的效率160

5.4.3并行移动160

§5.5库函数的实现161

5.5.1概述161

5.5.2习语提取162

§5.6并行关系模型的实现162

5.6.1概述162

5.6.2理想目标机162

5.6.3连接机并行关系LISP的编译器163

6.1.2通用性164

6.1.1等价模型164

§6.1并行关系模型的重要作用164

第六章多种并行程序设计模型的比较164

6.1.3非冗余性167

6.1.4几种可选择的并行关系模型168

6.1.5并行关系模型的贡献170

§6.2并行关系模型与其他几种并行程序设计模型的比较173

6.2.1语言比较173

6.2.2 APL：早期的显式并行模型173

6.2.3PRAM/MIMD程序设计模型175

6.2.4 SIMD程序设计模型176

6.2.5隐式并行模型180

6.2.6面向对象的语言183

6.2.7 C*语言183

6.2.8连接机LISP184

6.2.9 Multi LISP187

6.2.10 FORTRAN 8x 数组扩展187

6.2.11关系数据库语言189

6.2.12并行性和语言设计190