松耦合多处理机在大数据处理中的应用

唐俊奇

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

0 引言

随着社会的不断发展，人们需要处理的数据量在不断增大，己由TB级升至PB级，并且还在不断地增长，在某些情况下甚至还达到了EB级，其增长速度大大超过了摩尔定律的增长速度。由于数据量的快速增长，通常所用的并行数据库的规模也必须随之增大，所以导致了企业成本的快速增长。为降低成本，不少企业用户已将应用由原来高端的服务器转向了由中低端硬件构成的机群平台［1，2］。这种机群平台也称为松耦合多处理机系统，面对所要处理的巨大数据量，使用工作池技术可以使松耦合多处理机系统(尤其是异构机群平台)能及时给系统中处于空闲状态的处理器分派工作任务，这大大地提高了数据的处理速度。工作池可分为集中式工作池和分散式工作池两种。

1 集中式工作池

集中式工作池［3，4］是指:在松耦合多处理机系统中，当有某个处理器(机器)处于空闲状态时就立即向其分派工作任务，工作池中包含所有要完成的任务集合(任务池)。

1.1 集中式工作池的工作过程

在松耦合多处理机系统中，一旦某个处理器处于空闲状态，主处理器会立即向其分派工作任务。工作池中拥有所要完成的任务集(池)，工作池中的每个任务由主处理器分发给各个从处理器，每个从处理器完成一个任务后，它们都会向主处理器请求另一个任务。工作池技术虽然可用于那些任务很不相同、大小不同的问题，但最好优先分配较大或最复杂的任务。因为如果在计算过程中，较大的任务分配较晚时，那些己经完成小任务的从处理器就会一直等待持有较大或最复杂任务的处理器完成任务。

在各个处理器执行任务期间，如果出现任务数经常发生变化时，工作池技术就会充分发挥其优越性。在分析和处理大数据的搜索算法中，往往在一个任务的执行过程中还可能产生一些新的任务。在这种情况下，可采用一个队列存放当前等待的任务(见图1)。如果所有任务大小相同且同等重要，则可以用简单的先进先出队列;如果某些任务比其他任务更重要(如期望更快地得到解)，就优先把这些任务送到从处理器中，而其他的一些信息，如当前的最佳解等，可以用主处理器加以保存。

集中式工作池最突出的优点是:主处理器很容易识别计算会何时终止。对一个计算，如果其中的任务是从任务队列中获取的，则当满足下面两项时计算终止:

1)任务队列为空;

2)每个处理器己经请求了另一个任务，而又没有任何新的任务产生。

图1 集中式工作池Fig.1 Centralized work pool

1.2 集中式工作池算法

如图1所示，在集中式工作池中，主处理器负责运行主调度程序，循环检测从处理器的当前状态，当从处理器空闲时，主调度程序就按一定的策略给从处理器分配任务，其算法(pascal语言)的形式化描述如下:

集中式工作池的从处理器负责接收主处理器发送的消息并进行相应的处理工作，其算法(pascal语言)的形式化描述如下:

1.3 减少通信时间的集中式工作池算法

如果机群平台(松耦合多处理机系统)中各个节点的存贮器容量足够大，即可在系统中安排一台主机，专门备份系统中每个节点工作池中要完成的所有任务(任务本地化)。这样主处理器向从处理器发送任务时只需发送所要处理的任务号，可有效减少通信量，因为从处理器i发送运行子任务taskid所需的数据会产生较大的通信时间开销。其算法(pascal语言)的形式化描述如下:

集中式工作池的从处理器负责接收主处理器发送的消息并进行相应的工作，其算法(pascal语言)的形式化描述如下:

1.4 仿真实验结果

笔者分别采用1个处理器、5个处理器和6个处理器对一个较大的数据进行仿真实验，得到结果如表1所示。

表1 仿真运行结果(不包含通信时间开销)Tab.1 Simulation run results(not including communication time)

单个处理器串行计算时间T1=1.109 ms。加速度:sp=T1/Tp。效率:Ep=sp/P。其中T1为串行算法在单个处理器上的执行时间，TP表示并行算法在P个处理器上的执行时间。计算结果如表2所示。

由表2中的加速度可知，随着处理器的增多，运行速度得到了较大的提高。

表2 计算结果Tab.2 Calculation result

在现实中有下面的一种情况:机群平台(松耦合多处理机系统)中的各个节点的存贮器容量不足于备份工作池中要完成的所有任务。这种情况下，加速度计算必须考虑通信时间，则加速度就相应小一些。如果在计算中有大任务存在且分配较晚，则系统中就会出现己经完成了小任务的从处理器一直空闲，直到分配到大任务的处理器完成任务。从而造成资源浪费，而且集中式工作池较大的缺点是:主处理器一次只能发送一个任务，在初始任务发送后，它只能一次一个地响应新的任务请求，因此，当很多从处理器同时请求时就存在着潜在的瓶颈［5，6］。采用分布式工作池可以克服该瓶颈，从而提高机群(松耦合多处理机系统)的处理效率。

2 分布式工作池

在任务粒度比较细和从处理器较多的情况下，如果能把工作池分布在多个地点以实现分布式动态负载平衡［7，8］，会使系统的功能更加强大。如图2所示，把工作池分布在多个地点称为分布式工作池。

