炼数成金 门户 CUDA 查看内容

使用 OpenMP在现有串行代码中寻找重要的并行化机会

2015-9-11 15:06| 发布者: 炼数成金_小数| 查看: 1358| 评论: 0|来自: intel

摘要: 本文介绍了在现有串行代码中寻找重要的并行化(线程化)机会的基本方法。通过实施线程化,用户可使用多条线程同时执行多项大型任务,或者主要任务的多个大型组成部分,进而显著提高应用性能。然而,线程化同样带来了 ...

工具 算法 数学 分布式 C++

简介
本文介绍了在现有串行代码中寻找重要的并行化(线程化)机会的基本方法。通过实施线程化,用户可使用多条线程同时执行多项大型任务,或者主要任务的多个大型组成部分,进而显著提高应用性能。然而,线程化同样带来了严峻的挑战--如何适当地调整现有串行代码以实现多线程执行。

构建结构良好的并行代码是一个广泛的话题,相关的文字资料有很多。本文只是一个初级教程,介绍了如何使用英特尔工程师提供的方法在现有串行代码中添加并行性。

文章分为三个部分:

基本并行化概念简介
在现有串行代码中添加并行性的方法
如何识别串行代码中可实施并行化的内容
 
如果您非常熟悉并行化概念和并行开发,完全可以跳过前两部分,着重阅读第三部分。

基本并行化概念

并行编程的目标
并行代码可同时运行,使用更多的计算资源(多枚内核、单枚内核中的多个执行引擎等)在相同时间内完成更多的任务或在更短时间内完成固定大小的任务。并行运行的代码可以是同一代码中负责处理不同数据的多个实例,也可以是负责处理完全独立的任务的不同代码集。根据所执行的并行化类型,获得的优势可能是缩短解决固定大小的问题所需要的时间或者提高在相同时间内处理更大的问题的能力。

并行性与并发性
考虑到当前的处理器微架构,更可取的方式是,如有可能,对代码进行线程化,确保它们能够并发和并行执行。相互关联时,并行性和并发性并非同义词。理解并行性和并发性对开发人员制定编码决策的影响非常重要。

并发性指两条或更多线程同时处于进程中。但是,它们并不一定同时执行。它们可能全部位于管道内,但不会同时使用资源,也不会遇到与并行执行相同的风险,或者获得与并行执行相同的优势。

并行性指多条并发线程同时执行。这种情况能够带来许多并发执行所不具备的优势,但同时也会引发诸多新的风险。

通过同时执行多条线程,您将有机会提高性能和计算资源利用率。然而,多条线程会增加应用的复杂性,加大调试的难度,此外,查找数据争夺、死锁和其它并行挑战会占用大量时间(虽然某些编程工具如英特尔® VTune™ Amplifier XE 可帮助识别存在的问题,但仍无法彻底弥补该缺陷)。

通过有效地应用线程化和并行化,有望实现巨大的应用性能优势,并根据计算问题的规模随意扩展。

功能分解与数据分解
通常,对代码进行并行处理的目标是在最短的时间内完成单个任务。为了实现该目标,您可以将整个任务拆分为多个组成部分,然后适当地分配资源,并行处理这些部分。但是,应如何拆分任务呢?是否存在大量不同的独立功能(任务)可同时执行?是否存在大量数据可划分为相当大的工作负载?是否两者兼具?

这些问题可以帮助程序员识别代码中固有的并行性类型,这会在很大程度上影响代码的并行化方式。

功能分解 是将任务拆分为多个不同的功能部分,这种方式最适合工作量随独立任务数量扩展的情况。功能分解又称为基于任务的并行化。例如,要建造一幢房子,一个人施工所需要的时间无疑最长。如果同时聘用大量技术熟练的专业人员,让他们分开从事自己最擅长的工作,各方面齐头并进,那么工作效率会更高,施工速度会更快。例如,混凝土工负责构建地基,木工负责构建房屋框架,电工负责接线,水管工负责安装管道,墙板安装工负责安装墙板,装修木工负责安装模具,砖瓦匠负责安装台面等等。各方面的工作同时进行,能够较大限度地缩短施工时间。汽车组装线是另一个关于功能分解的典型示例。不同的工人负责不同的工作,完成对零部件的加工后便传给后面的工人:车身和引擎构建工作同时进行,在某个点相遇,最终完成整个制造过程。

