生成検査+α計算の効率的並列アルゴリズムの系統的導出

• 江本 健斗

  東京大学大学院情報理工学系研究科

書誌事項

タイトル別名

• Systematic Derivation of Efficient Parallel Algorithms for Generate-test-α Computation

抄録

What we call “generate-test-α” is a computation pattern in which we do some extra computation, such as choosing the optimal solution, after the usual generate&test computation that enumerates all solutions passing the test. A naive parallel algorithm of the generate-test-α can be given as a composition of parallel skeletons, but it will suffer from a heavy computation cost when the number of generated candidates is large. Such a situation often occurs when we generate a set of substructures from a source data structure. It is known in the field of skeletal parallel programming that a certain class of simplified computation without test phases can be given efficient linear cost algorithms by making systematic transformations exploiting semirings. However, no transformation is known as yet to optimize the generate-test-α computation uniformly. In this paper, we propose a novel transformation to embed the test phases into semirings so that generate-test-α computation can be transformed into a simplified generate-α computation. This transformation allows us to reuse efficient parallel algorithms of generate-α for the generate-test-α computation. In addition, we give powerful optimizations for a class of generate-α computations, so that we can give uniform optimizations for a wide class of generate-test-α computations.

収録刊行物

• コンピュータ ソフトウェア

  コンピュータ ソフトウェア 29 (1), 159-175, 2012

  日本ソフトウェア科学会

詳細情報

• CRID: 1390001204737183360
• NII論文ID: 130004549255
• DOI: 10.11309/jssst.29.1_159
• ISSN: 02896540
• データソース種別:
  • JaLC
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可