📄 chapter3.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>算法与数据结构 -- Brent定理与工作效率</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter2.htm";
next = "chapter4.htm";
contents="";
topic="";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h2>第三节 Brent定理与工作效率</h2>
<p>Brent定理说明我们如何用PRAM来有效地模拟组合电路。运用这一定理，我们就能把许多关于排序网络的结论和许多关于运算电路的结论进行改写以适合PRAM模型。对组合电路知识不太熟悉的读者也许希望复习一下相关的内容。</p>
<p><dfn>组合电路</dfn>是由组合元件构成的无回路网络。每个组合元件都具有一个或多个输入，在本节中，我们假定每个组合元件仅有1个输出(具有k>1个输出的组合元件可以看成是k个独立的元件)。输入的数目称为元件的扇入，其输出馈送到的地点个数称为元件的扇出。在本节中我们一般假定电路中的每个组合元件具有有限的扇入，但扇出数可以不受限制。</p>
<p>组合电路的<dfn>规模</dfn>是指它所包含的组合元件个数。从电路的输入到某组合元件的输出的最长路径中组合元件的数目称为该元件的<dfn>深度</dfn>。整个电路的深度是其任何元件的最大深度。</p>
<p class="theorem"><b>定理2 Brent定理</b></p>
<p>任何深度为d，规模为n并具有有限扇入的组合电路都能由一种p个处理器的CREW算法在O(n/p+d)的时间内对其进行模拟。</p>
<p class="proof"><b>证明：</b></p>
<p>我们把组合电路的输入存储于PRAM的全局存储器中，并且我们为电路中的每个组合元件保留了一个存储单元以有效经过计算后的输出值。这样，我们就能够在O(1)的时间内用单个PRAM处理器对指定的组合电路模拟如下：处理器仅仅为元件从相应于电路输入存储器单元中读入输入值，或馈送给它的其他元件的输出值，这样就模拟出电路中的线路。然后处理器计算出组合元件实现的函数并把结果写到存储器的适当存储单元中去。由于每个组合元件的扇入是有限的，所以可以在O(1)的运行时间内计算出每个函数。</p>
<p>因此，我们的任务就是找出关于p个处理器的PRAM的一种调度方法，使得所有的组合元件都能在O(n/p+d)的时间被模拟。主要的约束条件是：对于一个组合元件，直至对其有馈送的所有元件的输出都计算出后，才能对该元件进行模拟。每当被并行模拟的数个组合元件需要同一个值时，我们就运用并发读操作。</p>
<p>由于深度为1的所有元件仅依赖于电路的输入，所以初始时仅能对这些元件进行模拟；一旦对它们的模拟完成后，就可以对深度为2的所有元件进行模拟，如此下去，直至完成对深度为d的所有元件的模拟操作。其中最关键的思想在于：如果从深度为1到深度为i的所有元件均已被模拟，则我们就能并行地对深度为i+l的元件的任何子集进行模拟，这是因为它们各自的计算过程是相互独立的。</p>
<p>因此，调度策略是非常朴素的。我们在对深度为i的所有元件进行模拟后才继续对深度为i+1的那些元件进行模拟。在给定的深度i内，我们一次可模拟p个元件。</p>
<p>现在让我们来分析这种模拟策略。对i=1,2,...,d，设n<sub>i</sub>是电路中深度为i的元件数，因此</p>
<blockquote>
<p><img border="0" src="images/Eqn6.gif" width="61" height="46"></p>
</blockquote>
<p>考察深度为i的n<sub>i</sub>个组合元件。把这些元件分成<img border="0" src="images/parall1.gif" width="43" height="23">个组，其中前<img border="0" src="images/parall2.gif" width="43" height="23">个组每组包含p个元件，剩下的元件(如果有的话)放在最后一组中，这样PRAM就可以在<img border="0" src="images/parall3.gif" width="62" height="23">的时间内对这些组合元件执行的运算进行模拟。因此整个模拟时间与下式相似：</p>
<blockquote>
<p><img border="0" src="images/Eqn7.gif" width="188" height="49"></p>
</blockquote>
<p>当一个组合电路中每个组合元件的扇出为O(1)时，Brent定理可以推广到应用EREW进行模拟。</p>
<p class="deduction"><b>推论3<a name="deduction3"></a></b></p>
<p>任何深度为d，规模为n且具有有限的扇入与扇出的组合电路都能在p个处理器的EREW PRAM上在O(n/p+d)的运行时间内对其进行模拟。</p>
<p class="proof"><b>证明：</b></p>
<p>运用与Brent定理的证明过程中相类似的模拟方法，区别仅在于对线路的模拟方法不同，因为在Brent定理中要求执行并发读操作。对于EREW模拟方法来说，在计算出组合元件的输出后，该输出值并没有直接被需要该值的处理器读出，而是由模拟读元件的处理器把其输出值复制到需要其值的O(1)个输入中去。这样一来，需要读值的处理器就可以读出该值，而此间不会相互干扰。</p>
<p align="right">(证毕)</p>
<p>这种EREW模拟策略不适用于扇出不受限制的元件，因为每一步中的复制操作所需时间大于常数。因此，对于元件的扇出不受限制的组合电路，我们就需要并发读操作。(如果组合元件足够简单，则扇入不受限制的情形有时可以用同一种CRCW模拟方法来进行处理。)</p>
<p>推论3为我们提供了一种快速的EREW排序算法。AKS排序网络使用O(nlgn)个比较器能对深度为O(lgn)的n个数进行排序。由于比较器均有有限扇入，所以存在一种EREW算法，该算法使用n个处理器可以在O(lgn)的运行时间内对n个数进行排序。(<a href="chapter2_3.htm#theorem1">我们在定理1中运用了这个结论以证明一台EREW
PRAM可以模拟一台CRCW PRAM，其速度至多降低一个对数因子。</a>)不幸的是，O - 记号中所隐藏的常数太大，以致于这种排序算法仅有理论上的意义。但是，目前已发现很多实用的EREW排序算法，特别值得一提的是由Cole发现的并行合并排序算法。</p>
<p>假定有一个至多使用p个处理器的PRAM算法，但我们的PRAM仅有p'< p个处理器。我们非常希望能以一种高效的方式在p'个处理器的PRAM上运行p个处理器的算法。通过应用Brent定理证明中用到的思想，就能给出能否运行的条件。</p>
<p class="theorem"><b>定理4</b></p>
<p>如果用到p个处理器的PRAM算法A的运行时间为t，则对任意p'< p，存在一个能解决相同问题的具有p'个处理器的PRAM算法，该算法的运行时间为O(pt/p')。</p>
<p class="proof"><b>证明：</b></p>
<p>设算法A的时间步被编号为1,2,...,t。算法A'能在<img border="0" src="images/parall4.gif" width="64" height="21">的时间内模拟出A的每个时间步i=1,2,..,t的执行。因为总共有t个时间步，所以由于p'<
p，整个模拟过程需要的时间为：<img border="0" src="images/parall5.gif" width="138" height="21">。</p>
<p align="right">(证毕)</p>
<p>算法A完成的工作为pt，算法A'完成的工作为(pt/p')p'=pt；因此模拟过程是高效的。因此，如果算法A本身是高效的算法，则算法A'也同样是高效的。</p>
<p>因此，当对于某一问题开发高效的算法时，我们无需对不同数目的处理器建立不同的算法。例如，假设我们能够证明不论处理器数目是多少，解决某给定问题的任何并行算法的运行时间有严格下界t，再假设解决该问题最好的串行算法所做的工作为w，则为了获得所有可能的处理数目下的高效的算法，我们对这一问题只需开发一种使用p=Θ(w/t)个处理器的高效的算法就可以了。对p'=o(p)，定理4保证存在一个高效的算法。对p'=ω(p)，不存在高效的算法；这是因为如果t是任何并行算法运行时间的下界，则有p't=ω(pt)=ω(w)。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -