基于ＳＫＥＬＥＴＯＮ的并行程序設(shè)計方法的研究現(xiàn)狀

雷利桂　郭景娟

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

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

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

一、引言

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

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

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

（一）eSkel簡介

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

（二）SkeTo Project簡介

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

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

（三）P3L簡介

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

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

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

三、比較和總結(jié)

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

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

參考文獻(xiàn)：

[1]萬劍怡、孫永強、薛錦云，一種從Z規(guī)約到并行程序的精化方法，軟件學(xué)報，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/.

作者簡介：

雷利桂，女，江西瑞昌，碩士研究生，研究方向為并行計算。