12.7  探索

Explorations

12.36 我们第12.3.1节（第622页）提到设计无锁并发数据结构的问题，这种数据结构不需要锁也能正确工作。请进一步学习这方面的内容。写出正确的无锁代码有多么困难？与基于锁的代码相比，它们的性能怎么样？你可能需要从Michael [MS98] 和Sundell [Sun04] 的工作开始。

12.37 请学习Herlihy等 [HLM03] 和Harris与Fraser [HF03] 的软件交易存储（software transactional memory）系统。在多大程度上，这种系统能成为一种构造无锁并发数据结构的通用机制？在什么环境条件下它们可能比锁更适用？

12.38 对于某些你可以用的并发语言或库，请设法弄清楚其中的消息传递是如何实现的。这一系统提供了无等待send、同步send、远程调用send，或者它们的某些混合吗？如果你希望基于某种可用的东西实现其他东西，模拟的开销怎么样（与基于基础系统所执行的底层操作比较）？将模拟的开销与在同样基础系统上由语言或库提供的其他send的优化实现做一个对比，比较的情况怎么样？

12.39 在整个12.3节我们一直隐含地假定，不同处理器所共享的存储是顺序一致的，也就是说，所有存储器操作以某种全局的总体顺序发生，其顺序与每个独立处理器上的操作一致。然而，许多多处理器系统实现的是松弛的存储器模型，只提供了弱得多的一致性保证。

请学习这种松弛的存储器模型（例如，可以去看Adve和Gharachorloo的介绍性文章 [AG96]）。请解释一个语言的运行系统的实现者可能如何使用一种称为篱笆（fence）的指令来保证正确的程序行为。

12.40 由于前一练习所提出的问题的影响，一些程序设计语言（包括Ada、Java和C#）都在语言定义中明确规定了所需的存储器模型。请学习它们的相关规则，并对它们进行比较。每种规则在各种机器上实现的效率怎样？实现者遇到的主要挑战是什么？请特别注意围绕着Java原定义中存储器模型而出现的争议（已经在Java 5里修正。关于这方面的讨论，见Pugh的文章 [Pug00]）。

12.41 OpenMPI是编译指示和运行系统的组合，是为了用于大型多处理器系统和集群上的共享存储程序设计。其支持者提出用它作为MPI的一个易用的替代品。请学习OpenMP（访问openmp.org或阅读Chandra等的书 [CMD⁺01]）。请描述它的程序设计模型。它提供了怎样的线程创建机制和同步机制？这种机制与12.3节描述的那些东西比较起来怎么样？这里设计者为了在很大型的机器上取得高性能，做出了哪些让步（如果存在的话）？

12.42 请学习shmem库包，它最早是由Cray公司的Robert Numrich为T3D超级计算机开发的。shmem在大规模多处理器和集群的并行程序设计中使用广泛，并被说成是跨越了共享存储器和消息传递之间的分界线。这种评价公正吗？在什么样的环境中可以预计shmem程序的性能优于MPI或OpenMP？（请注意，在本书写作时，shmem还没有标准化。因此不同平台上的实现可能有差异。Cray的man [手册] 页可以在下面网址找到：docs.cray.com/books/ S-2383-23/S-2383-23-manual.pdf。）

12.43 按照前两个问题的精神，研究co-array Fortran（www.co-array.org）、UPC（upc.gwu.edu）和/或者Titanium（www.cs.berkeley.edu/projects/titanium/）。它们分别是Fortran、C和Java的扩充，其设计目标都是为了支持非统一形式的共享存储器计算，其中数据的物理位置都是在程序的显式控制下。这些语言扩充与OpenMP和shmem相比怎么样？它们各自为了效率做出了哪些让步（如果有的话）？