数据分解是将任务拆分为可单独处理的独立的数据块,这种方式最适合工作量随数据量扩展的情况。例如,为学生考试试卷评分时,如果将答题纸分给多个评卷人进行评分,速度将显著提高;假设有 1000 张试卷,由十个评卷人进行评分所需要的时间将远远少于一个评卷人的用时(很可能只需要十分之一的时间)。“天空实验室”(Skylab)空间站坠落后的零部件搜寻工作是另一个有关数据分解概念的代表性示例。相关部门指派了不同的搜寻人员来做这件事,将搜寻地段划分为多个区域。在典型应用中,通过对数据进行分区并针对每个分区应用相同的搜索,能够更加快速地在海量数据(如一张关于街道上熙熙攘攘的人群的照片)中找到特定的数据模式(如眼睛颜色)。

并行性和正确性
虽然完全并行化的代码能够显著提升性能,但如果它提供的结果不正确,很可能会造成最终行为与算法和代码初衷不符。开发人员必须选择能够出色地实施并行化或者可容忍错误结果(在某些情形下可以接受)的算法。部分极具挑战性的情形包括并行化随机数生成或序列算法。此外,为了确保获得正确的结果,必须特别关注组合的四舍五入和并行化浮点计算。如欲阅读有关这些话题的文章,请访问英特尔® 软件网络。

并行化性能:加速幅度和阿姆达尔定律
通过对应用进行并行化处理可实现多大程度的加速?对于希望缩短周转时间(turn-around time)的使用情形,阿姆达尔定律是一款出色的工具,能够帮助确定可能实现的加速幅度。根据阿姆达尔定律的描述,面对具体的计算问题,能够将解决问题的执行时间缩短多少取决于您即将实施并行化的代码中串行部分所占的比例,以及可用的计算资源。

在阿姆达尔定律中:

P = 代码中并行部分所占的比例(如 0.3 或 0.7)
N = 并行部分可用的处理器数量
(1 – P) 代表了代码中串行部分的比例

显而易见,随着 N 无限扩大,P/N 将越来越接近 0,而且计算结果与串行部分的大小密切相关。

意义
为了实现较大的速度提升,您需要将代码的串行执行时间缩至最短,同时较大限度地拓展并行机会。这意味着,您不但要对算法中显而易见的部分进行并行处理,如有可能还需要重新设计串行算法,采用并行方式更出色地表述算法。

请记住一点,虽然并行代码在大多数情况下都能实现出色的性能,但并不一定始终都是较佳的解决方案。在某些情形下,与相同算法的并行版本相比,经过良好优化的串行代码能够实现更出色的性能。

我们刚刚讨论了基本的并行化概念,下面就让我们看一下实施并行化的不同方法,共同探讨如何寻找潜在的并行化机会。

并行化方法
对应用实施并行化的方法有很多种。具体选择哪种方法取决于多个变量,其中包括:

您运行代码的计算平台。您所使用的是完全分布式计算平台如独立机器的大型集群,32、64 或 128 内核对称多处理器系统,还是四核工作站?
您对并行化精细度的要求。这往往反映了您的计算平台的特性,与每条线程处理的工作量类似。
您希望解决的问题。您要实施并行化的对象是嵌入式火箭控制系统还是在超级计算机上运行的药物建模应用?
性能目标。您是希望提高吞吐率还是希望缩短周转时间?
 
下文介绍了几种最常见的并行编码方法。

MPI
消息传递接口(MPI)是用于高性能计算(HPC)和高度分布式处理系统的一种分布式、多线程模型。MPI API 使用表述清晰的消息在整个计算系统内传递信息。每个节点独立运行,可创建并响应 MPI 消息。

MPI 适用于精细度较低的并行化处理。适合采用 MPI 的计算平台示例包括由通过高性能通信网络相互连接的独立式服务器所组成的集群,例如美国国立卫生研究院* 的 LoBoS*(Lots of Boxes on Shelves)。

在采用 MPI 的分布式计算平台中,各节点间的通信会影响整体系统性能,因为网络必须在节点之间传递消息和数据。此外,内存架构和分区对性能的影响也很大,因为某个节点所需要的数据可能存储于另一个节点之上。因此,若想实现最出色的系统性能,进行整体程序设计时,应将数据模型和面向通信的优化特性全部考虑在内。

