木構造処理からストリーム処理プログラムへの変換のための部分的バッファリングの挿入

情報処理学会 Web Site

書誌事項

タイトル別名
  • キコウゾウ ショリ カラ ストリーム ショリ プログラム エ ノ ヘンカン ノ タメ ノ ブブンテキ バッファリング ノ ソウニュウ
  • Type-based Partial Buffering for Stream Processing

この論文をさがす

抄録

XML等の木構造を論理構造として持つデータの処理の記述方式には，プログラムの可読性・保守性に優れた木構造処理方式と，メモリ効率に優れたストリーム処理方式がある．両者の利点を両立させるため，末永らは木構造処理プログラムをストリーム処理プログラムに自動変換する枠組みを提案している．しかし，変換時のバッファリング命令の挿入において，部分木全体がバッファリングされてしまうという問題点があった．この問題を解決するため，本研究では木の一部のみをバッファリングするための命令を挿入するための枠組みを提案する．部分的バッファリングの挿入は，既存の末永らの枠組みでバッファリングを挿入した後に，各データの不要部分を型として推論することによって行うことができる．そこで，本論文ではヴァリアント型を持つ一般的なλ計算の枠組みを対象として，不要データ除去変換を定式化する．この理論に基づき，XML処理プログラムに対する部分バッファリングの自動挿入器を実装し，ベンチマークプログラムを用いてその有効性を検証した．

Stream-processing is important for efficient processing of tree-structured data such as XML. Suenaga et al. have proposed a type-based framework for automatically translating tree-processing programs into stream-processing ones. Their framework uses ordered linear types to check whether an input tree data is accessed once in the left-to-right, depth-first order, and to insert buffering primitives when that access restriction is violated. We extend their framework by enabling partial buffering of input tree data, so that only necessary part of data is copied from stream to main memory. We reduce the problem of inserting partial buffering primitives to a problem of program optimization called useless data elimination, and propose a type-based method for the optimization. Based on the framework, we have implemented a prototype translator. The result of preliminary experiments shows that the partial buffering improves the efficiency of programs both in memory usage and execution time.

収録刊行物

キーワード

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

問題の指摘

ページトップへ