「非循環グラフにおける支配関係の簡潔な検出算法」(Vol.43,No.SIG1(PRO13))

平成14年度論文賞受賞者の紹介

「非循環グラフにおける支配関係の簡潔な検出算法」(Vol.43,No.SIG1(PRO13))

[論文概要]
 本論文は,非循環なフローグラフの支配関係を求める簡潔高速な算法を紹介する.この算法は頂点数N辺数Mのグラフに対して,大きさNのスタックを用い,支配木と支配辺境の算出を,グラフに対するN-1回のリダクションと同時に実行する.リダクション対象頂点の番号は,リダクションの進行中にスタックに貯えられる.本算法の計算量は大部分がO(M)の部分からなり,SPEC CFP92から約240題を選抜して評価した結果,計算量は統計的にMに対して多少のばらつきを伴なう線形性を示し,比例係数は平均1.5,最大2.5であった.これは既発表の他の方法より約3倍高速である.

[推薦理由]
 本論文は,コンパイラ最適化における重要な基礎技術である非循環グラフの支配関係(可約なグラフの支配関係と実質的に等価)の検出問題に対して,簡潔かつ実用的に高速な線形時間アルゴリズムを与えている.この問題の高速アルゴリズムの構成は自明ではなく,比較的最近まで多くの研究が行われてきたが,本論文は後継頂点集合とスタックを用いる手法によって簡潔なアルゴリズムを導いた.これにより計算量の線形性が明確になったばかりでなく,定数係数も改善された.実験的評価も綿密に行われている.著者らはさらに,この結果を非可約なグラフに一般化した結果を後に得ている.論文の記述も厳密かつ明快であり,本論文は論文賞にふさわしいものと判断する.

齋藤 鐵男君  昭和5年生.昭和28年東京大学工学部電気工学科卒.同年三菱鉱業株式会社.昭和42年(株)東京芝浦電気入社,昭和45年より(株)東京技術計算コンサルタント.平成2年東京大学工学部工学系大学院研究生修了.平成14年電気通信大学大学院電気通信学研究科博士後期課程情報工学専攻修了,工学博士.現在東京電機大学工学部非常勤講師,情報処理学会,電気学会等,各会員.

鈴木 貢君  昭和39年生.平成1年電気通信大学計算機科学科卒.平成7年同大学院博士後期課程単位取得退学.現在電気通信大学情報工学科助手.工学修士.生体の画像処理,記憶管理アルゴリズム等の研究を行ってきた.記憶管理法,並列/分散アルゴリズム,言語処理系の実現に興味を持つ.情報処理学会,電子情報通信学会,日本ソフトウエア科学会,ACM各会員.

渡邊 坦君  昭和37年京都大学理学部数学科卒.日本IBM(株),(株)日立製作所中央研究所,同システム開発研究所を経て,平成6年より電気通信大学情報工学科教授.工学博士.現在はコンパイラとプログラミング言語の研究を主要テーマとしている.著書「コンパイラの仕組み」(朝倉書店),他.情報処理学会,日本ソフトウェア科学会,ACM,IEEE 各会員.