📄 chapter2_1.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 = "chapter2.htm";
next = "chapter2_2.htm";
contents="";
topic="并行算法 -- CRCW 算法与 EREW 算法";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>2.1 并发操作发挥作用的有关问题</h3>
<p>假定已知一个二叉树组成的森林，其中每个结点都有一个指针parent[i]指向其父母结点，我们希望每个结点能找出它所在的树的根结点。我们把处理器i与森林F中的每个结点i相联结，下列指针转移算法把每个结i所在的树的根结点的值存储在root[i]中。</p>
<pre><code class="pseudocode">Find-Roots(F)
1 for 每个处理器i，并行地执行
2 do if parent[i]=NIL
3 then root[i]←i
4 while 存在一个结点i满足parent[i]≠NIL
5 do for 每个处理器i，并行地执行
6 do if parent[i]≠NIL
7 then root[i]← root[parent[i]]
8 parent[i]← parent[parent[i]]
</code></pre>
<p>图5说明了该算法的操作过程。在第1-3行执行初始化操作后，如图5(a)所示，知道根的值的唯一结点是根结点自身。第4-8行的while循环执行<a href="chapter1.htm">指针转移</a>操作，并填入root域。图5(b)-(d)分别说明了循环中的第1，第2和第3次迭代后森林的状态。我们可以看出，算法保持下列条件不变：如果parent[i]=NIL，则把该结点的根的值赋给root[i]。</p>
<p align="center"><img src="images/fig5a.gif" width="700" height="200"></p>
<p align="center">(a)</p>
<p align="center"><img src="images/fig5b.gif" width="700" height="200"></p>
<p align="center">(b)</p>
<p align="center"><img src="images/fig5c.gif" width="700" height="200"></p>
<p align="center">(c)</p>
<p align="center"><img src="images/fig5d.gif" width="700" height="200"></p>
<p align="center">(d)</p>
<p align="center">图5 用一台CREW PRAM在二叉树森林中寻找根的过程</p>
<p>我们说Find-Roots是一个运行时间为O(lgd)的CREW算法，其中d是森林中具有最大深度的树的深度。写操作仅出现在第3，7和8行，并且因为在每个写操作中处理器仅对结点i写入，所以这些写操作都是互斥性的。但是，第7-8行的读操作是并发执行的，这是因为数个结点的指针可能指向同一个结点。例如在图5(b)中，我们可以看到在while循环的第二次迭代中，root[4]和parent[4]同时被处理器18，2和7读出。</p>
<p>Find-Roots的运行时间为O(lgd)，其理由与<a href="chapter1_1.htm#ListRank">List-Rank</a>相同：每次迭代使每条路径的长度缩短一半。图5明显地说明了这一特征。</p>
<p>如果只允许互斥读操作，则树林中的n个结点要找出其所在二叉树的根又需要多少时间？我们可以简单地证明需要O(lgn)运行时间。关键的一点是：当读操作互斥时，PRAM的每一步只允许把一条已知信息复制到存储器中的至多一个其他存储单元，因此每一步执行后包含该信息的存储单元数至多增加一倍。在单棵树的情况下，初始时至多有一个存储器单元保存着根的值；在第一步执行后，至多有两个存储器单元包含根的值；执行k步后，至多有2k个存储单元包含根的值。如果树的规模为O(n)，则算法结束时就需要O(n)个存储单元来存储根的值。因此，总共要执行的步数是O(lgn)。</p>
<p>每当森林中各个树的最大深度d为2<sup>O(lgn)</sup>时，从渐近意义上来说，CREW算法Find-Roots要超过任何EREW算法。特别地，在一个由n个结点组成的森林中，最大深度的树是一棵具有O(n)个结点平衡二叉树，d
= O(lgn)，在这种情形下Find-Roots的运行时间为：O(lglgn)。用任何EREW算法解决这一问题则要Ω(lgn)的运行时间。因此，在这一问题中允许并发读对于我们是有帮助的。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -