雷利桂　郭景娟

[摘要]并行程序設(shè)計(jì)是并行計(jì)算的難點(diǎn)之一。而基于SKELETON的并行程序設(shè)計(jì)方法為程序員提供的是并行程序的框架，比使用并行庫(kù)（PVM和MPI）具有更高的抽象程度和通用性。簡(jiǎn)單地介紹目前國(guó)際上三種應(yīng)用此方法所開發(fā)的模型或項(xiàng)目以及我們所研究的DPAPD模型，并做出比較。

[關(guān)鍵詞]骨架 并行結(jié)構(gòu)骨架

中圖分類號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671-7597（2009）01103047-01

一、引言

并行程序設(shè)計(jì)是并行計(jì)算的兩大難題之一。20世紀(jì)90年代，國(guó)際上就開始使用基于模式的思想進(jìn)行并行程序開發(fā)，至今已發(fā)展出了多種方法和系統(tǒng)：如基于算法骨架的方法、基于設(shè)計(jì)典型的方法、基于并行結(jié)構(gòu)骨架的方法等；并分別對(duì)使用這三種方法所開發(fā)的模型或項(xiàng)目如基于結(jié)構(gòu)化的并行程序設(shè)計(jì)庫(kù)eSkel、關(guān)于算法模式的系統(tǒng)SkeTo Project和基于并行結(jié)構(gòu)骨架的方法研究的項(xiàng)目P3L以及我們正在研究的DPAPD模型進(jìn)行了簡(jiǎn)單的介紹。

二、四種基于Skeleton的并行程序設(shè)計(jì)方法的簡(jiǎn)介

目前對(duì)于Skeleton有許多不同的定義，但它的要義是并行計(jì)算和通信的模型，且這模型可以被打包為“框架、模板”等（即它的參數(shù)可以由其他的代碼來取代）。模型中的實(shí)現(xiàn)和分析部分可以共享，即模型中只有結(jié)構(gòu)或框架而沒有具體實(shí)現(xiàn)的細(xì)節(jié)部分。

（一）eSkel簡(jiǎn)介

eSkel(the Edinburgh Skeleton Library)是由愛丁堡大學(xué)信息學(xué)院開發(fā)的一種結(jié)構(gòu)化的并行程序設(shè)計(jì)庫(kù)，它為有經(jīng)驗(yàn)的C/MPI程序員提供很多并行結(jié)構(gòu)框架。eSkel的第一個(gè)版本eSkel1是由Murray Cole在2002年開發(fā)的。它是利用設(shè)計(jì)模式思想，即并行計(jì)算的重復(fù)出現(xiàn)的模式和迭代可以被抽象為框架或模板，并且可以把簡(jiǎn)單的操作作為參數(shù)。因此，提高了抽象的水平，并行程序可以用此框架或模板來得到，從而更加方便。它的目的是最大化由它的部件模式所提供的概念的靈活性，并且促進(jìn)模式組合的動(dòng)態(tài)選擇。

（二）SkeTo Project簡(jiǎn)介

SkeTo Project(Skeleton Libaray in Tokyo)是由日本東京科技研究所(JST)開發(fā)的一關(guān)于算法模式的系統(tǒng)。它是基于結(jié)構(gòu)化算法的，主要包含以下兩個(gè)方面：1.許多數(shù)據(jù)結(jié)構(gòu)的并行模式的實(shí)現(xiàn)，目前已經(jīng)實(shí)現(xiàn)的并行模式庫(kù)有：表(list)，樹(trees)，矩陣(matrices)，這些并行模式是用C++和MPI實(shí)現(xiàn)的；2.對(duì)模式程序的最優(yōu)機(jī)制，調(diào)用了模式的程序可能會(huì)帶來很多意想不到的負(fù)擔(dān)，所以必須對(duì)模式程序的最優(yōu)機(jī)制進(jìn)行研究。如：并行模式accumulate是由于運(yùn)用模式開發(fā)有效的并行程序和使用模式管理不規(guī)則的數(shù)據(jù)都不是容易而提出的，這模式不僅有效地描述了并行計(jì)算中的數(shù)據(jù)獨(dú)立性而且為管理呈現(xiàn)了好多的代數(shù)性質(zhì)。其他的關(guān)于最優(yōu)化機(jī)制的模式正在實(shí)現(xiàn)當(dāng)中，且實(shí)現(xiàn)后將添加到模式庫(kù)中。此系統(tǒng)的目的就是幫助程序員更容易開發(fā)有效的并行程序。

相對(duì)于以前的并行程序開發(fā)系統(tǒng)，SkeTo Project的優(yōu)勢(shì)主要體現(xiàn)它的擴(kuò)展性(Extensibility)上。這表現(xiàn)在，在此系統(tǒng)中，新的設(shè)計(jì)模式可以被定義，并且添加到系統(tǒng)的設(shè)計(jì)模式庫(kù)中。但同時(shí)，定義新的設(shè)計(jì)模式并將之添加到系統(tǒng)中這個(gè)功能并不完善，因此，在一定程度上限制了SkeTo的實(shí)用性。

（三）P3L簡(jiǎn)介

P3L(Pisa Parallel Programming Language)是由意大利的比薩大學(xué)計(jì)算機(jī)科學(xué)學(xué)院開發(fā)的一種結(jié)構(gòu)化的并行程序設(shè)計(jì)語言，它是基于骨架或模板的。P3L是建立在C語言的頂部，串行部分用C來實(shí)現(xiàn)（但也可擴(kuò)展為用C++、Java、Fortran、HPF等來實(shí)現(xiàn)串行部分），并行部分就通過選用骨架或模板來實(shí)現(xiàn)。目前已開發(fā)的骨架模型(Skeletons model)包括：任務(wù)并行（FARM和流水線PIPE）、數(shù)據(jù)并行(MAP、REDUCE、SCANR和COMP)、控制并行（迭代LOOP和SEQ）。它的第一個(gè)編譯器P31L是在1993/94年開發(fā)的，目前正在做的工作是：a：anacleto：產(chǎn)生C+MPI代碼的新的P3L-2編譯器，并且運(yùn)行在Linux和Fujitsu下；b：ocamlp3l：一種基于Ocaml擴(kuò)展的骨架。它比直接使用并行庫(kù)（PVM和MPI）的效率更高表現(xiàn)在：它的并行部分使用已實(shí)現(xiàn)的骨架，從而無需處理并行細(xì)節(jié)部分。

（四）DPAPD開發(fā)模型簡(jiǎn)介

在我們的前期研究中，我們提出了一種基于設(shè)計(jì)模式和泛型編程的并行程序開發(fā)模型DPAPD。此模型的結(jié)構(gòu)如圖1所示。系統(tǒng)結(jié)構(gòu)分為三層：抽象語言層、系統(tǒng)實(shí)現(xiàn)層和目標(biāo)語言層。在抽象語言層，我們借用江西師大的薛錦云教授提出的PAR方法中的APLA語言來描述泛型算法結(jié)構(gòu)庫(kù)和泛型并行結(jié)構(gòu)庫(kù)。這樣，程序員就可以直接使用該語言和模型中的設(shè)計(jì)模式庫(kù)來描述抽象的并行程序。在系統(tǒng)實(shí)現(xiàn)層，系統(tǒng)將實(shí)現(xiàn)四個(gè)主要模塊，設(shè)計(jì)模式庫(kù)（包括算法結(jié)構(gòu)庫(kù)和并行結(jié)構(gòu)庫(kù)），分析器（對(duì)抽象語言進(jìn)行分析，產(chǎn)生中間表示），優(yōu)化器（對(duì)中間程序進(jìn)行優(yōu)化），轉(zhuǎn)換器（將中間程序轉(zhuǎn)換成可運(yùn)行的目標(biāo)語言并行程序）。同樣的，在這層，我們也可借用江西師大的薛錦云教授提出的PAR方法中的系列轉(zhuǎn)換器，對(duì)此轉(zhuǎn)換器進(jìn)行相應(yīng)的擴(kuò)充即可實(shí)現(xiàn)。

三、比較和總結(jié)

本文討論了三種基于模式思想的并行程序開發(fā)方法：（1）基于結(jié)構(gòu)化的并行程序設(shè)計(jì)庫(kù)eSkel；（2）關(guān)于算法模式的系統(tǒng)SkeTo Project；（3）基于并行結(jié)構(gòu)骨架的方法研究的項(xiàng)目P3L等。這三種方法所采用的手段是通過將并行計(jì)算模式擴(kuò)充到順序語言環(huán)境中，以此來設(shè)計(jì)實(shí)現(xiàn)并行程序的開發(fā)環(huán)境（包括程序設(shè)計(jì)模型、語言、工具、及集成環(huán)境）。由于這類環(huán)境隱蔽了并行計(jì)算的底層實(shí)現(xiàn)細(xì)節(jié)，因此與低層次的并行程序設(shè)計(jì)環(huán)境相比具有更高的抽象程度。然而，對(duì)程序設(shè)計(jì)環(huán)境的研究并不能從根本上解決并行程序設(shè)計(jì)難的問題，因?yàn)椴⑿谐绦蛟O(shè)計(jì)困難的原因并不僅僅在于體系結(jié)構(gòu)的多樣性，還在于問題本身并行求解的困難。

我們正在研究的DPAPD模型不是傳統(tǒng)意義上的并行程序設(shè)計(jì)模型，而是一種支持整個(gè)并行程序開發(fā)過程的方法。因此，它不僅是作為一個(gè)并行程序設(shè)計(jì)的模型而提出的，更是作為一個(gè)并行算法設(shè)計(jì)的模型。而且，該模型將并行程序設(shè)計(jì)開發(fā)的兩個(gè)基本方面統(tǒng)一在一個(gè)抽象框架之下，為從問題規(guī)范出發(fā)，獲得并行程序提供了一種系統(tǒng)的方法。然而這一模型還有待進(jìn)一步的完善，包括足夠多的設(shè)計(jì)模式的開發(fā)和更多基于這一方法的模型的開發(fā)，這是我們進(jìn)一步的工作。

參考文獻(xiàn)：

[1]萬劍怡、孫永強(qiáng)、薛錦云，一種從Z規(guī)約到并行程序的精化方法，軟件學(xué)報(bào)，2002.

[2]K. Matsuzaki,Z. Hu,and M. Takeichi. Parallelization with tree skeletons. Technical Report METR 03-21,Mathematical Informatics,Graduate School of Information Science and Technology,University of Tokyo,2003.

[3]Z. Hu,H. Iwasaki,and M. Takeichi,An Accumulative Parallel Skeleton for All,Proc. 2002 European Symposium on Programming,Lecture Notes in Computer Science,Vol. 2305,pp.83-97,Springer-Verlag(2002).

[4]H.Kuchen and M.Cole，The Integration of Task and Data Parallel Skeletons，Proc.3rd International Workshop on Constructive Methods for Parallel Programming(CMPP2002)，pp.3-16(2002).

[5]http://homepages.inf.ed.ac.uk/mic/Skeletons/.

作者簡(jiǎn)介：

雷利桂，女，江西瑞昌，碩士研究生，研究方向?yàn)椴⑿杏?jì)算。