串行算法并行化基础

出版时间：2008-6  出版社：科学出版社  作者：胡玥  页数：116  
Tag标签：无  

前言

当今，高性能计算机系统令人注目。可惜高性能计算机系统两个重要难点至今没有解决：一是不好用，二是效率低。20世纪60年代研制的“单指令流一多数据流”ILLIAC-4机（最早的巨型机）就遇到了这样的问题，因为它在运行中的并行、存储和通信等全部需要用户进行人工处理，因此很不好用。科研人员通过改进系统结构、引入向量语言和高级编程语言自动向量化，解决了“不好用”的问题，同时“效率低”的问题也得到了缓解。而当今的高性能计算机系统是“多指令流一多数据流”，其在运行中的并行、存储和通信等还是由用户来人工处理，所以“不好用”的问题依然存在，“效率低”的问题由于并行台数激增而更加严重、更加突出了。本书一方面借助于“单指令流一多数据流”巨型机的历史经验，有助于寻找“多指令流一多数据流”高性能计算机系统“不好用”的问题的解决方法；另一方面通过串行算法并行化的基本方法的介绍，希望有助于读者独立处理各种实际问题的并行化，进而有效地提高计算效率。借本书出版介绍一下“为什么研究串行算法并行化”，和回答一下一些研究生提问的问题：“如何寻找科研课题”。一、为什么研究串行算法并行化为什么研究串行算法并行化呢？这要从我们接受亿次机设计任务说起。工973年3月中国科学院计算所老所长阎沛霖带我到国防科工委钱学森那里接受亿次机设计任务开始，两个月后，也就是1973年5月我们提出了可行的解决方案，并正式承担了亿次巨型机设计任务及其模型机——中国第一台向量计算机757的研制任务。

内容概要

　　《串行算法并行化基础》第1章首先介绍这些有关串行算法并行化基本概念。并行计算是在一定的并行计算系统的类型上实现的，所以第2章介绍一些基本并行计算系统类型。多指令流多数据流巨型机是当今高性能计算机系统的主流，许多大部头的书都有详细论述，本专著就不重复。单指令流多数据流巨型机是20世纪60年代末到80年代并行计算的高性能计算机系统的主流，其中许多设计思路在当今仍然不失其价值。它们很容易使用的原因是对应的并行计算模式可以规范到十分自然的向量运算形式，即有一个理想的描述语言：向量语言。第3章就介绍一种向量语言。多指令流多数据流巨型机的并行计算模式目前难于规范到十分自然的运算形式，也就是尚不存在一个理想的描述语言。通过向量语言的了解，或许有助于今后多指令流多数据流高性能计算机系统理想的描述语言的诞生。第4章介绍串行算法并行化的各种类型。第5章到第7章介绍具体的、典型的串行算法的并行化，包括两路归并、多路归并、排序和广义一阶递推。最后一章（第8章）介绍一类广函数一一纵横矩阵加工广数。　　引入并行是为了提高计算速度，到底能不能有效提高计算速度？如何度量计算速度的提高及其有效性？这些需要通过一些基本概念来刻画。

作者简介

高庆狮，1957年毕业于北京大学数学力学系。历任中国科学院计算技术研究所研究员、中科院技术科学部委员。擅长巨型电子计算机总体功能设计、并行算法和人工智能。完成了我国第一台晶体管大型电子计算机的功能总体设计和逻辑设计。是我国自行设计的第一台电子管大型计算机的体系功能设计和逻辑设计负责人之一。负责完成中国第一台每秒十万镒以上的晶体管大型计算机的体系功能设计。1973年提出纵横加工流水线向量机设计思想，领导完成了我国第一台千万次大型向量计算机的系统功能设计。著有《向量巨型机》等。

书籍目录

