译 者 序

受到能耗的限制，仅靠CPU提升工作频率便可直接提升处理性能的方式已经不再适用。因此设计更多但是频率更低的处理核心便成为处理器发展的方向。多核处理器成为趋势，为了充分利用这些处理核心，必须采用并行方式才可以发掘它们的计算能力。因此并行处理就成了未来提高处理器性能的一种必需的手段。

本书正好可以满足这样一种需求，它提供了关于并行计算与并行算法设计的基本知识与具体的实现案例，可以指导我们设计高效的并行算法。 

本书大概可以分为两大部分，第1～11章侧重于基本的并行算法与知识的介绍，第12～21章侧重于如何利用前面介绍的知识来解决具体的应用问题。其中，第1章对本书中出现的几种重要算法： 串行算法，并行算法，以及正则迭代算法等进行了介绍。第2章介绍了提升单处理器性能的手段。第3章介绍了并行计算机的主要类型，包括： 共享内存，分布式内存，单指令多数据流，脉动阵列以及多核系统。第4章介绍了共享内存多核系统以及紧密相关的两个问题： 高速缓存一致性和处理器同步。第5章介绍了并行处理器的集中内部互联网络： 总线型，星型，环型，以及网络拓扑，探讨了几种更高效的网络类型： 交换阵列，多层级网络。第6章介绍了用于开发并行应用的并发平台软件工具，包括Cilk++、OpenMP以及统一计算设备架构（CUDA) 。第7章介绍了特定算法在并行计算机上的实现方法、算法任务级别的流水线处理等。第8章介绍了NSPA算法的处理方法，NSPA是指无法归类于串行、并行或者是串并行的算法。第9章介绍z-变换的方法。第10章介绍构建迭代算法的依赖图。第11章介绍基于计算几何和线性代数概念的迭代算法分析技术。第12章探讨的是不同的一维（1D）有限脉冲响应（FIR）数码滤波器的并行处理架构。第13章探讨的是不同的二维（2D）和三维（3D）无限脉冲响应（IIR）数码滤波器的并行处理架构。第14章探讨的是不同的多采样率抽样器和中断器的并行处理架构。第15章探讨的是模式识别算法所需的并行处理架构。第16章探讨的是运用于视频压缩的运动估计并行处理架构。第17章探讨的是不同的有限域的2m阶伽罗瓦域乘法的并行处理架构。第18章探讨的是不同的有限域的2m阶伽罗瓦域除法的并行处理架构。第19章探讨的是不同的快速傅里叶变换算法的并行处理架构。第20章探讨了线性方程的求解系统。第21章讨论了使用有限差分法（FDM）来求解偏微分方程的不同的并行处理架构。

本书不是一本特别初级的入门教材，但是有一定计算机专业基础的读者阅读起来是不会有很大障碍的。另外对于需要直接了解某些具体案例的并行处理方法的读者，也可以从本书找到答案或者启发。推荐计算机、电子电气工程等相关专业的高年级本科生、研究生以及从事相关研究的科研人员阅读本书。

在翻译过程中我们尽量追求在忠于原著的同时符合中文的语言习惯，让读者在阅读时感到流畅和自然，对于书中出现的大量的专业术语我们尽量遵循标准的译法，在某些新的概念和名词出现之时我们尽量标注英文原文，方便读者的理解对照。为了尽快完成本书的翻译，有多位本研究组的人员并行参加了不同章节的翻译工作，他们是何禹、刘渊、邬凌超、王汉、芮然、高鹏、杨全、权思及、王璟尧、于卓然。都志辉负责全书的通稿与审校，王汉在参与翻译工作之余还协助我做了大量的协调、组织、排版等方面的工作，在此特表示感谢。

本书的翻译工作受到了国家自然科学基金（61073008）和北京市自然科学基金（4122039和4082016）的支持，在此表示感谢。

特别感谢清华大学出版社的龙启铭编辑，为本书的出版做了大量具体细致的工作，也感谢他对于我一再推迟交稿日期的理解与宽容。

由于本书涉及的领域与内容比较广，虽然我们尽力做到翻译的精准，但是一定会存在不妥甚至错误的地方，恳请读者批评指正。

