二分決定グラフに基づく組合せ論理回路の合成法に関する研究

点击翻译按钮获取中文摘要

(1)論理合成アルゴリズムの評価:3通りのアルゴリズムについて,論理合成プログラムの試作を行ない,実行速度,合成される回路の規模,遅延などの評価を,従来法に基づく合成ツールMISとの比較により行なった.MISでは16ビット以上の加算回路を直接合成することができなかったのに対し,本手法では16,32,64ビットについても合成を行なうことができた.加算回路の段数に関しては,本手法では入力数nに対してlogn段で合成できていることが実験から確かめられた.MCNCベンチマークに対する実験では,本手法により合成される回路の方が段数は少ないが,回路規模に関してはMISの方が優れており,この点で課題が残ることがわかった.BDDの構造から直接回路を合成するため,BDDを与えてからの実行時間ははいずれの方法でも大変短く,10〜20入力の回路でも合成は1秒程度で終了することが確かめられた.(2)合成法に関する理論的考察:与えられた論理関数のBDD表現の大きさと合成される回路の素子数,遅延の関係を理論的に考察した.排他的論理和,加算関数など,BDDのサイズが入力数の線形となるものに関しては,合成される回路の段数はO(log n)となること,対称関数に関してはO(log^2 n)となることが分かった.(3)BDDに基づく論理合成アルゴリズムの研究:本合成法で素子数が大きくなる問題を解決するべくアルゴリズムの見直しを行なった結果,本質的な問題は,論理関数f のBDDが与えられた時,これをf =f _1・f _2と分解するf _1,f _2で,BDDのサイズが小さいものを求めることであるということが判明した.この問題に対していくつかのアルゴリズムを考案したが,評価実験までを行なうことはできなかった.なお,本研究の基本アイデアとアルゴリズムをまとめた下記論文は,平成6年5月に,「電子情報通信学会平成5年度論文賞」を受賞した.N.Ishiura : "Synthesis of Multilevel Logic Circuits from Binary Decision Diagrams,"IEICE Trans. Information and Systems,vol.E76-D,no.9,pp.1085-1092 (Sept.1993)