雷利桂　郭景娟

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

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

中圖分類號：TP3文獻標識碼：A文章編號：1671-7597（2009）01103047-01

一、引言

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

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

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

（一）eSkel簡介

eSkel(the Edinburgh Skeleton Library)是由愛丁堡大學信息學院開發(fā)的一種結(jié)構(gòu)化的并行程序設計庫，它為有經(jīng)驗的C/MPI程序員提供很多并行結(jié)構(gòu)框架。eSkel的第一個版本eSkel1是由Murray Cole在2002年開發(fā)的。它是利用設計模式思想，即并行計算的重復出現(xiàn)的模式和迭代可以被抽象為框架或模板，并且可以把簡單的操作作為參數(shù)。因此，提高了抽象的水平，并行程序可以用此框架或模板來得到，從而更加方便。它的目的是最大化由它的部件模式所提供的概念的靈活性，并且促進模式組合的動態(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)用了模式的程序可能會帶來很多意想不到的負擔，所以必須對模式程序的最優(yōu)機制進行研究。如：并行模式accumulate是由于運用模式開發(fā)有效的并行程序和使用模式管理不規(guī)則的數(shù)據(jù)都不是容易而提出的，這模式不僅有效地描述了并行計算中的數(shù)據(jù)獨立性而且為管理呈現(xiàn)了好多的代數(shù)性質(zhì)。其他的關(guān)于最優(yōu)化機制的模式正在實現(xiàn)當中，且實現(xiàn)后將添加到模式庫中。此系統(tǒng)的目的就是幫助程序員更容易開發(fā)有效的并行程序。

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

（三）P3L簡介

P3L(Pisa Parallel Programming Language)是由意大利的比薩大學計算機科學學院開發(fā)的一種結(jié)構(gòu)化的并行程序設計語言，它是基于骨架或模板的。P3L是建立在C語言的頂部，串行部分用C來實現(xiàn)（但也可擴展為用C++、Java、Fortran、HPF等來實現(xiàn)串行部分），并行部分就通過選用骨架或模板來實現(xiàn)。目前已開發(fā)的骨架模型(Skeletons model)包括：任務并行（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)的骨架，從而無需處理并行細節(jié)部分。

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

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

三、比較和總結(jié)

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

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

參考文獻：

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

作者簡介：

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