201230

Size: px

Start display at page:

Download "201230"

散颜
7 years ago
Views:

1 Computer Engineering and Applications 计算机工程与应用 212,48(3) 73 多核机群上数据密集型应用并行程序性能优化 1,2 1 黄华林, 钟诚 HUANG Hualin 1,2, ZHONG Cheng 1 1. 广西大学计算机与电子学院, 南宁广西电网南宁供电局, 南宁 School of Computer, Electronics and Information, Guangxi University, Nanning 534, China 2.Nanning Power Supply Bureau, Guangxi Power Grid, Nanning 5331, China HUANG Hualin, ZHONG Cheng. Parallel program performance optimization for data-intensive applications on multi-core clusters. Computer Engineering and Applications, 212, 48(3): Abstract:Using dynamic data task block scheduling policy and all-locking technology on the heterogeneous multicore clusters, this paper presents a hybrid parallel programming mechanism of multiprocess-level and multithreadedlevel for the data-intensive applications, which can efficiently use the data in the main memory and dynamic schedule the data block in shared L2 cache, and presents the technology and strategy of paralleled application performance optimization for the data-intensive applications. The experiments for solving the multi-keyword search of random sequences parallelly on the heterogeneous multi-core clusters show that the parallel programming mechanism and performance optimization methods are usable and efficient. Key words:multi-core cluster; multiple threads; parallel programming; performance optimization 摘要 : 在异构多核机群系统上利用数据任务块的动态调度策略和全锁定技术, 给出一种面向数据密集型应用的结点内主存和可用的共享二级缓存大小中动态调度数据块的多进程级和多线程级并行编程机制, 给出了优化数据密集型应用并行程序性能的策略和技术在多核计算机组成的异构机群上并行求解随机序列多关键字查找的实验结果表明, 所给出的多核并行程序设计机制和性能优化方法可行和高效关键词 : 多核机群 ; 多线程 ; 并行编程 ; 性能优化文章编号 : (212) 文献标识码 :A 中图分类号 :TP311 1 引言多核技术和多核并行编程已经成为当今高性能计算的主流方向之一研究多核处理器平台上数据密集型应用并行编程和性能优化方法尤其重要文献 [1] 研究了在多核处理器上一级缓存进行选择性的只读共享数据和复制策略, 也就是私有一级缓存和共享二级缓存采用选择性复制策略, 降低了一致性开销, 减少了存取冲突和数据交换次数, 减少了平均访问延迟和节省了存储空间但是该文提出的策略方法还没有真正能解决数据密集型应用中频 [2-6] 繁的访问主存和共享 2 级缓存的次数问题文献[7] 研究设计了一个运行机制框架, 提出了最优化全锁定和缓存敏感的锁定方法, 对在多核机群系统上数据密集型应用进行了优化, 并在不同的应用程序上进行性能测试但上述文献中运用的各种共享主存并行技术还是以 SMP 机群系统的结构特点进行设计 [8-1] 的, 没有真正能够充分利用多核计算机一级缓存共享二级缓存和主存相互之间的特点, 没有对程序进一步细粒度并行化, 没有发挥多核技术多线程技术在数据密集型应用中的优势本文在面向计算密基金项目 : 广西高校优秀人才资助计划 (No.RC274); 广西研究生教育创新计划 (No ) 作者简介 : 黄华林 (1984 ), 男, 助理工程师, 主要研究方向 : 网络与并行计算技术 ; 钟诚 (1964 ), 男, 教授, 博士生导师, 主要研究方向 : 并行计算网络信息安全 hhlpxt@163.com 收稿日期 : 修回日期 : CNKI 出版日期 : DOI:1.3778/j.issn

