中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 并行计算实验室  > 学位论文
学科主题: 计算机软件::程序设计及其语言
题名:
OpenMP循环调度算法及SpMV多核并行化研究
作者: 刘胜飞
答辩日期: 2009-06-04
导师: 张云泉
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 硕士
关键词: OpenMP
其他题名: Research on OpenMP Loop Scheduling Algorithm and Parallel Sparse Matrix-Vector Multiplication Algorithm on Multi-core Processors
摘要: OpenMP是一种支持Fortran,C/C++的共享存储并行编程标准。它基于fork-join的并行执行模型,将程序划分为并行区和串行区。近几年来,OpenMP在SMP(Symmetric Multi-Processing)和多核体系结构的并行编程中得到了广泛的应用。随着多核处理器的发展,实际的应用程序如何充分利用多个处理器核来提高运算效率也成为研究的热点。 在科学计算中,循环结构是最核心的并行对象之一。考虑到负载平衡、调度开销、同步开销等多方面因素,OpenMP标准制定了Static调度、Dynamic调度、Guided调度和Runtime调度等不同策略。针对Guided调度策略不适合递减型循环结构的缺点,本文提出了一种改进的new_guided调度策略,并在OMPi编译器上加以实现。New_guided调度策略的主要思想是对前半部分的循环采用Static调度,后半部分的循环采用Guided调度。此外,本文针对不同的循环结构,在多核处理器上对不同的调度策略进行了评测。测试结果表明,在一般情况下,OpenMP默认的Static策略的调度性能最差;对于规则的循环结构和递增的循环结构,Dynamic调度策略、Guided调度策略和new_guided策略的性能差别不大;对于递减型的循环结构,Dynamic调度策略和new_guided策略的性能相当,要优于Guided调度策略;对于求解Mandelbrot集合这类计算量集中在中间的随机循环结构,Dynamic调度策略优于其它策略,new_guided策略的性能介于Dynamic调度和Guided调度之间。 随着多核处理器的问世和发展,多线程程序设计也已经成为一个不可回避的问题。稀疏矩阵向量乘(SpMV, Sparse Matrix-Vector Multiplication)是一个十分重要且经常被大量调用的科学计算内核。SpMV的存储访问一般都极不规则,导致现有的SpMV算法效率都比较低。目前,多核处理器芯片上的内核数量正在逐步增加。这使得在多核处理器上对SpMV进行并行化加速变得非常重要。本文介绍了稀疏矩阵的两种常用的存储格式CSR和BCSR,并采用OpenMP实现了SpMV的多核并行化。此外,本文还讨论了寄存器分块算法、压缩列索引等优化技术,以及不同调度策略对多线程并行后的SpMV的影响。在曙光天阔服务器S4800A1上的测试表明,大部分矩阵都取得了可扩展、甚至是超线性的加速比,但是对于部分规模较大的矩阵,加速效果并不明显。在我们的测试中,与基于CSR实现的多线程SpMV相比,采用寄存器分块算法优化后的SpMV运算速度平均提高了28.09%。在基于CSR实现的多线程SpMV中,采用列索引优化技术后的程序比优化前的速度平均提高了13.05%。此外,本文实现了一种基于非零元个数的调度策略。在该策略中,每个线程处理几乎相同数量的非零元。我们将它和OpenMP标准提供的三种调度策略进行了测试和分析。测试结果表明:与OpenMP提供的调度策略相比,基于非零元个数的调度策略能取得更好的负载平衡;Dynamic调度和Guided调度在多线程SpMV中的性能基本相当,均优于Static调度策略。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/110
Appears in Collections:并行计算实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
OpenMP循环调度算法及SpMV多核并行化研究_刘胜飞.pdf(536KB)----限制开放 联系获取全文

Recommended Citation:
刘胜飞. OpenMP循环调度算法及SpMV多核并行化研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2009-06-04.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[刘胜飞]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[刘胜飞]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace