スライドレジスタ割付問題の厳密解法

概要

論文の詳細を見る
レジスタ#0, #1,...を#(K+0), #(K+1),...にいっせいに改名する命令を持つプロセッサを仮定し, いっせいに改名されるレジスタをスライドレジスタとよぶことにする. このようなプロセッサを採用した計算機の1つとしては, 筑波大学のCP-PACSがあげられる. 従来のレジスタにおいては, ループプログラムのレジスタ割付問題はCyclic Arc Graphの彩色問題として定式化できることが知られているが, スライドレジスタに関してはその割付問題の性質が詳しくは分かっていなかった. 本論文では, この問題を巡回セールスマン問題の変形として定式化し, この問題に厳密解決を与える. また, 厳密解決で実際に最適解を求め, その求解時間をもとに本厳密解法の実用化の方法を提案する. さらに, 本厳密解法を近似解法の評価に応用する. 筆者らは先に近似解法を提案・評価しているが, 提案時の評価は55%程度の最適性しか保証できていなかった. 最適解を利用した新たな評価により, 同解法が85%以上の例題に対して最適解を与えていたことが確認できた.
一般社団法人情報処理学会の論文
1999-09-15