2 74 212,48(3) Computer Engineering and Applications 计算机工程与应用集型应用的进程级和线程级并行编程机制的基础上, 给出一种适合面向数据密集型应用结点内动态调度的进程级和线程级并行编程机制及程序性能优化技术, 并在多核计算机组成的机群上以并行查找多关键字为实例测试验证所给出的并行编程机制和性能优化方法 2 数据密集型应用多核并行编程机制为了充分利用多核机器特点, 针对数据密集型应用, 在多核异构机群上可采取如下策略设计开发优化存储结构层次数据密集型并行应用程序 : 第一, 对数据密集型应用问题的数据在程序中有无相关性进行分析, 根据多核结构的特性, 对并行程序的循环部分一般占运行时间的大部分, 那么就要从循环细粒度并行化来减少计算的开销, 因此, 并行程序中选择尽量在程序中数据之间是无关性或者相关性不是很多的循环计算区域进行集中细粒度并行化, 在程序中并行执行多个线程, 进而减少读写数据冲突, 提高程序并行计算的速度第二, 对要解决数据密集型应用问题进行具体的数据任务划分, 分析异构多核机群中各个结点的存储层次结构不同大小的主存私有 1 级缓存和共享 2 级缓存甚至可能有 3 级缓存, 然后按结点共享 2 级缓存和主存的不同大小, 分别对应地将划分数据块映射分配给各个多核结点处理, 根据每个结点的计算和传输能力不同, 不同的计算延迟和传输延迟, 并行处理发送给它们不同大小的任务, 使每个结点接收的数据块和本身处理能力相合适第三, 通过消息传递把数据块分配到各个多核计算机结点进行处理, 那么在每个结点中将通过添加 OpenMP 编译制导语句并行执行结点本身拥有的数据块, 然后在每个结点内通过运用 pragma omp for shared() 循环或 pragma omp for schedule() 循环调度, 在数据密集型应用程序中主要的循环迭代部分使用 schedule 语句将循环调度和任务数据块传到运行库和编译器, 并要采用动态调度策略即 dynamic 调度策略, 具体是对数据块大小进行选定, 对循环分块的大小要与其设定的线程数量相适应, 选定循环分块的大小是通过下面的参数进行相应设置 : 合理选择动态调度策略中调整块的大小, 通过不同参数的测试得到在每个结点上动态调度最佳的分块大小的具体范围, 即在程序中利用变量设置来进行多线程调度结点内数据块, 再根据每个结点接收的顺序来预先在并行应用程序初始化前设置相应的不同参数, 同时也考虑每个结点中的不同大小的 2 级缓存和具体的结点数目在共享数据块的并行区域中运用 OpenMP 不同的并行语句进行设置, 从而达到通过结点内并行执行多个线程来提高并行程序的处理与通信效率, 进而达到改进数据密集型应用并行程序的性能 3 数据密集型应用多核并行程序性能优化方法为了提高多核处理器核处理大规模数据的速度, 减少访问共享内存的次数和读写冲突, 减少远程访问的通信开销, 那么在并行混合程序优化性能技术中就要充分利用多核计算机和异构多核机群的优势, 发挥核间的通信开销小和数据传送时间较短, 结合多核计算机多级存储和多线程技术特点, 设计异构多核机群上适应数据密集型应用的多核并行程序设计框架, 如图 1 所示第一, 对于数据密集型应用程序, 需要进行多核结点之间的消息通信首先, 为了减少通信开销和解决通信带宽的影响, 主要采用消息传递的方式对数据任务进行划分和发送接收, 保证数据任务能在不同处理能力的各个多核结点都能接收到合适的数据规模其次, 有的数据密集型应用还具有些比较特殊的特点, 也就是说执行过程中可能有些应用程序是需要大量内存空间进行数据交换, 有些应用程序可能有频繁访问存储器, 因此, 在划分数据任务时, 采用的分配技术和策略是根据实际具体的多核异构机群中不同大小的二级缓存和主存, 让各个不同的多核结点分到不同的数据任务块最后, 应用程序中一般都有循环迭代的并行区域, 对于不同的多核结点之间, 并行应用程序通过主结点发送数据任务块给不同的处理能力大小的从结点进行计算, 最后由各个从结点计算得到的结果统一归并到主结点, 从而提高数据密集型应用程序性能线程技术和动态调度策处理任务多主结点发送任务量 ( 不参与计算 ) 发送消息 ( 任务量 ) 从结点接收消息 ( 任收消息 ( 任务量 ) 计算务量 ) 计算略处理任务图 1 第二, 在多核处理器为结点的异构多核机群中, 应用程序的计算操作的部分是在从结点内进行, 采数据密集型应用多核并行程序设计框架处理结果返回从结点接

