《多核与GPU编程:工具、方法及实践》----3.3 设计考虑

3.3 设计考虑

这个问题可以归结为:如何使多线程程序的行为与串行程序行为一致?

这就需要不同作用的一致性模型。一致性模型是一套规则,它定义了系统特定的行为方式。已经提出了大量一致性模型,每个模型都在效率和严格性之间权衡。其中一个实例是顺序一致性模型(sequential consistency model)。

在顺序一致性模型中,在共享存储器对象进行操作的所有事件应该发生在不同的时间点。此外,这些事件的时间点顺序应该符合每个线程的内部顺序。不同线程中的事件可以重排,从而使对一个对象总的事件/方法调用执行序列的效果满足串行规范(亦即与单个线程执行时的行为一致)。图3-5展示了这种顺序重排的一个实例。

这种情况下顺序一致性模型的问题在于其非组合性:将两个保证顺序一致性的软件模块组合在一起并不能保证整体满足顺序一致性。图3-6展示了一个实例用以说明这种情况,其中图3-5中的序列被复制了一份,虽然两个独立序列是顺序一致性的,但是没有办法保证两个时间线的组合依然满足顺序一致性。

更为严格的一致性模型是序列化(linearizability)[45]:事件满足同一时刻执行一个事件并且立即生效。后一要求是由于称为序列点的需要。序列点是一个方法调用期间生效的时间点。序列点的引入有两个意义。

1.可以根据方法的序列点来进行全排序。在一个方法的开始调用和结束返回这一时间窗口期间可以以任意点作为序列点。最后的排序结果必须与考虑序列化的并发执行的一个串行执行结果一致。

2.虽然并不强制加锁(并且实际上从性能角度考虑也应该避免加锁),但是在一个方法调用期间对一个对象加锁等价于使其效果立即生效并对所有其他线程可见。最简单的方法是使用加锁机制,因此接下来的几节讨论这些机制。

每个序列化执行都满足顺序一致性,但反之则不一定。图3-7展示了一个序列化执行示例。

接下来的几节将研究两种加锁机制,虽然其在功能上是等价的,但是在同步线程时导致不同的模式。

时间: 2024-09-29 12:08:35

《多核与GPU编程:工具、方法及实践》----3.3 设计考虑的相关文章

《多核与GPU编程:工具、方法及实践》----第2章 多核和并行程序设计 2.1 引言

第2章 多核和并行程序设计 本章目标 学习设计并行程序的PCAM方法. 使用任务图和数据依赖图来识别可以并行执行的计算部分. 学习将问题的解法分解为可并发执行部分的流行的分解模式. 学习编写并行软件的主要程序结构模式,如主/从和fork/join. 理解分解模式的性能特点,如流水线. 学习如何结合分解模式和合适的程序结构模式. 2.1 引言 即使是对于经验丰富的专业程序员,向多核编程的过渡也并不简单.多核和并行编程往往会打破语句按严格顺序执行的串行程序的传统风格.当许多事情在同一时间发生时,正如

《多核与GPU编程:工具、方法及实践》----导读