图2 分布式工作池Fig.2 Distributed work pool

2.1 分布式工作池的工作过程

在分布式工作池中，主处理器将初始的工作池分成几部分，并且将每部分发送给其中的一个小型主处理器“(M0到Mn－1)”。每个小型主处理器控制一组从处理器。在任务执行过程中，小型的主处理器会找到各自的本地最优解，然后再将其返回给主处理器，主处理器再从众多小型的主处理器送来的解中选出最优解，从而有效地实现了问题的优化［9-11］。由此可见，可通过几个层次的分解扩展这种方法。把从处理器放在叶结点上，采取内部结点分割工作的方法，就可形成一棵树。这种基本方法是将一个任务分成若干个相等的子任务。对于一棵二叉树，可在树的每层处理器把任务的一半送给一棵子树［12，13］，而把另一半送给另一棵子树。这样就能有效地克服集中式工作池中较复杂的任务在计算中因大任务分配较晚，造成完成小任务的从处理器空闲的缺点。

2.2 分布式工作池算法

在分布式工作池中，主处理器负责运行主调度程序循环检测小主处理器的当前状态，当小主处理器空闲时主调度程序按一定的策略给从处理器分配任务，小主处理器又负责循环检测从处理器的当前状态，当从处理器空闲时，小主处理器也按一定的策略给从处理器分配任务，其算法(pascal语言)的形式化描述如下:

2.3 通信和数据计算间的时间共享算法

由于分布式工作池中存在主处理器、小主处理器和从处理器，虽然事先也可给系统中的各节点进行备份主工作池中拥有要完成的所有任务，但在随后的数据通信处理中很难进行合理任务分配，甚至还有可能发生冲突。为提高加速度和处理效果，如果在通信过程中数据计算也同时进行，则可有效提高系统的处理速度。以下为实现通信和计算之间的时间共享的算法(pascal语言)的形式化描述如下:

2.4 仿真实验结果

笔者仍然采用1个处理器、5个处理器和6个处理器对一个较大的数据进行仿真实验，得到结果如表3所示，它将为表4中的计算提供数据。

表3 仿真运行结果(通信和数据计算之间的时间共享)Tab.3 Simulation run results(time used by communication and calculating)

单个处理器串行计算时间T1=1.109 ms。加速度计算:sp=T1/Tp。效率计算:Ep=sp/P。计算结果如表4所示。

表4 计算结果Tab.4 Calculation result

对照表4和表2可以看出:在计算中有大任务存在且分配较晚的情况下，应该采用分布工作池方式。若采用集中工作池方式，则系统中己经完成了小任务的从处理器会一直空闲，直到分配到大任务的处理器完成任务，造成资源浪费(加速度和效率都下降)，因此，集中式工作池技术最好用在任务大小相近和复杂程度较为均匀的松耦合多处理机系统中。

3 结语

综上所述，通过仿真实验，笔者成功地在松耦合多处理机系统中利用工作池技术及时给系统中处于空闲状态的处理器分派工作任务，实现了系统中各机器充分均衡协调地工作，大大地提高了数据的处理效率，达到预期的效果。

［1］王珊，王会举，覃雄派.架构大数据:挑战、现状与展望［J］.计算机学报，2011，34(10):1741-1752.WANG Shan，WANG Huiju，QIN Xiongpai.Architecting Big Data:Challenges，Studies and Forecasts［J］.Chinese Journal of Computers，2011，34(10):1741-1752.

［2］孟小峰，慈祥.大数据管理:概念、技术与挑战［J］.计算机研究与发展，2013，50(1):146-169.MENG Xiaofeng，CI Xiang.Big Data Management:Concepts，Techniques and Challenges［J］.Journal of Computer Research and Development，2013，50(1):146-169.

［3］唐俊奇.多处理机工作池方式负载平衡技术在机器人的应用［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.

［4］李颖，张晓贤，孙佳慧.基于频繁模式半结构化数据的模式抽取［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.

［5］杨柳，刘铁英.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.

［6］董延华，李晓佳，张晔.基于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.

［7］刘辉，黄海生.分布式多处理机的并行模拟测试［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.

［8］靖常峰，刘仁义，刘南.大数据量遥感图像处理系统算法模块的设计及实现［J］.浙江大学学报:理学版，2005，32(4):471-474.JING Changfeng，LIU Renyi，LIU Nan.Design and Development of Algorithm Module for a Remote Sensing Image Processing System［J］.Journal of Zhejiang University:Sciences Edition，2005，32(4):471-474.

［9］CHRIS ANDERSON J，JAN LEHNARDT，NOAH SLATER.O'Reilly Media［M］.CouchDB:The Definitive Guide，2010.

［10］JOE LENNON.Beginning CouchDB［M］.New York:Springer-Verlag，2009.

［11］BRADLEY HOLT.Writing and Querying MapReduce Views in CouchDB［M］.Beijing:O'Reilly Media，2011.

［12］COUCHDB WIKI.Apache CouchDB ［EB/OL］.(2010-08-18).http://wiki.apache.org/couchdb/.

［13］BRADLEY HOLT.Scaling CouchDB［M］.Beijing:O'Reilly Media，2011.