3 黄华林, 钟诚 : 多核机群上数据密集型应用并行程序性能优化 212,48(3) 75 用以下两个方面的技术策略进行程序性能优化 : 首先, 在不同的多核处理器结点内, 共享二级缓存和访问主存的冲突成为影响应用程序性能的关键因素, 那么就要在数据密集型应用中利用多线程技术来提高共享二级缓存和主存的效率, 具体要实现多线程 [12] 技术有三个可选择的策略 : 细粒度多线程技术粗粒度多线程技术和同时多线程技术结合异构多核机群和数据密集型的特点, 选择细粒度多线程技术来对应用程序的性能进行优化, 因此在利用细粒度多线程技术时要详细分析影响程序性能的因素, 对程序进行设置以下相应的各个参数 : 循环分块大小的参数结点内最优的可用二级缓存和内存大小的参数值多线程的个数其次, 在当多个线程执行应用程序中, 相同的数据任务会发生存取冲突 ( 读写冲突 ) 时, 这样使得应用程序中的主要循环部分很难得到正确有效的执行针对这个问题文献 [7] 提出了最优化全锁定和缓存敏感锁定两个方案最后, 更深入地采用以下技术和策略进行数据密集型应用程序的性能优化 :(1) 在并行程序中的主要循环迭代部分加上 OpenMP 的编译语句, 即主要循环迭代部分尽量是数据在程序中无相关性或者少量的相关性 (2) 应用程序的主要数据交换或者计算部分, 采用 OpenMP 产生的多线程来实现数据交换或者计算, 并通过细粒度多线程技术和充分利用一级缓存共享二级缓存来减少处理核访问主存的次数, 以避免结点内处理核之间不必要的通信开销和数据交换, 提高结点内处理核处理不同的数据任务的处理能力, 实现了细粒度线程级并行优化 (3) 采用动态调度策略即 dynamic 调度策略, 通过运用 pragma omp for shared() 循环或 pragma omp for schedule() 循环调度, 动态调整处理不同的数据任务块的能力, 从而更好地让多线程在并行应用程序细粒度并行发挥作用, 达到负载平衡, 进而提高数据密集型应用程序的性能以下给出运用数据密集型应用程序性能优化技术设计并行查找随机序列多关键字的关键代码 : ccsize=hcuanc[rank]/mmulti[rank]// 设置最佳动态调度循环的数据块大小 #pragma omp parallel shared(buff,b,ccsize)private(p, q,s)// 在从结点并行区域内共享变量和数据分块的大小参数并设置私有变量 #pragma omp for schedule(dynamic,ccsize)nowait // 从结点内动态地将循环迭代分配到各线程 4 实验性能测试 4.1 实验环境实验的操作系统为 Red Hat Linux 12., 采用 C 语言 MPI 和 OpenMP 进行编程 ; 硬件环境是 1 Mb/s 以太网连接的多核 PC 计算机组成的异构机群, 系统包括的多核处理器结点如表 1 所示结点类型 AMD CPU Xeon E GHz Athlon TM 64 X2 DualCore 2.3 GHz Pentium E GHz Pentium 4 3. GHz 实验测试程序是并行查找随机序列多关键字 4.2 实验结果及分析实验数据量 M 分别为 5 1,1 1, 在由 3~6 个结点组成的异构多核机群上测试, 三个结点机群由 1 个单核 1 个四核和 1 个双核计算机组成, 四个结点机群由 1 个单核 1 个四核和 2 个双核计算机组成, 五个结点机群由 1 个单核 1 个四核和 3 个双核计算机组成, 六个结点机群由 1 个单核 1 个四核和 4 个双核计算机组成实验中测试的范围取处理核数 p 到 2p 之间内存 /MB 二级缓存 /MB 由图 2 和图 3 中得到, 对结点数为 5 的异构多核图图 3 表 1 多核异构机群系统结点配置信息 M=5 1 时, 五个结点异构多核机群 12 并行查找随机序列多关键字的运行时间 M=1 1 时, 五个结点异构多核机群并行查找随机序列多关键字的运行时间 1 2 一级缓存 /KB

