研究紹介
丸文学術賞 受賞者

論理関数の自由度の新しい表現方法とその論理合成への応用新しいタイプの論理素子を使いこなすための新しい論理合成手法の確立

山下 茂
立命館大学 情報理工学部教授

研究の背景

1. 論理関数の自由度の新しい表現方法（SPFD）の考案

複数持つことにより関数fの自由度を表現する。

1 9 9 0 年 代までにL S I 設 計 のための

一般に論理回路には多くの潜在的な冗また、本研究ではSPFDによる自由度のCADの技術は大幅に発展し、実用的な長性があり、各結線で実現すべき論理関効率的な計算手法や回路変換への利用LSIをCADツールにより設計できるように数にはある程度の自由度（回路の出力が方法なども考案した【1, 3】。
さらに、SPFDをなった。CADツールの中に使われる設計変わらないという条件でその関数が変化利用すれば、どんな場合でも従来からの表技術の中でも特に論理合成の技術はか可能な範囲）が存在する。そのような自由現方法に比べて必ず大きな自由度が表現なり成熟したと考えられ、純粋な論理合成度は論理回路の設計や回路の最適化のできることを数学的に証明した【3】。

に関する新しい研究成果が学会などで発際に利用できる。従来のAND/OR/NOTSPFDを利用すれば、従来からの自由表される件数は少なくなってきている。

で構成される論理回路では、回路内の各度の表現方法を利用する場合よりも、回しかし、その一方で1990年代からよく部分で実現される関数の値がある入力パ路の変形の自由度が増大する。それを利使用されるようになってきたFPGA（Field

ターンの時に0か1にならなければならない用して、当初はLUT型のFPGAの回路のProgrammable Gate Array）などのよのか、どちらでも良い（ドントケア）のかで論最適化に利用されたが、通常の回路の最うにその論 理 的なプリミティブが従 来の理関数の自由度を表現していた。

適化にも応用されるようになり、現在ではAND/OR/NOTのような単純な論理でな上述した従来のドントケアの概念と全く配置・配線ツール、テスト生成ツール、仕い場合、従来の論理合成技術を単純に異なり、本研究ではSPFD（Sets of Pairs

様変更への対応手法など、LSI設計の幅利用するよりも、新たな論理合成技術のof Functions to be Distinguished）と広い分野で応用されている。また、本研究確立がより望ましいと考えられる。

呼ばれる関数の対の集合で関数の自由のSPFDに関する2つの論文【1, 3】が数多

また、近年LSIの信頼性の向上のために度を表現する概念と手法を考案した【1, 3】。

くの学術論文で参照され、大学でのLSI設

物理設計のレベルからアーキテクチャ設計

SPFDの考え方では、「 関数の対（f 0 , f 1 ）計技術の講義でも紹介されるなどSPFDのレベルで多くの研究が行われているが、に対して、f0 =1となる入力の時とf 1 =1となは論理合成の分野ではメジャーな概念に

論理合成のレベルでは、3重化を単純に利る入力の時とでは論理関数fの値（0またはなりつつある。

用した手法など限られたものしか研究が進

1）が異ならなければならない」という条件をんでいない。今後のLSI設計技術の更なる発展のためにも、論理合成のレベルで信頼性を向上させるための新しい設計技術の出現が望まれている。

研究の成果
本研究では、LSI設計技術の中でも純粋

図1 SPFDを用いたFPGA向けの論理回路の最適化手法
FPGA内の組合せ論理回路
L1L2L1L4
これらの出力論理を変えずに回路を簡単化

L3

L4L2L3に論理合成の技術に関して新しい理論的なブレークスルーを目指して、新しい概念の創出とその論理合成への応用に関して研究を進めてきた。

回路内に存在する他の論理関数が、この配線が実現すべき論理関数の自由度の範囲内にあるかを判定→L3を発見

L3の利用によりL2を削除（同時にL4の論理機能も変更）

図2 PPCの利用例

N1N2を様々な他の論理合成の技術と組み合

N3

N4LUT

LUT

回路の出力本研究では、SPFDをLUT型FPGAの回路の最適化【2, 5, 6】に利用し、その手法LUT