显式线程化
显式线程化将使用 POSIX 线程(Pthreads)、Windows* 线程或其它线程家族在代码中显式地创建线程。线程化过程完全在程序员的控制之下,代码能够彻底按照开发人员的需求实现线程化。显式线程化会生成复杂的代码,不过它能够在创建、使用和销毁线程的方式与时间方面为开发人员带来更多的控制权。显式线程化同时适用于精细度较低和较高的并行化实施。此外,它还能够与其它形式相结合,虽然这会为开发人员带来更多的挑战,增加应用的整体复杂性。

编译器指导的并行化
编译器指导的并行化(即自动并行化)可利用 API 如 OpenMP* 或英特尔® 线程构建模块显示代码内的线程化机会。兼容的编译器在编译时会自动创建必要的线程。对开发人员来说,线程化流程的复杂性降低,但程序员对线程实施方式的控制力度却有所减弱。请注意,编译器指导的并行化非常灵活,能够轻松地修改现有串行代码。作为一名工程师,我认为编译器指导的并行化是迅速构建并行代码原型的较佳方式。因此,本文将着重介绍如何寻找最适合使用这种并行化方式的机会。

并行库
英特尔可提供多个能够在英特尔® 处理器上实现并行优化的库。这些库可针对特定应用域执行复杂的并行化算法:

英特尔® 数学核心函数库(英特尔® MKL)是一个包含经过高度优化和广泛线程化的数学例程(专为需要极致性能的科学、工程及金融等领域的应用而设计)的函数库。核心数学函数包括 BLAS、LAPACK、ScalaPACK1(ScaLAPACK 不适合 Mac OS* X 操作环境)、稀疏矩阵解算器、快速傅立叶转换、矢量数学及其它函数。

它可为当前及下一代英特尔® 处理器提供性能优化特性,能够更出色地与Microsoft Visual Studio*、Eclipse* 和 XCode* 相集成。英特尔® MKL 支持完全集成英特尔兼容性 OpenMP* 运行时库,以实现更出色的 Windows*/Linux* 跨平台兼容性。

英特尔® 集成性能基元(英特尔® IPP)是一款面向多核的扩展函数库,其中包含众多针对多媒体数据处理和通信应用实现高度优化的软件函数。英特尔® IPP 提供了数千种优化函数,涵盖了大部分常用的基本算法。

英特尔® 线程构建模块(英特尔® TBB)是一个屡获殊荣的 C++ 模板库,能够为任务提取线程,以创建可靠、便携、可扩充的并行应用。正如 C++ 标准模板库(STL)能够扩展核心语言一样,英特尔® TBB 可为 C++ 用户提供更高级别的提取能力,以支持并行。为了部署英特尔® TBB,开发人员使用熟悉的 C++ 模板和编码类型,将低级线程详情留给函数库。它还便于在架构与操作系统之间移动。通过英特尔® TBB,开发人员获得了加快编程速度、扩充性能和更轻松地保存代码等优势。

下一步--寻找机会
我们已经讨论了并行化的基本概念和一些并行化实施方法,接下来让我们共同思考最复杂的问题:如何寻找并行处理机会?在下一部分内容中,我们将分析如何寻找适合实施并行化的对象,以及如何克服常见的并行化挑战。

寻找并行化候选对象

剖析应用以寻找性能瓶颈
在您的代码中,可能有很多地方能够实施并行处理,但所付出的努力究竟能否带来令人满意的性能提升呢?这很难判断,除非您仔细分析代码,了解处理器将时间用在了什么地方。通过使用性能分析器如英特尔® 性能瓶颈分析器(英特尔® PBA)剖析代码,您将能够找到性能瓶颈的所在。然后,您便可以确定需要对哪些地方进行优化,以及是否存在实施并行化或优化算法的机会。

方法
很多白皮书和文章都介绍了在现有串行代码中寻找并行化对象的不同方法。实际上,作为一名工程师,我自己也经常需要寻找这些机会,结果发现最简单的方法就是较好的方法。寻找热代码。热代码指所占用的处理器时间明显多于其它区段的应用区段。这通常出现在循环体中,但并非总是如此。

这种方法涉及使用特定类型的取样工具集如英特尔® VTune™ Amplifier、英特尔® 性能调试实用程序,或英特尔® 性能瓶颈分析器等查找热代码。

若想收集该数据,您必须拥有代表性工作负载,能够以切合实际的方式在应用上运行。如欲详细了解如何创建合适的工作负载,请参阅以下文章: (/zh-cn/articles/the-three-stages-of-preparation-for-optimizing-parallel-software/)。

