📄 chapter1_2.htm
字号:
<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>算法与数据结构 -- 列表的并行前缀</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter1_1.htm";
next = "chapter1_3.htm";
contents="";
topic="并行算法——指针转移";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>1.2 列表的并行前缀</h3>
<p>指针转移技术远不止应用于表排序问题。在算术电路中可以运用“前缀”计算来执行快速二进制加法。现在我们来探讨如何运用指针转移技术来进行前缀计算。有关前缀问题的EREW算法对由n个对象组成的表的运行时间为O(lgn)。</p>
<p>前缀计算是根据二进制中满足结合律的运算符<font face="MT Symbol">Ä</font>来决定的。计算时输入为序列<x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>>并产生一个输出序列<y<sub>1</sub>,y<sub>2</sub>,...,y<sub>n</sub>>，满足y<sub>1</sub>=x<sub>1</sub>，并且对k=2,3,...,n，有</p>
<blockquote>
<p><img border="0" src="images/Eqn2.gif" width="141" height="48"></p>
</blockquote>
<p>换句话说，每个y<sub>k</sub>是序列的头k个元素一起“相乘”而得到的。因此才有“前缀”这一意义。</p>
<p>作为前缀计算的一个实例，假定n个对象组成的表中的每个元素包含的值为1，并设<font face="MT Symbol">Ä</font>表示普通加法运算。因为对k=1,2,...,n，表中第k个元素包含的值为x<sub>k</sub>=1。所以前缀计算后的结果为y<sub>k</sub>=k，即为第k个元素的下标。因此，进行表排序的另一种方法是先把表颠倒(可以在O(1)的时间内完成)，执行前缀计算，然后把计算所得的每个值减1。</p>
<p>我们现在说明EREW算法是如何在O(lgn)的运行时间里对n个对象组成的表进行前缀计算的。为了方便起见，我们定义符号记法：</p>
<blockquote>
<p><img border="0" src="images/Eqn3.gif" width="160" height="25"></p>
</blockquote>
<p>其中整数i和j满足1≤i≤j≤n。则对k=1,2,..,n，有[k,k]=x<sub>k</sub>，并且对0≤i≤j≤k≤n，</p>
<blockquote>
<p><img border="0" src="images/Eqn4.gif" width="145" height="21"></p>
</blockquote>
<p>根据这一符号记法，前缀计算的目标就是计算y<sub>k</sub>=[1,k]，k=1,2,..n。</p>
<p>当我们对表进行前缀计算时，我们希望输入序列<x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>>的顺序由对象在链表中的链接关系来确定，而不是由存储对象的存储器阵列中对象的下标来确定。下列EREW算法开始时，表L中每个对象i都有一个相应的值x[i]。如果对象i是从表头开始的第k个对象，则x[i]=x<sub>k</sub>为输入序列中的第k个元素。因此，并行前缀计算产生y[i]=y<sub>k</sub>=[1,k]。</p>
<pre><code class="pseudocode">List-Prefix(L)
1. for 每个处理器i，并行地执行
2. do y[i] ← x[i]
3. while 存在一个对象i满灶next[i]≠NIL
4. do for 每个处理器i,并行地执行
5. do if next[i]≠NIL
6 then y[next[i]]← y[i]<font face="MT Symbol">Ä</font>y[next[i]];
7 next[i]← next[next[i]];</code></pre>
<p>上述伪代码和图3说明了这个算法和List-Rank的相似之处。仅有的差别在于初始化以及更新值的不同（d或y）。在List-Rank中，处理器i更新其自身的d[i]；在List-Prefix中，处理器i更新的是另一个处理器的y[next[i]]。注意，List-Prefix与List-Rank一样也是EREW算法，因为指针转移技术维持以下条件不变：对不同的对象i和j，或者next[i]≠next[j]，或者next[i]=next[j]=NIL。</p>
<p>图3说明了while循环中的每一次迭代执行前表的状态。这一过程保持下列条件不变：在第t次while循环执行结束时，第k个处理器中存放了[max(1，k-2<sup>t</sup>+1)，k]，k=1,2,..,n。在第一次迭代过程中，除最后一个对象的指针为NIL外，表中第k个对象均指向初始时的第k+1个对象。第6行使得第k个对象(k=1,2,..,n-1)从其后继中取得值[k+1,k+1]。然后执行运算[k,k]<font face="MT Symbol">Ä</font>[k+1,k+1]，得到[k,k+1]，再把它存储回其后继中。然后，next指针与在List-Rank中一样进行转移，得到图3(b)所示的第一次迭代后的结果。第二次迭代也是类似的。对k=1,2,...,n-2，第k个对象从其后继（由其next域的新的值所定义）取得值[k+1,k+2]，然后把[k-1,k]<font face="MT Symbol">Ä</font>[k+1,k+2]=[k-1,k+2]存入其后继中。结果如图3(c)所示。在第三次也是最后一次迭代中，只有表的开头两个对象的指针不是NIL，它们从其各自的表中分别从其后继取得相应的值。最后的结果如图3(d)所示。我们注意到使算法List-Prefix能够工作的关键是在每一步，如果我们对每一个存在的表进行先缀计算，则每个对象均包含正确的值。</p>
<p align="center"><img border="0" src="images/fig3a.gif" width="544" height="27"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/fig3b.gif" width="544" height="61"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/fig3c.gif" width="544" height="61"></p>
<p align="center">(c)</p>
<p align="center"><img border="0" src="images/fig3d.gif" width="544" height="27"></p>
<p align="center">(d)</p>
<p align="center">图3 在链表上并行前缀算法List-Prefix的执行过程</p>
<p>因为上面介绍的两种算法运用了同样的指针转移技术，所以对List-Prefix的分析与List-Rank相同：在EREW PRAM上的运行时间为O(lgn)，算法执行的全部工作为O(nlgn)。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -