开题外文翻译

1、目录多线程编程语言Cilk-5 的实现3摘要31 简介32 Cilk 语言43 工时第一原则5Cilk 的编译策略5任务窃取实现6测试程序6结论6多线程编程语言 Cilk-5 的实现摘要多线程编程语言 Cilk 发布的第五个版本仍然采用与第一版相同的“任务窃取”调度算法，但语言本身已经完全被重新设计，运行时系统也被重新构造。新实现版本的效率受助于一项从调度算法理论分析产生的清晰使以增加关键路径的开销为代价。尽管：集中精力最大限度的减少贡献于工时的开销，即上看起来好像是把开销转移到了关键路径，但是这种“工时第一”原则使得 Cilk-5 的实现更便捷，在当前大多数机器上 Cilk-5 派生一个并行

2、线程的典型开销只有 C 函数调用的 2 到 6 倍。很多跑在单线程上的 Cilk 程序与等价的 C 程序相比实际上没有明显的。这篇文章描述了“工时第一”原则如何在 Cilk-5 的编译器和运行时系统中被使用。特别的，在任务窃取调度中实现就绪双端队列的关键字提出了 Cilk-5 新奇的“双版本”编译策略和互斥协议关键路径，多线程，并行计算，编程语言，运行时系统，工时1 简介Cilk 是一种通过在 C 语言中引入并行控制结构行成的多线程并行编程语言。在原始的Cilk-1 版本中一个被证实高效的、随机的、“任务窃取”调度器起到了重要作用，但语言使实现的 Cilk-5 版本用了显示的传递使得并行性被手

3、动因而使用起来很笨拙。仍然使用一个理论上高效的调度器，但语言已经相当简化。它使用调用、返回语义来进行并行化，并实现了一个为了非确定性控制而实现的简单“”。Cilk-5 在当前提供共享硬件支持的对称多处理器(SMP)上能够高效运行。使用 Cilk 编写了很多应用程序，包括算法和在国际比赛中获奖的象棋程序 Cilkchess。Cilk 背后自然哲理的发展已经使得 Cilk 语言在语义和性能上真正成为 C 语言的并行扩展。在多核计算机上，Cilk 控制结构允许程序并行执行。如果把并行控制关键字从 Cilk 程包括序中省略掉，并且剩余部分在句法和语义上仍是正确的 C 程序，则称其为 Cilk 程序的C

4、 省略（或者更普通一些，叫做串行省略）。Cilk 是 C 语言的忠实扩展，因为一个 Cilk 程序的 C 省略是这个程序语义上的正确实现。此外，在单核机器上，一个并行 Cilk 程序和它的 C 省略几乎运行一样快。不同于 Cilk-1 中的调度器是可以确定的一段代码，在 Cilk-5 中编译器和运行时系统都承担起调度的责任。为了提高效率，尝试减小调度开销。无论如何，一些开销相比于其他的开销更加严重的影响执行时间。对 Cilk 调度器算法的理论认识，使保证了一般情况下开销的最优化。根据这个抽象理论，一个 Cilk 计算的性能可以用两个指标来衡量：工时，用来表示串行执行这个程序所需要的时间；关键路

5、径长度，当这个程序在无限多核上运行时所需要的时间（Cilk 提供插桩来测量这两个指标）。在 Cilk 的调度器中，可以确定一个给定开销是影响于工时还是关键路径。Cilk 的大部分效率源自于下面这个原则，在第三部分证明它。工时第一原则：使在计算中由工时承担的调度器开销最小化。明确说来，就是将负载从工时转移到了关键路径。工时第一原则在早期 Cilk 版本中扮演着重要的角色，但是 Cilk-5 更广泛的利用了这个原则。工时第一原则启发了编译 Cilk 程序的“双版本”策略。的 cilk2c 编译器是一个类型检查的源到源编译器，其通过调用 Cilk 的运行时库将一个 Cilk 程序翻译成一个 C 程序

6、。C 程序再通过 gcc 编译器产生可执行代码。cilk2c 编译器针对每个 Cilk 程序生成两个版本一个“快”版本和一个“慢”版本。“快”版本在很多方面和 Cilk 程序的 C 省略大致相同，在大多数串行语义的情况下执行。“慢”版本在少数有并行语义并需要相关的情况下执行。所有在“慢”版本中产生的调度通信都只增加于关键路径的开销，而没有增加工时开销。工时第一原则也启发了运行时负载平衡调度器中的、共享、互斥协议。Cilk 的调度器采用了“任务窃取”算法，其中空闲处理器（称为偷取者），偷取繁忙处理器（称为受害者）的任务。Cilk 的调度器保证窃取的开销只贡献于关键路径的开销，而不增加工时开销。然

