论文部分内容阅读
[摘要]并行程序设计是并行计算的难点之一。而基于SKELETON的并行程序设计方法为程序员提供的是并行程序的框架，比使用并行库（PVM和MPI）具有更高的抽象程度和通用性。简单地介绍目前国际上三种应用此方法所开发的模型或项目以及我们所研究的DPAPD模型，并做出比较。
[关键词]骨架 并行结构骨架
中图分类号：TP3文献标识码：A文章编号：1671-7597（2009）01103047-01
一、引言
并行程序设计是并行计算的两大难题之一。20世纪90年代，国际上就开始使用基于模式的思想进行并行程序开发，至今已发展出了多种方法和系统：如基于算法骨架的方法、基于设计典型的方法、基于并行结构骨架的方法等；并分别对使用这三种方法所开发的模型或项目如基于结构化的并行程序设计库eSkel、关于算法模式的系统SkeTo Project和基于并行结构骨架的方法研究的项目P3L以及我们正在研究的DPAPD模型进行了简单的介绍。
二、四种基于Skeleton的并行程序设计方法的简介
目前对于Skeleton有许多不同的定义，但它的要义是并行计算和通信的模型，且这模型可以被打包为“框架、模板”等（即它的参数可以由其他的代码来取代）。模型中的实现和分析部分可以共享，即模型中只有结构或框架而没有具体实现的细节部分。
（一）eSkel简介
eSkel(the Edinburgh Skeleton Library)是由爱丁堡大学信息学院开发的一种结构化的并行程序设计库，它为有经验的C/MPI程序员提供很多并行结构框架。eSkel的第一个版本eSkel1是由Murray Cole在2002年开发的。它是利用设计模式思想，即并行计算的重复出现的模式和迭代可以被抽象为框架或模板，并且可以把简单的操作作为参数。因此，提高了抽象的水平，并行程序可以用此框架或模板来得到，从而更加方便。它的目的是最大化由它的部件模式所提供的概念的灵活性，并且促进模式组合的动态选择。
（二）SkeTo Project简介
SkeTo Project(Skeleton Libaray in Tokyo)是由日本东京科技研究所(JST)开发的一关于算法模式的系统。它是基于结构化算法的，主要包含以下两个方面：1.许多数据结构的并行模式的实现，目前已经实现的并行模式库有：表(list)，树(trees)，矩阵(matrices)，这些并行模式是用C++和MPI实现的；2.对模式程序的最优机制，调用了模式的程序可能会带来很多意想不到的负担，所以必须对模式程序的最优机制进行研究。如：并行模式accumulate是由于运用模式開发有效的并行程序和使用模式管理不规则的数据都不是容易而提出的，这模式不仅有效地描述了并行计算中的数据独立性而且为管理呈现了好多的代数性质。其他的关于最优化机制的模式正在实现当中，且实现后将添加到模式库中。此系统的目的就是帮助程序员更容易开发有效的并行程序。
相对于以前的并行程序开发系统，SkeTo Project的优势主要体现它的扩展性(Extensibility)上。这表现在，在此系统中，新的设计模式可以被定义，并且添加到系统的设计模式库中。但同时，定义新的设计模式并将之添加到系统中这个功能并不完善，因此，在一定程度上限制了SkeTo的实用性。
（三）P3L简介
P3L(Pisa Parallel Programming Language)是由意大利的比萨大学计算机科学学院开发的一种结构化的并行程序设计语言，它是基于骨架或模板的。P3L是建立在C语言的顶部，串行部分用C来实现（但也可扩展为用C++、Java、Fortran、HPF等来实现串行部分），并行部分就通过选用骨架或模板来实现。目前已开发的骨架模型(Skeletons model)包括：任务并行（FARM和流水线PIPE）、数据并行(MAP、REDUCE、SCANR和COMP)、控制并行（迭代LOOP和SEQ）。它的第一个编译器P31L是在1993/94年开发的，目前正在做的工作是：a：anacleto：产生C+MPI代码的新的P3L-2编译器，并且运行在Linux和Fujitsu下；b：ocamlp3l：一种基于Ocaml扩展的骨架。它比直接使用并行库（PVM和MPI）的效率更高表现在：它的并行部分使用已实现的骨架，从而无需处理并行细节部分。
（四）DPAPD开发模型简介
在我们的前期研究中，我们提出了一种基于设计模式和泛型编程的并行程序开发模型DPAPD。此模型的结构如图1所示。系统结构分为三层：抽象语言层、系统实现层和目标语言层。在抽象语言层，我们借用江西师大的薛锦云教授提出的PAR方法中的APLA语言来描述泛型算法结构库和泛型并行结构库。这样，程序员就可以直接使用该语言和模型中的设计模式库来描述抽象的并行程序。在系统实现层，系统将实现四个主要模块，设计模式库（包括算法结构库和并行结构库），分析器（对抽象语言进行分析，产生中间表示），优化器（对中间程序进行优化），转换器（将中间程序转换成可运行的目标语言并行程序）。同样的，在这层，我们也可借用江西师大的薛锦云教授提出的PAR方法中的系列转换器，对此转换器进行相应的扩充即可实现。
三、比较和总结
本文讨论了三种基于模式思想的并行程序开发方法：（1）基于结构化的并行程序设计库eSkel；（2）关于算法模式的系统SkeTo Project；（3）基于并行结构骨架的方法研究的项目P3L等。这三种方法所采用的手段是通过将并行计算模式扩充到顺序语言环境中，以此来设计实现并行程序的开发环境（包括程序设计模型、语言、工具、及集成环境）。由于这类环境隐蔽了并行计算的底层实现细节，因此与低层次的并行程序设计环境相比具有更高的抽象程度。然而，对程序设计环境的研究并不能从根本上解决并行程序设计难的问题，因为并行程序设计困难的原因并不仅仅在于体系结构的多样性，还在于问题本身并行求解的困难。
我们正在研究的DPAPD模型不是传统意义上的并行程序设计模型，而是一种支持整个并行程序开发过程的方法。因此，它不仅是作为一个并行程序设计的模型而提出的，更是作为一个并行算法设计的模型。而且，该模型将并行程序设计开发的两个基本方面统一在一个抽象框架之下，为从问题规范出发，获得并行程序提供了一种系统的方法。然而这一模型还有待进一步的完善，包括足够多的设计模式的开发和更多基于这一方法的模型的开发，这是我们进一步的工作。
参考文献：
[1]万剑怡、孙永强、薛锦云，一种从Z规约到并行程序的精化方法，软件学报，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/.
作者简介：
雷利桂，女，江西瑞昌，硕士研究生，研究方向为并行计算。
[关键词]骨架 并行结构骨架
中图分类号：TP3文献标识码：A文章编号：1671-7597（2009）01103047-01
一、引言
并行程序设计是并行计算的两大难题之一。20世纪90年代，国际上就开始使用基于模式的思想进行并行程序开发，至今已发展出了多种方法和系统：如基于算法骨架的方法、基于设计典型的方法、基于并行结构骨架的方法等；并分别对使用这三种方法所开发的模型或项目如基于结构化的并行程序设计库eSkel、关于算法模式的系统SkeTo Project和基于并行结构骨架的方法研究的项目P3L以及我们正在研究的DPAPD模型进行了简单的介绍。
二、四种基于Skeleton的并行程序设计方法的简介
目前对于Skeleton有许多不同的定义，但它的要义是并行计算和通信的模型，且这模型可以被打包为“框架、模板”等（即它的参数可以由其他的代码来取代）。模型中的实现和分析部分可以共享，即模型中只有结构或框架而没有具体实现的细节部分。
（一）eSkel简介
eSkel(the Edinburgh Skeleton Library)是由爱丁堡大学信息学院开发的一种结构化的并行程序设计库，它为有经验的C/MPI程序员提供很多并行结构框架。eSkel的第一个版本eSkel1是由Murray Cole在2002年开发的。它是利用设计模式思想，即并行计算的重复出现的模式和迭代可以被抽象为框架或模板，并且可以把简单的操作作为参数。因此，提高了抽象的水平，并行程序可以用此框架或模板来得到，从而更加方便。它的目的是最大化由它的部件模式所提供的概念的灵活性，并且促进模式组合的动态选择。
（二）SkeTo Project简介
SkeTo Project(Skeleton Libaray in Tokyo)是由日本东京科技研究所(JST)开发的一关于算法模式的系统。它是基于结构化算法的，主要包含以下两个方面：1.许多数据结构的并行模式的实现，目前已经实现的并行模式库有：表(list)，树(trees)，矩阵(matrices)，这些并行模式是用C++和MPI实现的；2.对模式程序的最优机制，调用了模式的程序可能会带来很多意想不到的负担，所以必须对模式程序的最优机制进行研究。如：并行模式accumulate是由于运用模式開发有效的并行程序和使用模式管理不规则的数据都不是容易而提出的，这模式不仅有效地描述了并行计算中的数据独立性而且为管理呈现了好多的代数性质。其他的关于最优化机制的模式正在实现当中，且实现后将添加到模式库中。此系统的目的就是帮助程序员更容易开发有效的并行程序。
相对于以前的并行程序开发系统，SkeTo Project的优势主要体现它的扩展性(Extensibility)上。这表现在，在此系统中，新的设计模式可以被定义，并且添加到系统的设计模式库中。但同时，定义新的设计模式并将之添加到系统中这个功能并不完善，因此，在一定程度上限制了SkeTo的实用性。
（三）P3L简介
P3L(Pisa Parallel Programming Language)是由意大利的比萨大学计算机科学学院开发的一种结构化的并行程序设计语言，它是基于骨架或模板的。P3L是建立在C语言的顶部，串行部分用C来实现（但也可扩展为用C++、Java、Fortran、HPF等来实现串行部分），并行部分就通过选用骨架或模板来实现。目前已开发的骨架模型(Skeletons model)包括：任务并行（FARM和流水线PIPE）、数据并行(MAP、REDUCE、SCANR和COMP)、控制并行（迭代LOOP和SEQ）。它的第一个编译器P31L是在1993/94年开发的，目前正在做的工作是：a：anacleto：产生C+MPI代码的新的P3L-2编译器，并且运行在Linux和Fujitsu下；b：ocamlp3l：一种基于Ocaml扩展的骨架。它比直接使用并行库（PVM和MPI）的效率更高表现在：它的并行部分使用已实现的骨架，从而无需处理并行细节部分。
（四）DPAPD开发模型简介
在我们的前期研究中，我们提出了一种基于设计模式和泛型编程的并行程序开发模型DPAPD。此模型的结构如图1所示。系统结构分为三层：抽象语言层、系统实现层和目标语言层。在抽象语言层，我们借用江西师大的薛锦云教授提出的PAR方法中的APLA语言来描述泛型算法结构库和泛型并行结构库。这样，程序员就可以直接使用该语言和模型中的设计模式库来描述抽象的并行程序。在系统实现层，系统将实现四个主要模块，设计模式库（包括算法结构库和并行结构库），分析器（对抽象语言进行分析，产生中间表示），优化器（对中间程序进行优化），转换器（将中间程序转换成可运行的目标语言并行程序）。同样的，在这层，我们也可借用江西师大的薛锦云教授提出的PAR方法中的系列转换器，对此转换器进行相应的扩充即可实现。
三、比较和总结
本文讨论了三种基于模式思想的并行程序开发方法：（1）基于结构化的并行程序设计库eSkel；（2）关于算法模式的系统SkeTo Project；（3）基于并行结构骨架的方法研究的项目P3L等。这三种方法所采用的手段是通过将并行计算模式扩充到顺序语言环境中，以此来设计实现并行程序的开发环境（包括程序设计模型、语言、工具、及集成环境）。由于这类环境隐蔽了并行计算的底层实现细节，因此与低层次的并行程序设计环境相比具有更高的抽象程度。然而，对程序设计环境的研究并不能从根本上解决并行程序设计难的问题，因为并行程序设计困难的原因并不仅仅在于体系结构的多样性，还在于问题本身并行求解的困难。
我们正在研究的DPAPD模型不是传统意义上的并行程序设计模型，而是一种支持整个并行程序开发过程的方法。因此，它不仅是作为一个并行程序设计的模型而提出的，更是作为一个并行算法设计的模型。而且，该模型将并行程序设计开发的两个基本方面统一在一个抽象框架之下，为从问题规范出发，获得并行程序提供了一种系统的方法。然而这一模型还有待进一步的完善，包括足够多的设计模式的开发和更多基于这一方法的模型的开发，这是我们进一步的工作。
参考文献：
[1]万剑怡、孙永强、薛锦云，一种从Z规约到并行程序的精化方法，软件学报，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/.
作者简介：
雷利桂，女，江西瑞昌，硕士研究生，研究方向为并行计算。