第 205 回 PTT のお知らせ
日時: 1995年 2月23日 (木) 18:30 から
場所: 慶應義塾大学 理工学部 25-601 教室
(
日吉駅から理工学部キャンパスまでの地図 )
(
理工学部キャンパス内の25-601教室への地図 )
東横線日吉駅慶応大学側の出口(東側)を出て，東横線に沿って左(渋谷方向)へ
行く． 仲の谷という交差点(仏具屋が目印)を右に(中華料理屋と民家の間の道)
曲がり，4〜5分で理工学部の表札が見えるので，そこの左手の坂を登る．教室
は25棟の6階．
話者： 滝本 宗宏(慶大・理工・計算機科学)
題目： φ-関数移動による効率的な部分冗長計算除去
概要：
コード最適化の一手法に, 部分冗長計算除去が存在する.
この手法は, 部分冗長という考えに基づいて, 大域的な
冗長計算除去とループ不変計算のループ外移動を同時に
実現する強力な手法である. 部分冗長計算の除去は,
新たに, 部分冗長を生成する二次的効果を持つ. この
二次的効果を式同士の等価性の面から見直し, 二次的
効果によらない広範囲でかつ, 高速な冗長計算除去が
実現できることを報告する.
本手法においては, φ-関数移動と巻き上げの抑制という
2つの新しい考えを導入している. φ-関数移動は,
異なった場所に定義の結合を持つ式の等価性を露出し,
また, 制御の流れに依存して等価となる計算式を,
フローグラフと独立に見つけ出すことを可能にする.
巻き上げの抑制は, 付加的代入の導入過多を防ぐため
に提案された質問伝播を変形したものであり,
データフロー方程式に基づく効率的な解析を可能にする.
食事:
第 205 回 PTTメモ
日時: 1995年 2月23日 (木) 18:30 〜 21:00
場所: 慶應義塾大学 理工学部 25-601 教室
題目: φ-関数移動による効率的な部分冗長計算除去
話者: 滝本 宗宏(慶大・理工・計算機科学)
出席者:
和田 英一,
石畑 清 (明治大),
並木 美太郎 (農工大),
伊知地 宏 (富士ゼロックス),
下國 治 (東大),
大駒 誠一 (慶大),
遠山 元道 (慶大),
飯島 正 (慶大),
崔 梗ろく (慶大),
馬上 博樹 (慶大),
佐藤 一郎 (慶大),
質疑応答:
講演の内容
全冗長と部分冗長の違いについて述べ, コード巻き上げによって, 部分
冗長を除去することの有効性について述べた. 次に, 冗長の対象として,
共通部分式を用いることの限界と, その二次的効果について述べ, 二次
的効果によって, さらに冗長が生まれていく過程が, 式同士の等価性を
露出させる過程であることを説明した. ここで, 本研究の目的が, 同じ
値を計算していながら, 制御の結合部分における, 定義の結合の違いで,
等価であることを見出せない式同士も含め, 等価な式を見つけ出し, 互
いに辺でつなぐことによって, 新たなフローグラフを作り, その上で,
部分冗長除去のデータフロー解析を行うことであると説明した. この後,
式の構造を値グラフというグラフ構造で表現した際の, 等価性発見にお
ける問題点を述べ, 本研究で導入したφ関数移動の方法と, その際に必
要となる値グラフの拡張について述べた. 次に, 本研究の等価性発見の
方法を, 処理を追って説明し, 例を示した. そして, 等価な式同士をど
のように, 辺で結んで新たなフローグラフ(値流れグラフ)を構築するか
を述べ, その際に必要となる, 巻き上げ抑制の考えを, 大域値番号付け
(Global Value Numbering)の質問伝播と比較して示した. 最後に, 大域
値番号付けを基準に, 冗長除去の範囲が広く, プログラム構造を問わな
いことを示し, その他, ループ内除去が可能であり, より低い計算量で
実現が可能であることを示した.
いくつかの問題点を指摘して頂き, 大変参考になりました. 力不足で,
解説に不明解な点が多々ありましたが, 真剣に聞いて頂き, ありがとう
ございました.