新しい計算モデルキューマシンとその並列関数型言語への応用

機関リポジトリ 情報処理学会 HANDLE Web Site 被引用文献5件 参考文献22件 オープンアクセス

書誌事項

タイトル別名
  • New Computation Model Queue Machine and Its Application to Parallel Functional Programming Languages
  • アタラシイ ケイサン モデル キュー マシン ト ソノ ヘイレツ カンスウガタ

この論文をさがす

抄録

本論文では，幅優先で式の評価を行う新たな計算機アーキテクチャであるキューマシンを提案し，その実行モデルを用いて関数型言語を特殊なハードウェアのサポートのない密結合並列計算機上で効率良く自動並列実行する言語処理系の構築法を述べる．関数型言語においては複数の関数呼び出しを並列に処理することが可能であるが，すべての関数呼び出しの実行が終了するまで待って実行を再開するための同期オーバヘッドが問題となる．また，通常スタックに保持する局所的な実行の文脈をヒープ上に保持する必要があるため，メモリ管理のオーバヘッドも増大する．本論文では，キューマシンの実行モデルを模倣してスタックをキューに置き換えることにより上記のオーバヘッドを大幅に削減することができ，既存の計算機上で並列関数呼び出しが効率良く実現できることを示す．この手法を用いたプロトタイプ言語処理系の実行時間を密結合並列計算機で測定した結果，逐次実行ではCなどの他の（逐次）言語処理系に劣るものの，2CPU以上では他の処理系を上回り，高い台数効果が得られている．

We present a new evaluation scheme for expressions called queue machine model of execution which enables automatic (implicit) parallel execution of functional programming languages with very small synchronization overhead without special hardware support.In purely functional languages,multiple function call can be evaluated parallely without changing semantics of the program.But when implemented naively,synchronization overhead to wait for termination of all subcomputations becomes prohibitive.Moreover,local context information usually stored in stack must be maintained in garbage-collected heap.So overhead of memory management also increases when compared to sequential implementations.In this paper,we show that by emulating execution model of queue machines and by replacing stacks with queues,the overhead can be drastically reduced and parallel function invocation can be implemented efficiently on stock hardware.Preliminary measurement of prototype implementation based on this technique is presented.The measurement shows that,although programs compiled with our prototype compiler run slower than other implementations on sequential machines,they show good scalability and run faster than sequential implementations when executed with two or more processors.

収録刊行物

被引用文献 (5)*注記

もっと見る

参考文献 (22)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