目 录[第1章 概述 1.1 多核计算机时代 ](https://yq.aliyun.com/articles/90097)1.2 并行计算机的分类[1.3 现代计算机概览 1.3.1 Cell BE处理器 1.3.2 NVIDIA Kepler 1.3.3 AMD APU 1.3.4 从多核到众核:Tilera TILE-Gx8072和Intel Xeon Phi ](https://yq.aliyun.com/articles/90111)1.4 性能指标[1.5 并行程序性能的预测与测量

《多核与GPU编程:工具、方法及实践》----2.3 分解模式

2.3 分解模式 设计过程最困难同时也最关键的部分无疑是分解过程,即确定可以并发执行的计算.虽然任务图法是最常用的,但开发者无法从中获取以往的经验,这时就需要模式.Mattson等人[33]列出了若干分解模式(在他们的书中表示为"algorithm structure design space patterns"), 该参考文献包含了工作负载被分解并最终分配到并行或多核平台各个节点上的基本方法.图2-4显示了能得到6个模式之一的决策树. 上一节提到了两类分解,即功能分解和域分解,现在又

《多核与GPU编程:工具、方法及实践》----2.4 程序结构模式

2.4 程序结构模式 模式不仅可以帮助选择合适的工作负载分解方法,还可用于程序的开发,这正是程序结构模式的目标.接下来的一节将讨论和分析几个最著名的模式. 并行程序结构模式可以分为两大类. 全局并行局部串行(Globally Parallel Locally Sequential,GPLS):GPLS表示应用程序可以并发执行多个任务,每个任务串行执行.这类模式包括: 单程序多数据 多程序多数据 主/从 map-reduce 全局串行局部并行(GSLP):GSLP表示应用程序串行执行,当需要时,一

《多核与GPU编程:工具、方法及实践》----1.5 并行程序性能的预测与测量

1.5 并行程序性能的预测与测量 构建并行程序要比串行程序更具挑战性.并行程序程序员需要解决诸如共享资源访问.负载均衡(即,将计算负载分配到所有计算资源上来最小化执行时间)以及程序终止(即,以协调方式暂停程序)等相关问题. 编写并行程序应该首先确定并行能否提升程序性能,加速问题的解决.并行程序的开发成本决定了程序员不可能简单地实现多个并行版本,通过测试找出最佳和最差版本,来评估项目的可行性.虽然对于最简单的问题,这个方法可能是可行的.但是即使能够这样,如果能够确定一个先验的最佳开发路径,并按照这

《多核与GPU编程:工具、方法及实践》----第1章 概 述 1.1 多核计算机时代

第1章 概 述 本章目标: 了解计算机(计算机体系架构)设计的发展趋势以及该趋势如何影响软件开发. 学习基于Flynn分类的计算机分类方法. 学习评估多核/并行程序性能即加速比和效率的必备工具. 学习测量和报告程序性能的正确实验方法. 学习Amdahl和Gustafson-Barsis定律,并使用这两个定律预测并行程序性能. 1.1 多核计算机时代 在过去的40年中,数字计算机已经成为技术和科学发展的基石.遵循20世纪70年代摩尔(Gordon E. Moore)发现的摩尔定律,计算机的信息处理

《多核与GPU编程:工具、方法及实践》----3.2 线程

3.2 线程 3.2.1 线程的定义 线程可以被认为是轻量级进程.更精确的定义是线程是一个执行路径,亦即一个指令序列,可以被操作系统作为整体单元进行管理调度.一个进程中可以有多个线程. 线程可以减轻原有生成进程机制中的开销,仅需要拷贝基本的数据,即运行栈.由于线程包括被调用函数的动态框架(或动态记录),因此运行栈不能被多个线程共享.共享栈意味着控制权可能返回一个与调用线程不同的位置. 当一个进程的主线程(初始线程)生成一个新线程时,最终的内存布局十分类似于图3-3.这里父线程和子线程的关系也是如

《多核与GPU编程:工具、方法及实践》----1.4 性能指标

1.4 性能指标 发展多核硬件和开发多核软件的目标是获取更高性能,例如更短的执行时间.更大规模的问题和更大的数据集等.很明显,这需要一个客观的标准或者准则来评估这些努力的有效性. 最起码,一个并行程序的执行时间应该要比其对应的串行程序的执行时间短(然而,并不是所有情况都这样).执行时间的缩短通常表述为加速比,可用如下公式表达: (1-1) 其中,对于解决同一个问题实例,tseq是串行程序的执行时间,tpar是并行程序的执行 时间. tseq和tpar都是时间,但它们并不总客观.二者会受到如下因素

《多核与GPU编程:工具、方法及实践》----第3章 共享内存编程:线程 3.1 引言

第3章 共享内存编程:线程 本章目标: 学习线程的定义以及创建方法. 学习完成特定任务的初始化线程方法. 学习多种终止多线程程序的技术. 理解多线程访问共享数据过程中的主要问题,例如竞争和死锁. 学习信号量和监视器的定义和使用方法. 熟悉经典同步问题及其解决方法. 学习运行时动态管理线程. 学习多线程程序的调试技术. 3.1 引言 从20世纪60年代麻省理工学院引入兼容分时系统(CTSS)以来,多个程序并发执行的现象已经变得较为常见.操作系统通过中断当前正在执行的程序并将CPU的控制权交由另一个

《多核与GPU编程:工具、方法及实践》----1.2 并行计算机的分类

1.2 并行计算机的分类 使用多种资源获取更高性能并不是最新的技术,这个技术最早开始于20世纪60年代.因此,定义一种描述并行计算机架构特征的方法是非常重要的.1966年,Michael Flynn引入了一种计算机体系结构分类方法:根据能够并发处理的数据量和同时执行的不同指令数目进行分类.根据这两个条件,计算机体系结构可以分为四类: 单指令单数据(Single Instruction Single Data,SISD):只能同时执行一条指令并处理一个数据的串行计算机.出人意料的是,绝大多数现代C