都志辉2012年8月于清华园算法与并行计算作 者 序作 者 序关 于 本 书  用如今的软件进行并行编程，开发工具所能达到的表现和硬件的潜在表现之间有一种“软件差距”。编程工具需要程序员的人工干预才能将代码并行化。本书的目的是为程序员提供在算法、串行代码以及迭代中寻求并行化时所需的技巧。并行计算在之前只是少数精英企业或集团才能支付得起的昂贵系统，如今已经几乎应用于每一台计算机上。我们可以在笔记本上，台式机上，甚至是智能手机的嵌入式系统中找到并行计算的身影。传统的并行计算旨在进行天气预报、风洞模拟，计算生物学以及信号处理等大型应用。如今，几乎所有的应用程序都涉及并行处理器的操作，而并行处理器已经成为现代计算机的标配。

并行算法可以是为了某一特殊目的特别定制的，也可以是通用的，并行算法的开发从技术角度上可以分为数个层次，如并行程序开发、编译器并行化、多线程操作系统或是超大规模多处理器系统。本书主要关注第一类：为了特殊目的定制的算法及其处理器架构的并行化。我们称此类系统为“核心加速器”。本书的第1～4章是关于上述内容的基础知识，随后的章节中将精选数个案例用于探讨分析。

虽然超大规模集成电路(VLSI)技术能够将更多的处理器整合在同一芯片上，但并行编程技术并没有跟上科技进步的脚步。例如，如今并行硬件系统的应用主要还是为加速特殊目的算法定制而成。这是出于两个实际问题:

 (1)  在当前的计算机平台中多核系统是主流。

 (2)  如在数据加密/解密、图形处理、数字信号处理、滤波等应用中使用的算法多数都是简单串行算法。

介绍本书更简单的方法是先说一说本书中没有涉及哪些内容。本书没有给出体系结构，并行计算机和通用并行算法的具体实现细节。这3个主题中的任何一个都需要很多的优秀的标准教材来详细讲解，例如“Computer Organization and Design"  (D.A. Patterson and J.L Hennessy) ,  "Parallel Computer Architecture"  (D.E. Culler, J.P. Singh, A. Gupta) ,  "Introduction to Algorithms"  (T.H. Cormen, C.E. Leiserson, R.L. Rivest) 。我希望多数读者都能在阅读本书之前学习这些伟大的作品，若我之前列出的书单不够翔实明确也请大家见谅。 

本书阐述了如何为实现特定的算法，系统地构建并行体系结构。此书中出现的算法也可以用于实现通用算法，无论并行与否。

本书适合计算机工程、电气工程和计算机科学行业的研究人员和研究生。本书需要用到线性代数和数字信号处理的基础知识。

本书的目的是：

(1) 对几种表述方法进行解释，如并行算法的依赖图或依赖矩阵。

(2) 探讨进程任务的调度方案，同时要符合输入和输出数据时序，可以流水线处理数据，并能将数据广播到所有处理器。

(3) 探讨处理单元的任务分配方案。

章 节 预 览

第1章主要内容包括：

 定义了本书中出现的几种重要算法，即串行算法、并行算法以及正则迭代算法。

 为并行计算机设计并行算法时需要考虑两者间的联系。

 用加速因子和通信开销来量化并行化带来的优势。

 举例说明并行计算机的两种应用。

第2章主要介绍提升单处理器性能的手段：

 提升时钟频率。

 ALU（算术逻辑单元）结构并行化。

 流水线作业。

 超长指令字（VLIW) . 

 超大规模计算以及多线程。

第3章主要介绍并行计算机的主要类型：共享内存、分布式内存、单指令多数据流（SIMD) 、脉动阵列以及多核系统。

第4章主要介绍共享内存多核系统以及紧密相关的两个问题，即高速缓存一致性和处理器同步。

第5章主要介绍并行处理器的内联网络的主要类型，即总线型、星型、环型以及网络拓扑，探讨了几种更高效的网络类型，如开关阵列、多层级网络。

第6章主要介绍了用于开发并行应用的并发平台软件工具，包括Cilk++、OpenMP以及统一计算设备架构（CUDA) 。这些工具都只能解决相对简单的数据依赖问题，数据的完整性，正确性和任务执行的时间调度等问题都应该由编程者自己来决定。本书中出现的一些技巧能帮助编程者解决串行算法和正则递归算法中出现的一些问题。

第7章主要内容包括：

 特定算法在并行计算机上的实现方法。包括独立环的调度，非独立环的传播，非独立换的展开，分治策略。

 算法任务级别的流水线处理。

 利用坐标旋转数码计算机（CORDIC）实现算法。

