并行算法并行算法及其应用及其应用计算机学院卢光辉Email:*Tel:*主楼B1-*教学安排：教学安排：2020学时学时教材教材：孙世新，卢光辉等，孙世新，卢光辉等，孙世新，卢光辉等，孙世新，卢光辉等，并行算法及其应用并行算法及其应用并行算法及其应用并行算法及其应用参考书参考书：黄铠、徐志伟著，陆鑫达等译黄铠、徐志伟著，陆鑫达等译. .可扩展并行计算可扩展并行计算技术、结构与编程技术、结构与编程. .机器工业出版社，机器工业出版社，2000. 2000. 李李晓晓梅梅、蒋蒋增增荣荣等等著著. .并并行行算算法法, ,湖湖南南科科学学技技术术出版社，出版社，1992.1992.陈陈国国良良. .并并行行算算法法的的设设计计与与分分析析. .高高等等教教育育出出版版社，社，2002.11. 2002.11. 序言1.什么叫并行算法？ 一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。2.并行算法与串行算法的关系：P1P2P33. 并行与并发的关系：并行并发并发是指两个或者多个事件在同一时间间隔内并发是指两个或者多个事件在同一时间间隔内发生。在单处理机系统中，每一时刻仅能有一道发生。在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。这些程序是分时交替执行。4. 并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明网络；并行更注重性能，而分布式更注重透明共享。共享。 5.并行与网格计算（普适计算）的关系： 网格通过网络连接地理上分布的各类计算资源、存储资源、通信网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这些资源和功能。它们与并拟的高性能计算环境，让人们透明地使用这些资源和功能。它们与并行计算存在规模上的差异。行计算存在规模上的差异。 6 .并行与云计算的关系： 云计算以开放的标准和服务为基础，以互联网为中心，提供安全、云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片快速、便捷的数据存储和网络计算服务，让互联网这片“ “云云” ”上的各上的各种计算机共同组成数个庞大的数据中心及计算中心。云计算把计算及种计算机共同组成数个庞大的数据中心及计算中心。云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都来自互联网上的虚拟化计算中心，该数应用软件、开发平台等资源都来自互联网上的虚拟化计算中心，该数据中心负责对分布在互联网上的各种资源进行分配、负载的均衡、软据中心负责对分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。件的部署、安全的控制等。7. 为什么要研究并行算法？（1）CPU的发展速度：Moore Law。（2）深蓝与国际象棋大师：1996年2月，国际象棋世界冠军卡斯帕罗夫与IBM开发的“深蓝”计算机对奕，卡斯帕罗夫最终四比二战胜 “深蓝”（IBM，它带有256个处理器 ）。 1997年5月， “深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）8.8.国内外发展现状国内外发展现状 （1 1）国内发展情况：）国内发展情况：20102010年年1111月中国国防科学月中国国防科学技术大学研制的技术大学研制的“ “天河天河天河天河1A1A” ” 运算速度达每秒运算速度达每秒25702570万亿次万亿次, ,有有186186，368368个核，在第三十六期全个核，在第三十六期全球超级计算机球超级计算机TOP500TOP500中曾排名第一，中曾排名第一，20122012年年6 6月月排名第排名第5 5。 “ “863863” ”计划、计划、“ “973973” ”计划、国家自然科学计划、国家自然科学基金都对并行计算十分重视。基金都对并行计算十分重视。 （2 2）国外发展情况）国外发展情况 20122012年年6 6月，月， Rank 1: Rank 1: 美国美国IBMIBM的的“ “BlueGene/QBlueGene/Q” ”，1,572,8641,572,864个个核，核，运算速度已运算速度已达达16,32416,324万亿次万亿次。 最新见附表（附表中计算速度单位为Gflops/s）。美国HPCC、ASCI计划； 早在20世纪80年代末期，美国政府就制定了一项高性能计算计划（Federal High Performance Computing Program）。旨在发展美国的的高性能计算机并将其用于解决一些有关国民经济与国家安全的重大问题，后来，随着通信技术的发展，这个计划被修改为高性能计算与通信计划（HPCC）。 后来，美国政府为了把HPCC计划向更高、更深入的层次发展，又提出了三个计划：推动战略计算计划（Accelerated Strategic Computing Initiative, ASCI）其目的是为模拟核试验和核武器储备管理提供足够的计算能力。高性能计算现代化计划（HPC Modernization Program）。 其目的是为了改善国防研究的计算，降低武器设计、测试费用，保持美国在军事上的优势。其任务是建立16个由高速网络连接的高性能计算中心。每秒千万亿次浮点计算计划（Petaflops Computing） 这是美国的前瞻性研究计划。日本真实世界计算计划: 日本早在20世纪90年代初就制定了这一项雄心勃勃的计划。这项计划的目的在于超越信息处理的原有框架，研制超并行、超分布的光计算机系统，并在神经科学和认知科学等方面取得重大进展。真实世界内的信息包括图像、声音、触觉、符号型知识数据等，种类极为繁杂、信息量非常庞大。另外，日本1997年计划开发的“地球模拟器”已于2002年研发成功，成为一度领先的世界最快的超级计算机。 （3）并行算法的发展状况：（4）并行计算模型发展状况：LogP，LogGP，BSP（5）并行开发环境发展状况：PVM、MPI、HPF、OpenMP（利用超线程技术，针对共享内存多处理器体系结构并行计算机）、OpenCL（支持多核、GPU、DSP等硬件平台，【目前主要建立在CUDA架构上】 ）全书共分为三个部分：1.基础理论:主要介绍并行计算平台、并行算法概述、并行程序开发环境等；2.基础应用：主要包含矩阵运算、快速傅立叶变换、卷积运算、数字滤波、离散余弦变换、哈达玛变换、2D离散小波变换、数字图像处理等方面的并行算法设计、分析与测试；3.实际应用:主要介绍并行算法在电磁散射中的应用和无线电波参数联合估计中的应用。第一章 并行计算平台 并行计算机分类并行计算机分类1. SISD,Single Instruction Stream & Single Data Stream:特征：串行的和确定的。 指令系统:CISC, RISC 2. SIMD,Single Instruction Stream & Multiple Data Stream:特征：同步的；确定的；适合于指令适合于指令/ /操作操作级并行并行。 1)阵列处理机（资源重复）;2)流水线处理机（时间重叠）.3. MISD,Multiple Instruction Stream & Single Data Stream : 4. MIMD,Multiple Instruction Stream & Multiple Data Stream共享存储MIMD，也称对称多处理机（SMP，Symmetry MultiProcessors） 适合于适合于小粒度小粒度并行并行分布式共享存储MIMD，也称为非一致内存访问（NUMA, Non-Uniform Memory Access） 适合于适合于中小粒度中小粒度并行并行分布式存储MIMD 1). MPP (Massively Parallel Processing) ASCI Option Red、Inter Paragon、Meiko CS-2、nCUBE、CM-5、曙光1000、神州-巨型机 适合于适合于中小粒度中小粒度并行并行2). Cluster特点： 适合适合于粗粒度于粗粒度并行并行多核处理器：SMPIntel的MMX、SSE：SIMD电子科大IBM中心IBM EServer Z900:Cluster附TIs C64+:哈佛（Harvard ）结构 、SIMD程序：程序： ADD .L2 val_lb18b,m0_7,m1_7 ; |82| ADD .L2 val_lb18b,m0_7,m1_7 ; |82| | MPYU .M2 m1_6,qp_tab,m2_6$1 ; |101| | MPYU .M2 m1_6,qp_tab,m2_6$1 ; |101| | SHR .S2 m1_4,0x13,m1_4 ; |94| | SHR .S2 m1_4,0x13,m1_4 ; |94| | SHR .S1 m1_3,0x13,m1_3 ; |95| | SHR .S1 m1_3,0x13,m1_3 ; |95| ADD .D2 qp_constb,m2_7,m2_7 ; |109| ADD .D2 qp_constb,m2_7,m2_7 ; |109| | SHR .S2 m2_6,0xf,m3_6 ; |119| | SHR .S2 m2_6,0xf,m3_6 ; |119| | ADD .L1 qp_consta,m2_3,m2_3 ; |113| | ADD .L1 qp_consta,m2_3,m2_3 ; |113| | SHR .S1 m1_2,0x13,m1_2 ; |96| | SHR .S1 m1_2,0x13,m1_2 ; |96| | MPYU .M1X m1_1,qp_tab,m2_1 ; |106| | MPYU .M1X m1_1,qp_tab,m2_1 ; |106| | OR .L2 val_1,sign5,sign5 ; |144| | OR .L2 val_1,sign5,sign5 ; |144| | MPY2 .M2 x2_54,val_2B1b,x5:x4 ; |69| | MPY2 .M2 x2_54,val_2B1b,x5:x4 ; |69| | LDDW .D1T1 *-scaleM(8),sm3:sm2 ; |61| | LDDW .D1T1 *-scaleM(8),sm3:sm2 ; |61| PACK2 .L2 m4_7,m4_6,m76 ; |170| PACK2 .L2 m4_7,m4_6,m76 ; |170| | PACK2 .L1 m4_3,m4_2,m32 ; |172| | PACK2 .L1 m4_3,m4_2,m32 ; |172| | OR .D1X val_1,sign2,sign2 ; |147| | OR .D1X val_1,sign2,sign2 ; |147| | MPYU .M2X x6,sm2,m0_6 ; |74| | MPYU .M2X x6,sm2,m0_6 ; |74| | SHL .S2 x76,0x10,sign6 ; |132| | SHL .S2 x76,0x10,sign6 ; |132| | SHL .S1 x10,0x10,sign0 ; |135| | SHL .S1 x10,0x10,sign0 ; |135| | MPY2 .M1 x2_10,val_2B1a,x1:x0 ; |71| | MPY2 .M1 x2_10,val_2B1a,x1:x0 ; |71| 执行时的最小单位是执行时的最小单位是 threadthread；数个；数个 thread thread 可以组成一个可以组成一个 blockblock；一个；一个 block block 中的中的 thread thread 能存取同一块能存取同一块共享的内存，而且可共享的内存，而且可以快速进行同步的动以快速进行同步的动作；不同作；不同 block block 中的中的 thread thread 无法存取同一无法存取同一个共享的内存，因此个共享的内存，因此无法直接互通或进行无法直接互通或进行同步；执行相同程序同步；执行相同程序的的 blockblock，可以组成，可以组成 gridgrid。GPU并行:CUDA(Compute Unified Device Architecture ),SIMD/SMPnVIDIA GTX200核心核心 Tesla GPGPUTesla GPGPU可以看作之前的可以看作之前的Nvidia QuadroNvidia Quadro专业卡的通用专业卡的通用计算版本计算版本 GTX200GTX200的的240240个流处理器被个流处理器被分为分为1010组并行的材质处理簇组并行的材质处理簇TPCTPC（ Texture Processing Texture Processing Cluster Cluster ） 每个每个TPCTPC由由3 3个流处理器单元个流处理器单元SMSM（ Streaming Streaming Multiprocessors Multiprocessors ）组成）组成 每个每个SMSM由由8 8个流处理器个流处理器SPSP（Stream ProcessorStream Processor）；）；每个每个TPCTPC内的内的2424个流处理器个流处理器共享共享L1L1缓存（缓存（TPCTPC的核内内的核内内存）存） 每个每个SMSM可以支持可以支持10241024个并个并行线程行线程 整个整个GTX200GTX200核心可以支持核心可以支持3072030720个线程个线程定义：定义：network diameternetwork diameter:bisection widthbisection width：并行计算机的处理器连接方式并行计算机的处理器连接方式 一.总线结构总线结构 二.一维阵列结构一维阵列结构 三. 网格结构网格结构 四.超立方体结构超立方体结构 五.蝶网几个并行系统简介1.Cluster(PC,Workstation(NOWS)2.曙光系列（1000A,2000）并行计算模型并行计算模型 LogP模型与模型与LogGP模型模型：L:Latency O:overhead G:GapP:Processor BSPBSP模型模型 ：三个定量参数P、g、L，分别是处理器数、选路器吞吐率（亦称带宽因子）、全局同步之间时间间隔