第0章 绪论0.1 计算科学0.2 为什么要并行计算0.3 巨型机、高性能计算机本质特征：并行计算0.4 巨型机、高性能计算机基本矛盾：台数与计算效率的矛盾0.5 并行运算和并行数据传送0.6 并行执行方式和重叠执行方式0.7 并行算法与串行算法并行化0.8 巨型机、高性能计算机的关键技术0.9 数据相关和控制相关第1章 串行算法并行化的基本概念1.1 题目的规模与计算工作量N1.2 题目的计算时间T1.3 题目最快串行计算算法C01.4 题目在并行计算模型M（S）下并行计算算法B1.5 题目在M（S）下并行计算算法B的计算速度：Vb，M（s）（N）1.6 在并行计算模型M（S）下题目并行计算算法B的加速比1.7 在并行计算模型M（S）下题目并行计算算法B的效率1.8 并行算法B的计算复杂性1.9 常数效率并行算法1.10 在某些讨论中的算法分类1.11 并行计算台数S对并行计算速度的影响及串行算法并行化的意义第2章 执行并行计算算法的并行计算机系统结构模型2.1 并行算法实现的两要素之一：并行传送2.2 单指令流一单数据流（SIMD）计算机2.3 SIMD二维阵列机2.4 流水线向量机2.5 第二代巨型机：纵横加工（分段处理）流水线向量机2.6 细胞结构化虚共存纵横加工向量机2.7 多维立方体机2.8 多指令流一多数据流系统MIMD2.9 内部互联网络2.10 通用或专用计算网络2.11 PRAM并行随机访问计算机2.12 可变总线结构2.13 素数存储系统2.14 分段线性变换存储系统第3章 向量语言3.1 数据类型与数据结构3.2 向量基本运算3.3 向量或者数组中的向量3.4 可以用硬件实现的控制向量3.5 变长向量运算3.6 向量语言的扩充3.7 向量高级语言第4章 串行算法并行化方法综述与比较4.1 串行算法并行化之一：多分法方法4.2 串行算法并行化之二：倍增法4.3 串行算法并行化之三：纵横加工法4.4 串行算法并行化效率比较4.5 串行算法并行化之四：利用软件、硬件和软件硬件结合的优化方法4.6 串行算法并行化之五：利用硬件直接实现的控制向量一第5章 两路归并与分类串行算法并行化5.1 归并与排序的快速串行算法5.2 归并基本定义与定理5.3 K E Batcher的Odd-even并行归并网络5.4 根据归并基本定理所构造的快速并行归并算法5.5 K E Batcher的Bitonic归并算法5.6 利用并行归并来实现并行排序5.7 归并与排序串行算法并行化的OPTIMAL并行算法之一：纵横并行归并算法5.8 归并与分类串行算法并行化的OPTIMAL并行算法之二：k-维并行归并算法5.9 在理论模型上的排序第6章 多路归并串行算法并行化第7章 一类一阶递推串行算法并行化第8章 一类广函数：纵橫矩加工广函数附录 （m,N）选择问题的纵横并行算法例子参考文献

章节摘录

插图：2.6.2 虚共存的提出由于器件迅速发展，不仅使得通过扩大台数解决某些类型大型计算问题的实现性不断增加，而且也使得合理经济选择台数不断增加。对集中存储的向量机而言，扩大台数的主要困难是运算细胞单元与公共存储系统之间的数据传输，这是瓶子口。因此，要扩大运算并行台数，最方便的方法是分散存储。存储系统分散到各个细胞单元，这就是通常的阵列机结构。这样做不仅便于扩大并行台数，而且还有利于适应超大规模集成电路的发展，所以说，从物理结构的角度，希望采用分散存储的阵列机结构。但是，通常的阵列机，程序编制比较困难，不仅要考虑数据从哪个细胞单元中取出，需要在细胞单元之间作怎么样的移动，而且还要考虑如何安排使得这种移动最少。因此，可以说从使用的角度，希望使用具有集中统一的存储系统的向量机，能够使用高级语言编制程序，并能在一个统一的存储空间中编制程序，而不考虑哪个分量在哪个细胞单元的存储器中。能否设计一个计算系统，使其既具有阵列机便于扩大台数和适于超大规模集成电路的发展的优点，又具有向量机便于使用高级向量语言和可以在一个统一的存储空间编制程序的优点，回答是肯定的。这就是说，可以设计一个计算机系统，它同时具有阵列机和向量机的优点，而同时又克服了阵列机和向量机的缺点。单指令流一多数据流虚共存细胞结构纵横加工向量机方案，给这个肯定的回答一个构造性的证明。具体请参考文献（高庆狮1979）。2.6.3 单指令流一多指令流混合的向量语言中的函数向量在单指令流一多指令流混合的向量语言中“函数向量”的每一个分量可以是不同的标量函数。在细胞结构化虚共存纵横加工向量机中，各个不同的标量函数分量是通过多指令流的各个不同的指令流来实现（参看3.6 节）。进一步研究请参考文献（高庆狮1979），这里从略。

编辑推荐

《串行算法并行化基础》由科学出版社出版。