哈工大-并行处理-第一章绪论

并行处理技术第一章绪论计算机种类低端计算机（pc机、工作站）——一般计算机用户高端计算机（超级计算机、并行机）——复杂科学计算、大型工程应用、大存储容量和高RAS商务处理1、科学和工程计算、应用主流的科学计算有：物理、化学、材料学、生物学、天文学、地球科学工程应用：能源勘探、油藏模拟、药物分析、汽车碰撞模拟、气流分析为此，美国制定HPCC计划和ASCI计划HPCC——高性能计算和通信

HighperformanceComputingandCommunication

HPCC计划分布的重大挑战应用课题有：磁记录技术、新药设计、高速民航、催化作用、燃料燃烧、海洋建模、臭氧耗损、数字解析、大气污染、蛋白质结构设计、图象处理、密码破译HPCC对计算机突出3T要求：1Tflop/s计算能力1TB主存1TB/sI/O带宽超级机、并行机的应用：化学（催化剂研究、化学工厂模拟）物理学（新材料研究、基本粒子研究、聚变系统……）天文学（宇宙论、太阳动力学、黑洞碰撞……）气候（中、长期预报……）环境（生态系统、地球观察系统、空气和水质建模）地理物理学（地震数据分析、水库建模、地震预报……）工程（交通工具、建筑及桥梁设计、芯片模拟、发动机电路设计）图象和信号处理(合成孔径雷达、虚拟现实、空时自适应系统）统）商业应用（数据库查询、数据仓库、决策支持系统、在线事务处理）计算机应用可归纳为逐步升级的：数据处理（Dataprocessing）信息处理（Informationprocessing）知识处理（Knowledgeprocessing）智能处理（Intelligenceprocessing）都隐含有能同时进行运算或操作的特性，称之为并行性ASCI计划——加速战略计算创新

（AcceleratedStrategicComputingInitiative）通过数值模拟，评估核武器的性能：安全性、可靠性、更新等。要求数值模拟达到高分辨率、高逼真度、三维、全物理、全系统……美能源部目前使用的计算机：100Tflop/s50TB

目前ASCI计划正把各项应用要求与计算机平台推进到万亿级规模的体系中去（美目前最快的计算机是70万亿次，3.3万个CPU）商务应用数据库管理和查询、在线事物处理、数据仓库、数据挖掘、决策支持系统,数据库,硬件和软件供应商,多处理机系统。以上应用可用TPM表示:将计算机系统的速度容量换算成每秒钟事务处理数。

网络计算应用：应用主要要求有效的通信、协同和互动操作、良好的安全性等。应用有：WWW服务、多媒体处理、视频点播、电子商务、数字图书馆、远程学习、医疗诊断。因特网的网格计算研究，个人互联网的研究等

2004年美快闪族联网完成1800亿次运算，冲击500强。国计民生方面的应用：医疗保健、教育、能源管理、环境保护、文化娱乐、国防安全……都涉及到了高性能并行机的使用

1995世界第一部全计算机动画片<玩具总动员>是由上百台SUN工作站并行完成的。以上的应用涉及并行机和机群。1.2并行性的概念1、并行性（parallelism）——在同一时刻或同一时间间隔内完成两种以上性质相同或不相同的工作，只要时间上相互重叠，均存在并行性。2、并行性含义同时性（Simultaneity）——两个或多个事件在同一时刻发生并发性（Concurency）——两个或多个事件在同一时间间隔内发生3、并行性分类粗粒度并行——在多处理机上分别运行多个进程，由多台处理机合作完成一个程序。细粒度并行——指在一个进程中，进行操作一级或指令一级的并行处理当代并行机系统大型并行计算机（scalable-parallelComputer）可分为:单指令多数据流机SIMD并行向量处理机PVP对称多处理机SMP

大规模并行处理机MPP

分布式共享存储DSM多处理机

工作站机群COW

*可扩展并行计算机发展正趋于三种系统结构：1、无共享体系结构2、共享磁盘体系结构3、共享存储器体系结构属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD互联网络交叉开关交叉开关，总线定制网络定制网络商业化网络通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA无共享体系结构（可以有多个p）

CMDNIC互连网络

CMDNIC…PP共享磁盘体系结构

CMDNIC互连网络

CMDNIC…共享磁盘PP互连网络…共享磁盘共享存储器CPCP共享存储器体系结构规模可伸缩性——增加机器规模，即处理机数。用可扩展性衡量一个系统能容纳的最大处理机数。资源扩展——可保持cpu数不变，增加存储容量，更大的高速缓存、磁盘……软件可扩展性——①操作系统用一个新版本，多线程，多用户…②更大的地址空间，以及高效的内核功能③更有效的数学和工程库④更有效和易于使用的应用软件⑤对用户更友好的编程环境应用可扩展性——①机器规模可扩展性（增加机器数，系统性能有多大改进）②问题规模可扩展性（例：并行雷达程序256cpu,100雷达）技术可扩展性代（时间）可扩展性——一个系统通过使用下一代的部件，一个新的OS，更强的编译器，计算能力增加。空间可扩展性——Internet具有最好的空间可扩展性异构可扩展性——系统集成不同厂商提供的软件和硬件而扩展的能力，具有开放系统结构，在软件领域有可移植性并行处理所涉及的问题系统规模——处理单元有多少（小规模、中规模、大规模）系统的组织策略——处理单元的功能有多强蚁军法象群法系统的互连问题——各处理单元之间按什么样的拓扑结构彼此相连系统的通信方式——处理单元的数据如何运输共享变量方式消息传递方式同步互斥问题——保证多处理单元操作的顺序性数据一致性——不同存储层次中的共享数据的完整性并行算法的研究——对串行应用找出能利用多机并行的新算法并行编译技术——并行语言的研究、自动并行识别器、编译程序本身的并行化、并行程序开发工具、调试工具、分析工具并行操作系统——支持多处理机并行；自动调度和负载平衡并行程序设计支持机制；Unix并行化…并行处理系统的三个主要优点1、有很高的运算速度，处理能力2、良好的性能价格比。3、系统规模的可伸缩性好。并行程序的设计方法隐式并行性——用传统cFORTRAN编；并行编译器。显式并行性——用并行语言编源程序并行计算机定义——由多个处理器组成的计算机系统，这些处理单元相互通信和协作，快速高效求解复杂问题。6、从标量处理计算机到并行计算机的演变标量顺序的先行I/E重叠功能并行多功能部件流水线隐式向量显式向量存储器到存储器寄存器到存储器SIMDMIMD多处理机多计算机处理机阵列关联处理器1.3并行处理机的发展1、提高并行性的三种主要技术途径1）时间重叠（Time-interleaving）即多个处理过程在时间上相互错开，轮流重叠使用同一套硬件的各个部件，以加强部件的周转而提高速度。2）资源重复（resource-replication）根据以数量取胜原则，重复设置硬件资源以大幅度提高系统的性能。3）资源共享（resource-sharing）利用软件方法，使多个用户分时使用同一个计算机系统。2、计算机系统并行处理的发展1）按照指令流和数据流的多倍性概念将计算机系统结构分类指令流——指机器所执行的指令序列数据流——指指令所调用的数据序列多倍性——指机器的瓶颈部件上所可能并行执行的最大指令或数据的个数。单机系统多道程序分时系统多终端远程系统智能终端分布处理系统局部计算机网通信处理机远程网络部件冗余多操作部件多存储体并行处理机联想处理机同构型多处理机可重构多处理机容错处理机紧密偶合系统重叠方式先行控制指令流水数据流水向量处理机异构型多处理机高级语言处理机数据库处理机松散耦合系统多机系统资源共享资源重复时间重叠网络化机间互联功能专用2）计算机并行处理的发展1.4并行性的等级1）从计算机系统中执行程序的角度分级指令内部的并行——一条指令内部各个微操作之间的并行。指令之间的并行——多指令的并行执行。任务或进程的并行——多个任务或程序段的并行执行。作业或程序之间的并行——多个任务或多道程序的并行。2）从计算机系统中处理数据的并行性分级位串字串——同时只对一个字的一位进行处理，没有并行。位并字串——同时对一个字的全方位进行处理，开始出现并行。位片串字并——同时对许多字的同一位（位片）进行处理，显示出开始进入并行处理领域。全并行——同时对许多字的全部或部位组进行处理。3）从计算机对信息加工的步骤和阶段来分级：存储器操作并行——采用单体多字，多体单字，多体多字方式在同一周期内访多字。处理器操作步骤并行——将操作步骤或具体执行步骤在时间上重叠流水。处理器操作并行——让多个处理器在同一控制器下按照同一条指令的要求对多个数据同时操作。指令、任务、作业并行——多个处理机同时对多条指令及有关数据组操作。Flynn将计算机系统结构分类如下：

单指令单数据流（SISD）

单指令多数据流（SIMD）

多指令单数据流（MISD）

多指令多数据流（MIMD）

CUPUMMISISISSISD计算机CUPU1PU2PUnMM1MM2MMnDS1DS2DSn....ISISSIMD计算机PU1PU2PUnDS..MM2MM1MMn…MM1MM1MM1IS1IS2ISnIS1IS2ISnISnIS2IS1DSMISD计算机…PU1PU2PUnMM1MM2MMnDS1DS2DSn....CU1CU2CUn..IS1IS2ISnIS1IS2ISn..MIMD计算机3）多处理机系统比较项目同构型多处理机异构型多处理机分布处理系统目的提高系统性能（可靠性、速度）提高系统的使用效率兼顾效率与性能技术途径资源重复（机间互联）时间重叠（功能专用化）资源共享（网络化）组成同类型（同等功能）不同类型（不同功能）不限制分工方式任务分布功能分布硬、软件、数据等资源的分布工作方式一个作业由多机协同并行地完成一个作业由多机协同串行地完成一个作业由一台处理机完成，必要时才请求他机协作控制方式常采用浮动控制方式采用专用控制方式分布控制方式耦合度紧密耦合紧密、松散耦合松散、紧密耦合对互联网的要求快速、灵活、可重构性专用性快速、简单、灵活、通用同构型——对称型异构型——非对称型浮动控制方式——即整个系统的管理由一台处理机管理控制