Generator-of-generators に基づく Fortress ライブラリ

Bibliographic Information

Other Title
  • Generator-based Fortress GG Library

Search this article


我々は,プレフィックス計算のような複雑な依存関係を持つ並列計算を簡潔に記述し効率的に実行することができる,Fortress の新しいライブラリを提案する.このような複雑な依存関係を持つ並列計算は,Fortress における並列計算の既存の抽象化である generator を用いることで,現状でもある程度簡潔に記述することができる.しかしながら,その簡潔な記述に対して効率的な実装を適用するための枠組みがなく,また,問題の仕様変更に対する記述の柔軟性に欠ける.そこで,我々は,generator を拡張し,複雑な依存関係を持つネストしたデータ構造上の並列計算を抽象化する generator-of-generators を導入する.そして,generator-of-generators のコレクションと,generator-of-generators の最適化理論のコレクションとで構成される新しいライブラリを提案し,上記の問題を解決する.このライブラリにより,ユーザは複雑な依存関係を持つ計算に対して柔軟かつ簡潔なプログラムを記述することができる.そして,ライブラリは,最適化理論により与えられる効率的な実装をユーザプログラムに割り当てることにより,ユーザプログラムの自動最適化を行う.これらにより,ユーザは効率の低下なしに正しく柔軟な並列プログラムを容易に作成できる.

We propose a new library on Fortress to deal with parallel computation with complex dependency such as prefix sums, which cannot be efficiently dealt with by simple comprehensions or generator-reduction patterns of Fortress. The library provides a collection of generator-of-generators that abstract generation (parallel computation) of nested data structures with complex dependency, for allowing users to write their parallel programs in an easy and uniform way. The library also provides an automatic optimization mechanism that dispatches correct and efficient implementation to those user programs, based on a collection of optimization theories on generator-of-generators. Thus, users can easily make correct and flexible parallel programs without losing efficiency. The proposed library is implemented on Fortress, and techniques used here can be reused for other libraries on Fortress.




Report a problem

Back to top