学位论文 > 优秀研究生学位论文题录展示

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

作　者: 潘威
导　师: 杨学军
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 并行递归 Cilk 静态优化 负载均衡 数据重用
分类号: TP338.6
类　型: 硕士论文
年　份: 2010年
下　载: 23次
引　用: 0次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  8-9
Abstract  9-10
第一章 引言  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
  4.2 面向Cilk 应用的并行递归数据重用模型  48-55
    4.2.1 单层并行子递归例程模式  51-52
    4.2.2 二层并行子递归例程模式  52-55
  4.3 小结  55-57
第五章 Cilk 优化技术编译实现方案  57-69
  5.1 静态优化编译实现技术研究  57-67
    5.1.1 Cilk 程序编译词法分析  59-61
    5.1.2 Cilk 程序编译语法分析及实现  61-67
  5.2 动态优化编译实现方案研究  67-69
第六章 优化模型实验验证  69-74
  6.1 矩阵乘程序分析及性能测试  69-72
    6.1.1 矩阵乘Cilk 实现及分析  69-71
    6.1.2 矩阵乘Cilk 优化测试  71-72
  6.2 快速排序分析及性能测试  72-74
第七章 结束语  74-76
  7.1 工作总结  74-75
  7.2 展望  75-76
致谢  76-78
参考文献  78-83
作者在学期间取得的学术成果  83

相似论文

  1. 随机路由在无线传感器网络中的研究与应用,TN929.5
  2. 高校教务管理网上选课系统优化研究,TP393.09
  3. 基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
  4. LTE-A异构网络中的自组网技术研究,TN929.5
  5. 基于一种新经济模型的异构网络选择算法,TN929.5
  6. 基于QoS的无线Mesh网络路由协议及相关技术的研究,TN929.5
  7. 构建分布式系统的关键技术研究与实现,TP338.8
  8. 基于S2SH框架的雅砻江虚拟研究中心系统研究与设计,TP311.52
  9. 基于负载均衡的混合型应用层组播模型研究,TP393.02
  10. 异构网络联合接纳与切换控制技术研究,TN929.5
  11. 基于逻辑卷的分级存储系统设计与实现,TP333
  12. 虚拟环境中多网络接口卡I/O调度系统的研究,TP334.7
  13. RFID数据清洗处理策略与算法,TP391.44
  14. 基于分布式实时数据库的事务调度策略研究与改进,TP311.13
  15. 分布式内存数据库存储研究,TP311.13
  16. 负载均衡调度系统的设计与实现,TP393.02
  17. 基于CDN和P2P技术的混合流媒体内容分发机制研究,TN919.8
  18. 图像检索的并行计算方法与系统,TP391.3
  19. 并行与分布入侵检测技术研究,TP393.08
  20. 基于负载均衡的3G视频传输系统的设计与实现,TN919.8
  21. 基于能量感知的无线传感器网络分簇算法研究,TP212.9

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 电子数字计算机（不连续作用电子计算机） > 各种电子数字计算机 > 并行计算机
© 2012 www.xueweilunwen.com