第8章主要介绍了非串行算法（NSPA）的处理方法，非线性算法是指无法归类于串行、并行或者是串并行的算法。多数通用算法都属于NSPA，它们的并行性不明显，任务依赖图比较复杂。本章教授了提取此类算法中的并行部分的一种正规且有力的方法，此方法的好处在于将一个算法运行在一台并行计算机上时利用该方法可以有效提升算法的效率，并且此方法还可以估算出达到最大执行加速比所需的并行处理器的数量。

在该方法中，我们用任务W、并行度P和深度D来量化某个NSPA的并行化程度。

第9章主要内容包括：

 z-变换的方法。

 z-变换应用于数码滤波器以及不同并行平台上多采样率系统的实现。

此类应用一般都是在z域进行的，所以此类应用的软硬件实现也要在z域中进行研究。

第10章主要内容包括：

 构建迭代算法的依赖图。

 此方法应用于不超过索引数量不超过3个的迭代算法。

 利用该依赖图，算法中的任务可以自动分配至软件线程和硬件处理器。

第11章主要介绍了基于计算几何和线性代数概念的迭代算法分析技术。此方法适用于当迭代算法的索引数多于3个的情况。例如二维（2D）和三维（3D）数码滤波器。对于此类算法，我们用一个多维空间中的凸壳和相关的依赖矩阵来表示算法中的每一个变量。该矩阵的零向量空间帮助我们对不同的并行软件线程和硬件处理单元进行分配和时间调度。

第12章探讨的是不同的一维（1D）有限脉冲响应（FIR）数码滤波器的并行处理架构。首先，运用11章中的计算几何的知识我们可以构建此系统的硬件结构。之后利用第9章中的z-变换了实现可能的软件并行处理架构。

第13章探讨的是不同的二维（2D）和三维（3D）无限脉冲响应（IIR）数码滤波器的并行处理架构。我们运用z-变换来实现此类滤波器。

第14章探讨的是不同的多采样率抽样器和中断器的并行处理架构。此类算法在无线通信中广泛应用。运用的技术是第10章的依赖图。

第15章探讨的是模式识别算法所需的并行处理架构。此类算法在无线通信中广泛应用。运用的技术是第10章的依赖图。

第16章探讨的是运用于视频压缩中的不同的运动估计的并行处理架构。为了适应这种复杂的算法，我们将问题简化，分为几个层次。运用的技术是第10章的依赖图。

第17章探讨的是不同的有限域的2m阶伽罗瓦域乘法的并行处理架构。运用的技术是第10章的依赖图。

第18章探讨的是不同的有限域的2m阶伽罗瓦域除法的并行处理架构。运用的技术是第10章的依赖图。

第19章探讨的是不同的快速傅里叶变换算法的并行处理架构。会运用流水线技术来实现该算法。

第20章探讨线性公式的求解系统。该系统有直接和间接两种实现方法。本章讨论的是如何将前置直接替换技术并行化。中间会涉及一个利用Givens公式将稠密矩阵转换为等价的三角矩阵的算法。本章也会讨论逐次超松弛（SOR）简介求解方法的并行化。

第21章讨论使用有限差分法（FDM）来求解偏微分方程的不同的并行处理架构。在许多工程和科学应用中都对此类方程的求解有很大的需求。

鸣  谢

我希望在此表达我深深的谢意。

感谢埃及的Ain Shams大学的M.W.El-Kharashi博士在本书筹备过程中提供的建议和鼓励。我也在此对下述的同僚表达我诚挚的谢意，没有你们的帮助我不可能完成此书：

Dr. Esam Abdel-Raheem        Dr. Turki Al-Somani  

University of Windsor, CanadaAl-Baha University, Saudi Arabia   

Dr. Atef IbrahimDr. Mohamed Fayed  

Electronics Research Institute, Egypt Al-Azhar University, Egypt   

Mr. Brian McKinneyDr. Newaz Raiq  

ICEsoft, Canada ParetoLogic, Inc., Canada   

Dr. Mohamed RehanDr. Ayman Tawik  

British University, EgyptAjman University, United Arab Emirates   

忠告与建议

本书覆盖了关于并行计算的许多方面。很有可能在本书中出现各种错误与疏漏。万望其他领域的学者和工程师能就本书的内容，行文和章节布置等方面提出宝贵意见。同时也欢迎来信提出问题和案例（若非原创请标明引用出处）. 

请您将您的宝贵意见发送电邮至：fayez@uvic. 

来电、来信或传真请按照以下方式联络：

Dr. Fayez Gebali  

Electrical and Computer Engineering Department 

