并行处理技术

《并行处理技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章并行处理技术要点并行性SIMD计算机多处理机系统并行机的发展9.1并行处理技术的发展1.并行性基本概念并行性在数值计算、数据处理、知识处理/人工智能求解过程中可能存在能同时运算/操作的部分。同时性：同一时刻发生的两个/多个事件并发性：同一时间间隔内发生两个/多个事件并行性开发并行性的目的能进行并行处理，提高计算机系统求解问题的效率。并行性颗粒度G每次并行处理的规模大小G=TW/TC所有处理器计算时间总和所有处理器通信时间总和TW=∑twii=1PTC=∑tCii=1P系统共有P个处理器TC较大时，G较小，处

2、理粒度较细，通信量大。并行处理：开发计算过程中并发事件的信息处理方式并行性等级并行处理：任一级/多级上的并行性开发粗（细）粒度并行性开发采用MIMD（SIMD）作业级（程序）任务级（过程/程序段）子任务级（例行程序，子程序）指令/语句循环/递归循环层次5层次4层次3层次2层次1通信需求与调度开销并行处理粒度粗粒度细粒度细2.并行性的开发策略并行性概念中引入时间因素。多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各部分，加快硬件周转而赢得速度。①时间重叠②资源重复例：流水操作并行性概念中引入空间因素。

3、重复设置硬件资源来提高系统可靠性/性能。例：n个完全相同的处理器，受同一控制器控制的以SIMD方式工作的系统。软件方法让多用户按一定时间顺序轮流使用同一套资源，提高利用率。③资源共享例：多道程序，分时系统并行性的开发①开发细粒度并行性--采用硬件，辅以软件例：指令级/循环级上借助于并行化/向量化编译器进行开发；RISC，超标量，VLIW，超级流水等技术例：作业/程序级并行性在于对并行算法的分析；任务级并行性开发在于分解任务：任务中的各子任务及其循环/例行程序分配到不同处理器上。②开发粗粒度并行性--利用软件9.2

4、SIMD并行计算机（阵列处理机）1.阵列机的基本结构CUPEN个MM个IN阵列机指令广播给PE活跃的PE同步地执行指令PE/PE和M间实现通信连接--细粒度并行性开发主要采用SIMD方式2.阵列机的分类分布式存储器的阵列机分类依据存储器模块是分布式/集中式存取对指令译码，判断它在何处执行数据对象PE间数据交换，单向性CUP0INPE0M0Pn-1PEn-1Mn-1指令活跃PE非活跃PE存储器：存放系统/用户程序，共享数据运算部件：执行标量/控制指令CU向量指令集中式存储器的阵列机CUPE0INPE1M0PEn-1

5、…Mm-1指令M1数据对象PE、M间的数据交换通路，双向性3.阵列机的特征C=PE数确定互连网络结构及连接拓扑的参数指令集，进行标/向量，数据传送通路操作，网络变换操作屏蔽方式集合，每个PE没有局存，存储器模块以集中形式通过IN为所有PE共享4.阵列机的主要特点利用资源重复（空间因素）而非时间重叠；利用同时性而非并发性。每个PE在同一时刻同等地担负起运算功能；提高运算速度靠增大PE个数，比向量流水线处理机靠缩短时钟周期，速度提高的潜力大得多；使用简单、规整的IN确定多个PE间的连接模式；阵列机研

6、究+并行算法研究，使之适应性更强，应用面更广；异构型多处理机（PE+CU+前端机）。同构型并行机相同的PE阵列机通过各种途径把数据转化为对数组/向量的处理，利用多个处理单元对向量/数组包含的各分量同时运算，易于获得很高的处理速度。5.阵列机的并行算法①图象平滑化算法平滑输入图象的灰度级（表示象素的黑色程度，0—白色，255—黑色）S输入图象输出图象I512*512I（i,j）512*512S（i,j）I(i,j)I(i-1,j-1)I(i,j-1)I(i+1,j-1)I(i+1,j)I(i+1,j+1)I(i,j

7、+1)I(i-1,j+1)I(i-1,j)=I（i，j）和8个最邻近的象素的灰度级的平均值数据分配并行处理完成的平滑操作：16*16=256次串行处理完成的平滑操作：512*512=262144次PE0PE1PE31PE32…PE992…PE1023512象素512象素PEJ16象素16象素32*32∴并行算法比串行算法快：262144/256=1024倍PE间数据传送PEJ16象素16象素16象素16象素1象素1象素1象素1象素并行数据元素的传送数：4*16+1*4=68次计入PE间传送的时间，设每次并行数据传

8、送时间相当于1次平滑操作时间，则改进倍数：262144/（256+68）=809倍②递归折叠方法例：求向量元素累加和。某向量含N个向量元素，求这些元素的累加和。（1）单机中的串行方法N-1次加法（2）递归折叠方法PE值步1步2步30A0A0+A1A0+A1+A2+A3A0+A1+…+A71A12A2A2+A33A34A4A4+A5A4+A5+A6+A75A56A6A6+A