Microsoft PowerPoint - 11.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 11.ppt"

うたろうてっちがわら
6 years ago
Views:

1 多段論理合成 ( 前半概要 ) 第章多段論理合成年月改訂論理合成システム積項を用いたファクタリング TVF 論理式の割り算関数分解回路の変換 //5 多段論理合成 //5 多段論理合成 LSI の設計システム論理合成システム Loic Sntesis Sstem 半導体技術に独立半導体技術に依存動作記術機能記術ネットリストネットリストレイアウト動作記述言語, 機能記述言語論理式, 真理値表, 状態遷移図論理生成二段論理最適化 ( ゲート数 ) 多段論理最適化 ( 接続線数 ) 論理合成最適化 ( 面積, 時間 ) 半導体技術マッピングレイアウトシステム //5 多段論理合成マスクマスクパターン変換システム //5 多段論理合成 4 多段論理回路の設計法仕様の記述 ( 高級言語 ) 二段論理回路へ変形 ( ブロック分割 ) 二段回路へ変換多段論理回路の設計法簡単化 ( ドントケア ) タイミング最適化 ( 遅延時間の減少 ) ゲートアレイで実現 ( テクノロジマッピング ) 簡単化 (MINI, ESPRESSO) 局所的変換法 ( 回路の更なる改良 ) 多段回路へ変換 ( ファクタリング, 論理式の割り算 ) //5 多段論理合成 5 //5 多段論理合成 6

2 多段回路のメリット二段論理回路 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 多段論理合成

3 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 となるので, 通常の論理式を用いて表現すると,,, が得られる. //5 多段論理合成 7 マクロ展開を用いる //5 多段論理合成 8

4 論理式の割り算論理式の割り算定理 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

5 論理式の割り算例題 : 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 多段論理合成

6 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

7 関数分解の原理 (μ=) 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

8 例題 : 45 関数分解 Hの関数入力変数は減らない列複雑度 H の出力数に対するマップ 45 ドントケア //5 多段論理合成 4 関数分解 H 4 5 //5 多段論理合成 44 対称関数と関数分解関数が {} において部分対称. ()=((),) の列複雑度は高々 n+. n はの変数の個数. 重要な演算回路. 部分対称なものが多い. //5 多段論理合成 45 SYM6 の設計 6 入力出力の対称関数. 入力のの個数が,, または 4 のとき出力がで, その他の場合は, 出力が SYM6 //5 多段論理合成 46 SYM6 の分解による実現入力変数を =(,,), =(4,5,6) と分割. 完全対称関数 : 入力のの個数のみに依存. FA(ull adder). の個数を計数する入力出力回路 FA FA 4 SYM6 の実現 ( その ) //5 多段論理合成 47 //5 多段論理合成 48

9 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

10 講義概要多段論理回路簡単化とドントケア 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 のカルノー図

11 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

12 トランスダクション法による回路の簡単化例 :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

13 例 : 加算器 + 比較回路二つのビットの数を加算加算結果 > (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

14 論理設計の目標タイミング最適化ハードウェアのコストの削減ゲート数接続線数遅延時間の削減特に遅延時間を削減したい //5 多段論理合成 79 //5 多段論理合成 8 回路の段数ゲートの種類ファンアウト配線長遅延の要因回路の段数について着目する遅延最小化のモデル各ゲートの遅延時間は等しい配線遅延は無視できる回路の遅延時間は, 信号が入力から出力まで伝播する際に通過するゲートの最大数に比例. //5 多段論理合成 8 //5 多段論理合成 8 クリティカルパス Critical Pat 回路の入出力間の経路上でゲート数が最大となる経路 Y W 図 5 段論理回路クリティカルパス上のゲート数を回路の段数という上例では回路の段数 = 5 しかし回路の段数回路の遅延時間となる場合がある //5 多段論理合成 8 例の変化が出力に伝播するためには = Y = 段論理回路 //5 多段論理合成 84

15 例 NAND ゲートでは, 出力関数を変化させず定数を除去できるので, 下図のように変形できる //5 多段論理合成 85 4 簡単化した 5 段論理回路ゲートの出力値は, の値にかかわらず 5 6 例経路,,, 5,6 は決して活性化されない //5 多段論理合成 86 フォールスパス決して活性されない信号経路のことをフォールスパス (alse pat) という回路の遅延時間フォールスパスの存在のために, 遅延時間回路の段数ゲートの遅延時間となる //5 多段論理合成 87

スライド 1

スライド 1 ブール代数ブール代数集合 { 0, 1 } の上で演算 AND, OR, NOT からなる数学的体系何のため? ある演算をどのような回路で実現すればよいのか? どうすれば回路が小さくなるのか? どうすれば回路が速く動くのか? 3 復習 : 真理値表とゲート記号真理値表 A B A B 0 0 0 0 1 0 1 0 0 1 1 1 A B A+B 0 0 0 0 1 1 1 0 1 1 1