多段論理合成 ( 前半概要 ) 第 章多段論理合成 年 月改訂 論理合成システム 積項を用いたファクタリング TVF 論理式の割り算 関数分解 回路の変換 //5 多段論理合成 //5 多段論理合成 LSI の設計システム 論理合成システム Loic Sntesis Sstem 半導体技術に独立 半導体技術に依存 動作記術機能記術 ネットリスト ネットリスト レイアウト 動作記述言語, 機能記述言語論理式, 真理値表, 状態遷移図 論理生成二段論理最適化 ( ゲート数 ) 多段論理最適化 ( 接続線数 ) 論理合成最適化 ( 面積, 時間 ) 半導体技術マッピング レイアウトシステム //5 多段論理合成 マスク マスクパターン変換システム //5 多段論理合成 4 多段論理回路の設計法 仕様の記述 ( 高級言語 ) 二段論理回路へ変形 ( ブロック分割 ) 二段回路へ変換 多段論理回路の設計法 簡単化 ( ドント ケア ) タイミング最適化 ( 遅延時間の減少 ) ゲートアレイで実現 ( テクノロジマッピング ) 簡単化 (MINI, ESPRESSO) 局所的変換法 ( 回路の更なる改良 ) 多段回路へ変換 ( ファクタリング, 論理式の割り算 ) //5 多段論理合成 5 //5 多段論理合成 6
多段回路のメリット 二段論理回路 O( n ) 多段論理回路 O( n /n) 多段回路にすると, 回路がコンパクトになる 多段化の原理 ( avb) vc av( bvc) a( bvc) abvac avb bva 結合律分配律交換律 //5 多段論理合成 7 //5 多段論理合成 8 積項を用いたファクタリング a b c d a b e a b i z ファクタリング (Factorin) abcd abe ab i z を二段論理回路で実現 ファクタリングを行うと //5 多段論理合成 9 //5 多段論理合成 e c d ab ab ファクタリング //5 多段論理合成 i z abcd abe ab i z a b cd e i z cd e i z ファクタリング リテラル数が減る ファンイン数が減る アルゴリズム. 共通積項を列挙する. リテラル数を最も減らす積項を選択する. 論理式を再構築し,, を繰り返す //5 多段論理合成
TVF TVF( 二変数関数発生器 ) TwoVariable Function enerator OVF 一変数のすべての関数を生成するマクロ素子 TVF 二変数以下のすべての関数を生成するマクロ素子 定理任意の論理関数 で表現できる. ) は, 4 値入力の論理和形,,, n ( n r S S,,, n V S, S,, S r S r r //5 多段論理合成 //5 多段論理合成 4 A B select select A B A B A A B B A B A B A B A B B A B A A B A B //5 多段論理合成 5 例題 :,, 4 TVF 論理式は 簡単化,,,, //5 多段論理合成 6 TVF TVF, 4 となるので, 通常の論理式を用いて表現すると,,, 4 4 4 4 4 4 4 が得られる. //5 多段論理合成 7 マクロ展開を用いる 4 4 4 //5 多段論理合成 8
論理式の割り算 論理式の割り算 定理 p 次の多項式を P, s 次の多項式を S とする. p s ならば, 次の条件を満たすq 次多項式 Q と r 次多項式 R が一意的に定まる. S P Q R, q s p, r p 商 剰余 //5 多段論理合成 9 //5 多段論理合成 例題 : S 論理式の割り算 P R 5 一意的に定まる. Q z F z w R w P z. Q z w R z w 一意的には定まらない //5 多段論理合成 Q 論理式の割り算, 代数的論理和形ブール代数における特有の関係が生じない論理式. この場合, 商や余剰などは一意的に定まる. 定義 F p i i おいて F と が共通の変数を持たないとき, F と の代数的論理積が定義できる., i q i F, //5 多段論理合成 論理式の割り算 定義 つの代数的論理和形をFとPとする. Q F / P として F Q P R においてRの積項数が最小のときこの割り算を弱い割り算 (Weak Division) という. 弱い割り算ではQとRは一意的に定まる. アルゴリズム ( 弱い割り算 ) F,,, t U u, u,, u t P p, p, としたとき, p s V v, v,, u v //5 多段論理合成 v t で U は F のリテラルのうちで積項 P にあるリテラルの積で V は F のリテラルのうちで積項 P にないリテラルの積 論理式の割り算 u,v ですべてのリテラルを除去した場合は V Q p i v s i //5 多段論理合成 4 V u p p i i R F P Q
論理式の割り算 例題 : F ac ad ae bc bd be ab とすると P a b a, a, a, b, b, b b V a c, d, e U, V c, d, e, c, d, e, a c, d, e F P b c, d, e a V, Q / R ab F a b c d e ab //5 多段論理合成 5 既約 論理式の割り算を行う際, リテラル数がなるべく減るような除数 P を求める. 論理和形で, すべての項に同じリテラルが現れない場合 それは既約である. 一つの積項からなるものは既約ではない. 既約でない abc abd abc ad cd ad 既約 c d ab cd a b c d //5 多段論理合成 6 カーネル (Kernel) 定義 Fを論理和形, cを積項とするとき, 既約な商 F/cをFのカーネルという. Fのカーネルの集合を K(F) で表す. 例題 : F ae be cde ad ae bd be b H abc のとき K F a b cd K a b, d e, d e, ad ae bd be b K H //5 多段論理合成 7 カーネル ファクタリングとカーネルの比較例題 : F ade bde cde b c d ae H ae bc ファクタリングの場合 F d bde cde 共通積項はaeである. =aeとおくと b c d H bc リテラル数は ae //5 多段論理合成 8 カーネル カーネルの場合 F のカーネルは av bv c, のカーネルは bv cv d F a b c de b c d ae H ae bc Fとの共通カーネルはbv c F a de d ae H ae bc b c =bv c とおくと リテラル数は 8 //5 多段論理合成 9 関数分解 Functional Decomposition //5 多段論理合成
R. L. Asenurst (957) 論理関数の分解理論 (,)=((),) 分解表 関数分解 一般にn 変数関数 を実現するにはゲート数が n / n 個必要. nが大きいとき図のように分解できればゲート数を削減できる. m n n H H n n //5 多段論理合成 //5 多段論理合成 関数分解の用語 例 :, をの分割,,, とする5 変数関数の分解表の例 4, 5 n, n 列複雑度 4 5 分解の利得 n n min, / 4 //5 多段論理合成 =(4,5) 分解表 =(,,) //5 多段論理合成 4 列複雑度 (column multiplicit) 列複雑度 (μ=) =(,,) 分解表 (,) の異なる列パターン数. μで表わす. =(4,5) //5 多段論理合成 5 //5 多段論理合成 6
関数分解の原理 (μ=) 4,5 =((,,),4,5) の実現 H 4 5 //5 多段論理合成 7 //5 多段論理合成 8 分解表 =(,4,5) μ= =(,) =((,),,4,5) の実現 H 4 5 //5 多段論理合成 9 //5 多段論理合成 4 列複雑度と回路構造 μ= 列複雑度と回路構造 μ r H H r //5 多段論理合成 4 //5 多段論理合成 4
例題 : 45 関数分解 Hの関数 入力変数は減らない 列複雑度 H の出力数 に対するマップ 45 ドント ケア //5 多段論理合成 4 関数分解 H 4 5 //5 多段論理合成 44 対称関数と関数分解 関数 が {} において部分対称. ()=((),) の列複雑度は高々 n+. n は の変数の個数. 重要な演算回路. 部分対称なものが多い. //5 多段論理合成 45 SYM6 の設計 6 入力 出力の対称関数. 入力の の個数が,, または 4 のとき出力が で, その他の場合は, 出力が. 4 5 6 SYM6 //5 多段論理合成 46 SYM6 の分解による実現 入力変数を =(,,), =(4,5,6) と分割. 完全対称関数 : 入力の の個数のみに依存. FA(ull adder). の個数を計数する 入力 出力回路. 4 5 6 FA FA 4 SYM6 の実現 ( その ) 4 4 6 5 5 4 4 //5 多段論理合成 47 //5 多段論理合成 48
SYM6 の実現 ( その ) 4 回路の変換 //5 多段論理合成 49 //5 多段論理合成 5 回路の変換 局所的変換法 (Local Transormation) 与えられた多段論理回路の一部に対して, ブール代数の規則を繰り返し適用することにより簡単化を行う方法 定数削除 など 回路の変換 入力 ANDおよび 入力 ORの削減 インバータ削減 重複ゲート削減 未使用ゲート削除 //5 多段論理合成 5 //5 多段論理合成 5 ゲート併合 因子共有化 z u z v 回路の変換 //5 多段論理合成 5 z u v 回路の変換 否定ゲート付加による簡単化 冗長な接続線の除去 i i //5 多段論理合成 54 i
講義概要 多段論理回路簡単化とドント ケア Satisiabilit don t care (SDC) Observabilit don t care (ODC) トランスダクション法 ブール関係 タイミング最適化 多段論理回路の設計 回路を小さな部分に分割し, 別々に設計ドント ケアが生じるドント ケアを用いて回路を簡単化 //5 多段論理合成 55 //5 多段論理合成 56 Satisiabilit Don t Care (SDC) A B 図多段論理回路の構成 回路 A が既存, 回路 B を設計中とする 回路 A の出力関数 = (,,) 回路 B の出力関数 z = z(,,,) = は中間変数 Bの入力 (,,,) には決してあり得ない組み合わせが存在この組み合わせが Satisiabilit don t care //5 多段論理合成 57 Satisiabilit Don t Care (SDC) SDC 上式は と の値が一致しない組み合わせを示す回路 Aが多出力 (,, k ) の時, SDC ( ) i 中間変数が多いと SDC は非常に複雑になり, 簡単化は困難 //5 多段論理合成 58 k A 例 下の回路において, 回路 Aが関数 を生成し, 回路 Bが z 実現する時, SDC を求め, 回路 B を簡単化せよ //5 多段論理合成 59 B 図実現する回路 解 SDC ( ) ( ) ( ) ( ) ( ) ( ) //5 多段論理合成 6 SDC のカルノー図
SDC のカルノー図 z 解 z のカルノー図 となる Observabilit Don t Care (ODC) A B 回路 B が既存, 回路 A を設計中とする 回路 B のため回路 A の出力値が外部出力値 z に影響を与えない場合がある z の値に影響を与えないような回路 B の入力の集合を Obsevabilit don t care という ODC z( ) z( ) //5 多段論理合成 6 //5 多段論理合成 6 例 下図のような回路において, 回路 Bが関数 z を生成し, 回路 Aが を生成する時, ODCを求め, 回路 Aを簡単化せよ A //5 多段論理合成 6 B 解 ODC z( ) z( ) ( ) ( ) ( ) ( ) ODC のカルノー図 //5 多段論理合成 64 のカルノー図 解 回路 A のカルノー図 となる トランスダクション法 Transduction 法 許容関数の概念を用いて, 回路を簡単化する手法 97 年イリノイ大学の室賀教授らが考案 99 年代に, BDD による論理関数表現法が開発され, 実際の回路設計に使用された //5 多段論理合成 65 //5 多段論理合成 66
トランスダクション法による回路の簡単化 例 :EOR 回路の簡単化 a b =(,,,) =(,,,) a b d =(,,,) c d c =(,,,) c =(,,,) a b (,,,) (,,,) (,,,) c d (,,,) e (,,,) (,,,) (,,,) //5 多段論理合成 67 //5 多段論理合成 68 トランスダクション法 c =(,,,) である必要はなく, c =(,,,) であればよい この時, c を c の許容関数という a (,,,) (,,,) e (,,,) c d (,,,) (,,,) b (,,,) (,,,) //5 多段論理合成 69 トランスダクション法 共通な関数 =(,,,) を用いると, 二個のインバータを 個の NAND ゲートに置換できる a (,,,) b (,,,) (,,,) (,,,) //5 多段論理合成 7 e (,,,) (,,,) 関係と関数 ブール関係 Boolean Relation 関係 (Relation) 直積 AB の部分集合 関数 (Function) 関係の特別のもの A B //5 多段論理合成 7 //5 多段論理合成 7
例 : 加算器 + 比較回路 二つの ビットの数を加算 加算結果 > (w,w) = (,) 加算結果 = (w,w) = (,) 加算結果 < (w,w) = (,) を生成する 加算器 比較回路 //5 多段論理合成 7 z 図 w z w z 実現する回路 ビット加算器の真理値表 z z z //5 74 比較回路の真理値表 z z z w w //5 多段論理合成 75 比較回路の仕様 z z z 比較回路の真理値表 w w {,,} は同値類を形成 {} も同値類 {,,,} も同値類を形成 //5 多段論理合成 76 ビット加算器のブール関係による記述 {,,} {,,} {,,} {} {,,} {,,} {} {,,,} {,,} {} {,,,} {,,,} {} z z z {,,,} {,,,} {,,,} 入力 の時, 出力は,,のいずれでも可 入力に対して, 出力が一意的に定まらない ブール関係 77 ブール関係 最小表現を求める手法が開発されている 通常のドント ケア手法よりも表現が簡単になる ブール関係を満たす表現の簡単化の結果 //5 多段論理合成 78 z z z
論理設計の目標 タイミング最適化 ハードウェアのコストの削減 ゲート数 接続線数 遅延時間の削減 特に遅延時間を削減したい //5 多段論理合成 79 //5 多段論理合成 8 回路の段数 ゲートの種類 ファンアウト 配線長 遅延の要因 回路の段数について着目する 遅延最小化のモデル 各ゲートの遅延時間は等しい 配線遅延は無視できる 回路の遅延時間は, 信号が入力から出力まで伝播する際に通過するゲートの最大数に比例. //5 多段論理合成 8 //5 多段論理合成 8 クリティカル パス Critical Pat 回路の入出力間の経路上でゲート数が最大となる経路 Y 4 6 5 W 図 5 段論理回路クリティカル パス上のゲート数を回路の段数という上例では回路の段数 = 5 しかし 回路の段数 回路の遅延時間 となる場合がある //5 多段論理合成 8 例 の変化が出力に伝播するためには = Y = 4 6 5 5 段論理回路 //5 多段論理合成 84
例 NAND ゲートでは, 出力関数を変化させず定数 を除去できるので, 下図のように変形できる //5 多段論理合成 85 4 簡単化した 5 段論理回路 ゲート の出力値は, の値にかかわらず 5 6 例 経路,,, 5,6 は決して活性化されない //5 多段論理合成 86 フォールス パス 決して活性されない信号経路のことをフォールス パス (alse pat) という 4 5 6 回路の遅延時間 フォールス パスの存在のために, 遅延時間 回路の段数 ゲートの遅延時間 となる //5 多段論理合成 87