Using Algebraic Properties and Function Fusion to Evaluate Tree Accumulations in Parallel

DOI 情報処理学会 Web Site 参考文献4件

この論文をさがす

説明

<p>Parallel evaluation of tree processing using accumulation parameters tends to be difficult because the accumulation parameters may introduce data dependencies between computations for subtrees. Some proposals have broken these data dependencies by using algebraic properties such as associativity and commutativity, but, none has achieved both the capability of complex tree traversals like attribute grammars and a theoretical guarantee of parallel speedup. This paper proposes a tree processing language based on macro tree transducers and provides a parallel evaluation algorithm for programs written in the language. The language can express complex accumulations like attribute grammars, and moreover, the number of parallel computational steps for evaluation is proportional to the height of the input tree. This paper also shows that combining the proposed approach with function fusion for macro tree transducers leads to improvement in the parallel computational complexity. Although comparable complexity improvement can be obtained from known parallel algorithms, the proof and parallel evaluation algorithm here are remarkably simpler.</p>

収録刊行物

参考文献 (4)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