[Updated on Apr. 18] Integration of CiNii Articles into CiNii Research

New Computation Model Queue Machine and Its Application to Parallel Functional Programming Languages

Bibliographic Information

Other Title
  • 新しい計算モデルキューマシンとその並列関数型言語への応用
  • アタラシイ ケイサン モデル キュー マシン ト ソノ ヘイレツ カンスウガタ

Search this article


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


Citations (5)*help

See more


See more



Report a problem

Back to top