7、而，很难避免由潜在受害者引起的互斥开销，进而导致工时增加。为了减少工时开销，使用了协议（也称之为 THE 协议）而不是锁，来管理在任务窃取算法中的就绪线程的运行时双端队列。THE 协议的一个额外好处是，它允许一个异常作为信号传递给工作线程，这在 Cilk 终止机制中得到了显著地应用。本文的其余部分组织如下：第二节概述了 Cilk 语言的基本特征。第三节证明了“工时第一”原则。第四节描述“双克隆”策略是如何实现的,第五节介绍了 THE 协议。第六节提供实验性论。表明 Cilk-5 调度程序是有效的。最后,第七节介绍了相关工作并提供了一些结2 Cilk 语言本节通过 Cilk-5 提供了一个对 C

8、 扩展语言 Cilk 的简短概述(对于一个完整的描述，请查看 Cilk-5 手册)。语言的主要特点是通过使用“spawn”和“sync”关键字来实现并行性的规范，以及通过使用“进口”和“中止”来实现非确定性的规范。Cilk 基本语言可以从一个例子来进行理解。图 1 显示了一个用来计算 n数列的 Cilk 程序。观察这个程序，如果三个程序将成为一个普通的 C 程序。“cilk”、“spawn”和“sync”省略掉，这个Cilk 关键字标识 fib 是一个 Cilk 程序，其是一个 C 函数的并行化。当“spawn”关键字出现在程序调用之前时并行被创建。“spawn”的语义与一个 C 函数调用不同

9、的地方只在于父函数可以与子函数一起并行执行，而不是像在 C 函数中那样等待子函数完成之后再去执行。Cilk 的调度器负责调度在并行计算机处理器上衍生的子程序。Cilk 程序不能安全地使用它的子函数返回的数据直到执行一个同步操作。同步语句是一个当地的“屏障”，并不是全局中的一个，例如，在消息传递编程模型中使用。在斐波的例子中，在返回（x + y）之前需要使用同步语句，以避免可能发生的x 和 y 在计算出来之前被求和的异常。除了显式同步语句提供的同步外，每个 Cilk 程序在它返回之前有一个隐含的同步，从而确保在务执行前所有的子任务运行结束。图 1 一个简单的用来计算 n 阶 Fibonacc 数

10、列的并行 Cilk 程序(使用一个非常坏的算法)3 工时第一原则本节将证明在第一节提到的“工时第一”原则，规定它遵循从三个假设。首先，假设Cilk的调度器操作在实践中的性能遵循理论分析。第二，认为一般而言，充足的“并行宽松度”是存在的，也就是说，Cilk程序的平均并行度超过运行它的处理器数量。第三，假设(事实上确实如此)，每个Cilk程序都有一个C省略，使得程序在单核处理器上的性能可以被测量。4 Cilk 的编译策略本节描述了cilk2c 编译器如何由 Cilk 程序生成 C 程序。根据工时第一原则，的编译器和调度程序旨在尽可能多的减少工时开销的策略是每个程序生成两个编译版本一个“快”版本和一

11、个“慢”版本。“快”版本的操作和 C 省略执行一样并且几乎没们首先描述 Cilk 调度有并行性。“慢”版本则完全支持并行性，但也伴随着开销的增描述编译器如何将 Cilk 程序语言结构转换为“快”和“慢”两种版本。算法。然后，“快”和“慢”版本来产生一个完整的 Cilk 程序实最后，现。描述运行时系统如何5 任务窃取实现在本节中，描述 Cilk-5 的任务窃取机制，它基于、共享、互斥协议（称之为“THE”协议）。按照工时第一原则，该协议被设计成旨在最大程度降低工时的开销。举个例子，在 167 兆赫的 UltraSPARC 处理器上，使用“THE”协议的 fib 程序比使用硬件锁定的fib 程序运

12、行快 25%。接下来，首先介绍这个协议的简化版本。然后，实际实现的版本，它允许异常作为信号进行传递而不引入额外开销。6 测试程序在本节中，评估 Cilk-5 的性能。12 个应用程序显示，工作开销 cl 接近在 4 台机器上分解 Cilk于 1，这表明 Cilk-5 的实现有效利用了工时第一原则。然后，程序的工时开销 cl。最后，目前的实验显示，关键路径的开销也相当小。7 结论通过介绍一些相关工作来总结本文。等人在 Mul-T 语言实现中介绍了懒惰任务的创建方法。懒惰任务创建在许多方面的懒惰调度技术类似。等人介绍其工时开销与串行 T 比较大约为 2，串行 T 是和Mul-T 所基于的基本语言实现的。的研究证实了他们的方法并且显示工时开销接近于 1 是可以Cid 语言和 Cilk 很相似，它也使用 C 作为基础语言并且使用一个简单的预处理编译器将并行 Cid 转换为 C。Cid 设计工作在分布式内存环境中，所以使用了 latency-hiding 机制而Cilk-5 没有（正在研发 Cilk 的分布式版本）。Cilk 和 Cid 都基于 C 进行扩展然后利用 C 编译器技术形成高性能代码的。然而，Cilk 是 C 语言的一个忠实扩展，支持简化 C 省略的概念，因而允许 Cilk