加速比定律习题.doc

1、两个N*N阶的矩阵相乘，时间复杂度为：s，其中c为常数；在n个节点的并行机上并行矩阵乘法的时间为： s，其中b是另一常数，第一项代表计算时间，第二项代表通信开销；1) 试求固定负载时的加速比并讨论其结果；2) 试求固定时间时的加速比并讨论其结果；3) 试求存储受限时的加速比并讨论其结果。解：工作负载为：开销为：(a) 固定工作负载：由加速比的定义，可以得到 又根据Amdahl定律，有因此，可以得到。结果说明当问题规模不是很大时，固定工作负载情况下的加速比与成线性比例，但是当问题规模很大时，其加速比与成线性比例。用于解决问题的处理器数目越多，加速比越大。这种情况下，并行程序的性能仅仅受到平均开销的限制，因为不存在串行瓶颈。固定工作负载的加速比会随着开销的增大而降低。(b) 固定时间：根据Gustafson定律，有 结果说明加速比与成线性比例。在固定的时间内，用于解决问题的处理器数目越多，加速比越大。这种情况下，并行程序的性能仅仅受到平均开销的限制，因为不存在串行瓶颈。固定时间的加速比会随着开销的增大而降低。 (c) 存储受限：根据Sun和Ni定律，有当G(n)=1，与固定工作负载情况下的结果一致；当G(n)=n，与固定时间情况下的结果一致；当G(n)n，说明工作负载比存储要求增加得快，此时可以获得最好的加速比。2、假设某应用问题在单结点机器上求解时需要执行的运算量为10106次浮点运算（工作负载）, 其中有6103次浮点运算必须顺序执行。现考虑在一包含10个结点的多计算机系统求解该问题，同时将工作负载按以下两种情况进行调整：（a）总运算量为10106次浮点运算，其中6103次浮点运算可由任一结点执行；（b）总运算量为99.946106次浮点运算，其中的6103次浮点运算可由任一结点执行。试计算(a)和(b)两种情况下获得的加速比。解：W = 10*106 Ws = 6*103 f = Ws / W = 0.0006 p = 10(1) 属于工作负载不变的情况，应使用Amdahl定律求其加速比：S = 1/(f+(1-f)/p) = 1 / (0.0006+0.9994/10) = 1/ (0.0006+0.09994) = 9.946(2) 属于工作负载增加，由于没有说明程序运行时间是否不变，因此应使用Sun & Ni定律求其加速比：G(p)Wp=99.946106 Ws=6103 p=10S = (Ws+ G(p)Wp)/(Ws+G(p)Wp/p)= 9.99463、假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？解：根据另一种Amdahl定律加速比=采用改进措施之后的性能/没有改进前的性能=没有采用改进措施之前的执行时间/采用改进措施之后的执行时间在Amdahl定律中，加速比与两个因素有关：一是计算机执行某个任务的总时间中可以被改进部分的时间所占的百分比，即可以改进部分占用的时间/改进前整个任务的执行时间，记为Fe(Fe1)。因此，改进后的执行时间为：Tn=T1*(1-Fe+Fe/Se)Sn=T1/Tn=1/(1-Fe+Fe/Se)本题中，Fe=0.4, Se=10Sn=1/(1-0.4+0.4/10)=1.564、一个多处理机系统由10台处理器组成，每台处理器的峰值执行速度为500Mflops。当10%的代码为顺序的，而90%代码为可并行化时，该系统的实际执行速度（以Mflops表示）为多少？解：设该程序的总工作量为W，W10%是必须顺序执行的代码的工作量，W90%是可并行化的工作量。该算法的执行时间为：W10% / 500M + W90% / (10*500M)该算法的执行速度为：总工作量 / 算法的执行时间 = W / (W10% / 500M + W90% / (10*500M) = 1 / (0.1/500M + 0.9/5000M) = 1 / (1.9 / 5000M) = 5000M / 1.9 2631.58M 该并行算法的加速比 = 串行算法的执行时间/并行算法的执行时间 = (W / 500M) / (W10% / 500M + W90%