文档介绍：国防科学技术大学
硕士学位论文
面向Cilk的并行递归程序优化技术研究
姓名:潘威
申请学位级别:硕士
专业:计算机科学与技术
指导教师:杨学军
2010-12
国防科学技术大学研究生院硕士学位论文
摘要
随着多核体系结构的出现和快速发展,如何在多核体系结构上进行简单高效
的并行程序设计以充分利用多核所提供的并行性已变得日益重要。
然而要在传统的并行程序语言上编写出高效的并行程序,程序员需要对底层
细节和程序结构有清晰的认识。因此,需要有一种新的编程模型既能简单的实现
并行,同时又能高效的执行。有研究指出利用分治法和递归模型能在实现这一目
的的过程中起到很大的作用。目前有一种简单的基于线程的并行程序设计语言—
—Cilk 能自然的实现并行递归。作为对 C 语言的精简扩展,程序员在编写 Cilk 程
序时,更多的关注于开发并行性和局部性,而不用关心底层的调度和负载均衡。
但是我们研究中发现,在并行度远高于处理器个数的情况下,特别是并行递归程
序,会因为派生过多的例程导致过多的开销,甚至使并行程序的性能还不如串行
程序,因此需要通过降低这部分开销来优化 Cilk 并行递归程序,以提高其性能。
本文根据不同并行递归问题的计算过程,总结出其辅助性能模型。在该模型
下,能推断出例程派生开销对程序性能的影响,进一步的可以推断出减少这部分
开销后对并行递归程序的性能影响。本文首先对 Cilk 程序进行静态优化,包含并
行度优化和负载均衡优化。并行度优化根据硬件平台限制其例程派生总数,使 Cilk
程序在派生例程的过程中当例程派生到一定数量时就不再派生例程,从而降低并
行化开销。负载均衡优化在此基础上对例程派生的深度做进一步限制,使得各个
例程间继续向下派生例程的能力差距缩小,从而减少各个例程间计算量的差距以
提高均衡性,最终实现稳定的性能改进。此外,本文还针对静态优化在负载均衡
方面的不足提出了动态优化方法,它能保证程序在执行过程中派生例程数保持在
一个均衡的区间内,从而既不产生巨额的例程派生开销,又能保持一定的并行度
和负载均衡。
另外,本文在面向循环的数据重用模型基础上构建并行递归程序的数据重用
模型,该模型首先分析基于例程的并行递归数据重用模型,然后分析静态优化后,
基于静态调度的 Cilk 并行递归程序的数据重用性模型,最后给出不同条件下并行
递归程序中数据重用的分类和求解方法。

关键词:并行递归;Cilk;静态优化;负载均衡;数据重用
第 i 页
国防科学技术大学研究生院硕士学位论文
Abstract
Along with the fast development of multi-core architecture, it es more and
more important how to realize efficient parallel programming to make use of the
parallelism provided by the multi-core.
However, when writing parallel program on traditional parallel programming
languages, programmers need to know the bottom details and the structure of the
program well; thereby it’s needed that a new programming model for realizing parallel
simply and efficiently. Studies have pointed out that the use of divide and conquer and
recursive is great useful in realizing the aim. There is an algorithmic multithreaded
language——Cilk, which can realize parallel recursion naturally. As a faithful extension
of C, when building a Cilk program, a programmer can concentrate on structuring his
program to expose parallelism and exploit locality, leaving the runtim