评估多处理机系统计算速度的要素研究

唐俊奇

(湄洲湾职业技术学院 信息工程系, 福建 莆田 351254)

0 引 言

在现实工作中, 对多处理机系统计算速度的需求不断增长。例如在科学计算建模或模拟和工程问题的数值计算等领域需多处理系统具有更快的计算速度, 而要解决这两个领域的问题则经常需对庞大的数据进行若干次重复计算才能得到有效的结果[1-3]。多处理系统一定要在合理的时间内完成规定的工作任务。人们希望一个工程计算或模拟能在较短时间内完成。当一个系统很复杂时, 其必然要花费更多时间进行计算或模拟。有的应用计算的时效性很强(如天气预报), 若花费24 h以上的时间获取当地的精确的天气预报数据, 则这种工作就将变得毫无意义。为此笔者从计算进程数与进程间通信时间开销对系统速度的影响、 多处理机系统的加速系数、 多处理机系统开销对提高加速比的影响、 顺序问题的并行化获取最大加速比等因素出发, 给出了加速系数和实现过程的算法描述, 为优化多处理机系统提供有效方法。

1 计算进程数与进程间通信时间开销对系统速度的影响

对于不同类型的多处理机系统, 要通过并行计算机制以达到提高速度的目的, 系统必须具备能同时执行多个任务或进程的能力。可用粒度表示进程的大小, 在粗粒度中, 每个进程包含有很多顺序指令, 要执行这些顺序指令则需花费大量的时间; 在细粒度中, 一个进程里可能只有少数几条指令, 有的甚至可能只有一条指令; 中粒度介于粗粒度和细粒度之间属于中等程度。有时还可用粒度定义通信子或同步点之间的计算量大小。通常粒度增大, 进程数就会减少, 创建进程的时间相应就减少, 进程之间的通信时间也相应减少, 但同时可能会减少并发进程数和并行性, 因此二者之间必须进行合理的优化处理以达到最优状态[4,5]。

对以消息传递方式的多处理机系统, 尤其需要减少通讯时间开销, 因为系统中计算机之间的通信需花费大量时间, 而对于工作站则更是如此, 因为这时的通讯时延非常大。当将一个计算分割成若干个并行部分时, 在分割到一定程度后, 通信时间将占总的执行时间中的大部分。计算时间与通信时间比tcomp/tcomm(其中tcomp为计算时间;tcomm为通信时间)可作为粒度的衡量标准。多处理系统在保持足够并行性的同时, 增大tcomp/tcomm能大幅提高系统的性能。粒度与处理器数量有关。例如, 在区域分解中, 由一个处理器所使用的数据块大小将随计算和通信时间比增加而增加。对于一个固定问题的数据, 所使用的处理器实际数量将会减少。一般情况下, 都尽量把并行程序设计成可以改变粒度大小的形式, 即一种可拓展的程序。

2 加速系数与加速比对系统速度的影响

2.1 多处理机系统的加速系数

加速系数S(n)可作为衡量一个多处理机系统和一个单处理机系统相对性能的标准[6-8], 定义为

(1)

其中ts表示单处理机系统计算用时,tp表示多处理机系统计算用时。S(n)表示在使用多处理机系统执行计算后, 计算速度的增加情况。

为对并行求解和顺序求解进行比较, 使用运行在单处理机上最快的已知顺序算法, 而并行实现的基本算法可能(并且通常是)不尽相同。在做理论分析时, 也可用下式

S(n)=S1/Sn

(2)

计算加速系数[9]。其中S1为使用单个处理器所需的计算步数,Sn为使用n个处理器所需的并行计算步数。

假设一个并行排序算法需4Sn步, 而最好的顺序排序算法需SnlogSn(比较和交换排序)步, 则加速系数将是(1/4)logSn。

对于n个处理器, 其最大加速比为n(线性加速)。若并行算法可获得的加速比超过当前顺序算法的n倍, 则该并行算法可在单处理机上仿真, 可以确定原先的顺序算法不是优化的。当计算可被分成相等持续时间的进程, 且一个进程映射到一个处理器上时(且无开销)。就可获得最大的加速系数n, 即

(3)

图1 消息传递程序的时空图Fig.1 Spatio temporal graph of message passing program

当S(n)>n时, 出现了超线性加速情况, 通常这是由于使用了一个次优化顺序算法或是某些有利于并行构造的独特体系结构而造成的, 超线性加速常见的一个原因是由于在多处理机系统中有额外的存储器(即紧耦合多处理机系统)。例如, 假设多处理机系统中每个处理器所含有的主存储器与单处理机系统所拥有主储器容量相同, 由于在多处理机系统中的总的主存储器容量大于在单处理机系统中的主存储器容量, 因此在任何时刻它总能保存更多的求解问题数据, 这会减少对工作速度相对较慢的硬盘存储器的访问。超线性加速比也可在搜索算法中应用。