University of Victoria, Victoria, B.C., Canada V8W 3P6 

电话: 250-721-6509 

传真: 250-721-6052算法与并行计算缩 写 表缩 写 表

1-D     one-dimensional 

2-Dtwo-dimensional  

3-Dthree-dimensional  

ALUarithmetic and logicunit  

AMPasymmetric multiprocessing system  

APIapplication program interface  

ASAacyclic sequential algorithm  

ASICapplication-specificintegrated circuit  

ASMPasymmetric multiprocessor  

CADcomputer-aided design  

CFDcomputational fluid dynamics  

CMPchip multiprocessor  

CORDICcoordinate rotation digital computer  

CPIclock cycles per instruction  

CPUcentral processing unit  

CRCcyclic redundancy check  

CTcomputerized tomography  

CUDAcompute unified device architecture  

DAGdirected acyclic graph  

DBMSdatabase management system  

DCGdirected cyclic graph  

DFTdiscrete Fourier transform  

DGdirected graph  

DHTdiscrete Hilbert transform  

DRAMdynamic random access memory  

DSPdigital signal processing  

FBMAfull-search block matching algorithm  

FDMfinite difference method  

FDMfrequency division multiplexing  

FFTfast Fourier transform  

FIRfinite impulse response  

FLOPSfloating point operations per second  

FPGAfield-programmable gate array  

GF(2m)Galois field with 2m elements  

GFLOPSgiga floating point operations per second  

GPGPUgeneral purpose graphics processor unit  

GPUgraphics processing unit 

HCORDIChigh-performance coordinate rotation digital computer  

HDLhardware description language  

HDTVhigh-definition TV  

HRCThigh-resolution computerized tomography  

HTMhardware-based transactional memory  

IAiterative algorithm  

IDHTinverse discrete Hilbert transform  

IEEEInstitute of Electrical and Electronic Engineers  

IIRinfinite impulse response  

ILPinstruction-level parallelism  

I/Oinput/output  

IPintellectual property modules  

IPInternet protocol  

IRinstruction register  

ISAinstruction set architecture  

JVMJava virtual machine  

LANlocal area network  

LCAlinear cellular automaton  

LFSRlinear feedback shift register  

LHSleft-hand side  

LSBleast-significant bit  

MACmedium access control  

MACmultiply/accumulate  

MCAPIMulticore Communications Management API  

MIMDmultiple instruction multiple data  

MIMOmultiple-input multiple-output  

MINmultistage interconnection networks  

MISDmultiple instruction single data stream  

MIMDmultiple instruction multiple data  

MPImessage passing interface  

MRAPIMulticore Resource Management API  

MRImagnetic resonance imaging  

MSBmost significant bit  

MTAPIMulticore Task Management API  

NISTNational Institute for Standards and Technology  

NoCnetwork-on-chip  

NSPAnonserial-parallel algorithm  

NUMAnonuniform memory access  

NVCCNVIDIA C compiler  

OFDMorthogonal frequency division multiplexing  

OFDMAorthogonal frequency division multiple access  

OSoperating system  

P2Ppeer-to-peer  

PAprocessor array  

PEprocessing element 

PRAMparallel random access machine  

QoSquality of service  

RAIDredundant array of inexpensive disks  

RAMrandom access memory  

RAWread after write  

RHSright-hand side  

RIAregular iterative algorithm  

RTLregister transfer language  

SEswitching element  

SFswitch fabric  

SFGsignal flow graph  

SIMDsingle instruction multiple data stream  

SIMPsingle instruction multiple program  

SISDsingle instruction single data stream  

SLAservice-level agreement  

SMstreaming multiprocessor  

SMPsymmetric multiprocessor  

SMTsimultaneous multithreading  

SoCsystem-on-chip  

SORsuccessive over-relaxation  

SPstreaming processor  

SPAserial-parallel algorithm  

SPMDsingle program multiple data stream  

SRAMstatic random access memory  

STMsoftware-based transactional memory  

TCPtransfer control protocol  

TFLOPStera floating point operations per second  

TLPthread-level parallelism  

TMtransactional memory  

UMAuniform memory access  

VHDLvery high-speed integrated circuit hardware description language  

VHSICvery high-speed integrated circuit  

VIQvirtual input queuing  

VLIWvery long instruction word  

VLSIvery large-scale integration  

VOQvirtual output queuing  

VRQvirtual routing/virtual queuing  

WANwide area network  

WARwrite after read  

WAWwrite after write  

WiFiwireless fidelity