南京林业大学南京林业大学南京林业大学南京林业大学-信息学院信息学院信息学院信息学院并行算法南京林业大学-信息学院2任课教师：章春芳任课教师：章春芳办公室：办公室：0250E-mail：2任课教师：章春芳3教材、参考书 教材教材教材教材并行计算并行计算并行计算并行计算-结构结构结构结构 算法算法算法算法 编程编程编程编程 陈国良陈国良陈国良陈国良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社并行算法实践并行算法实践并行算法实践并行算法实践 陈国良陈国良陈国良陈国良 高等教育出版社高等教育出版社高等教育出版社高等教育出版社 参考书参考书参考书参考书并行处理技术并行处理技术并行处理技术并行处理技术 张德富张德富张德富张德富 南京大学南京大学南京大学南京大学出版社出版社出版社出版社面向结构的并行算法设计与分析面向结构的并行算法设计与分析面向结构的并行算法设计与分析面向结构的并行算法设计与分析 李晓梅李晓梅李晓梅李晓梅 国防科技大学国防科技大学国防科技大学国防科技大学出版社出版社出版社出版社3教材、参考书 教材主要内容 并行处理概论并行处理概论并行处理概论并行处理概论 1 1 并行计算性能测评并行计算性能测评并行计算性能测评并行计算性能测评 2 2 并行算法的一般设计方法并行算法的一般设计方法并行算法的一般设计方法并行算法的一般设计方法 4 4 并行算法的基本设计技术并行算法的基本设计技术并行算法的基本设计技术并行算法的基本设计技术 5 5 非数值并行算法非数值并行算法非数值并行算法非数值并行算法 6 6 图论图论图论图论 7 7 矩阵运算矩阵运算矩阵运算矩阵运算 8 8 并行算法的设计基础并行算法的设计基础并行算法的设计基础并行算法的设计基础 3 3 并行程序设计基础并行程序设计基础并行程序设计基础并行程序设计基础 9 9主要内容 并行处理概论 1 并行计算性5第一章并行计算机系统及结构模型1.1 并行计算概论并行计算概论1.2 并行计算机系统互并行计算机系统互连连1.3 并行计算机系统结并行计算机系统结构构5第一章并行计算机系统及结构模型1.1 并行计算概论1.2 1.1 并行计算概论并行处理的定义并行处理的定义并行处理的定义并行处理的定义 并行性的含义并行性的含义并行性的含义并行性的含义并行处理的应用并行处理的应用并行处理的应用并行处理的应用并行处理中的几个难题并行处理中的几个难题并行处理中的几个难题并行处理中的几个难题61.1 并行计算概论并行处理的定义 671.1.1并行处理的含义发展背景：发展背景：发展背景：发展背景：仅提高电子部件的速度来改善计算机仅提高电子部件的速度来改善计算机仅提高电子部件的速度来改善计算机仅提高电子部件的速度来改善计算机的性能以满足用户越来越高的要求是不可能的。
的性能以满足用户越来越高的要求是不可能的的性能以满足用户越来越高的要求是不可能的的性能以满足用户越来越高的要求是不可能的计算科学：计算科学：计算科学：计算科学：计算物理、计算化学、计算生物等计算物理、计算化学、计算生物等计算物理、计算化学、计算生物等计算物理、计算化学、计算生物等并行处理：并行处理：并行处理：并行处理：一种有效的强调开发计算过程中并行一种有效的强调开发计算过程中并行一种有效的强调开发计算过程中并行一种有效的强调开发计算过程中并行事件的信息处理方式事件的信息处理方式事件的信息处理方式事件的信息处理方式并行计算：并行计算：并行计算：并行计算：并行机上的计算，又称高性能计算并行机上的计算，又称高性能计算并行机上的计算，又称高性能计算并行机上的计算，又称高性能计算（HPC)HPC)并行计算机：并行计算机：并行计算机：并行计算机：为并行处理所设计的计算机系统为并行处理所设计的计算机系统为并行处理所设计的计算机系统为并行处理所设计的计算机系统71.1.1并行处理的含义发展背景：仅提高电子部件的速度来改8并行性的含义同时性：同时性：同时性：同时性：两个或多个事件在两个或多个事件在两个或多个事件在两个或多个事件在同一时刻同一时刻同一时刻同一时刻发生在多个发生在多个发生在多个发生在多个资源中资源中资源中资源中并发性：并发性：并发性：并发性：两个或多个事件在两个或多个事件在两个或多个事件在两个或多个事件在同一时间间隔内同一时间间隔内同一时间间隔内同一时间间隔内发生发生发生发生在多个资源中在多个资源中在多个资源中在多个资源中流水线：流水线：流水线：流水线：两个或多个事件发生在两个或多个事件发生在两个或多个事件发生在两个或多个事件发生在可能重叠的时间可能重叠的时间可能重叠的时间可能重叠的时间内内内内模式：模式：模式：模式：以数值计算为例计算并行性，有以数值计算为例计算并行性，有以数值计算为例计算并行性，有以数值计算为例计算并行性，有表达模式表达模式表达模式表达模式与与与与递归模式递归模式递归模式递归模式8并行性的含义同时性：两个或多个事件在同一时刻发生在多个资源9并行性的含义 例如：两个向量的内积：例如：两个向量的内积：例如：两个向量的内积：例如：两个向量的内积：表达式形式：表达式形式：表达式形式：表达式形式：9并行性的含义例如：两个向量的内积：10并行性的含义 并行模式：并行模式：并行模式：并行模式：x x1 1Y Y1 1x x2 2Y Y2 2 X Xn-1n-1Y Yn-1n-1x xn nY Yn n R R10并行性的含义并行模式：x1Y1x2Y2Xn-1Yn-111并行性的含义 递归模式：递归模式：递归模式：递归模式：流水线模式：流水线模式：流水线模式：流水线模式：*+11并行性的含义递归模式：*+121.1.2 并行处理的应用高速并行计算主要有三种类型的应用需求：高速并行计算主要有三种类型的应用需求：高速并行计算主要有三种类型的应用需求：高速并行计算主要有三种类型的应用需求：121.1.2 并行处理的应用高速并行计算主要有三种类型的应13并行处理的应用主要应用领域：主要应用领域：主要应用领域：主要应用领域：气象、海洋、天体物理气象、海洋、天体物理气象、海洋、天体物理气象、海洋、天体物理 遥测地球资源数据处理遥测地球资源数据处理遥测地球资源数据处理遥测地球资源数据处理 石油开采及管理石油开采及管理石油开采及管理石油开采及管理 磁聚变及核反应堆磁聚变及核反应堆磁聚变及核反应堆磁聚变及核反应堆 生物及医学生物及医学生物及医学生物及医学 工程计算工程计算工程计算工程计算 社会经济学及政府部门社会经济学及政府部门社会经济学及政府部门社会经济学及政府部门 国防国防国防国防 13并行处理的应用主要应用领域：14气象数值预报 将地球由北至南分成将地球由北至南分成将地球由北至南分成将地球由北至南分成2 2度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成度一格，延赤道分成4 4度一格，度一格，度一格，度一格，将大气层分成将大气层分成将大气层分成将大气层分成2020层，形成一个三维网格。
设每个网格层，形成一个三维网格设每个网格层，形成一个三维网格设每个网格层，形成一个三维网格设每个网格上计算量约为上计算量约为上计算量约为上计算量约为30003000次，若时间步长为次，若时间步长为次，若时间步长为次，若时间步长为2 2分钟，则当给分钟，则当给分钟，则当给分钟，则当给出出出出一天的气象预报一天的气象预报一天的气象预报一天的气象预报时，总计算量为时，总计算量为时，总计算量为时，总计算量为3.5103.5101111次在在在在Gray1Gray1（GrayGray公司的向量流水机）上进行计算（每公司的向量流水机）上进行计算（每公司的向量流水机）上进行计算（每公司的向量流水机）上进行计算（每秒秒秒秒1 1亿次浮点运算，需计算亿次浮点运算，需计算亿次浮点运算，需计算亿次浮点运算，需计算1 1小时小时小时小时左右，若左右，若左右，若左右，若将网格边长将网格边长将网格边长将网格边长减半减半减半减半，是，是，是，是原来计算量的原来计算量的原来计算量的原来计算量的8 8倍倍倍倍14气象数值预报将地球由北至南分成2度一格，延赤道分成4度一15海洋学、天体物理 以以以以1 1为为为为间间间间隔隔隔隔的的的的类类类类似似似似网网网网格格格格，用用用用Gyber-205Gyber-205（美美美美国国国国数数数数据据据据控控控控制制制制公公公公司司司司CDCCDC，19821982，5252位位位位4 4亿亿亿亿次次次次每每每每秒秒秒秒，400mflops400mflops的的的的流水线机）对太平洋流水线机）对太平洋流水线机）对太平洋流水线机）对太平洋5050年作一次完整模拟要年作一次完整模拟要年作一次完整模拟要年作一次完整模拟要10001000小时小时小时小时。
模模模模拟拟拟拟地地地地球球球球等等等等行行行行星星星星的的的的形形形形成成成成过过过过程程程程，其其其其动动动动态态态态范范范范围围围围从从从从毫毫毫毫秒秒秒秒到到到到几几几几十十十十亿亿亿亿，ILLIAC-VILLIAC-V阵阵阵阵 列列列列 处处处处 理理理理 机机机机（美美美美 国国国国 Illinios Illinios uinv,1973,64uinv,1973,64个个个个PEPE主主主主存存存存1313万万万万字字字字，1.51.5亿亿亿亿次次次次每每每每秒秒秒秒的的的的阵阵阵阵列列列列机）曾用于这一方面的研究机）曾用于这一方面的研究机）曾用于这一方面的研究机）曾用于这一方面的研究15海洋学、天体物理以1为间隔的类似网格，用Gyber-216遥测地球资源数据处理 大大大大量量量量卫卫卫卫星星星星图图图图像像像像资资资资料料料料处处处处理理理理陆陆陆陆地地地地探探探探测测测测卫卫卫卫星星星星的的的的一一一一张张张张图图图图像像像像有有有有3 3千千千千万万万万个个个个字字字字符符符符，覆覆覆覆盖盖盖盖美美美美国国国国AlabamaAlabama州州州州需需需需要要要要1313幅幅幅幅这这这这样样样样的的的的图图图图像像像像，每每每每1515天天天天产产产产生生生生一一一一次次次次新新新新的的的的图图图图像像像像，计计计计算算算算量量量量很很很很大大大大。
美美美美国国国国宇宇宇宇航航航航 局局局局 订订订订 购购购购 了了了了 并并并并 行行行行 处处处处 理理理理 机机机机 MPPMPP（美美美美 国国国国 Goodyear Goodyear AerospaceAerospace，19791979，128128PES128128PES），最最最最高高高高速速速速度度度度每每每每秒秒秒秒6060亿次亿次亿次亿次8 8位整数运算位整数运算位整数运算位整数运算，能提供实时的情景分析能提供实时的情景分析能提供实时的情景分析能提供实时的情景分析16遥测地球资源数据处理大量卫星图像资料处理陆地探测卫星的17石油开采及管理地震探测地震探测地震探测地震探测 19851985年年年年，我我我我国国国国南南南南海海海海西西西西部部部部石石石石油油油油公公公公司司司司向向向向美美美美国国国国订订订订购购购购PE3230MPSPE3230MPS并并并并行行行行处处处处理理理理计计计计算算算算机机机机地地地地震震震震数数数数据据据据处处处处理理理理费费费费用用用用占占占占地地地地震震震震探探探探测测测测总总总总费费费费用用用用的的的的10%10%，地地地地震震震震数数数数据据据据相相相相当当当当多多多多，仅仅仅仅19791979年年年年就就就就有有有有10101515位位位位地地地地震震震震数数数数据据据据处处处处理理理理。
美美美美国国国国休休休休斯斯斯斯顿顿顿顿一一一一家家家家地地地地球球球球物物物物理理理理公公公公司司司司存存存存储储储储的的的的地地地地球球球球地地地地震震震震数数数数据据据据有有有有200200万个磁带卷万个磁带卷万个磁带卷万个磁带卷17石油开采及管理地震探测18石油开采及管理储油层模型的建立储油层模型的建立储油层模型的建立储油层模型的建立 SOHOSOHO公公公公司司司司用用用用Cyber-203Cyber-203（CDCCDC）建建建建立立立立波波波波罗罗罗罗的的的的海海海海湾湾湾湾油油油油田田田田数数数数值值值值模模模模拟拟拟拟器器器器，包包包包括括括括10001000个个个个油油油油井井井井，一一一一个个个个需需需需一一一一年年年年模模模模拟拟拟拟实实实实验验验验的的的的工工工工作作作作量量量量，在在在在Cyber-203Cyber-203仅仅仅仅用用用用3333分钟分钟分钟分钟即可完成即可完成即可完成即可完成18石油开采及管理储油层模型的建立19工程计算 水水水水坝坝坝坝、桥桥桥桥梁梁梁梁、船船船船只只只只、超超超超音音音音速速速速飞飞飞飞机机机机、高高高高层层层层建建建建筑筑筑筑、太太太太空空空空飞飞飞飞行行行行器器器器设设设设计计计计需需需需解解解解大大大大型型型型偏偏偏偏微微微微分分分分方方方方程程程程组组组组和和和和代代代代数数数数方方方方程程程程组组组组，可可可可以以以以用用用用并并并并行处理机提高设计效率行处理机提高设计效率行处理机提高设计效率行处理机提高设计效率。
在在在在空空空空气气气气动动动动力力力力学学学学计计计计算算算算中中中中美美美美国国国国航航航航天天天天局局局局AmesAmes研研研研究究究究中中中中心心心心用用用用超超超超级级级级计算机作风洞实验三级模拟计算机作风洞实验三级模拟计算机作风洞实验三级模拟计算机作风洞实验三级模拟由由由由BurroughsBurroughs公公公公司司司司及及及及CDCCDC公公公公司司司司推推推推出出出出“数数数数值值值值航航航航空空空空动动动动力力力力学学学学模模模模拟拟拟拟设设设设备备备备“（NAFSNAFS）的的的的两两两两台台台台1010亿亿亿亿次次次次超超超超级级级级计计计计算算算算机机机机可可可可以以以以模模模模拟完整的飞机设计拟完整的飞机设计拟完整的飞机设计拟完整的飞机设计19工程计算水坝、桥梁、船只、超音速飞机、高层建筑、太空飞行20社会经济学及政府部门 计计计计量量量量经经经经济济济济学学学学、社社社社会会会会工工工工程程程程、政政政政府府府府人人人人口口口口普普普普查查查查、犯犯犯犯罪罪罪罪控控控控制制制制20002000年世界经济模型构造等计算的计算量大，需并行计算年世界经济模型构造等计算的计算量大，需并行计算。
年世界经济模型构造等计算的计算量大，需并行计算年世界经济模型构造等计算的计算量大，需并行计算诺诺诺诺贝贝贝贝尔尔尔尔奖奖奖奖学学学学金金金金获获获获得得得得者者者者W.W.Leontief W.W.Leontief 19801980年年年年提提提提出出出出一一一一个个个个世世世世界界界界经经经经济济济济输输输输入入入入/输输输输出出出出模模模模型型型型，在在在在CDCCDC科科科科学学学学计计计计算算算算机机机机上上上上运运运运算算算算，认认认认为为为为一一一一个个个个以以以以部部部部分分分分裁裁裁裁军军军军为为为为特特特特征征征征的的的的国国国国际际际际性性性性经经经经济济济济关关关关系系系系系系系系统统统统，可可可可以以以以缩小贫富国家的差距，该项目受到联合国支持缩小贫富国家的差距，该项目受到联合国支持缩小贫富国家的差距，该项目受到联合国支持缩小贫富国家的差距，该项目受到联合国支持美美美美国国国国使使使使用用用用大大大大型型型型计计计计算算算算机机机机控控控控制制制制犯犯犯犯罪罪罪罪、收收收收税税税税与与与与审审审审计计计计，进进进进行行行行人人人人口口口口普普普普查查查查及及及及民民民民意意意意测测测测验验验验。
过过过过去去去去美美美美国国国国制制制制造造造造的的的的大大大大型型型型计计计计算算算算机机机机57%57%由由由由政政政政府使用20社会经济学及政府部门计量经济学、社会工程、政府人口普查、21国防、人工智能、基础研究国防国防国防国防军军军军事事事事部部部部门门门门使使使使用用用用现现现现存存存存的的的的大大大大部部部部分分分分超超超超级级级级计计计计算算算算机机机机，如如如如Cray-1Cray-1多用于弹头核武器设计多用于弹头核武器设计多用于弹头核武器设计多用于弹头核武器设计在在在在关关关关联联联联处处处处理理理理机机机机上上上上为为为为反反反反弹弹弹弹道道道道导导导导弹弹弹弹程程程程序序序序处处处处理理理理雷雷雷雷达达达达信信信信号号号号，用用用用S-1S-1多处理机做反潜艇海洋监视多处理机做反潜艇海洋监视多处理机做反潜艇海洋监视多处理机做反潜艇海洋监视21国防、人工智能、基础研究国防22国防、人工智能、基础研究人工智能人工智能人工智能人工智能 图像处理图像处理图像处理图像处理 模式识别模式识别模式识别模式识别 计算机视觉计算机视觉计算机视觉计算机视觉 自然语言理解自然语言理解自然语言理解自然语言理解 机器推理机器推理机器推理机器推理 智能机器人智能机器人智能机器人智能机器人 专家系统专家系统专家系统专家系统 知识工程知识工程知识工程知识工程基础研究基础研究基础研究基础研究 计算化学计算化学计算化学计算化学 计算物理计算物理计算物理计算物理 计算几何计算几何计算几何计算几何 VLSIVLSI辅助设计辅助设计辅助设计辅助设计22国防、人工智能、基础研究人工智能23当代科学与工程问题的计算需求评测计算机性能的指标评测计算机性能的指标评测计算机性能的指标评测计算机性能的指标7070年代年代年代年代Mflops 10Mflops 106 6 百万百万百万百万现在现在现在现在Pflops 10Pflops 101515 千万亿次千万亿次千万亿次千万亿次9090年代年代年代年代Tflops 10Tflops 101212 万亿万亿万亿万亿8080年代年代年代年代Gflops 10Gflops 109 9 十亿十亿十亿十亿世界上第一台峰值速度世界上第一台峰值速度超过超过1Tflops1Tflops的高性能计的高性能计算机是由算机是由IntelIntel公司于公司于19961996年年1212月研制成功的。
月研制成功的23当代科学与工程问题的计算需求评测计算机性能的指标70年代24当代科学与工程问题的计算需求美美美美 国国国国 HPCCHPCC计计计计 划划划划（High High Performance Performance Computing&CommunicationComputing&Communication）为为为为了了了了保保保保持持持持美美美美国国国国的的的的世世世世界界界界领领领领先先先先地地地地位位位位，19931993年年年年，美美美美国国国国科科科科学学学学、工工工工程程程程、技技技技术术术术联联联联邦邦邦邦协协协协调调调调理理理理事事事事会会会会的的的的国国国国会会会会提提提提出出出出了了了了题题题题为为为为“重重重重大大大大挑挑挑挑战战战战项项项项目目目目：高高高高性性性性能能能能计计计计算算算算与与与与通通通通信信信信”的报告，简称的报告，简称的报告，简称的报告，简称HPCCHPCC计划计划计划计划3T3T性能目标性能目标性能目标性能目标 TflopsTflops计算能力、计算能力、计算能力、计算能力、1TB1TB主存容量、主存容量、主存容量、主存容量、1TB/s1TB/s的的的的I/OI/O带宽带宽带宽带宽24当代科学与工程问题的计算需求美国HPCC计划（High 25HPCC应用领域高速民航高速民航高速民航高速民航用计算流体动力学来研制超音速喷气发动机用计算流体动力学来研制超音速喷气发动机用计算流体动力学来研制超音速喷气发动机用计算流体动力学来研制超音速喷气发动机新药设计新药设计新药设计新药设计研制癌症和艾滋病的药物研制癌症和艾滋病的药物研制癌症和艾滋病的药物研制癌症和艾滋病的药物催化作用催化作用催化作用催化作用仿生催化剂计算机建模，分析合成过程中酶的作用仿生催化剂计算机建模，分析合成过程中酶的作用仿生催化剂计算机建模，分析合成过程中酶的作用仿生催化剂计算机建模，分析合成过程中酶的作用燃料燃烧燃料燃烧燃料燃烧燃料燃烧通过化学动力学，揭示流体力学的作用，设计新型发动通过化学动力学，揭示流体力学的作用，设计新型发动通过化学动力学，揭示流体力学的作用，设计新型发动通过化学动力学，揭示流体力学的作用，设计新型发动机机机机海洋建模海洋建模海洋建模海洋建模对海洋活动与大气流的热交换进行整体海洋模拟对海洋活动与大气流的热交换进行整体海洋模拟对海洋活动与大气流的热交换进行整体海洋模拟对海洋活动与大气流的热交换进行整体海洋模拟大气污染大气污染大气污染大气污染对大气质量模型进行模拟研究，揭示其物理和化学机理对大气质量模型进行模拟研究，揭示其物理和化学机理对大气质量模型进行模拟研究，揭示其物理和化学机理对大气质量模型进行模拟研究，揭示其物理和化学机理蛋白质结构设计蛋白质结构设计蛋白质结构设计蛋白质结构设计使用计算机模拟，对蛋白质组成的三维结构进行研究使用计算机模拟，对蛋白质组成的三维结构进行研究使用计算机模拟，对蛋白质组成的三维结构进行研究使用计算机模拟，对蛋白质组成的三维结构进行研究图像理解图像理解图像理解图像理解实时绘制图像或动画实时绘制图像或动画实时绘制图像或动画实时绘制图像或动画密码破译密码破译密码破译密码破译破译由长位数组成的密码，求找该数的两个乘积因子破译由长位数组成的密码，求找该数的两个乘积因子破译由长位数组成的密码，求找该数的两个乘积因子破译由长位数组成的密码，求找该数的两个乘积因子19941994年年4 4月月2626日，美国宣日，美国宣布破译了世界上最长的布破译了世界上最长的RSA129RSA129密码，在因特网上密码，在因特网上使用使用16001600台计算机，台计算机，600600多人工作多人工作8 8个月个月，破译了，破译了129129位数字组成的密码位数字组成的密码25HPCC应用领域高速民航用计算流体动力学来研制超音速喷气26科学计算的需要26科学计算的需要27当代科学与工程问题的计算需求美美美美 国国国国 ASCIASCI计计计计 划划划划（Accelerated Accelerated Strategic Strategic Computing InitiativeComputing Initiative）全全全全面面面面禁禁禁禁止止止止核核核核实实实实验验验验条条条条约约约约签签签签订订订订后后后后，19961996年年年年6 6月月月月能能能能源源源源部部部部联联联联合合合合美美美美国国国国三三三三大大大大武武武武器器器器实实实实验验验验室室室室共共共共同同同同提提提提出出出出了了了了“加加加加速速速速战战战战略略略略计划创新计划创新计划创新计划创新”，简称为，简称为，简称为，简称为ASCIASCI计划计划计划计划27当代科学与工程问题的计算需求美国ASCI计划（Accel28美国美国ASCI计划划 目的目的目的目的 通通通通过过过过数数数数值值值值模模模模拟拟拟拟，评评评评估估估估核核核核武武武武器器器器的的的的性性性性能能能能、安安安安全全全全性性性性、可可可可靠靠靠靠性性性性等等等等，达达达达到到到到高高高高分分分分辨辨辨辨率率率率、高高高高逼逼逼逼真真真真度度度度、三三三三维维维维、全全全全物物物物理理理理、全全全全系系系系统统统统的的的的规规规规模模模模和和和和能能能能力力力力，该该该该计计计计划划划划被被被被认认认认为为为为是是是是与与与与当当当当年年年年曼曼曼曼哈哈哈哈顿顿顿顿计计计计划划划划等等等等同同同同的的的的一一一一个个个个巨巨巨巨大的挑战。
大的挑战大的挑战大的挑战平台平台平台平台 三三三三 大大大大 核核核核 武武武武 器器器器 实实实实 验验验验 室室室室 向向向向 三三三三 大大大大 公公公公 司司司司（IntelIntel，IBMIBM和和和和SGI/CraySGI/Cray）预预预预订订订订了了了了峰峰峰峰值值值值超超超超过过过过1Tflops1Tflops的的的的并并并并行行行行计计计计算算算算机机机机，预预预预计计计计20032003年年年年使使使使用用用用运运运运算算算算100Tflops100Tflops，50TB50TB存存存存储储储储容容容容量量量量，I/OI/O传传传传输输输输速率为速率为速率为速率为5000GB/s5000GB/s的并行机的并行机的并行机的并行机28美国ASCI计划29并行处理中的几个难题任务分配非常困难任务分配非常困难任务分配非常困难任务分配非常困难 考虑时空复杂度，还需考虑模块之间的通信量考虑时空复杂度，还需考虑模块之间的通信量考虑时空复杂度，还需考虑模块之间的通信量考虑时空复杂度，还需考虑模块之间的通信量 很难摆脱串行处理方式的约束很难摆脱串行处理方式的约束很难摆脱串行处理方式的约束很难摆脱串行处理方式的约束 软件和算法大都是按照串行结构设计的软件和算法大都是按照串行结构设计的软件和算法大都是按照串行结构设计的软件和算法大都是按照串行结构设计的 现有的算法语言对并行性限制很大现有的算法语言对并行性限制很大现有的算法语言对并行性限制很大现有的算法语言对并行性限制很大 现有语言以现有语言以现有语言以现有语言以Von NeumannVon Neumann方式为基础，对并行性限方式为基础，对并行性限方式为基础，对并行性限方式为基础，对并行性限 制严重：制严重：制严重：制严重：l l 语句执行结果、执行顺序与前面结果和状态相关语句执行结果、执行顺序与前面结果和状态相关语句执行结果、执行顺序与前面结果和状态相关语句执行结果、执行顺序与前面结果和状态相关l l 大量赋值语句使得处理器与存储器频繁交换信息，大量赋值语句使得处理器与存储器频繁交换信息，大量赋值语句使得处理器与存储器频繁交换信息，大量赋值语句使得处理器与存储器频繁交换信息，降低系统效率降低系统效率降低系统效率降低系统效率29并行处理中的几个难题任务分配非常困难30并行处理中的几个难题Von NeumannVon Neumann模式一直伴随着并行机模式一直伴随着并行机模式一直伴随着并行机模式一直伴随着并行机 未摆脱以未摆脱以未摆脱以未摆脱以指令流指令流指令流指令流为主导的为主导的为主导的为主导的Von NeumannVon Neumann模式，由于指模式，由于指模式，由于指模式，由于指令相关及地址空间相关，使并行受到制约令相关及地址空间相关，使并行受到制约令相关及地址空间相关，使并行受到制约令相关及地址空间相关，使并行受到制约处理机间的通讯开销使并行处理技术可能得不偿失处理机间的通讯开销使并行处理技术可能得不偿失处理机间的通讯开销使并行处理技术可能得不偿失处理机间的通讯开销使并行处理技术可能得不偿失 并行处理技术的主要难点在于软件并行处理技术的主要难点在于软件并行处理技术的主要难点在于软件并行处理技术的主要难点在于软件 串行机中软件好坏对于工作性能影响串行机中软件好坏对于工作性能影响串行机中软件好坏对于工作性能影响串行机中软件好坏对于工作性能影响2-32-3倍，并行计算倍，并行计算倍，并行计算倍，并行计算机中却是机中却是机中却是机中却是50-10050-100倍，而且最困难的在于并行编译程序倍，而且最困难的在于并行编译程序倍，而且最困难的在于并行编译程序倍，而且最困难的在于并行编译程序30并行处理中的几个难题Von Neumann模式一直伴随着传统Von Neumann结构及其存在构及其存在问题 存储程序控制方式存储程序控制方式存储程序控制方式存储程序控制方式31存储器指令寄存器、计数器存储器指令数据指令流驱动传统Von Neumann结构及其存在问题存储程序控制方式332研究并行处理应考虑的几个问题算法、体系结构、高级语言三者之间的关系应考虑：算法、体系结构、高级语言三者之间的关系应考虑：算法、体系结构、高级语言三者之间的关系应考虑：算法、体系结构、高级语言三者之间的关系应考虑：对于一些特定的计算机对于一些特定的计算机对于一些特定的计算机对于一些特定的计算机如何设计软件如何设计软件如何设计软件如何设计软件 对于一个给定的程序对于一个给定的程序对于一个给定的程序对于一个给定的程序如何使之结构化以便在给定的计算如何使之结构化以便在给定的计算如何使之结构化以便在给定的计算如何使之结构化以便在给定的计算机上处理机上处理机上处理机上处理 对于一个给定的计算机和一组应用软件对于一个给定的计算机和一组应用软件对于一个给定的计算机和一组应用软件对于一个给定的计算机和一组应用软件怎样设计语言及怎样设计语言及怎样设计语言及怎样设计语言及编译系统编译系统编译系统编译系统 对于给定的计算机、语言及编译系统对于给定的计算机、语言及编译系统对于给定的计算机、语言及编译系统对于给定的计算机、语言及编译系统如何设计算法与程如何设计算法与程如何设计算法与程如何设计算法与程序序序序32研究并行处理应考虑的几个问题算法、体系结构、高级语言三者33并行处理机系统的优点具有很高的性能价格比具有很高的性能价格比具有很高的性能价格比具有很高的性能价格比由于系统的模块性，使之便于维护由于系统的模块性，使之便于维护由于系统的模块性，使之便于维护由于系统的模块性，使之便于维护具有较高的可靠性具有较高的可靠性具有较高的可靠性具有较高的可靠性具有较高的处理速度具有较高的处理速度具有较高的处理速度具有较高的处理速度结构的灵活性结构的灵活性结构的灵活性结构的灵活性便于便于便于便于VLSIVLSI实现实现实现实现33并行处理机系统的优点具有很高的性能价格比341.1.3 并行处理机的分类1 13 34 42 2341.1.3 并行处理机的分类134235Flynn分类法单单单单指令流指令流指令流指令流单单单单数据流数据流数据流数据流SISDSISD单单单单指令流指令流指令流指令流多多多多数据流数据流数据流数据流SIMDSIMD多多多多指令流指令流指令流指令流单单单单数据流数据流数据流数据流MISDMISD（实际不存在）（实际不存在）（实际不存在）（实际不存在）多多多多指令流指令流指令流指令流多多多多数据流数据流数据流数据流MIMDMIMD35Flynn分类法单指令流单数据流SISD36SISDCUCUPUPUMMMMISISDSDSISISCUCU：控制单元：控制单元：控制单元：控制单元 PUPU：处理单元：处理单元：处理单元：处理单元 MMMM：存储器：存储器：存储器：存储器 IS IS：指令流：指令流：指令流：指令流 DSDS：数据流：数据流：数据流：数据流36SISDCUPUMMISDSISCU：控制单元 PU37SIMDCUCUPUPU1 1ISISPUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS37SIMDCUPU1ISPU2PUnMM1MM2MMn38MIMDPUPU1 1PUPU2 2PUPUn n MMMM1 1MMMM2 2MMMMn n DSDS1 1DSDS2 2DSDSn nISIS1 1ISIS2 2ISISn nCUCU1 1CUCU2 2CUCUn n ISIS1 1ISIS2 2ISISn n38MIMDPU1PU2PUnMM1MM2MMnDS1D39Handler分类法 19771977年，年，年，年，HandlerHandler根据计算机系统中流水线和并行度根据计算机系统中流水线和并行度根据计算机系统中流水线和并行度根据计算机系统中流水线和并行度出现的级别，将一台计算机表示为三对整数：出现的级别，将一台计算机表示为三对整数：出现的级别，将一台计算机表示为三对整数：出现的级别，将一台计算机表示为三对整数：CPUCPU数目数目能执行流水线的能执行流水线的CPUCPU数目数目 CPU CPU所控制的所控制的ALUALU数目数目 能执行流水线的能执行流水线的ALUALU数目数目ALUALU或或PEPE中的位数中的位数ALUALU或或PEPE中流水线的位数中流水线的位数39Handler分类法1977年，Handler根据计算机40按体系结构分类 同步系统同步系统同步系统同步系统 向量向量向量向量流水机流水机流水机流水机 阵列阵列阵列阵列处理机：（含心动阵列）处理机：（含心动阵列）处理机：（含心动阵列）处理机：（含心动阵列）SIMDSIMD 关联关联关联关联处理机：具有联想存储、按内容存取、逻辑操作等处理机：具有联想存储、按内容存取、逻辑操作等处理机：具有联想存储、按内容存取、逻辑操作等处理机：具有联想存储、按内容存取、逻辑操作等 多处理机系统多处理机系统多处理机系统多处理机系统MIMD:MIMD:由独立执行指令的处理器由独立执行指令的处理器由独立执行指令的处理器由独立执行指令的处理器构成构成构成构成 分布分布分布分布存储系统：每个结点有独立的存储单元存储系统：每个结点有独立的存储单元存储系统：每个结点有独立的存储单元存储系统：每个结点有独立的存储单元 共享共享共享共享存储系统存储系统存储系统存储系统 MIMDMIMD变体变体变体变体（MIMD/SIMDMIMD/SIMD混合型）混合型）混合型）混合型）40按体系结构分类同步系统41现代并行机结构分类 SIMDSIMD PVPPVP并行向量处理机并行向量处理机并行向量处理机并行向量处理机 SMPSMP对称多处理机对称多处理机对称多处理机对称多处理机 MPPMPP大规模并行处理机大规模并行处理机大规模并行处理机大规模并行处理机 DSMDSM分布式共享存储多处理机分布式共享存储多处理机分布式共享存储多处理机分布式共享存储多处理机 COWCOW工作站机群工作站机群工作站机群工作站机群Gray C-90Gray C-90Gray T-90Gray T-90银河银河1 1号号41现代并行机结构分类SIMDGray C-9042对称多处理机SMPIBM R50IBM R50、SGI Power ChakengeSGI Power Chakenge、曙光、曙光、曙光、曙光1 1号号号号使用商用微处理的芯片，由高速总线连向共享使用商用微处理的芯片，由高速总线连向共享使用商用微处理的芯片，由高速总线连向共享使用商用微处理的芯片，由高速总线连向共享存储器，对称性存储器，对称性存储器，对称性存储器，对称性共享存储共享存储共享存储共享存储，PEPE个数不能太多个数不能太多个数不能太多个数不能太多。
系统是系统是系统是系统是对称对称对称对称的，每个处理器可的，每个处理器可的，每个处理器可的，每个处理器可等同的访问共享等同的访问共享等同的访问共享等同的访问共享存储存储存储存储，I/OI/O设备42对称多处理机SMPIBM R50、SGI Power 43大规模并行处理机MPP 经典机型：经典机型：经典机型：经典机型：IBM SP2IBM SP2、Intel ParagonIntel Paragon、Intel Intel TFLOPSTFLOPS、曙光、曙光、曙光、曙光10001000等特性：特性：特性：特性：节点为微处理器节点为微处理器节点为微处理器节点为微处理器物理上的物理上的物理上的物理上的分布存储分布存储分布存储分布存储高带宽、低延迟的网络高带宽、低延迟的网络高带宽、低延迟的网络高带宽、低延迟的网络成百上千个成百上千个成百上千个成百上千个PEPE异步异步异步异步MIMDMIMD，程序由多个进程组成，每个进程有私，程序由多个进程组成，每个进程有私，程序由多个进程组成，每个进程有私，程序由多个进程组成，每个进程有私有空间，进程间采用有空间，进程间采用有空间，进程间采用有空间，进程间采用消息传递消息传递消息传递消息传递的方式的方式的方式的方式43大规模并行处理机MPP经典机型：IBM SP2、Inte44分布式共享存储多处理机DSM经典机型：经典机型：经典机型：经典机型：Cray T3DCray T3D、SGI/Gray Origin 2000SGI/Gray Origin 2000特点：特点：特点：特点：分布在各个节点上的局存形成了一个共享的存储器分布在各个节点上的局存形成了一个共享的存储器分布在各个节点上的局存形成了一个共享的存储器分布在各个节点上的局存形成了一个共享的存储器与与与与SIMDSIMD相相相相同同同同，在在在在物物物物理理理理上上上上有有有有分分分分布布布布在在在在各各各各点点点点的的的的共共共共享享享享主主主主存存存存，但采用但采用但采用但采用单一地址空间单一地址空间单一地址空间单一地址空间，与，与，与，与MPPMPP相比，相比，相比，相比，易于编程易于编程易于编程易于编程44分布式共享存储多处理机DSM经典机型：Cray T3D、45工作站机群COW 经典机型：经典机型：经典机型：经典机型：Berkeley NowBerkeley Now、DigitalDigital、TouclusterToucluster等等等等 特点：特点：特点：特点：每个节点都是一个工作站、每个节点都是一个工作站、每个节点都是一个工作站、每个节点都是一个工作站、PCPC机或机或机或机或SMPSMP 各节点各节点各节点各节点由低成本网络相连由低成本网络相连由低成本网络相连由低成本网络相连（商品网络、以太网、（商品网络、以太网、（商品网络、以太网、（商品网络、以太网、FDDIFDDI等）等）等）等）各节点有本地磁盘各节点有本地磁盘各节点有本地磁盘各节点有本地磁盘 各节点有一完整的各节点有一完整的各节点有一完整的各节点有一完整的OSOS（MPPMPP中只有一个微核），整个系统中只有一个微核），整个系统中只有一个微核），整个系统中只有一个微核），整个系统是工作站是工作站是工作站是工作站UnixUnix45工作站机群COW经典机型：Berkeley Now、Di461.2 并行计算机系统互连静态互连网络：静态互连网络：静态互连网络：静态互连网络：处理单元间有着处理单元间有着处理单元间有着处理单元间有着固定连接固定连接固定连接固定连接的一类网络，在程序执的一类网络，在程序执的一类网络，在程序执的一类网络，在程序执行期间，这种行期间，这种行期间，这种行期间，这种点到点的连接保持不变点到点的连接保持不变点到点的连接保持不变点到点的连接保持不变动态网络：动态网络：动态网络：动态网络：用用用用交换开关构成交换开关构成交换开关构成交换开关构成的，可按应用程序的要求的，可按应用程序的要求的，可按应用程序的要求的，可按应用程序的要求动态地动态地动态地动态地改变连接组成改变连接组成改变连接组成改变连接组成 461.2 并行计算机系统互连静态互连网络：47静态互连网络一维线性阵列一维线性阵列一维线性阵列一维线性阵列二维网孔二维网孔二维网孔二维网孔树形连接树形连接树形连接树形连接超立方网络超立方网络超立方网络超立方网络立方环立方环立方环立方环洗牌交换网洗牌交换网洗牌交换网洗牌交换网蝶形网络蝶形网络蝶形网络蝶形网络 47静态互连网络一维线性阵列48动态连接总线总线总线总线交叉开关交叉开关交叉开关交叉开关多级互连网络多级互连网络多级互连网络多级互连网络48动态连接总线49网络性能指标网络网络网络网络直径直径直径直径对剖对剖对剖对剖宽度宽度宽度宽度49网络性能指标网络直径对剖宽度50网络性能指标 节节节节点点点点：用用用用图图图图表表表表示示示示网网网网络络络络，则则则则处处处处理理理理机机机机或或或或存存存存储储储储器器器器为为为为节节节节点点点点，连连连连接接接接为边为边为边为边 节节节节点点点点度度度度（Node Node DegreeDegree）：射射射射入入入入或或或或射射射射出出出出一一一一个个个个节节节节点点点点的的的的边边边边数数数数。
在单向网络中，射入和射出边之和称为节点度在单向网络中，射入和射出边之和称为节点度在单向网络中，射入和射出边之和称为节点度在单向网络中，射入和射出边之和称为节点度 网网网网络络络络直直直直径径径径（Network Network DiameterDiameter）：网网网网络络络络中中中中任任任任何何何何两两两两个个个个节节节节点之间的点之间的点之间的点之间的最长距离最长距离最长距离最长距离，即最大路径数，即最大路径数，即最大路径数，即最大路径数 对对对对剖剖剖剖宽宽宽宽度度度度（Bisection Bisection WidthWidth）：将将将将网网网网络络络络分分分分成成成成两两两两部部部部分分分分必必必必须移去的最少边数须移去的最少边数须移去的最少边数须移去的最少边数 如如如如果果果果从从从从任任任任一一一一节节节节点点点点观观观观看看看看网网网网络络络络都都都都一一一一样样样样，则则则则称称称称网网网网络络络络为为为为对对对对称称称称的的的的（SymmetrySymmetry）50网络性能指标节点：用图表示网络，则处理机或存储器为节点，51静态互连网络（1）一维线性阵列（一维线性阵列（一维线性阵列（一维线性阵列（1-1-D Linear ArrayD Linear Array）：）：）：）：并行机中最简单、最基本的互连方式并行机中最简单、最基本的互连方式并行机中最简单、最基本的互连方式并行机中最简单、最基本的互连方式每个节点每个节点每个节点每个节点只与其左、右近邻只与其左、右近邻只与其左、右近邻只与其左、右近邻相连，也叫二近相连，也叫二近相连，也叫二近相连，也叫二近邻连接邻连接邻连接邻连接节点度为节点度为节点度为节点度为直径为直径为直径为直径为对剖宽度为对剖宽度为对剖宽度为对剖宽度为2 21 1N-1N-151静态互连网络（1）一维线性阵列（1-D Linear A52一一维线性性阵列列线性连接函数：线性连接函数：线性连接函数：线性连接函数：52一维线性阵列线性连接函数：53一维线性阵列 当首、尾节点相连时可构成循环移位器，在拓扑结当首、尾节点相连时可构成循环移位器，在拓扑结当首、尾节点相连时可构成循环移位器，在拓扑结当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是构上等同于环，环可以是构上等同于环，环可以是构上等同于环，环可以是双向的双向的双向的双向的或或或或单向的单向的单向的单向的互连网络互连网络互连网络互连网络节点度节点度节点度节点度直径直径直径直径对剖宽度对剖宽度对剖宽度对剖宽度单向环单向环单向环单向环双向环双向环双向环双向环2 22 22 2N-1N-12 2双向环双向环单向环单向环53一维线性阵列当首、尾节点相连时可构成循环移位器，在拓扑结54二二维网孔网孔四近邻连接：四近邻连接：四近邻连接：四近邻连接：每个节点只与其每个节点只与其每个节点只与其每个节点只与其上、下、左、右上、下、左、右上、下、左、右上、下、左、右的近的近的近的近邻相连邻相连邻相连邻相连54二维网孔四近邻连接：每个节点只与其上、下、左、右的近邻相55二二维网孔网孔IlliacIlliac网孔：网孔：网孔：网孔：简记为简记为简记为简记为MCMC2 2，在在在在垂直方向上带环垂直方向上带环垂直方向上带环垂直方向上带环绕绕绕绕，水平方向呈蛇状水平方向呈蛇状水平方向呈蛇状水平方向呈蛇状55二维网孔Illiac网孔：简记为MC2，在垂直方向上带环56二二维网孔网孔2-2-D D环绕：环绕：环绕：环绕：垂直和水平方向垂直和水平方向垂直和水平方向垂直和水平方向均带环绕均带环绕均带环绕均带环绕56二维网孔2-D环绕：垂直和水平方向均带环绕57二二维网孔网孔4 4互连网络互连网络互连网络互连网络节点度节点度节点度节点度直径直径直径直径对剖宽度对剖宽度对剖宽度对剖宽度四近邻连接四近邻连接四近邻连接四近邻连接IlliacIlliac网孔网孔2-2-D D环绕环绕4 44 457二维网孔4互连网络节点度直径对剖宽度四近邻连接Illia58网孔连接 网孔中的网孔中的网孔中的网孔中的PEPE节点编号是按行为主顺序，编号为节点编号是按行为主顺序，编号为节点编号是按行为主顺序，编号为节点编号是按行为主顺序，编号为0 0N-1N-1 连接函数：连接函数：连接函数：连接函数：0 01 12 23 34 45 56 67 78 89 910101111121213131414151558网孔连接网孔中的PE节点编号是按行为主顺序，编号为0N59网孔连接例：例：例：例：n=16n=16时的网孔时的网孔时的网孔时的网孔0 01 12 23 34 45 56 67 78 89 910101111121213131414151559网孔连接例：n=16时的网孔012345678910119-1-57-56-48-47-46-459-1-57-56-48-47-46-45网孔连接 在在在在MCMC2 2上已经有许多有效的并行算法，但上已经有许多有效的并行算法，但上已经有许多有效的并行算法，但上已经有许多有效的并行算法，但MCMC2 2通信功能较通信功能较通信功能较通信功能较差，在最坏情况下，任意两个差，在最坏情况下，任意两个差，在最坏情况下，任意两个差，在最坏情况下，任意两个PEPE间信息交换至少要间信息交换至少要间信息交换至少要间信息交换至少要 步。
步如如如如N=64N=64时时时时 P P6363-P-P1010：P P9 9-P-P4545：63-7-8-9-1063-7-8-9-109-1-57-56-48-47-46-45网孔连接在MC2上61树形连接 二叉树连接（简记为二叉树连接（简记为二叉树连接（简记为二叉树连接（简记为TCTC）：）：）：）：P P1 1P P8 8P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7P P9 9P P1010P P1111P P1212P P1313P P1414P P151561树形连接二叉树连接（简记为TC）：P1P8P2P3P4P62树形连接除了根、叶节点，每个内节点只与其父节点除了根、叶节点，每个内节点只与其父节点除了根、叶节点，每个内节点只与其父节点除了根、叶节点，每个内节点只与其父节点和两个子节点相连和两个子节点相连和两个子节点相连和两个子节点相连设二叉树有设二叉树有设二叉树有设二叉树有d d d d层，层号由根至叶子为层，层号由根至叶子为层，层号由根至叶子为层，层号由根至叶子为1d1d1d1d，则，则，则，则共有共有共有共有 个节点个节点个节点个节点节点度为：节点度为：节点度为：节点度为：对剖宽度为：对剖宽度为：对剖宽度为：对剖宽度为：直径为：直径为：直径为：直径为：2 2 2 2d d d d-1-1-1-13162树形连接除了根、叶节点，每个内节点只与其父节点和两个子节树形连接的典型用法P P1 1P P8 8P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7P P9 9P P1010P P1111P P1212P P1313P P1414P P1515根根根根及及及及叶叶叶叶子子子子节节节节点点点点具具具具有有有有I/OI/O功功功功能能能能，且且且且叶叶叶叶子子子子节节节节点点点点执执执执行行行行并并并并行行行行计计计计算算算算，内节点内节点内节点内节点负责负责负责负责节点间的通信节点间的通信节点间的通信节点间的通信树树树树型型型型连连连连接接接接的的的的最最最最长长长长通通通通信信信信路路路路径径径径与与与与树树树树高高高高相相相相关关关关，显显显显然然然然根根根根为为为为通通通通信信信信瓶瓶瓶瓶颈颈颈颈，因因因因此此此此使使使使用用用用X-X-树树树树，形形形形成成成成树树树树网网网网连连连连接接接接，可可可可使使使使同同同同级级级级兄兄兄兄弟弟弟弟之之之之间间间间彼此相连彼此相连彼此相连彼此相连树形连接的典型用法P1P8P2P3P4P5P6P7P9P1064超立方体连接 一个一个一个一个n-n-立方由立方由立方由立方由 个顶点组成，个顶点组成，个顶点组成，个顶点组成，3-。