9 种可重复使用的并行数据结构和算法
2011年10月16日
倒计数锁存 (Countdown Latch)Semaphore 之所以成为并发编程中一种较为知名的数据结构,原因是多方面的,而并不只是因为它在计算机科学领域有着悠久的历史(可以追溯到 19 世纪 60 年代的操作系统设计)。Semaphore 只是一种带有一个计数字段的数据结构,它只支持两种操作:放置和取走(通常分别称为 P 和 V)。一次放置操作会增加一个 semaphore 计数,而一次取走操作会减少一个 semaphore 计数。当 semaphore 计数为零时,除非执行一项并发的放置操作使计数变为非零值,否则任何后续的取走尝试都将阻塞(等待)。这两种操作均为不可再分 (atomic) 操作,并发时不会产生错误,能够确保并发的放置和取走操作有序地进行。Windows®具有基础内核和对 semaphore 对象的 Win32® 支持(请参阅 CreateSemaphore 和相关 API),并且在 .NET Framework 中这些对象可以通过 System.Threading.Semaphore 类公开到上层。Mutex 和 Monitor 所支持的临界区,通常被认为是一种特殊的 semaphore,其计数会在 0 和 1 之间来回切换,换句话说,是一个二进制的 semaphore。另外还有一种“反向 semaphore”也是非常有用。也就是说,有时您需要数据结构能够等待数据结构计数归零。Fork/join 式并行模式在数据并行编程中是极为常见的,其中由单个“主”线程控制执行若干“辅助”线程并等待线程执行完毕。在这类情况下,使用反向 semaphore 会很有帮助。大多数时候,您其实并不想唤醒线程来修改计数。因此在这种情况下,我们将结构称为倒计数“锁存”,用来表示计数的减少,同时还表明一旦设置为“Signaled”状态,锁存将保持“signaled”(这是一个与锁存相关的属性)。遗憾的是,Windows 和 .NET Framework 均不支持这种数据结构。但令人欣慰的是,构建这种数据闭锁并不难。要构建一个倒计数锁存,只需将其计数器的初始值设为 n,并让每项辅助任务在完成时不可再分地将 n 减掉一个计数,这一点可以通过为减量操作加上“锁”或调用 Interlocked.Decrement 来实现。接下来,线程可以不执行取走操作,而是减少计数并等待计数器归零;而当线程被唤醒时,它就可以得知已经有 n 个信号向锁存注册。在 while (count != 0) 循环中,让等待的线程阻塞通常是不错的选择(这种情况下,您稍后将不得不使用事件),而不是使用旋转。 图 1 是一个简单的 CountdownLatch 类型的示例。
Figure 1 CountdownLatch
public class CountdownLatch { private int m_remain; private EventWaitHandle m_event; public CountdownLatch(int count) { m_remain = count; m_event = new ManualResetEvent(false); } public void Signal() { // The last thread to signal also sets the event. if (Interlocked.Decrement(ref m_remain) == 0) m_event.Set(); } public void Wait() { m_event.WaitOne(); }}
这看上去极为简单,但要正确运用还需要技巧。稍后我们将通过一些示例来讲解如何使用这种数据结构。请注意,此处所示的基本实现还有很多可以改进的地方,例如:在事件上调用 WaitOne 之前添加某种程度的旋转等待、缓慢分配事件而不是在构造器中进行分配(以防足够的旋转会避免出现阻塞,如本专栏稍后介绍的 ThinEvent 演示的那样)、添加重置功能以及提供 Dispose 方法(以便在不再需要内部事件对象时将对象关闭)。这些都是留给读者作为练习之用。
可重用旋转等待 (Spin Wait)虽然忙碌等待 (busy waiting) 更容易实现阻塞,但在某些情况下,您也许的确想在退回到真正的等待状态前先旋转 (spin) 一段时间。我们很难理解为何这样做会有帮助,而大多数人之所以一开始就避免旋转等待,是因为旋转看上去像是在做无用功;如果上下文切换(每当线程等待内核事件时都会发生)需要几千个周期(在 Windows 上确实是这样),我们称之为 c,并且线程所等待的条件出现的时间少于 2c 周期时间(1c 用于等待自身,1c 用于唤醒),则旋转可以降低等待所造成的系统开销和滞后时间,从而提升算法的整体吞吐量和可伸缩性。如果您决定使用旋转等待,就必须谨慎行事。因为如果这样做,您可能需要注意很多问题,比如:要确保在旋转循环内调用 Thread.SpinWait,以提高 Intel 超线程技术的计算机上硬件对其他硬件线程的可用性;偶尔使用参数 1 而非 0 来调用 Thread.Sleep,以避免优先级反向问题;通过轻微的回退 (back-off) 来引入随机选择,从而改善访问的局部性(假定调用方持续重读共享状态)并可能避免活锁;当然,在单 CPU 的计算机最好不要采用这种方法(因为在这种环境下旋转是非常浪费资源的)。SpinWait 类需要被定义为值类型,以便分配起来更加节省资源(请参见图 2)。现在,我们可以使用此算法来避免前述 CountdownLatch 算法中出现的阻塞。
Figure 2 SpinWait
public struct SpinWait { private int m_count; private static readonly bool s_isSingleProc = (Environment.ProcessorCount == 1); private const int s_yieldFrequency = 4000; private const int s_yieldOneFrequency = 3*s_yieldFrequency; public int Spin() { int oldCount = m_count; // On a single-CPU machine, we ensure our counter is always // a multiple of ‘s_yieldFrequency’, so we yield every time. // Else, we just increment by one. m_count += (s_isSingleProc ? s_yieldFrequency : 1); // If not a multiple of ‘s_yieldFrequency’ spin (w/ backoff). int countModFrequency = m_count % s_yieldFrequency; if (countModFrequency > 0) Thread.SpinWait((int)(1 + (countModFrequency * 0.05f))); else Thread.Sleep(m_count 0) { if (s.Spin() >= s_spinCount) m_event.WaitOne(); }}
不可否认,选择频率和旋转计数是不确定的。与 Win32 临界区旋转计数类似,我们应该根据测试和实验的结果来选择合理的数值,而且即使合理的数值在不同系统中也会发生变化。例如,根据 Microsoft Media Center 和 Windows kernel 团队的经验,MSDN 文档建议临界区旋转计数为 4,000 ,但您的选择可以有所不同。理想的计数取决于多种因素,包括在给定时间等待事件的线程数和事件出现的频率等。大多数情况下,您会希望通过等待事件来消除显式让出时间,如锁存的示例中所示。您甚至可以选择动态调整计数:例如,从中等数量的旋转开始,每次旋转失败就增加计数。一旦计数达到预定的最大值,就完全停止旋转并立即发出 WaitOne。逻辑如下所示:您希望立即增加达到预定的最大周期数,但却无法超过最大周期数。如果您发现此最大值不足以阻止上下文切换,那么立即执行上下文切换总的算来占用的资源更少。慢慢您就会希望旋转计数能够达到一个稳定的值。屏障 (Barrier)屏障,又称集合点,是一种并发性基元,它无需另一“主”线程控制即可实现各线程之间简单的互相协调。每个线程在到达屏障时都会不可再分地发出信号并等待。仅当所有 n 都到达屏障时,才允许所有线程继续。这种方法可用于协调算法 (cooperative algorithms),该算法广泛应用于科学、数学和图形领域。很多计算中都适合使用屏障,实际上,甚至 CLR 的垃圾收集器都在使用它们。屏障只是将较大的计算分割为若干较小的协作阶段 (cooperative phase),例如:
const int P = ...;Barrier barrier = new Barrier(P);Data[] partitions = new Data[P];// Running on ‘P’ separate threads in parallel:public void Body(int myIndex) { FillMyPartition(partitions[myIndex]); barrier.Await(); ReadOtherPartition(partitions[P
发表评论
-
uboot讲解
2012-01-20 08:21 696uboot讲解 2010年09月15日 实验:p167 ... -
Proc 文件系统信息
2012-01-20 08:21 598Proc 文件系统信息 2011年03月30日 Proc ... -
C语言深度剖析总结(一)
2012-01-20 08:21 646C语言深度剖析总结(一) ... -
第二章 Android内核和驱动程序(转)
2012-01-20 08:21 749第二章 Android内核和驱 ... -
java线程安全总结
2012-01-20 08:19 423java线程安全总结 2010年11月11日 转载自:h ... -
zz:OpenGL实用开源代码列表
2012-01-19 13:34 686zz:OpenGL实用开源代码列 ... -
2011-7-27
2012-01-19 13:34 6172011-7-27 2011年07月27日 CS1.6完 ... -
【装机至尊】《中关村GHOSTXPSP3纯净装机自选DVD特别版V201011A》(海量驱动)
2012-01-19 13:34 554【装机至尊】《中关村G ... -
工作站电脑配件详解(仅以45纳米双路四核至强及NV Quadro FX图形卡为例,还有价格):
2012-01-19 13:34 813工作站电脑配件详解(仅以45纳米双路四核至强及NV Quadr ... -
苹果4代电池不耐用iphone论坛!入手IPHONE必看!
2012-01-17 03:23 806苹果4代电池不耐用iphone ... -
笔记本电脑死机 笔记本老是死机 蓝屏死机
2012-01-17 03:23 547笔记本电脑死机 笔记本 ... -
as3面试题
2012-01-17 03:23 605as3面试题 2011年09月13日 ... -
2011-11-1
2012-01-17 03:23 4312011-11-1 2011年11月01日 第一篇:一 ... -
我与三抗情
2012-01-16 01:57 422我与三抗情 2009年08月08日 07 ... -
坏蛋是怎样炼成的5
2012-01-16 01:57 1003坏蛋是怎样炼成的5 2009 ... -
java读取文件输出流出现的问题
2012-01-11 01:57 588java读取文件输出流出现的问题 2011年08月01日 ... -
GT-Grid 1.0 基础教程(十)
2012-01-11 01:56 475GT-Grid 1.0 基础教程(十) 2011年08月01 ... -
autocomplete自动匹配
2012-01-11 01:56 572autocomplete自动匹配 2011年08月01日 ... -
Oracle Express 修改字符集,升级APEX
2012-01-11 01:56 637Oracle Express 修改字符集,升级APEX 20 ... -
java多线程及线程池小结-atomti-iteye技术网站
2012-01-11 01:56 509java多线程及线程池小结 ...
相关推荐
可重复使用的并行数据结构和算法.doc
可重复使用的并行数据结构和算法.pdf
。。。
广义自动校准部分并行采集 (GRAPPA) 基于结构化低秩矩阵补全的无标定并行成像重建 用于约束 MRI 的局部 k 空间邻域 (LORAKS) 的低秩建模 使用双半回波 k 空间采集和低秩重建最小化磁共振成像中的回波和重复时间
结合航迹规划多约束条件的实际,改进了启发式A*系列算法的流程及数据结构,将A*算法中的OPEN表映射到CLOSED表中,提出一种装箱式方法管理CLOSED表,提高了对重复节点的查找效率,解决了并行A*算法中维护CLOSED表时...
为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的...理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。
主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”(第6~11章 )按章节顺序分别讨论了基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方 法,归并和归并排序方法、优先...
主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”(第6~11章 )按章节顺序分别讨论了基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方 法,归并和归并排序方法、优先...
针对已有的社团发现算法存在时间复杂度较高、运行过程会产生大量重复团等问题,引入二叉树的存储结构、权重排序、深度优先遍历的概念,与Spark基于内存计算的特点相结合,提出一种改进的并行化S-T-CS算法。...
缓存优化:利用缓存技术减少密钥生成和子密钥混淆置换等耗时操作的重复计算,提高算法的执行效率。 通过以上设计与实现,基于Misty1算法的加密软件能够为用户提供安全、可靠的文件加密和解密功能,保护用户的数据...
结合航迹规划多约束条件的实际,改进了启发式A*系列算法的流程及数据结构,将A*算法中的OPEN表映射到CLOSED表中,提出一种装箱式方法管理CLOSED表,提高了对重复节点的查找效率,解决了并行A*算法中维护CLOSED表时存在的...
为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行...理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。
此快速参考是对C++17标准库提供的基本数据结构、算法和功能的浓缩指南。它不解释C语言或语法,但任何具有基本C知识或编程经验的人都可以访问。即使是最有经验的C程序员也会从中学到一两样东西,并发现它是一种有用的...
1.4.3 关系的和面向对象的数据 1.5 小结 1.6 参考文献 第2章 数据存储 2.1 存储器层次 2.1.1 高速缓冲存储器 2.1.2 主存储器 2.1.3 虚拟存储器 2.1.4 第二级存储器 2.1.5 第三级存储器 2.1.6 易...
3.并行任务派生 并行处理机通过指令本身就可启动多个PE并行工作;多处理机由可由任务派生任务,任务多于处理机时多余任务进入排队器等待。 4.进程同步 并行处理机自然同步;多处理机需要特殊的同步措施。 5.资源...
4、软件的观点 操作系统是程序和数据结构的集合。 5、管理的观点 操作系统是计算机硬件和软件资源的合理而协调的管理者。 6、 操作系统是一个大型的程序系统,它负责计算机的全部软、硬件资源的分配、调度工作,控制...