并行算法的设计与分析
2002-11
高等教育出版社
陈国良编著
607
无
高性能计算机是一个国家经济和科技实力的综合体现，也是促进经济、科技发展，社会进步和国防安全的重要工具，已成为世界各国竞相争夺的战略制高点。一些发达国家纷纷制定战略计划，提出很高目标，投入大量资金，加速研究开发步伐。多年来，随着大规模集成电路技术的不断进步，以多CPU为基础的高性能并行计算机得到了迅速的发展，其高端系统正向百万亿次、千万亿次迈进。我国近十年来，对高性能并行计算的研究开发也给予了很大重视，取得了长足进步和可贵经验，研制出了具有相当水平的并行机系统，但与发达国家相比，差距仍然甚大，在高性能并行计算的应用开发与相关的人才培养教育方面尤显不足。如何使高性能并行机系统深入充分地在国民经济、科研和社会应用的发展中发挥作用，实为当务之急，引起人们的普遍关心。由中国科技大学陈国良教授主编的这套丛书，正适应了我国高性能并行计算研究、开发、应用、教育之需。本丛书由《并行算法的设计与分析》、《并行计算机体系结构》和《并行算法实践》三大部分组成，而以《并行计算——结构·算法·编程》为全丛书之提要。该丛书以并行计算为主题，对并行计算的硬件平台（当代主流并行计算机系统）、并行计算的理论基础（并行算法的设计与分析）和并行计算的软件支撑（并行程序设计）全面系统地展开了讨论，内容丰富，取材新近，具有相当的深度和广度，涵盖了并行计算机体系结构和并行算法的理论、设计和实践的各个方面，是国内外不多见的优秀著作。陈国良教授是国家高性能计算中心（合肥）主任，长期从事并行算法和并行计算机体系结构的研究，本套丛书是作者几十年从事教学与科研工作的结晶，是目前国内该领域内容涵盖最为全面的系列著作。它的出版必将对进一步推动我国并行计算学科的发展与应用推广产生深远的影响。
《并行算法的设计与分析（修订版）》在初版基础上，对个别章节进行了修改补充，并在每章的开头，除原有的“内容提要”外，又新增加，“讲授要点”，可作为授课教师的教学指导和参考。《并行算法的设计与分析（修订版）》系统全面地讨论了各种专用和通用并行计算模型上的算法的设计和分析方法。书中以并行计算模型为线索，强调算法、结构和模型三者之间的密切关系，着重介绍了各种最基本、常用和典型的并行算法，同时也力图反映本学科的最新成就和发展趋势。 全书共分二十章，主要内容包括并行算法基础，并行算法的基本设计技术，各种计算模型上的计算机领域中诸多常用计算问题的并行算法的设计和分析方法，最后还讨论了各种并行计算模型的能力、限制、等价性以及与并行计算有关的NC一理论问题。 《并行算法的设计与分析（修订版）》取材丰富，内容系统全面，可作为高等学校计算机及其他信息科学类有关专业高年级学生或研究生的教材．也可供从事计算机科学理论和算法研究的科技人员阅读参考。 《并行算法的设计与分析（修订版）》初版于1994年，曾获教育部高等学校优秀教材一等奖。
陈国良，中国科学技术大学教授，博士生导师，中国科学院院士，1938年6月生于安徽省颍上县，1961年毕业于西安交通大学无线电系计算机专业。1981-1983年在美国普度大学作访问学者，1984年至今曾多次应邀赴东京大学、普度大学、澳大利亚国立大学、新南威尔士大学、昆士兰大学、格里福斯大学、堪萨斯城市大学、依阿华大学、威斯康星大学、Mahat‘ish国际大学、香港理工大学、澳门大学、北京大学、国防科技大学等讲学交流。现任国家高性能计算中心（合肥）主任，国际高性能计算（亚洲）常务理事，中国计算机学会开放系统专业委员会副主任，中国数学会计算数学并行计算专业委员会委员。曾任国家教育部高等学校计算机科学与技术教学指导委员会副主任，全国高等教育电子、电工和信息类专业自考指导委员会副主任，安徽省高校计算机基础课程教学指导委员会副主任，中国计算机学会理事，安徽省计算机学会理事长，全国自然科学名词审定委员会委员，中国科学技术大学计算机系主任。陈国良教授长期从事计算机科学技术的研究与教学工作。主要研究领域为并行算法、并行计算机体系结构和智能计算等。先后承担10多项国家863计划、国家攀登计划、国家自然科学基金、国家973计划、教育部博士点基金等科研项目。取得了多项被国内外广泛引用、达国际先进水平的科研成果，发表论文200多篇，出版著作9部、译著5部，参与主编计算机类辞典、词汇5部，主审、主编计算机类各种教材8部。曾获国家科技进步二等奖、国家级教学成果二等奖、国家教育部科技进步一等奖、中国科学院科技进步二等奖和自然科学三等奖、全国优秀教材一等奖、全国学术著作优秀奖、安徽省科技进步二等奖、国家科委高技术研究与发展计划三等奖、国家教委科技进步三等奖共18项，并获2001年度“国家863计划15周年先进个人重要贡献奖”。陈国良教授在中国科学技术大学执教30多年。长期以来，围绕着并行算法的教学与研究，逐渐形成了一套完整的“算法理论一算法设计一算法实现一算法应用”的并行算法学科体系，营造了我国并行算法类的教学基地。他先后指导培养研究生100多名，其中博士生60名，为我国培养了一批在国内外从事算法研究的高级人才。曾荣获1998年度安徽省教育系统劳动模范、安徽省优秀教师称号、2001年度宝钢教育基金优秀教师特等奖和2003年度第一届高等学校教学名师奖。陈国良教授是我国非数值并行算法研究的学科带头人。他率先创建的我国第一个国家高性能计算中心是我国并行算法研究、环境科学与工程计算软件的重要基地，在学术界和教育界有一定的影响和地位。
第一章 并行算法基础1.1 并行算法的硬件基础1.1.1 当代并行计算机体系结构1.1.2 并行计算机互连网络1.2 并行计算模型1.2.1 SIMD同步并行计算模型1.2.2 MIMD异步并行计算模型1.2.3 其他并行计算模型1.3 并行算法编程模型1.3.1 数据并行模型1.3.2 消息传递模型1.3.3 共享变量模型1.4 并行算法的一般概念1.4.1 并行算法的定义和分类1.4.2 并行算法的表达1.4.3 并行算法的复杂性度量1.4.4 并行算法的WT表示1.4.5 并行算法的同步和通信习题参考文献第二章 并行算法的基本设计技术2.1 平衡树方法2.1.1 求取最大值2.1.2 计算前缀和2.2 倍增技术2.2.1 表序问题的计算2.2.2 求森林的根2.3 分治策略2.3.1 SIMD模型上分治算法的描述2.3.2 SIMD共享存储模型上的FFT算法2.4 划分原理2.4.1 归并原理2.4.2 划分算法与归并算法2.5 流水线技术2.5.1 一维阵列上的流水线归并排序原理2.5.2 一维阵列上的流水线归并排序算法2.6 加速级联策略2.6.1 常数时间求最大值算法2.6.2 双对数时间算法2.6.3 加速级联算法2.7 破对称技术2.7.1 基本着色算法2.7.2 快速3-着色算法2.7.3 最优3-着色算法习题参考文献第三章 比较器网络上的排序和选择算法3.1 Batcher归并和排序网络3.1.1 比较操作和[0，1]原理3.1.2 奇偶归并网络3.1.3 双调归并网络3.1.4 Bateher排序网络3.2 （m，n）一选择网络3.2.1 分组选择网络3.2.2 平衡分组选择网络3.3 AKS排序网络3.3.1 扩展图和划分网络3.3.2 部分排序算法3.3.3 完全排序算法习题参考文献第四章 排序和选择的同步算法4.1 Stone双调排序算法4.1.1 均匀洗牌函数及其性质4.1.2 Stone的观察及其计算模型4.1.3 Stone的并行排序算法4.2 Thompson和Kung双调排序算法4.2.1 处理器编号方式4.2.2 Thompon和Kung的观察4.2.3 Thompon和Kung的双调排序算法4.3 Preparata和Vuilemin双调排序算法4.3.1 算法原理4.3.2 流水线技术4.3.3 算法描述4.4 Akl并行k-选择算法4.4.1 算法原理及物理描述4.4.2 并行k-选择算法4.4.3 算法分析4.5 Valiant并行归并算法4.5.1 归并算法的基本原理4.5.2 k=pq时Valiant归并4.5.3 k=rpq时Valiant归并4.6 Hirschberg并行桶排序算法4.6.1 并行桶排序算法原理4.6.2 并行桶排序算法描述4.7 Preparata并行枚举排序算法4.7.1 枚举排序及其实现方法4.7.2 排序算法的设计和分析4.8 Cole并行归并排序算法4.8.1 使用覆盖和位序的归并方法4.8.2 Cole最佳排序算法4.8.3 算法的正确性证明及分析习题参考文献第五章排序和选择的异步和分布式算法5.1 MIMD-CREW模型上的异步枚举排序算法5.1.1 算法原理和描述5.1.2 算法举例和分析5.2 MIMD.TC模型上的异步快排序算法5.2.1 算法原理和描述5.2.2 算法举例和分析5.3 分布式k-选择算法5.3.1 随机k-选择算法5.3.2 确定k-选择算法5.4 分布式求中值算法5.4.1 分布式中值5.4.2 分布式求中值算法5.5 分布式定序算法5.5.1 分布式计算模型5.5.2 分布式定序算法5.5.3 算法复杂度分析5.6 分布式排序算法5.6.1 模型和定义5.6.2 静态排序算法5.6.3 算法复杂度分析习题参考文献第六章并行搜索6.1 单处理机上的搜索6.1.1 单处理机上的顺序搜索6.1.2 单处理机上有序表的对半搜索6.2 SIMD共享存储模型上有序表的搜索6.2.1 SIMD-EREW模型上的搜索6.2.2 SIMD-CREW模型上的搜索6.3 SIMD共享存储模型上随机序列的搜索6.3.1 sIMD-SM模型上的随机序列搜索.算法描述6.3.2 sIMDS-M模型上的随机序列搜索算法分析6.4 树连接的SIMD模型上随机序列的搜索6.4.1 提问6.4.2 维护6.5 网孔连接的SIMD模型上随机序列的搜索6.5.1 提问6.5.2 维护6.6 MIMD共享存储模型上有序表的搜索6.6.1 AVL树及其顺序插入算法6.6.2 Ellis并行搜索和插入算法习题第七章排列和组合第八章数据传输与选路第九章并行串匹配第十章表达式求值第十一章上下文无关语富的并行识别与语法分析第十二章矩阵运算第十三章数值计算第四章肿和卷积与滤波
插图：
无
不是我自己愿意买的
陈国良院士的杰作为何这么少人关注呢？书不在新，而在于精！