要求駆動計算における要求粒度調節機構

• Item type: Journal(1)
• 公開日: 2006-12-15
• タイトル: 要求駆動計算における要求粒度調節機構
• タイトル / 言語: en
• タイトル: A Mechanism for Adjusting Granularity of Demand Driven Computation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: プログラミング言語の設計
• 著者所属: 電気通信大学大学院情報工学専攻
• 著者所属: 電気通信大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro-Communications
• 著者名: 森本, 武資; 岩崎, 英哉
• 著者名(英): Takeshi, Morimoto; Hideya, Iwasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 要求駆動計算において要求を細かく出せば，計算の必要性を細かい単位で調べられ，より多くの不要計算を除去できる．しかし，要求を細かくしすぎると，いずれ必要になる計算の必要性を調べるという無駄が生じ，せっかくの不要計算除去による改善効果を打ち消してしまう．これまでに，細かい要求を簡潔に記述するための言語機構が提案されているが，その機構において要求の細かさ（要求の粒度）を適切に調節する方法については十分な検討がなされていなかった．本論文では，この問題を解決するため，投機的評価を用いて要求の粒度を調節する機構を提案する．提案機構では，要求に応じて計算を進める際に，要求された計算の後続計算も投機的に進めることで，要求の粒度を調節する．適用例としてナップサック問題と8 パズルを解くプログラムを取り上げ，実験により安定した改善効果を確かめた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Demand driven computation is potentially efficient by incrementally issuing small demands, because it helps prune many unnecessary computations by carefully checking whether each computation is necessary or not. However, if the granularity of demands are too small, the efficiency may be spoilt due to the overhead of the control of demand driven computation. Although a mechanism that enables programmers to concisely write small-demand driven programs has been already proposed, controlling granularity of demands is not well investigated. To resolve this problem, this paper proposes a mechanism that controls the granularity of demands by the introduction of speculative evaluation. In the proposed mechanism, when a small demand is issued, the rest computation for this demand is also evaluated speculatively, so that the granularity is adjusted. We described two concrete programs for knapsack problem and eight-puzzle with the proposed mechanism. Their experimental results show the stable effectiveness of the proposed mechanism.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 47, 号 12, p. 3277-3286, 発行日 2006-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764