4 76 212,48(3) Computer Engineering and Applications 计算机工程与应用机群进行测试, 数据量 M 为 5 1 时, 线程数与处理核数之间的关系是 n=(8/5)p 时 ; 数据量 M 为 1 1 时, 线程数与处理核数之间的关系 n= (3/2)p 时, 那么其并行计算所需时间最小从图 4 和图 5 可以看出, 对结点数为 6 的异构多核机群进行测试, 数据量 M 为 5 1 时, 线程数与处理核数之间的关系是 n=(13/12)p 时 ; 数据量 M 分别为 1 1 时, 线程数与处理核数之间的关系分别是 n=(17/12)p 时, 并行求解随机序列多关键字的查找问题所需的运行时间最少图 4 图 6 和图 7 给出的是, 在并行求解随机序列多关键字的查找的应用程序中设置不同大小的循环分块和相同的线程数, 然后在异构多核机群上运用结点中可执行时间 /s 图图 M=5 1 时, 六个结点异构多核机群并行查找随机序列多关键字的运行时间 M=1 1 时, 六个结点异构多核机群并行查找随机序列多关键字的运行时间二级缓存大小为 14 MB 二级缓存大小为 16 MB 二级缓存大小为 17 MB 二级缓存大小为 18 MB M=5 1 时, 不同个数结点的异构多核机群并行查找随机序列多关键字的执行时间执行时间 /s 图 7 用的不同大小的二级缓存空间, 对不同的数据量, 分别在三个四个五个和六个结点进行测试其对并行求解随机序列多关键字的查找问题执行时间的影响从图 6 和图 7 可以看出, 对并行求解随机序列多关键字的查找问题的不同大小的数据量进行测试, 在并行应用程序中设置了相同的线程数和通过在程序中动态调度循环任务块的大小, 那么随着在并行程序可用的二级缓存的大小和数据量的增大, 并行求解随机序列多关键字的查找问题所需的执行时间明显减少从上面可以得到, 在并行程序中通过充分利用异构多核机群系统中的各个结点处理能力的不同各个结点的通信开销的不同和不同大小的可用的二级缓存, 可以降低处理核访问主存的频率, 大大缩减应用程序的计算时间, 从而可以提高并行处理数据密集型应用程序的性能然后分别在 2~6 个结点的异构多核机群上测试并行求解随机序列多关键字的查找问题的加速比, 实验结果如图 8 所示加速比二级缓存大小为 14 MB 二级缓存大小为 16 MB 二级缓存大小为 17 MB 二级缓存大小为 18 MB M=1 1 时, 不同个数结点的异构多核机群并行查找随机序列多关键字的执行时间图 8 数据量 M=1 1 数据量 M=5 1 数据量 M=1 1 数据量 M=5 1 数据量 M= 结点数异构多核机群并行求解随机序列多关键字查找问题获得的加速比图 8 可以看出, 对于具体的应用程序, 增加并行程序中的数据量, 在给定的异构多核机群上, 通过运用 dynamic 调度策略要对数据块大小进行合理设置, 并使循环分块的大小要与并行程序中设定的线程数量相适应, 在并行求解随机序列多关键字的查找问

