并行数据算法简介课件

《并行数据算法简介课件》由会员分享，可在线阅读，更多相关《并行数据算法简介课件（34页珍藏版）》请在金锄头文库上搜索。

1、数据并行算法,谢莹,数据并行算法,被称作数据并行算法是因为它要对大量数据同时进行操作。它甚至可以解决那些第一眼看去属于串行的操作。,机器模型,可以完成一般通信的并行机器模型以Connection Machine System（简称CMS） 为基础。,系统有两部分组成,前端计算机（冯诺依曼结构）,一组Connection Machine 处理器,每个处理器都有一个本地内存。对前端来说，处理器组就好像一个存储器。处理器组与前端计算机的内存总线相连，所以前端可以直接访问处理器组的本地内存。处理器组扩大了前端的指令集，使其可以对大量数据进行同时操作。,机器模型,对于运行在CMS上的程序，是由前端计算机

2、按照通常的方式执行。处理器组按照SIMD的方式执行命令。一个从前端传来的简单的指令作用于多个数据项，每个处理器负责一个数据或几个。 许多指令的执行是有条件的：每个处理器有个状态位（被称为context flag）来决定哪条指令它将执行。由前端计算机设置处理器的context flag. 有些指令的执行是没有条件的：这些指令不考虑context flag的值，被所有的处理器执行。这些指令用来存储contexts. context：所有context flags 的值的集合。,机器模型,这些处理器可以独自执行所有常用的逻辑、整型、浮点型操作。另外，在前端计算出来的简单的值可以从前端同时广播到所有的

3、处理器。 这种计算机系统有大量的并行处理器，每个处理器都有一个本地存储器并且具有执行指令的能力。这种Connection Machine 还有两个特点：基于指针的通信和虚拟处理机。 这种CMS允许处理器与其它处理器在单位时间内直接通信，而且其它的处理器也可以并发通信。这种通信通过SEND指令实现。SEND 指令有两个操作数：1.数据将被发送到的地址（在处理器内），2.处理器指针，数据将被发送到哪个处理器。,机器模型,在实际的实现过程中，并没有那么多数量的硬件处理器，有些程序作为虚拟处理器，而硬件处理器在需要的时候作为多路复用。所以前端处理器通常与虚拟处理器通信。 虚拟处理器有两个好处：1.同样

4、的程序可以不经改变地运行在不同型号的CMS上。2.我们可以认为处理器的数量是可以增加的，而不是固定的。,机器模型,在接下来的讨论中，我们认为处理器的大小和数目是足够多的。我们采用一种模型，在这个模型中，以下操作被看成单位时间操作。 任何常见的word-at-a-time运算； 任何类似的可以适用所有数据元素同时进行的运算，或适用一些特定的子集同时运算的操作； 涉及到对所有数据元素进行广播的操作； 每个数据元素间不多于一个的消息传输的通信步骤。 为了便于分析，把processor-cons也看成单位时间操作。在Connection Machine模型中，可以用processor-cons来分配新

5、的内存，但是新分配的内存附属于创建它的处理器。,并行程序的例子,数组求和 数组的所有部分求和 基数排序 分析正则语言 并行指针处理 并行组合减少,求链表的尾部 求链表的所有部分和 两个链表中元素相互匹配 区域标记 递归数据并行,数组求和,类似于求二叉树叶子节点的和。数组的每个元素位于叶子节点。每一个非叶子节点的值是它左右两个孩子的值的和。根节点即为所有叶子节点（数组的所有元素）的和。,数组求和,算法描述：,处理器的个数与数组元素的个数相同。每个处理器存一个数组元素。 for all k in parallel do s：指所有的处理器都执行s语句。 K代表每个处理器，也可理解为每个处理器的下标

6、。,假如数组有a0, a1, a2, a3四个数。总共循环两次。 k: 0 1 2 3 j为1,执行后，a0不变，a1里存放的是a0和a1的和，a2不变，a3里存放的是a2和a3的和。 j为2,执行后，a0 a1 a2不变，a3里存放的是a3和a1的和。其实a3里存放的是最初的a0, a1, a2, a3的和。,数组求和,数组的所有部分求和,在数组求和的算法中，有很多处理器是空闲的，在第j行只有n/ 个处理器在工作。如果我们充分利用闲置的处理器，求和算法就可以在计算单个求和的时间内求出数组的所有部分和。,数组的所有部分求和,if语句中， 应改为 。,假如数组有a0, a1, a2, a3四个数

7、。总共循环两次。 j为1,执行后，a0不变；a1里存放的是a0和a1的和；a2存放的是a1和a2的和；a3里存放的是a2和a3的和。 j为2,执行后，a0 a1不变；a2里存放a0和a2（a1a2的和），即现在a2里放的是最初a0,a1,a2的和；a3里存放a1（a0a1的和）和a3（a2a3的和）的和，即现在其实a3里存放的是最初的a0, a1, a2, a3的和。,数组的所有部分求和,与之前的求和算法的不同之处：if语句决定 哪个处理器执行任务，在这里if语句使更多的处 理器处于工作状态。 在第j行，有n- 个处理器在工作。,数组的所有部分求和,分析正则语言,把一个长的字符串分解成各个标识

8、符。,上面的处理过程被称为lexing a string。 这种类型的正则语言可以被理解成一个有限状态机，开始有一个起始状态，然后每读入一个字符，就从一个状态转向另外一个状态。,分析正则语言,分析正则语言的有限状态机一种有以下9种状态： N：初始状态。 A：字母标识符的开始。 Z：字母标识符的继续。 *：单个的特殊的字符标识符。 字符。 =：跟在 后面的=，即=中的=。如果是单个=，则应转向状态*。 Q：表示一个字符串开始的双引号。 S：表示字符串中的字符 E：表示一个字符串结束的双引号。 注意：如果处于这些状态：A,*,Q，说明刚刚读入的字符是一个标识符的开始。,状态转换图,在转换过程中可能

9、遇到以下6种操作： 1：表示读入一个字母字符 2：表示读入一个单个的特殊字符，如：+、-、* 3：表示读入字符 4：表示读入字符= 5：表示读入一个双引号 6：表示space或者new line,状态转换图,分析正则语言的并行处理,每个处理器存放一个字符。例如：分析int a; step1:用一个数组去代替这个字符，这个数组指的是在这9种状态下读入当前字符之后的状态。数组的下标可以理解为读入这个字符之前的状态。,分析正则语言的并行处理,每个处理器存放一个字符。例如：分析int a; step2:修改每个处理器中的数组的下标。读在它之前的那个处理器之后的状态如果和它的下标一样，则把它之前的那个处

10、理器的下标改成它的下标。则现在处理器中的数组就变成从这个字符串的开始一直读到它自己的字符后的状态。,分析正则语言的并行处理,在每个处理器的数组中，下标为N的那个状态就指的是在初始状态下，从字符串的开始读到当前这个字符后应该处于的状态。 在下面的表格中，黄色代表读完它之前的那些字符不可能出现的这种状态。,分析正则语言的并行处理,根据上面的结果： 在N状态下，读完字符i的状态为A； 在N状态下，读完字符in的状态为Z； 在N状态下，读完字符int的状态为Z； 在N状态下，读完字符int space（空格）的状态为N； 说明一个标识符结束！ 在N状态下，读完字符int space a的状态为A； 在

11、N状态下，读完字符int space a;的状态为*。 说明当前读入的字符是另一个标识符的开始，即上一个标识符结束。 则int a;被分解为int, a, ;, 三个标识符。,基数排序,首先，基数排序是一种稳定的排序。在本算法中，依次从低位开始判断一个二进制数。判断某位的值是0还是1，把是0的数放在前面，是1的数放在后面。然后判断下一位，如此循环。当所有的位都判断完成之后，这个数组就已经按照从小到大或者从大到小的顺序排列了。 count:计算所有被激活的处理器的个数。 enumerate:给所有处理器表上序号。如果有n个处理器，则处理器的序号从0到n-1。,基数排序,二进制有几位循环几次 如果

12、此处if语句成立，则说明这个数从低位数第j位为0. yk:给所有j位为0的标上序号（0到c-1) c:j位为0的数的个数 如果此处if语句成立，则说明这个数的第j位为1. yk:从c到n-1 这一步就把j位为0的放在了前面，因为它们的yk在前面（0到c-1)，把j位为1的放在了后面。,找出链表的尾部,基本思想：首先，每个节点都有一个chum指向它的下一个节点；然后每次都用它的chum的chum去代替它的chum。 最开始，chum指向跟着这个节点的第一个节点；第二步后，chum chum指向跟着这个节点的第二个节点；第三步后，chum指向跟着这个节点的第四个节点。 整个执行完成之后，每个节点的

13、chum都指向这个链表的结尾。,找出链表的尾部,这个为chum指针,求链表的所有部分和,这个算法的理解可以参照数组的局部求和。这种算法的好处是它可以不改变代码同时作用于不同长度的链表。,求链表的所有部分和,这个为chum指针,两个链表中元素相互匹配,这个算法的目的是让两个链表中相对应的两个元素相互连接起来。把两个相互对应的元素称为一对朋友。链表中的每个节点都有一个friend指针指向它在另一个链表中的朋友。 基本思想：AB互为朋友，A的chum的朋友为A的朋友B的chum。然后把所有chum变成chum的chum。,区域标签,二维图像中，相互连接在一起具有相同像素值的最大集合为一个区域。每个区

14、域都应该有一个标签，并且这个标签要分配给区域中的每个像素。 N个处理器，每个处理器存放一个像素。我们把具有相同像素值的处理器的地址的最大值作为这个区域的标签。并且标签存放在largest变量中。,区域标签算法一,每个处理器的largest初始为它自己的地址值。然后每个处理器跟所有与它相邻的具有相同像素的处理器的largest值进行比较，把它们的largest替换成大的地址的值。最终，最大的地址值会传播给这个区域的每个像素。,区域标签算法二,每个像素与周围的邻居进行通信，可以知道它自己是否位于这个区域的边界。如果是，则它的邻居也位于区域的边界。则让这个像素为它的邻居建立指针。最后所有的边界相互连接，组成一个双向链表。 假如处理器的地址为x+Wy的形式（x,y是二维坐标，W是图像的宽度）。则具有最大地址的处理器肯定位于这个区域的边界，那么边界上的处理器会决定出哪个地址值作为标签。同时把这个值向区域内部传播。,区域标签说明为什么A=x+Wy，则最大地址位于边界,表格中，每个小方块作为一个像素。红色的为横坐标X，蓝色的为纵坐标Y。黑色的为这个像素存放在的处理器的地址A。这个图片的宽度W为4。 A=x+Wy. 随便选中一个区域，不难发现，地址值最大的那个像素肯定是位于这个区域的边界中。,y,x,