消息传递程序的时空图如图1所示。显然不能苛求所有的计算都能分成并发进程, 因为有些计算必须对其串行求解。在某个时间段(比如： 在初始化阶段或是在并发进程被创建前的一段时间)内, 仅只有单个处理器在做有效的计算工作, 而在上述时间段外的其余计算中, 剩余的处理器将运行这些进程。可借助能显示时空图的可视化工具观察并行程序, 在含有4个处理器的多处理机系统中, 若每个处理器上运行一个进程, 则这时消息传递的时空图可能从一个进程开始, 之后其他进程开始执行并将消息送回, 由图1可见, 总有一些时间段, 此时处理器处于闲置状态, 并等待发送其消息。

2.2 多处理机系统开销对提高加速比的影响

多处理机在现实工作中, 经常出现以下几个因素从而限制了系统加速[10]。

1) 系统中仍有少部分处理器未完成当前有用的工作, 从而使系统中的其他处理器处于空闲状态。这里包括只能进行串行工作的计算部分, 在此时只有一个处理器处于活动状态。

2) 在并行计算过程中出现的诸如对常数重新进行局部计算等(这些在顺序计算中是不会出现的)的额外计算。

3) 在多处理机系统中因发送消息所需的通信时间。

2.3 顺序问题的并行化获取最大加速比

图2 顺序问题的并行化Fig.2 Parallelization of sequential problems

假设在一个程序中, 程序的某些部分只能在单处理机上执行, 则整个多处理机系统的最理想情况是所有可用处理器在余下的时间内同时运行[11]。设不能被分解成并行任务的计算部分所占的比例为f, 并且假设把计算分为若干个并发部分的过程无需时间开销, 则如图2所示采用n个处理器完成本计算所需的时间为fts+(1-f)ts/n。图2描述的多处理机系统在计算开始时是一个串行计算部分, 但并行部分可分布在整个计算中[12], 因此加速系数为

(4)

图3给出了S(n)相对于处理器数以及S(n)相对于f的变化关系。由图3可见, 该多处理机系统的计算速度得到了一定的改进, 但若要使多处理系统的速度有更显著的增长就必须使能由并发进程执行的计算部分成为整个计算的主要部分。即使使用了无限多个处理器, 但该多处理机系统的最大加速比仍然被限制在1/f, 即

(5)

a 加速比与处理器数的关系 b 加速比与串行部分的关系图3 S(n)相对于处理器数以及S(n)相对于f的变化关系Fig.3 The relationship between speedup and number of processors and the relationship between speedup and serial part

由图3可见, 在串行计算越少时, 处理器的数量越多则计算速度就越快, 某些情况下, 速度的改进可达到几个数量级。

2.4 多处理机系统的工作效率

多处理机系统的效率E可表示为

(6)

其中ts为使用单个处理器的执行时间,tp为使用n个处理器的执行时间,n为处理器个数。也可写成

(7)

其中E是以百分比形式表示。效率给定了处理器用于计算的时间比例。若E=50%, 则多处理机系统中的处理器平均只有一半的时间是用于计算的。若要获取100%的最大效率则仅当所有处理器在所有时间都用于计算时才会出现, 此时的加速比系数S(n)将为n。

3 多处理机系统的可扩展性

可扩展性(Scalability)是表示一种允许系统规模增大的硬件设计, 这样可获得更高的性能, 这种可扩展性描述为体系结构可扩展性和硬件扩展性。可扩展性也可用于指明一个并行算法能容纳更多的数据项而只需增加少量和有限的计算步数, 这种可扩展性描述为算法的可扩展性。

笔者希望所有多处理机系统是体系结构可扩展的(制造厂商以这种方式将他们的系统推向市场), 但这将严重依赖于系统的设计。通常将更多的处理器加入到系统中时, 必须同时扩展互连网络, 这种扩展性将导致更大的通信延迟和更多的系统任务争用CPU资源, 从而使系统的效率E减小。

组合的体系结构/算法可扩展性表明对于特定的体系结构和算法而言, 随系统规模的增大, 它可容纳更大规模的求解问题。增大系统规模显然要增加处理器的数量。以算法中要处理的数据元素总数作为衡量规模的标准, 但若使求解问题规模扩大一倍, 并不一定会使计算步数也增大一倍, 这将依赖于要求解的问题。例如, 将两个矩阵相加会有这样的结果, 但将两个矩阵相乘就不会遵从这一规律, 因为扩展的矩阵相乘将使计算步数增为4倍。因此, 扩大不同的求解问题意味着会有不同的计算要求。问题规模另一种定义是使问题规模与最佳顺序算法中所需的基本步数等同起来。当然, 使用这种定义时, 如果增加了数据点的数目, 将增大问题的规模。

4 结 语

综上所述, 影响多处理机系统计算速度的因素有许多, 只有充分了解影响多处理机系统计算速度的几大要素, 综合考虑这些要素对系统性能的影响才能最大可能地优化多处理机系统, 笔者给出了加速系数和实现过程的算法描述, 以满足现实的需求。

参考文献：

[1]杨柳, 刘铁英. GPU架构下的并行计算 [J]. 吉林大学学报： 信息科学版, 2012, 30(6): 629-632.

YANG Liu, LIU Tieying. GPU Architecture of Parallel Computing [J]. Journal of Jilin University： Information Science Edition, 2012, 30(6): 629-632.

[2]董延华, 李晓佳, 张晔. 基于MPICH并行计算系统安全通信策略研究 [J]. 吉林大学学报： 信息科学版, 2011, 29(5)： 481-483.

DONG Yanhua, LI Xiaojia, ZHANG Ye. Research on Security Telecommunication of MPICH Parallel Computing System [J]. Journal of Jilin University： Information Science Edition, 2011, 29(5)： 481-483.

[3]刘辉, 黄海生. 分布式多处理机的并行模拟测试 [J]. 上海电力学院学报, 2012, 28(5): 485-489.

LIU Hui, HUANG Haisheng. The Parallel Simulation Test in Distributed Multiprocessors [J]. Journal of Shanghai University of Electric, 2012, 28(5): 485-489.

[4]张庆华, 韩吉韬. 振动信号连续采集实时分析的实现方法 [J]. 测控技术, 2003, 20(3): 20-23.

ZHANG Qinghua, HAN Jitao. A Continuous Acquisition and Real-Time Analysis Method [J]. Measurement & Control Technology, 2003, 20(3): 20-23.

[5]张燕燕, 洪龙. Windows环境下FFT多核并行算法的设计实现 [J]. 计算机技术与发展, 2010, 16(9): 74-82.

ZHANG Yanyan, HONG Long. Design and Implementation of FFT Parallel Algorithm with Multi-Core Techniques in Windows Environment [J]. Computer Technology and Development, 2010, 16(9): 74-82.

[6]杨建军, 刘雄. 基于Unix的负载均衡集群方案设计 [J]. 计算机工程与设计, 2005, 26(7): 1897-1899.

YANG Jianjun, LIU Xiong. Load Balance Clustering Solution Based on Unix [J]. Computer Engineering and Design, 2005, 26(7): 1897-1899.

[7]张庆华, 吴印, 程国全, 等. 基于Windows数据连续采集实时分析的实现及应用 [J]. 南京理工大学学报: 自然科学版, 2004, 28(3): 281-285.

ZHANG Qinghua, WU Yin, CHENG Guoquan, et al. A Continuous Acquisition and Real-Time Analysis Method Based on Windows System [J]. Journal of Nanjing University of Science and Technology: Natural Science, 2004, 28(3): 281-285.

[8]唐俊奇. 多处理机工作池方式负载平衡技术在机器人的应用 [J]. 计算机系统应用, 2008, 17(11): 82-86.

TANG Junqi. Work Pool Load Balancing Technology of Multiprocessor in the Application of Robots [J]. Computer Systems & Applications, 2008, 17(11): 82-86.

[9]李颖, 张晓贤, 孙佳慧. 基于频繁模式半结构化数据的模式抽取 [J]. 吉林大学学报： 信息科学版, 2012, 30(5)： 540-543.

LI Ying, ZHANG Xiaoxian, SUN Jiahui. Semi-Structured Data Model Extraction Based on Frequent Patterns [J]. Journal of Jilin University： Information Science Edition, 2012, 30(5)： 540-543.

[10]BRADLEY HOLT. Writing and Querying MapReduce Views in CouchDB [M]. Beijing： O’Reilly Media, 2011.

[11]唐俊奇. 多处理机系统中曲面轮廓图像处理的并行化研究 [J]. 西南大学学报: 自然科学版, 2014, 36(2)： 156-163.

TANG Junqi. Parallelization Study of Curved Surface Contour Image Processing in a Multi-Processor System [J]. Journal of Southwest University: Natural Science, 2014, 36(2)： 156-163.

[12]唐俊奇. 松耦合多处理机在大数据处理中的应用 [J]. 吉林大学学报: 信息科学版, 2014, 32(2)： 205-210.

TANG Junqi. Application of Loosely Coupled Multiprocessor in Data Processing [J]. Journal of Jilin University: Information Science Edition, 2014, 32(2)： 205-210.