上文提到的工具集配有详细的教程,可帮助您在获得合适的工作负载后执行基本分析(请参见下方的“参考资料”部分,查看这些工具的链接)。

待适合的工作负载和数据收集工具集准备就绪后,寻找并行化对象的过程就非常简单了,只要查找最热的代码即可。图 1 为英特尔® PBA 提供的示例工作负载代码执行报告。
图 1. 英特尔® PBA 工具集提供的用于识别热代码区段的流分解图。

找到自己的热代码后,您需要根据它占用的时间(或周期)和与它相关的功能对它进行分类。再强调一次,较佳的并行化对象通常位于最热的代码中。一项通用实践是,从前五个最热的代码区段着手。秉承易于开发的宗旨,更轻松的做法是将这些热代码区段与对应的母函数相关联。请参见图 2。
图 2. 英特尔® PBA 工具集提供的用于识别热函数的流分解图。

确定候选对象后,下一步便是判断它们能否实现并行化。

候选对象是否支持并行处理?
在现有串行代码中表达并行性的方法多种多样。然而,从本质上讲,迭代操作比其它类型的操作更适合进行并行化。此外,正如本文所强调的,实施多线程的方法不计其数。不过,出于文章简短性方面的考虑,本部分的示例将只着重讨论 OpenMP 由编译器指导的编译指示的使用情况。如上文所述,OpenMP 小巧、便携,可轻松地以随机方式集成至现有串行代码中。

循环(for、do、while 等)
毫无疑问,循环是向现有串行代码中添加并行性的较佳选择。这主要是因为循环经过预先处置,可轻松地应用“worksharing”结构。Worksharing 指将存在的大问题拆分为多个并行执行线程,并将任务的不同部分分配给这些线程。在循环中,这是常见的数据分解示例(参见上文)。

简单的 for 循环
分析下方的循环可否经过并行处理:

1for(i = 0; i < N; i++)
2c[i] = a[i] + b[i];
 
要判断循环是否适合执行并行化,首先应回答几个关键问题。其中最重要的是:

当前的迭代是否独立于之前的迭代?

换句话说,当前的迭代不会依赖任何从之前迭代中获得的值。在上方的示例中,除指定迭代之外,任何迭代都没有引用 c[i] 和。所以说,这里不存在可能加大代码并行化难度的循环依赖性。

使用 OpenMP 进行以下更改,便可实现循环的并行化:
1#pragma omp parallel for
2for(i = 0; i < N; i++)
3c[i] = a[i] + b[i];
omp parallel for 指令要求编译器在一组遇到该 worksharing 结构的线程之间分配循环迭代。

假设 N=12,该并行区域所处的线程组中包括 4 条线程,上方的编译指示加法和兼容的编译器将生成以下行为:

使用循环迭代数 N 除以线程数 4,获得每条线程的工作量是3。
为每条线程分派不同的迭代集。如此一来,一条线程被指派为处理迭代 1-3,另一条线程则负责处理迭代 4-6。
在并行区域的末端,线程重新聚合,此时,整个并行区域中只存在一条线程。

我们所做的简单更改将能够显著缩短执行时间。该循环的并行执行时间是串行执行时间的四分之一左右--处理速度约为原来的四倍左右。即使您不熟悉 OpenMP,也很容易看出,基于编译指示的并行化非常容易集成至现有串行代码中,具备巨大的潜在优势。

更复杂的循环
下面,让我们来看一个更复杂的循环示例,该循环为并行化操作带来了一些挑战,阅读下文,了解如何克服这些挑战。该循环是一个数值积分示例,目标是计算值 Pi。在这里,我们将使用典型的基本积分代码。

代码将计算函数从 0 到 1 的积分。.您们当中有些人可能能够利用微积分学知识看出该积分求的是什么值。如果您不具备相关的数学知识,我可以告诉您,该从 0 到 1 的积分计算的是 Pi 的近似值。

为了估算曲线下方的面积(估算积分),我们将累加大量小面积(many = num_steps)。每个面积的宽度为“step”,即 num_steps 的倒数。然后,将这些小面积加在一起,得出到这一刻我们通过计算出的所有面积的总和。

代码如下:
01static long num_steps=100000;
02double step, pi;
03void main(){
04    int I;

鲜花

握手

雷人

路过

鸡蛋

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

热门文章

     

    GMT+8, 2020-1-21 19:13 , Processed in 0.140601 second(s), 23 queries .