有些问题使用越多的资源就能越快地解决——越多的工人参与收割庄稼,那么就能越快地完成收获。另一些任务根本就是串行化的——增加更多的工人根本不可能提高收割速度。如果我们使用线程的重要原因之一是为了支配多处理器的能力,我们必须保证问题被恰当地进行了并行化的分解,并且我们的程序有效地使用了这种并行的潜能。
大多数并发程序都与农耕有着很多相似之处,由一系列并行和串行化的片断组成。Amdahl定律描述了在一个系统中,基于可并行化和串行化的组件各自所占的比重,程序通过获得额外的计算资源,理论上能够加速多少。如果F
是必须串行化执行的比重,那么Amdahl定律告诉我们,在一个N
处理器的机器中,我们最多可以加速:
当N
无限增大趋近无穷时,speedup
的最大值无限趋近1/F
,这意味着一个程序中如果50%的处理都需要串行进行的话,speedup
只能提升2倍(不考虑事实上有多少线程可用);如果程序的10%需要串行进行,speedup
最多能够提高近10倍。Amdahl定律同样量化了串行化的效率开销。在拥有10个处理器的系统中,程序如果有10%是串行化的,那么最多可以加速5.3倍(53%的使用率),在拥有100个处理器的系统中,这个数字可以达到9.2(9%的使用率)。这使得无效的CPU利用永远不可能到达10倍。
图11.1展示了随着串行执行和处理器数量变化,处理器最大限度的利用率的曲线。随着处理器数量的增加,我们很明显地看到,即使串行化执行的程度发生细微的百分比变化,都会大大限制吞吐量随计算资源增加。
第6章探究了如何识别逻辑边界,从而把应用程序分解为不同的任务。但是为了在多处理器系统中预知你的程序是否存在加速的可能性,你同样需要识别你的任务中串行的部分。
图11.1 Amdahl定律中不同串行化的百分比,带来的最大的效能
清单11.1中,假设应用程序中N
个线程正在执行doWork,从一个共享的工作队列中取出任务,并处理;假设这里的任务并不依赖其他任务的结果或边界效应。忽略任务进行队列操作的时间,如果我们增加处理器,应用程序会随之发生什么样的改进呢?乍看这个程序可能完全由并行任务组成,并不会相互等待,那么处理器越多,更多的任务就越可能并发处理。然而,其中也包含串行组件——从队列中获取任务。所有工作者线程都共享工作队列,因此它会需要一些同步机制,从而在并发访问中保持完整性。如果通过加锁来守卫队列状态,那么当一个线程从队列中取出任务的时候,其他线程想要取得下一个任务就必须等待——这便是任务处理中串行的部分。
单个任务的处理时间不仅包括执行任务Runnable的时间,也包括从共享队列中取出任务的时间。如果工作队列是LinkedBlockingQueue类型的,这个取出的操作被阻塞的可能性小于使用同步的LinkedList的阻塞可能,这是因为LinkedBlockingQueue使用了更具伸缩性的算法,但是访问所有共享的数据结构,本质上都会向程序引入一个串行的元素。
这个例子同样忽略了另一个的相同的串行源(source of serialization):结果处理。所有有用的计算都产生一些结果集或者边界效应——如果不是,它们可以当作死代码(dead code)被遗弃掉。因为Runnable没有提供明确的结果处理,这些任务必须具有一些边界效应,设定把它们的结果写入日志还是存入一个数据结构。日志文件和结果容器通常由多
清单11.1 串行访问任务队列
public class WorkerThread extends Thread {
private final BlockingQueue<Runnable> queue;
public WorkerThread(BlockingQueue<Runnable> queue) {
this.queue = queue;
}
public void run() {
while (true) {
try {
Runnable task = queue.take();
task.run();
} catch (InterruptedException e) {
break; /* 允许线程退出 */
}
}
}
}
个工作者线程共享,并且因此成为了同源的串行部分。如果不是每个线程各自维护自己的结果的数据结构,而是在所有任务都执行完成后合并所有的结果,这最终的合并就成为了一个串行源。
- 大小: 774 Bytes
- 大小: 17.2 KB
分享到:
相关推荐
应用Amdahl定律对多核处理器性能的分析.pdf
基于Amdahl定律的多核密码处理器性能模型研究.pdf
基于Amdahl定律扩展的多核处理器性能模型研究.pdf
Amdahl定律在层次化片上多核处理器中的扩展.pdf
1.7-1.9(透明性概念),1.12-1.18(Amdahl定律),1.19、1.21、1.24(CPI/MIPS) 第二章(P124) 2.3、2.5、2.6(浮点数性能),2.13、2.15(指令编码) 第三章(P202) 3.3(存储层次性能),3.5(并行主存系统),...
三、 简答题 (共40分) 1. 短期调度将进程分为哪几种状态?这几种状态各代表什么含义,如何转换?(8分) 2. 什么是中断?为什么需要中断?...5. 什么是Amdahl定律?该定律说明了什么问题?(8分)
1.7-1.9(透明性概念),1.12-1.18(Amdahl定律),1.19、1.21、1.24(CPI/MIPS) 第二章(P124) 2.3、2.5、2.6(浮点数性能),2.13、2.15(指令编码) 第三章(P202) 3.3(存储层次性能),3.5(并行主存系统),...
思想篇 CAP 最终一致性 变体 BASE 其他 I/O的五分钟法则 不要删除数据 RAM是硬盘,硬盘是磁带 Amdahl定律和Gustafson定律 万兆以太网 3. 手段篇 一致性哈希 亚马逊的现状 算法的选择 Quorum NRW Vector clock ...
①、Amdahl定律,CPU性能公式。 ②、平均存储器访问时间AMAT,缺失率,缺失代价。 ③、循环展开实现流水线调度。 ④、应用时空图解决线性流水线调度问题,计算流水线吞吐率、加速比、效率。 ⑤、应用禁止启动距离、...
1.7-1.9(透明性概念),1.12-1.18(Amdahl定律),1.19、1.21、1.24(CPI/MIPS) 第二章(P124) 2.3、2.5、2.6(浮点数性能),2.13、2.15(指令编码) 第三章(P202) 3.3(存储层次性能),3.5(并行主存系统),...
近年来,由于频率墙和功耗墙的存在,计算机计算性能的提升主要... 并行程序设计方法PCAM,Amdahl定律,Gustafson定律,加速比等。 第4章 基于消息传递编程(MPI)的并行程序开发 (2学时) MPI并行程序设计开发,点对
1.根据Amdahl定律,系统加速比由哪两个因素决定? 2.多模块交叉存储器是如何加速CPU和存储器之间的有效传输的? 3.什么是虚拟存储器中的段页式管理? 4.CPU中,指令寄存器(IR)、程序计数器(PC)、状态条件寄存器...
答:(1)固定负载,符合Amdahl定律的前提条件,根据Amdahl定律,S=p/(1+f(p-1)),所以使用的节点数越多(也就是增加处理器的个数)那么加速越
根据gprof统计的程序运行时函数调用次数及执行时间,进行程序代码优化,这是amdahl定律的应用 B. 计算机网络设备的缓冲区是时间和空间局部性原理的应用 C. 局域网内的计算机发送数据包的数学模型遵循泊松分布 ...
I/O的五分钟法则 不要删除数据 RAM是硬盘,硬盘是磁带 Amdahl定律和Gustafson定律 万兆以太网 3. 手段篇 一致性哈希 亚马逊的现状 算法的选择 Quorum NRW Vector clock Virtual node gossip Gossip (State Transfer ...
2 Amdahl定律和Gustafson定律 2 万兆以太网 3 手段篇 3 一致性哈希 3 亚马逊的现状 3 算法的选择 3 Quorum NRW 3 Vector clock 3 Virtual node 3 gossip 3 Gossip (State Transfer Model) 3 Gossip (Operation ...
求该计算机的有效 CPI 和程序执行时间,amdahl定律计算,加速比,系统的性能提高
Amdahl law Amdahl定律 系统中某部件由于采用某种方式时系统性能改进后,整个系统性能的提高与该方式的使 用频率或占的执行时间的比例有关。 SCALAR PROCESSING 标量处理机 在同一时间内只处理一条数据。 LOOK-...
计算机组织与体系结构课程复习要点-2020.7复习要点参考例题、习题第1章冯·诺依曼计算机结构、工作原理及特点。Amdahl定律应用(应能从题目中找到加速比和可