An Automatic Fusion Mechanism for Variable-Length List Skeletons in SkeTo
An Automatic Fusion Mechanism for Variable-Length List Skeletons in SkeTo
复制标题
SkeTo 中变长列表骨架的自动融合机制
DOI：
10.1007/s10766-013-0263-8
复制
发表时间：
2014
影响因子：
1.5
通讯作者：
Kiminori Matsuzaki
中科院分区：
文献类型：
--
作者：
Kento Emoto;Kiminori Matsuzaki
骨架式并行编程是一种很有前途的简单并行编程方法，用户只需将给定的一组现成的并行计算模式(称为骨架式)的部分组合在一起，就可以构建并行程序。对于这种易用性，存在着一种权衡，其形式是由编程的组合风格引起的效率问题。这个问题的一种解决方案是融合转换，它通过消除冗余的中间数据结构来优化简单组合的骨架程序。几个并行骨架文库具有自动融合机制。然而，目前还没有提出用于可变长度列表(Vll)骨架的自动融合机制，尽管这种骨架在实际问题中是有用的。主要的困难是以前的融合机制不适用于Vll骨架，因此融合不能完成。在本文中，我们提出了一种新颖的Vll骨架融合机制，既可以实现简单的编程接口，又可以实现完全融合。该机制已经在我们的骨架库SkeTo中实现，通过使用表达式模板技术，实验结果表明该机制非常有效。
Skeletal parallel programming is a promising approach to easy parallel programming in which users can build parallel programs simply by combining parts of a given set of ready-made parallel computation patterns called skeletons. There is a trade-off for this easiness in the form of an efficiency problem caused by the compositional style of the programming. One solution to this problem is fusion transformation that optimizes naively composed skeleton programs by eliminating redundant intermediate data structures. Several parallel skeleton libraries have automatic fusion mechanisms. However, there have been no automatic fusion mechanisms proposed for variable-length list (VLL) skeletons, even though such skeletons are useful for practical problems. The main difficulty is that previous fusion mechanisms are not applicable to VLL skeletons, and so the fusion cannot be completed. In this paper, we propose a novel fusion mechanism for VLL skeletons that can achieve both an easy programming interface and complete fusion. The proposed mechanism has been implemented in our skeleton library, SkeTo, by using the expression templates technique, experimental results have shown that it is very effective.