面向Cilk的并行递归程序优化技术研究

发布时间：2020-12-13 22:00

　　随着多核体系结构的出现和快速发展,如何在多核体系结构上进行简单高效的并行程序设计以充分利用多核所提供的并行性已变得日益重要。然而要在传统的并行程序语言上编写出高效的并行程序,程序员需要对底层细节和程序结构有清晰的认识。因此,需要有一种新的编程模型既能简单的实现并行,同时又能高效的执行。有研究指出利用分治法和递归模型能在实现这一目的的过程中起到很大的作用。目前有一种简单的基于线程的并行程序设计语言——Cilk能自然的实现并行递归。作为对C语言的精简扩展,程序员在编写Cilk程序时,更多的关注于开发并行性和局部性,而不用关心底层的调度和负载均衡。但是我们研究中发现,在并行度远高于处理器个数的情况下,特别是并行递归程序,会因为派生过多的例程导致过多的开销,甚至使并行程序的性能还不如串行程序,因此需要通过降低这部分开销来优化Cilk并行递归程序,以提高其性能。本文根据不同并行递归问题的计算过程,总结出其辅助性能模型。在该模型下,能推断出例程派生开销对程序性能的影响,进一步的可以推断出减少这部分开销后对并行递归程序的性能影响。本文首先对Cilk程序进行静态优化,包含并行度优化和负载均衡优化。并行... 

【文章来源】：国防科技大学湖南省 211工程院校 985工程院校

【文章页数】：83 页

【学位级别】：硕士

【部分图文】：

计算fib(4)流程图

当限制例程数最大值小于某临界点时，第一次任务窃取后计算终会一直以串行副本执行计算，而其他例程的计算任务 fi得该例程是整个计算过程中执行计算时间最长的例程。在程其他处理器会不停的执行任务窃取而且不断失败，从而从根果。此节点也就位于关键路径之上，即便是在无穷多个处理如此，这也是导致'T 增加的根源所在，其结果必然导致负载够大的 NUMTHREADS 也能解决这个问题，但是这样的后果例程，会在一定程度上对提高性能起到副作用，这与优化的，需要针对这个问题进一步优化。原来的优化方法降低了工作能，但是却降低了均衡。现在需要在原来限制例程派生数的，从而进一步的提高性能。 静态优化：例程深度优化出了优化后程序还存在的均衡问题，本节将进一步提高均衡

种基于线程的并行程序设计语言，能较好的应用于共过添加几个关键字来指出并实现并行，不需要额外的体系结构中，不仅主存共享，一般而言末级 Cache 也常适合在目前的多核处理器上进行并行程序设计。在据重用模型后，我们将提出面向 Cilk 的并行递归程序4.1 基于例程的并行递归数据重用模型的模型中，并行执行体的调度单位将是并行子递归例例程的并行递归数据重用。基于例程的并行递归数据并行子递归之间的关系。在 Cilk 程序中，并行子递归，因此，面向 Cilk 应用的并行递归数据重用理论将在间的关系。通过下图可以看出基于例程的并行递归数的并行递归数据重用模型的关系。


本文编号：2915245