5 黄华林, 钟诚 : 多核机群上数据密集型应用并行程序性能优化 212,48(3) 77 题的应用程序获得了明显的加速最后分析判断并行求解随机序列多关键字的查找问题的可扩展性 [13] 实验测出问题规模不变时的加速比 A, 然后推出并行求解随机序列多关键字算法中串行分量的比例 c: 1/A - 1/p c = 1-1/p (1) 分析增加 p 时所计算出的 c 的增减性来判断并行求解随机序列多关键字的查找问题算法的可扩展性图 9 所示为 M 为 5 1 测试并行查找随机序列多关键字时 c 随着 p 增加而变化的情况串行分量图 9 从图 9 可看出, 当多处理核心数目 p 较小时, 那么随着 p 的增加串行分量 c 减小较快 ; 当 p 较大时, 那么随着 p 的增加串行分量 c 总体趋势仍在减小可见, 本文给出的多核并行程序性能优化技术在求解数据密集型应用时具有较好的可扩展性 5 结束语处理器核数目 M=5 1 时, 串行分量 f 随处理器核数目 p 的增加的变化情况针对数据密集型应用, 从提高处理核心访问主存效率和利用多级存储角度, 给出 OpenMP 的动态调度策略核心代码, 设计了数据密集型应用多核并行程序设计流程, 具体给出了优化存储结构层次数据密集型并行应用程序性能的技术, 并利用数据任务块的动态调度策略来改善并行程序运行性能参考文献 : [1] 郭惠芳, 姜鲲鹏, 赵荣彩, 等. 多核处理器片上 Cache 的选择性复制策略 [J]. 计算机工程,29,35(4): [2] 李清宝, 张平. 基于分布 / 共享内存层次结构的并行程序设计 [J]. 计算机应用,24,24(6): [3] 宋伟, 宋玉. 基于 SMP 集群系统的并行编程模式研究与分析 [J]. 计算机技术与发展,27,17(2): [4] 刘玮. 一种 SMP 机群下程序并行化模式的设计与应用 [J]. 微电子学与计算机,25,22(11): [5] 胡晨骏, 王晓蔚. 基于多核集群系统的并行编程模型的研究 [J]. 计算机技术与发展,28,18(4):7-73. [6] 涂碧波, 邹铭, 詹剑锋, 等. 多核处理器机群 Memory 层次化并行计算模型研究 [J]. 计算机学报,28,31(11): [7] Ravi V T,Agrawal G.Performance issues in parallelizing data-intensive applications on a multi-core cluster[c]//proceedings of 29 Conference on Clustering Computing and Grids,29: [8] Chapman B,Merlin J,Pritchard D,et al.program development tools for clusters of shared memory multiprocessors[j].journal of Super-Computing,2,17: [9] Rabenseifner R,Wellein G.Communication and optimization aspects of parallel programming models on hybrid architecture[j].international Journal of High Performance Computing Applications,23,17(1): [1] Wu Chao-chin,Lai Lien-fu,Yang Chao-tung,et al.using hybrid MPI and OpenMP programming to optimize communications in parallel loop self-scheduling schemes for multicore PC clusters[j].journal of Supercomputing,212, 6(1): Huang Hualin,Zhong Cheng,Lu Zhonglong.Process-level and thread-level parallel programming mechanism and performance optimization techniques on multi-core clusters[c]//proceedings of Second International Symposium on Parallel Architectures,Algorithms and Programming, 29: [12] Olukotun K,Hammon L,Laudon J.Chip multiprocessor architecture:techniques to improve throughput and latency[m].america:morgan & Claypool,27. [13] 陈国良. 并行算法的可扩放性分析 [J]. 小型微型计算机系统,1995,16(12):1-16.

《嵌入式系统设计》教学大纲

《嵌入式系统设计》教学大纲多核架构及编程技术教学大纲课程代码 :20062022071 课程负责人 : 杨剑锋课程中文名称 : 多核架构及编程技术课程英文名称 :Multi-Core Architecture and Programming Technologies 课程类别 : 专业必修课程学分数 :3 课程学时