関数型言語における要求駆動型評価の並列処理向き最適化

小野 諭  高橋 直久  

誌名
電子情報通信学会論文誌 D   Vol.J70-D   No.2   pp.259-268
発行日: 1987/02/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(924.7KB)>>
論文を購入




あらまし: 
関数型言語を並列処理する場合に適した,新たな要求駆動型評価の最適化アルゴリズムを提案する.最適化は,必須引数の先評価とデマンド波及の効率化および不要グラフの除去の三点に関して行う.この最適化の基礎となる広域データフロー解析として,引数依存属性集合解析および部分値依存属性集合解析を用いる.最適化に必要な計算量の削減のため,プログラム全体を同時に処理する関数間解析と,関数定義ごとに閉じた処理を行う関数内解析を別フェーズとして実行する階層的アプローチを採用している.本方法を用いると,データ駆動型評価を並列実行するデータフローマシンに若干の拡張を行うことにより,ディスクリートなドメインにおける逐次関数を不動点計算規則に基づいて効率良く実行できる.