LUT回路の入力2. SPFDの概念を利用したLUT型FPGA向けの論理合成システムの開発わせることにより、LUT型FPGA向けのテクノロジーマッピングを行う設計ツール【4】を開発した。
例えば、図1に示す回路において、L 2の出力論理関数の自由度をSPFDで表現しPPCは、従来手法の冗長なモジュールのト生成、仕様変更への対応などLSI設計技て、L 3の出力論理関数がその自由度に含追加による面積の増大や、FPGAのように術の様々な分野に応用できることが分かまれると分かれば、図1のように回路を変形配線を自由に変更できる機能による速度低り、さらに様々な応用が広がることが期待でしてL2を削除することが可能である。

下などのオーバーヘッドなしで耐故障性を向きる。

開発した手法【4】は、当時の商用の設計ツールよりも回路規模が小さく、配置・配線後の最大遅延時間も少ない回路を合成することができた。
3. SPFDの概念を利用した少ないオーバーヘッドで故障に対応可能な論理回路モデルの考案上させることができる画期的な回路モデルであると考えられる。

また、SPFDの概念を応用して考案したPPCの回路モデルは、今後ますます信頼

本研究では、SPFDを利用してPPCの回性の確保が難しくなると考えられる次世代路を設計する手法および故障の修正方法

素子によるLSIの設計技術に、新たな設も考案しベンチマーク回路でその有効性を計手法を提供すると考えられる。これによ確認した【7】。

り、今後の半導体産業において特に製造歩留まりを向上させる論理回路設計技術を確立し、将来的には廃棄するLSIの削減

将来の展望や一部が故障しても動作し続けるLSIの本 研 究では、S P F Dの応 用として、従来からのようにモジュールを多 重 化 す

SPFDは、当初はLUT型FPGAの最適ることなく製 造 後 の 故 障を回 避して回化に利用されたが、その後配置・配線、テス設計手法の確立などに寄与することが期待できる。

路を使 用 可 能とすることが可 能なP P C（Partially-Programmable Circuit）という回路モデルを考案した【7】。

References（参 考 文 献 ）PPCの回路モデルを図2に示す。点線は設計後に追加する冗長結線であり、最初に回路を合成した際にはない結線である。
もしＳＰＦＤにより、N 1からN 4へ冗長な結線（図の点線）をつなげばN 2からN 3への結線が冗長になると判断可能であるとする。それは、N 1からN 4へ冗長な結線をつないでおけば、もしN 2からN 3の結線に故障が起こったとしても、N 3やN 4などのＬＵＴの内部論理を変更することによりN 2からN 3の結線を論理的に冗長とすることが可能であることを意味する。つまり、ある程度の数の冗長な結線をあらかじめ追加しておくだけで、回路の多くの部分の結線の故障にLUTの論理機能の変更をするだけで対応することが可能となることが期待できる。

【1】S. Yamashita, H. Sawada, A. Nagoya, A New Method to Express Functional
Permissibilities for LUT based FPGAs and Its Applications, Proc. Int l Conf.
Computer-Aided Design (ICCAD 96), pp. 254-261, Nov. 1996.
【2】T. Kouda, S. Yamashita, Y. Kambayashi, Reduction of the Number of FPGA Blocks byMaximizing Flexibility of Internal Functions, IEICE Trans. Fundamentals, Vol. E81-A,
No. 12, pp. 2554-2562, Dec. 1998.
【3】S. Yamashita, H. Sawada, A. Nagoya, SPFD: A New Method to Express Functional
Flexibility, IEEE Trans. CAD, Vol. 19, No. 8, pp. 840-849, Aug. 2000.
【4】S. Yamashita, H. Sawada, A. Nagoya, A General Framework to Use Various
Decomposition Methods for LUT Network Synthesis, IEICE Trans. Fundamentals,
Vol. E84-A, No. 11, pp. 2915-2922, Nov. 2001.
【5】K. Tanaka, S. Yamashita, Y. Kambayashi, SPFD-based One-to-Many Rewiring (OMR) for
Delay Reduction of LUT-based FPGA Circuits, Proc. of GLS-VLSI 2004, pp. 348-353,
Apr. 2004.
【6】K. Tanaka, S. Yamashita, Y. Kambayashi, SPFD-Based Flexible Transformationof LUT-Based FPGA Circuits, IEICE Trans. Fundamentals, Vol. E88-A, No. 4, pp.
1039-1046, Apr. 2005.
【7】S. Yamashita, H. Yoshida and M. Fujita, Increasing Yield Using Partially-ProgrammableCircuits, Proc. of The 16th Workshop on Synthesis and System Integration of MixedInformation Technologies (SASIMI2010), pp. 237-242, Oct. 2010.