计算机并行处理机制的研究要点.docx
- 文档编号:9804467
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:16
- 大小:27.43KB
计算机并行处理机制的研究要点.docx
《计算机并行处理机制的研究要点.docx》由会员分享,可在线阅读,更多相关《计算机并行处理机制的研究要点.docx(16页珍藏版)》请在冰点文库上搜索。
计算机并行处理机制的研究要点
河南理工大学
计算机科学与技术学院
课程设计报告
20—20学年第学期
课程名称
设计题目
学生姓名
学号
专业班级
指导教师
年月日
目录
目录2
摘要4
1绪论5
1.1概述5
1.2国内相关研究5
2分布式系统6
2.1分布式系统的定义6
2.2分布式系统的特性7
2.3分布式系统的拓扑结构8
3并行处理技术8
3.1、并行的概念9
3.1.1并行性9
3.1.2并行等级的划分9
3.1.3实现并行处理的技术途径10
3.2指令并行处理10
3.3线程并行处理11
3.4并行程序设计12
3.5并行处理机14
3.5.1SIMD并行计算机(阵列处理机)14
3.5.2多处理机15
4前景展望16
5参考文献17
摘要
计算机诞生60多年以来,计算机技术发生了一系列伟大的革命,随着人们对计算速度、系统可靠性和成本实效性等要求的不断提高,传统的冯·诺依曼型结构已经无法满足上述的要求,而随着计算机网络的出现,分布式系统成为可能并得到飞速发展和应用。
其中,并行处理计算机是计算机设计的未来。
当代面临着的重大科学技术问题要依赖于计算技术协助解决,一方面要作大型计算以得到更精确的解,另一方面要作计算机模拟,以便进一步了解所探讨问题的结构与运动规律。
这两个方面都离不开并行处理技术。
虽然许多人都认识到并行处理技术的重要性,但并行处理技术的发展道路并不平坦。
从70年代到90年代中期,中间几起几落,究其原因,就是并行计算技术仍然遇到若干困难,使其无法推广应用。
这其中既有软件方面的(并行程序设计)问题,也有硬件方面(并行处理机)的原因。
并行处理是提高计算机系统性能的重要途径。
目前几乎所有的高性能计算机系统,都或多或少地采用了并行处理技术。
本文主要就分布式并行处理技术做简要的介绍
关键词:
分布式系统,网络,并行处理技术,并行处理机
1绪论
1.1概述
计算机从1946年的ENIAC机问世以来,至今已经历了五次更新换代。
每一代计算机的性能都成数量级倍的提高,计算机的体积、重量、价格、稳定性、可靠性、可维护性及功能的多样性等均有了显著的改善。
人们通常以电子管、晶体管、中小规模集成电路、大规模和超大规模集成电路等器件的变革作为计算机换代的标志。
但是,计算机系统实际上是器件、硬件、软件、算法、语言、系统结构以及通讯技术等的综合,所以计算机的换代也反映在上述各方面的巨大变革上。
促使计算机迅速发展和系统性能极大提高的因素是多方面的,其中,器件技术尤其是微电子技术的迅速发展无疑是最为关键的因素,它是计算机得以迅速发展的物质基础。
然而,应当看到,如果不能最合理地利用这些新器件、新设备,最大限度地发挥出它们的内在潜力,设计和构成综合性能指标最佳的计算机系统,只靠器件技术的变革是不行的,还需要硬件、软件、算法、语言、系统结构、通讯技术等多方面的发展变革才行。
在特定的时期里,器件的发展变化会因物理、工艺、价格等条件限制而有一定限度。
在同一种器件技术水平上,进一步提高计算机系统性能的有效途径就是在系统结构上使用并行处理技术,挖掘出系统固有的并行性潜力,提高其并行性操作的程度。
并行性在不同的处理级别中可表现为多种形式,如先行方式、流水方式、向量化、并发行、同时性、数据并行性、划分、交叉、重叠、多重性、重复、时间共享、空间共享、多任务处理、多道程序、多线程方式和分布式计算等
1.2国内相关研究
近10a来,我国在多处理机系统特别是分布式并行处理系统方面的研究已硕果累累,现简介如下:
(1)BJ-02系统
它是1991年由中国科学院计算技术研究所研制成的一个分布式MIMD系统。
有17个处理器节点,其中一个主节点承担与主机的通信;16个从节点构成一个四维超立方体或网格结构。
节点之间采用消息传递机制来实现并发同步。
4个处理器做到一个插件板上,整个系统有4块插件板,它们插到微机的总线插槽上作为PC微机的加速板使用。
(2)BJ-1系统
这是中科院计算技术研究所、中科院计算中心、东南大学、中国科技大学和复旦大学联合研制的一个分布式MIMD并行系统,于1994年7月研制完成。
它是国家自然科学基金委的“七五”重大项目“并行计算机及并行算法”的研究成果。
整个系统由2个处理器簇组成,每簇有两个i860/XP处理器。
处理器簇间通过双端口存储器进行消息传递;簇内的处理器之间通过快速总线通信。
因此,它既可采用共享内存的同步机制,又可采用消息传递的模式来实现处理机的并发和同步。
(3)江南3号系统
它是由江南计算技术研究所于1994年研制成功的一个分布式MIMD系统。
整个系统有10个i860/XP处理器。
处理器之间通过总线进行消息传递。
其系统结构是一种共享内存与分布式局域存储相结合的混合结构,因此,既可以使用共享内存同步机制又可采用消息传递模式进行程序设计。
(4)曙光1000并行系统
国家智能机中心在成功推出曙光1号后,又于1995年5月推出曙光1000分布式存储MPP多处理机系统。
该系统目前由36个处理节点组成。
其中有32个计算结点,2个I/O结点和2个服务结点。
所有节点经过一个二维连接的路由芯片网络相连。
在每个路由芯片中采用Wormhole算法决定路由。
据报道,其浮点运算速度可达每秒25亿次。
而每秒500亿次和每秒3000亿次的新一代MPP分布式并行计算系统也正在紧张研制之中。
2分布式系统
2.1分布式系统的定义
分布式系统是若干独立计算机的集合,这些计算机对于用户来说就像是单个相关系统。
这包含了两方面的内容。
第一个方面是关于硬件的:
机器本身是独立的。
第二个方面是关于软件的:
对用户来说他们就想在于单个系统打交道。
如果一个系统的部件局限在一个地方,它就是集中式的;如果它的部件在不同地方,部件之间要么不存在或仅存在有限的合作,要么存在紧密的合作,它是分散式的。
当一个分散式系统不存在或仅存在有限的合作时,它就被称作网络的;否则它就被称作分布式的,表示在不同地方的部件之间存在紧密的合作。
在给出分布式系统具体定义的模型中,分布式系统可以用硬件、控制、数据这三个维度加以检验。
从狭义上分析,分布式计算就是在两个或多个软件互相共享信息,这些软件既可以在同一台计算机上运行,也可以在通过网络连接起来的多台计算机上运行。
从广义上讲,它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后把这些部分分配给许多计算机进行处理,最后把这些计算结果综合起来得到最终的结果。
因此分布式计算比起其它算法具有以下几个优点:
1.稀有资源可以共享。
2.通过分布式计算可以在多台计算机上平衡计算负载。
3.可以把程序放在最适合运行它的计算机上。
其中,共享稀有资源和平衡负载是计算机分布式计算的核心思想之一。
2.2分布式系统的特性
分布式系统有以下几个主要特性:
有多个对等进程进行合作,明确了具体的工作目标,有个性化的控制方式(这是分布式系统设计的核心问题),具有数据共享/消息传递的功能,系统设计考虑了网络通信的延迟,具有故障化解的能力。
概括地讲具有分布式的、网络的、并行的、并发的和分散的五个特点。
“并行的”意味着从一个单一控制线程对数据集的锁步(10ckstep)动作。
在并行计算机级别上,单指令流多数据流(SIMD)计算机就是一个使用多个数据处理单元在许多数据项上同时进行相同或相似操作的例子。
“并发的”意味着某些动作可以以任意次序执行。
例如,在更高级别上和在多指令流多数据流(MIMD)并行计算机上进行部分独立的操作。
“分布式的”意味着计算的成本或性能取决于数据和控制的通信。
分布式系统一般具有以下4个关键目标,即分布式系统能够让用户方便地与资源连接;必须隐藏资源在一个网络上分布这样一个事实;必须是开放的;必须是可扩展的。
同时也要注意解决的以下几个基本问题:
进程通信、命名、同步、一致性与复制、容错、安全等。
只有解决好上述几个关键目标和基本问题,这个分布式系统才会稳定、高效,真正的物有所值。
2.3分布式系统的拓扑结构
分布式系统有着多样化的拓扑结构,分为规则和不规则的结构,常用的有如下几种静态拓扑结构。
1.直线型:
所有处理机排列在一条直线上,内部结点有2个连接,而边界结点只有1个;
2.环型:
将直线型拓扑的边界结点相连所构成的拓扑;
3.树型:
任意两个结点间只存在唯一的通路;
4.星型:
N个结点所构成的一个2层的树,其中一个结点的度数为N-1,其余结点的度数均为1;
5.网格:
由n维,每维均有K个单元整齐排列构成的;
6.超立方:
由一个n维立方体的顶点(结点)和棱(边)构成的拓扑。
3并行处理技术
并行性主要是指同时性或并发性,并行处理是指对一种相对于串行处理的处理方式,它着重开发计算过程中存在的并发事件。
并行性通常划分为作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级。
作业级的层次高,并行处理粒度粗。
粗粒度开并行性开发主要采用MIMD方式,而细粒度并行性开发则主要采用SIMD方式。
开发计算机并行性的方法主要有:
资源重复、时间重叠和资源共享三种方法。
3.1、并行的概念
3.1.1并行性
只要在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或不同的工作,它们在时间上相互重叠,都体现了并行性。
也就是说,并行性包括同时性和并发性两重含义。
同时性(simultaneity)指的是两个或多个时间在同一时刻发生,并发性(concurrency)指的是两个或多个事件在同一时间间隔内发生。
3.1.2并行等级的划分
并行性可以划分为不同的等级,从不同的角度出发,等级的划分方法也不一样。
(1)从计算机系统内部执行程序的角度来划分
指令内部——一条指令内部各种微操作之间的并行
指令之间——多条指令在某一时刻或同一时间间隔内并行执行
任务或进程之间——多个任务或程序段之间的并行执行
作业或程序之间——多个作业或多道程序之间的并行执行
(2)从计算机系统中处理数据的并行性角度来看
字串位串——同时只对一个字的一位进行处理,通常指传统的串行单处理机,没有并行性
字串位并——同时对一个字的全部位进行并行处理,通常指传统的并行单处理机,开始出现并行性
字并位串——同时对许多字的同一位进行处理,开始进入并行处理领域
字并位并——同时对许多字的全部或部分位组进行处理。
(3)从计算机信息加工的各个步骤和阶段来看
存储器操作并行——可以采用单体多字、多体单字或多体多字方式在一个存储周期内访问多个字,进而采用按内容访问方式在一个存储周期内用位串字并获全并行方式实现对存储器中大量字的高速并行比较、检索、更新、变换等操作。
典型的例子就是并行存储器系统和以相联存储器为核心构成的相联处理机。
处理机操作步骤并行——处理机操作步骤可以指一条指令的取指、分析、执行等操作步骤,也可指如浮点加法的求阶差、对阶、尾加、舍入、规格化等具体操作的执行步骤。
操作步骤并行就是将操作步骤或具体操作的执行步骤在时间上重叠流水地进行。
典型的例子就是流水线处理机。
处理机操作并行——为支持向量、数组运算,可以通过重复设置大量处理单元,让它们在同一控制器控制下按照同一条指令的要求对多个数据组同时操作。
典型的例子就是并行处理机。
指令、任务、作业并行——这是较高级的并行,虽然它也可包含如操作、操作步骤等较低等级的并行,但原则上与操作级并行是不同的。
指令级以上的并行是多个处理机同时对多条指令及有关的多数据组进行处理,而操作级并行是对同一条指令及其有关的多数据组进行处理。
因此,前者构成的是多指令流多数据流(MIMD)计算机,后者构成的则是单指令流多数据流(SIMD)计算机。
典型的例子是多处理机。
3.1.3实现并行处理的技术途径
实现并行处理的技术途径是各种各样的,其中主要有时间重叠、资源重复和资源共享等方法。
时间重叠在并行性概念中引入时间因素,使多个处理过程在时间上错开,轮流重叠地使用同一套硬件设备的不同部件,以加快硬件周转而赢得速度。
最典型的例子就是流水线工作方式。
时间重叠原则上不需要重复增加硬件设备就可提高系统的性能。
资源重复在并行性概念中引入空间因素,通过重复设置硬件资源,如处理机或外围设备等,来达到大幅度提高可靠性和处理速度的目的。
资源共享让多个用户按一定时间间隔轮流使用同一套资源,以提高系统的整体性能。
3.2指令并行处理
指令并行技术是在微处理器发展初期引入的,其前身是8086中不太典型的2级流水线,目前其技术发展已十分成熟。
主要包括超流水(SuperPipeline)、超标量(SuperSalar)、以及指令宏融合、超宽区动态执行等技术。
超流水技术是在通过分侧细化指令,加深流水线(Pipeline)深度,使一个周期内尽可能多地指令在流水线中“并行”执行,从而提高CPU效率。
比如:
NetBurst微架构的Northwood核心Pentium4CPU中流水线深度多达20级。
而Prescott核心的Pentium4中流水线深度更是达到了创纪录的31级。
超标量技术是通过增加核心中的流水线数来实现指令的并行执行的。
比如:
在Pentium中由U(复杂)、V(简单)实现的简单发超标量。
在Core微架构中有四个指令解码器和三条全功能流水线,从而实现真正的指令级并行。
指令宏融合技术是Pentium引入的技术在Core微架构中的发扬,其解码器可以对一些相关联的指令进行宏融合。
如cmp和jne融合成cmpjne,从而在一个周期内执行两条指令。
由于指令并行技术很大程度上提升了CPU的执行效率,因此,这种技术广泛的被应用在CPU中,但其也存在难以克服的局限性。
例如,流水线深度不能随着加深,加深流水线深度虽然提升CPU效率,但同时也提升了CPU的功耗,加大了CPU的发热量,使CPU工作不稳定。
超标量技术虽然可以实现理论意义上的真正的指令并行,但由于指令的相关性,绝对的指令并行就目前技术来看是不可能的。
这是由于不同程序对运算单元的孺求是不同的,如3DMax、Maya等需要大量浮点运算单元,而一些商业办公软件需要进行更多的是整形运算。
由于不同程序对运算单元的需求不同,就不可避免的会出现较多的运算单元空闲,而更深更多的流水线也加剧了这种现象的产生.据Intel调查表明大部分桌面程序代码只使用了35%的Pentium4的执行单元,其资很浪费之严重可见一斑。
3.3线程并行处理
线程级并行处理指在系统上同时并行执行多个线程,是并行处理技术主要实现方式。
目前应用较多的主要有多线程技术(Hyper一Threading,HT),多处理器系统(Multi一Processors,MP),多核心处理器(Multi—Core,MC)以及新发展出的通用图形处理器(GeneralPurposeGraphicProcessunit,GPGPU)等技术。
超线程技术很于同步多线程技术(SunultaneousMulti一Threading,SMT),其本质是利用CPU上空闲的资像在一块CPU核心上虚拟出两个逻辑CPU,从而拥有两条线程并行执行的能力。
采用HT技术的CPU,每个逻辑核心都拥有自己独立的IA一32架构状态单元(IA一32architecturalstate)、全部的数据寄存器、段寄存器、控制寄存器、debug寄存器和大多数模块定义寄存器(DefineModelSpecifiicRegister,MSR),并且还有独立的高级可编程中断控制器(advancedprogrammablein-terruptcontruller,APIC)两个逻辑核心共享前端总线(FSB)和内核中的执行资源。
多处理器(MP)技术是采用总线网络、高速光纤通道甚至网络电缆把多个CPU(主机)相连。
在HT技术出现前,多处理器技术几乎是唯一实现线程级并行的解决方案,发展相对较为成熟。
主要包括共享内存式架构(SharedMemoryArchitecture)、消息传递架构(Message一PassingArchitecture)、混合式架构(Mixed一TypeMultiprocessorArehitecture)三种体系结构。
多核心技术是近几年半导体工艺高速发展的产物,把多个完整的CPU核心做在一个晶片(die)上,多个核心共享前端总线,核心间通过二级缓存或芯片级的总线逻辑单元(如HyPer一Transport、CSI)传输数据。
3.4并行程序设计
在并行处理技术中,并行程序是最为核心的领域之一。
没有好的并行程序的支持,并行处理机就不可能很好的工作,所谓超级计算也就更加无从谈起了。
并行程序设计方法不同于顺序程序设计方法,主要在于对问题采取何种看法:
顺序程序设计方法把事物的变化发展看成是单线程的,任何两种事物之间必然存在因果关系,从而把一系列统一事物看成是不可分割的整体。
后来的结构程序设计特别是对象式程序设计把一个复杂的事物分解成多个简单的事物,或者把一个系统看成是由多个相互联系的实体构成的。
应该说,这里在对事物的认识上取得了突破性的进展,但也是从事物的静态结构上来看的,并未从行为上来分解。
从行为上来看,它们仍然被认为或者是一致的,或者是先后相继的,相互之间不存在有并发干扰现象,更不存在可同时发生的相互作用的行为。
并行程序设计方法的一个最基本的观点,就是把一个事物的行为看成是多个事物互相作用的结果。
这是一个观念上的根本转变,根据这个观点,并行程序设计方法的核心内容就是并行划分与算法映射。
其理论基础是并行计算模型。
并行计算模型决定了并行语义,并行语义决定了可并行执行的准则,从而决定了并行划分的原则。
要研究并行程序设计,首先就要讨论并行算法的结构,这涉及到对并行算法的理解、并行程序设计方法、并行算法与并行系统结构匹配等问题。
所谓并行算法结构,就是构成并行算法的基本组成部分与属性及其互相之间的关系。
一般来讲,一个并行算法结构由以下几部分组成:
(1)划分模式,即并行划分类型与并行模块;
(2)合作模式,即合作方式与计算图;
(3)映射(分配)格局;
(4)通信模式;
(5)运行模式。
一个并行算法的结构既是该算法的骨架,也是该算法的精髓,这些方面确定了,这个算法也就基本上确定了。
理解或者说一个算法,都可以从这几个方面来考虑。
算法结构应当与机器结构相匹配,这是提高应用程序实际执行性能的一条重要途径。
因此,从算法结构应与机器系统结构相匹配的观点出发,对算法结构作一个分类,具有重要的实际意义。
根据算法结构的组成部分,我们按以下优先级进行分类:
运行模式→通信模式→并行划分类型与合作模式。
分类情况如下:
1.同步操作
(1)公共变量型
(2)消息传递型
向量型水平数据划分+分工式
水线型垂直划分+接力式
脉动型水平垂直划分+接力式
2.异步操作
(1)公共变量型
(2)消息传递型
数据流型垂直水平划分+合力式
对话型垂直水平划分+对话式
过程型(归约型,对象型)垂直水平划分+请求式
会议型垂直水平划分+会议式
SPMD型水平划分+分工式
MPMD型混合划分+合力式
以上这些算法结构类型,大多数都有一种特定的系统与之对应。
算法结构的分类,对于设计一个满足与系统结构相匹配的算法也是很有意义的。
3.5并行处理机
好的并行程序也要在好的并行处理机上运行,才能发挥出最大的能量。
并行机按系统结构划分可分为以下五类:
向量流水巨型机、SIMD阵列机、共享主存多处理机、分布存储多计算机和联网计算机。
3.5.1SIMD并行计算机(阵列处理机)
阵列机也称并行处理机。
它将大量重复设置的处理单元按一定方式互连成阵列,在单一控制部件CU(ContrulUnit)控制下对各自所分配的不同数据并行执行同一指令规定的操作,是操作并行的SIMD计算机。
它采用资源重复的措施开发并行性。
是以SIMD(单指令流多数据流)方式工作的。
1、阵列机的基本结构
阵列机通常由一个控制器CU、N个处理器单元PE(ProcessingElement)、M个存储模块以及一个互连网络部件(IN)组成。
根据其中存储器模块的分布方式,阵列机可分为两种基本结构:
分布式存储器的阵列机和共享存储器的阵列机。
阵列机的主要特点:
它采用资源重复的方法引入空间因素,这与利用时间重叠的流水线处理机是不一样的。
它是利用并行性中的同时性而不是并发性,所有的处理单元必须同时进行相同操作(资源重复同时性)(我们想象一下亚运会的开幕式大型团体操表演,每个人就是一个PE,他们听从一个总指挥的指令,同时进行自己的操作,很快地就能“计算”出一个结果(队形)来。
它是以某类算法为背景的专用计算机,基本上是专用于向量处理的计算机(某类算法专用机)。
阵列机的研究必须与并行算法研究密切结合,以使它的求解算法适应性更强一些,应用面更广一些(并行算法合研究)。
阵列机实质上是由专门对付数据组运算的处理单元阵列组成的处理机(M个PE)、专门从事处理单元阵列的控制及标量处理机(控制器CU)和专门从事系统输入输出操作及操作系统管理的处理机三部分构成的一个异构型多处理机系统(三个部分成异构)。
3、阵列机的并行算法
阵列机的算法是与结构紧密联系在一起的,阵列机上常用的算法有矩阵计算、图形处理等,我们对教材中举的两种算法要领会,特别是累加和递归操作,不难理解。
它就是使各个处理器同时进行加的操作,但并不是全部处理器都参加运算,在处理时,根据累加计算的需要,由控制器CU借助屏蔽的方式将一部分PE设置成不活动的状态。
这种累加操作的速度提高倍数是N/log2N倍。
3.5.2多处理机
多处理机具有两台以上的处理机,在操作系统控制下通过共享的主存或输入输出子系统或高速通讯网络进行通讯。
多处理机属MIMD系统。
多处理机与SIMD相比有较大不同,表现在:
◎结构灵活性:
MIMD机结构上具有更大灵活性和更强的通用性;
◎程序并行性:
前者是作业级并行,后者则是操作级并行;
◎并行任务派生:
前者需要由专用语句显式指明是否派生并行任务,而后者则不需要专门指令;
◎进程同步:
MIMD机中各进程的同步需要采取特殊措施来保证,而SIMD机则由于受同一控制器控制,自然是同步的;
◎资源分配和调度:
MIMD机任务调度要采用软件手段,而SIMD机中,只需用屏蔽来控制实际参加并行操作的处理单元数目。
多处理机在系统结构上分为两类:
紧耦合和松耦合系统。
紧耦合是通过共享主存实现处理机间的互相通信,处理机间的相互联系比较紧密。
按所用处理机类型是否相同及对称,又可分为同构或异构及对称或非对称的形式。
常见组合是同构对称式和异构非对称式多机系统。
松耦合是通过消息传递方式来实现处理机间的相互通信,而每个处理机是由一个独立性较强的计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 并行 处理 机制 研究 要点