并行递归Cilk静态优化负载均衡数据重用硕士论文.docVIP

面向Cilk的并行递归程序优化技术研究 计算机科学与技术， 2010， 硕士 【摘要】 随着多核体系结构的出现和快速发展,如何在多核体系结构上进行简单高效的并行程序设计以充分利用多核所提供的并行性已变得日益重要。然而要在传统的并行程序语言上编写出高效的并行程序,程序员需要对底层细节和程序结构有清晰的认识。因此,需要有一种新的编程模型既能简单的实现并行,同时又能高效的执行。有研究指出利用分治法和递归模型能在实现这一目的的过程中起到很大的作用。目前有一种简单的基于线程的并行程序设计语言——Cilk能自然的实现并行递归。作为对C语言的精简扩展,程序员在编写Cilk程序时,更多的关注于开发并行性和局部性,而不用关心底层的调度和负载均衡。但是我们研究中发现,在并行度远高于处理器个数的情况下,特别是并行递归程序,会因为派生过多的例程导致过多的开销,甚至使并行程序的性能还不如串行程序,因此需要通过降低这部分开销来优化Cilk并行递归程序,以提高其性能。本文根据不同并行递归问题的计算过程,总结出其辅助性能模型。在该模型下,能推断出例程派生开销对程序性能的影响,进一步的可以推断出减少这部分开销后对并行递归程序的性能影响。本文首先对Cilk程序进行静态优化,包含并行度优化和负载均衡优化。并行...?更多还原 【Abstract】 Along with the fast development of multi-core architecture, it becomes 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抯 needed that a new programming model for realizing parallel simply and efficiently. Studies have pointed out that the us...?更多还原 【关键词】 并行递归； Cilk； 静态优化； 负载均衡； 数据重用； 【Key words】 Parallel recursion； Cilk； static optimization； Load balance； data reuse； 摘要 8-9 Abstract 9 第一章 引言 10-13 1.1 课题背景 10 1.2 研究现状 10-11 1.3 本文工作 11-12 1.4 论文结构 12-13 第二章 背景知识 13-27 2.1 Cilk 介绍 13-18 2.1.1 Cilk 编程模型 13-16 2.1.2 Cilk 调度策略 16-17 2.1.3 Cilk 性能模型 17-18 2.2 Lex 和Yacc 介绍 18-23 2.2.1 Lex 介绍 18-20 2.2.2 Yacc 介绍 20-23 2.3 传统数据重用模型介绍[51,52] 23-27 2.3.1 串行循环数据重用[51,52] 23-24 2.3.2 并行循环数据重用[52] 24-27 第三章 Cilk 并行递归程序并行度及负载均衡优化 27-43 3.1 Cilk 并行递归程序案例分析 27-29 3.1.1 实验平台 27 3.1.2 案例分析及实验结果 27-29 3.2 Cilk 并行递归程序优化理论模型 29-31 3.3 Cilk 并行递归程序并行度优化技术研究 31-34 3.4 并行度优化进一步分析 34-35 3.5 Cilk 负载均衡优化技术研究 35-43 3.5.1 静态优化：例程深度优化 38-41 3.5.2 动态优化：例程再次派生实现 41-43 第四章 Cilk 并行递归程序数据重用模型 43-57 4.1 基于例程的并行递归数据重用模型 43-48