Microsoft PowerPoint - 11.ppt

(1)

2010/11/15 多段論理合成 1

第11章

多段論理合成

2010年11月改訂

2010/11/15 多段論理合成 2

多段論理合成（前半概要）

• 論理合成システム

• 積項を用いたファクタリング

• TVFG

• 論理式の割り算

• 関数分解

• 回路の変換

2010/11/15 多段論理合成 3

論理合成システム

Logic Synthesis System

2010/11/15 多段論理合成 4

LSIの設計システム

動作記術機能記術ネットリストネットリストレイアウトマスク半導体技術に独立半導体技術に依存 動作記述言語, 機能記述言語 論理式, 真理値表, 状態遷移図 論理生成二段論理最適化（ゲート数）多段論理最適化（接続線数） 最適化（面積, 時間） 半導体技術マッピングレイアウトシステムマスクパターン変換システム論理合成 2010/11/15 多段論理合成 5

多段論理回路の設計法

仕様の記述（高級言語）二段論理回路へ変形（ブロック分割）二段回路へ変換簡単化 (MINI, ESPRESSO) 多段回路へ変換（ファクタリング, 論理式の割り算） 2010/11/15 多段論理合成 6

多段論理回路の設計法

簡単化（ドント･ケア）タイミング最適化（遅延時間の減少）ゲートアレイで実現（テクノロジマッピング）局所的変換法（回路の更なる改良）

(2)

2010/11/15 多段論理合成 7

多段回路のメリット

• 二段論理回路

Ｏ

（２

ｎ

_）

• 多段論理回路

Ｏ（

２

ｎ

/n)

– 多段回路にすると，回路がコンパクトになる

2010/11/15 多段論理合成 8

多段化の原理

a

)

(

)

(

)

(

交換律　

　　　　

ｖ

　　　　分配律

ｖ

　

　　結合律

ｖ

a

b

ac

ab

c

b

a

c

b

a

c

b

a



2010/11/15 多段論理合成 9

積項を用いたファクタリング

2010/11/15 多段論理合成 10

ファクタリング(Factoring)

f

a b c d a b e f a b f g h i j x y z

xyz

hij

abfg

abef

abcd

f





を二段論理回路で実現

ファクタリングを行うと･･･

ファクタリング

x y z h i j a b

f

c d f

e

g











cd e g f



hij xyz ab xyz hij fg ef cd ab xyz hij abfg abef abcd f               

ファクタリング

• リテラル数が減る

• ファンイン数が減る

アルゴリズム

1. 共通積項を列挙する

2. リテラル数を最も減らす積項を選択する

3. 論理式を再構築し, 1,2を繰り返す

(3)

2010/11/15 多段論理合成 13

TVFG（二変数関数発生器）

Two-Variable Function Generator

2010/11/15 多段論理合成 14

TVFG

OVFG

一変数のすべての関数を生成するマクロ素子

TVFG

二変数以下のすべての関数を生成するマクロ素子

定理任意の論理関数は, ４値入力の論理和形で表現できる.





  r r S r S S S S S n

X

x

f

_

_V

_

 2 1 2 1 2 1 , , , 2 1

,





x1,x2, ,x



(n 2r) f  n  2010/11/15 多段論理合成 15 A B B A B A A B A B B A B A B A B A B B A B A B A A select select 2010/11/15 多段論理合成 16

TVFG

例題：

00 01 11 10 00 1 01 1 1 11 1 1 1 10 1 1



1 2



1 x, x X 



3 4



2 , x x X  論理式は・・・_{ } _{ } _{ } _{ } _{ } _{ } _{ } _{ }                11 2 10 1 10 2 10 1 01 2 10 1 11 2 01 1 10 2 01 1 01 2 01 1 11 2 00 1 00 2 00 1 X X X X X X X X X X X X X X X X f         簡単化       01,10,11 2 10 , 01 1 11 , 00 2 00 1

X

f





2010/11/15 多段論理合成 17

となるので, 通常の論理式を用いて表現すると

TVFG

  2 1 00 1

x

X



  4 3 11 , 00 2

x

X





  3 4 11 , 10 , 01 2

x

X





  2 1 10 , 01 1

x

X







x

1

x

2



x

3

x

4





x

1

x

2



x

3

x

4



f











が得られる.

2010/11/15 多段論理合成 18

TVFG

1 X 2 X 1 x 2 x 3 x 4 x 2 1x x 2 1 x x  4 3 x x  4 3 x x  1 x 1 x 2 x 2 x 3 x 3 x 4 x 4 x 2 1x x 2 1 x x 4 3 x x  4 3 x x  マクロ展開を用いる

(4)

2010/11/15 多段論理合成 19

論理式の割り算

2010/11/15 多段論理合成 20

論理式の割り算

定理 p次の多項式を , s次の多項式をとする. ならば, 次の条件を満たすq次多項式と r次多項式が一意的に定まる.

 

x 0 P S

 

x s p  1 Q

 

x

 

x R

 

x

P

   

x

Q

x

R

 

x

q

s

p

r

p

S





,





,

0 



商剰余 2010/11/15 多段論理合成 21

論理式の割り算

例題：

 

_ 3_ _1 x x x S

 

x  x2 P R

 

x 5

 

_ 2_2 _3 x x x Q w z xy F   z x P  z y Q  w R w z y Q   w z R  一意的に定まる一意的には定まらない 1．２． 2010/11/15 多段論理合成 22

論理式の割り算

代数的論理和形

ブール代数における特有の関係が生じない論理式. この場合, 商や余剰などは一意的に定まる. 定義おいて FとGが共通の変数を持たないとき, FとGの代数的論理積が定義できる. i p i f F



  1 j q j g G



  1  ij



i j



g f G F , ,



  x x x x x 0,  

論理式の割り算

定義 2つの代数的論理和形をFとPとする. としてにおいてRの積項数が最小のときこの割り算を弱い割り算(Weak Division)という. 弱い割り算ではQとRは一意的に定まる. アルゴリズム(弱い割り算) R P Q F  



f f ft



F ₁, ₂,_,



p p ps



P ₁, ₂,_,



u u ut



U ₁, ₂,_,



v v vt



V ₁, ₂,, としたとき j j j u v f   でUはFのリテラルのうちで積項Pにあるリテラルの積 でVはFのリテラルのうちで積項Pにないリテラルの積 P F Q /

論理式の割り算

 

_

i j p u j i

v

p

V



 



_is

V

p

i

Q

1 



Q

P

F

R







uj,vjですべてのリテラルを除去した場合は1

(5)

2010/11/15 多段論理合成 25

論理式の割り算

例題：

_F_ac_ad_ae_bc_bd_be_a_b b a P 



c d e



F P Q , ,  / b a R F 



ab



cd e



ab



a a a b b b b



U  , , , , , , V

  

a  c,d,e



 

b



c d ea



V  , , ,



c d ec d e a



V , , , , , ,

とすると

2010/11/15 多段論理合成 26

既約

論理式の割り算を行う際, リテラル数がなるべく減るような除数Pを求める. 論理和形で, すべての項に同じリテラルが現れない場合、それは既約である. 一つの積項からなるものは既約ではない. ad cd ad abc abd abc    d c b a cd ab d c     

既約でない

既約

2010/11/15 多段論理合成 27

カーネル(Kernel)

定義

Fを論理和形, cを積項とするとき, 既約な

商F/cをFの

カーネル

という. Fのカーネルの集合を

K(F)で表す.

例題： cde be ae F   bf be bd ae ad G     abc H

  

F a b cd



K   

  

G a b d ed e f ad ae bd be bf



K   ,  ,   ,    

 

H  K のとき 2010/11/15 多段論理合成 28

カーネル

ファクタリングとカーネルの比較

例題：

bc aeg H aef dg cg bg G f cde bde ade F           ファクタリングの場合共通積項はaeである. X=aeとおくと ae X bc Xg H Xf dg cg bg G f cde bde Xd F            リテラル数は

２３

2010/11/15 多段論理合成 29

カーネル

カーネルの場合 Fのカーネルはaｖ bｖ c, Gのカーネルはｂｖ cｖ d









bc aeg H aef g d c b G f de c b a F           FとGの共通カーネルはbｖ c X=bｖ c とおくと









c b X bc aeg H aef g d X G f de X a F           リテラル数は

1８

2010/11/15 多段論理合成 30

関数分解

Functional Decomposition

(6)

2010/11/15 多段論理合成 31

R. L. Ashenhurst (1957)

• 論理関数の分解理論

• f(X1,X2)=g(h(X1),X2)

• 分解表

Ｘ1

Ｘ２

2010/11/15 多段論理合成 32

関数分解

一般にn変数関数fを実現するにはゲート数が 個必要. nが大きいとき図のように分解できればゲート数を削減できる. n n / 2 H G X1 n1 h n2 X2 H G

X1

n1 m1 h n2 X2 g g 2010/11/15 多段論理合成 33

関数分解の用語

例：をXの分割, とする５変数関数の分解表の例



X1,X2



X 







4 5



2 3 2 1 1 , , , x x X x x x X   0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 010 0 01 10 0 1 111 1 11 11 1 0 101 1 10 01 1 1 0 10 0 01 10 X1 x1 x2 x3 x4 x5 X2 列複雑度分解の利得

2 







4 / 2 , 2 min 1 22  





_n n 2 , 3 2 1 n  n 2010/11/15 多段論理合成 34

分解表

11

10

01

00

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0 X1=(x1，x2，x3)

X2=(x4，x5)

列複雑度(column multiplicity)

• 分解表 f(X1,X2)の異なる列パターン数.

• μで表わす．

列複雑度（μ＝２）

11

10

01

00

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0 Ｘ

1 ＝（ｘ

1 ，ｘ２，ｘ３）

Ｘ２＝（ｘ４

，

ｘ５）

(7)

2010/11/15 多段論理合成 37

関数分解の原理（μ＝２）

1 1

1 0

0 1

0 0

ｘ４，ｘ５

1

0

1

0

1

0 ｈ

ｘ

1x2x3

0 1 1 1

1 1 1 0

1 1 0 1

0 1 0 0

0 0 1 1

0 0 1 0

1 0 0 1

0 0 0 0

ｈ

ｇ

2010/11/15 多段論理合成 38

ｘ

1 ｘ２

ｘ３

ｘ４

ｘ５

ｈ

ｆ

Ｈ

Ｇ

f

＝

g(h(x1,x2,x3),x4,x5)の実現

2010/11/15 多段論理合成 39

分解表

0

1

0

1

110

1

0

1

0

110

1

101

1

0

1

100

1

0

011

0

1

010

1

001

1

0

000

11

10

01

00 X2=(x3

，

x4

，

x5)

X1=(x1

，

x2)

μ＝３ 2010/11/15 多段論理合成 40

ｘ

1 ｘ

2 ｘ４

ｘ５

ｈ

ｆ

Ｈ

Ｇ

f

＝

g(h(x1,x2) ,x3,x4,x5)の実現

ｘ

3

2010/11/15 多段論理合成 41

列複雑度と回路構造μ＝２

Ｘ

1 Ｘ２

Ｇ

Ｈ

2010/11/15 多段論理合成 42

列複雑度と回路構造μ ≦

２ ｒ

Ｘ1

Ｘ２

Ｇ

Ｈ

ｒ

(8)

2010/11/15 多段論理合成 43

関数分解

例題：

0 0 1 1 x1 0 1 0 1 x2 x3x4x5 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 2 0 1 0   Hの関数 x1 x2 f h1 h2 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 2 1 0 列複雑度３ Hの出力数２ Gに対するマップ 00 01 11 10 x3x4x5 0 0 0 0 0 x 1 0 0 1 1 1 x 1 0 1 1 0 0 x 1 0 1 0 1 1 x 0 1 1 0 0 1 x 1 1 1 1 1 0 x 0 1 0 1 1 1 x 1 1 0 0 1 0 x 0 ドント・ケア入力変数は減らない 2010/11/15 多段論理合成 44

関数分解

H G x1 x2 h1 h2 x3 x4 x5 2010/11/15 多段論理合成 45

対称関数と関数分解

• 関数fが{X1}において部分対称．

– f(X)=g(h(X1),X2)の列複雑度は高々n1+1．

–

ｎ

1はＸ1の変数の個数．

• 重要な演算回路．

– 部分対称なものが多い．

2010/11/15 多段論理合成 46

ＳＹＭ６の設計

• ６入力1出力の対称関数．

• 入力の1の個数が２，３，または４のとき出

力が1で，その他の場合は，出力が0．

f

SYM6

x1

x2

x3

x4

x5

x6

SYM6 の分解による実現

• 入力変数を

X1=(x1,x2,x3),

X2=(x4,x5,x6)と分割．

• 完全対称関数：入力の1

の個数のみに依存．

• ＦＡ(full adder)．

– 1の個数を計数する３入力２出力回路． G ｆ FA FA h1 ｈ2 ｈ3 ｈ4 x1 x2 x3 x4 x5 x6

SYM6の実現（その２）

4

5

3

2

5

6

4

3

4

2

1

2

3

1

0

1

３

２

0

1

３

２

1

1 ₁

₁

h2 h1 h4 h3

1

(9)

2010/11/15 多段論理合成 49

SYM6の実現（その３）

1

1 ₁

₁

h2 h1 h4 h3 2010/11/15 多段論理合成 50

回路の変換

2010/11/15 多段論理合成 51

回路の変換

局所的変換法(Local Transformation)

与えられた多段論理回路の一部に対して, ブール代数の規則を繰り返し適用することにより簡単化を行う方法 •定数削除 •未使用ゲート削除 1 1 1

など・・・

2010/11/15 多段論理合成 52

回路の変換

•1入力ANDおよび1入力ORの削減 •インバータ削減 •重複ゲート削減 2010/11/15 多段論理合成 53

回路の変換

•ゲート併合 •因子共有化 x y z u x y z v x y z u v 2010/11/15 多段論理合成 54

回路の変換

•否定ゲート付加による簡単化 •冗長な接続線の除去 x y x y y x xy y x xy xy xi xi xi

(10)

2010/11/15 多段論理合成 55

講義概要

• 多段論理回路簡単化とドント・ケア

– Satisfiability don’t care (SDC)

– Observability don’t care (ODC)

– トランスダクション法

• ブール関係

• タイミング最適化

2010/11/15 多段論理合成 56

多段論理回路の設計

回路を小さな部分に分割し, 別々に設計

ドント・ケアが生じる

ドント・ケアを用いて回路を簡単化

2010/11/15 多段論理合成 57

Satisfiability Don’t Care (SDC)

A

B

X1 X1 X2 X3 X2 X3 h y Z

• 回路Aが既存, 回路B

を設計中とする

• 回路Aの出力関数

h = h(x1,x2,x3)

• 回路Bの出力関数

z = z(x1,x2,x3,y)

y = h は中間変数

Bの入力(x1,x2,x3,y)には決して

あり得ない組み合わせが存在

この組み合わせが

Satisfiability don’t care

図多段論理回路の構成

2010/11/15 多段論理合成 58

Satisfiability Don’t Care (SDC)

)

(

0

h

y

SDC

k i







_

回路Aが多出力(h

1

,h

2

,…h

k

)

の時

,

y

h

SDC





中間変数が多いとSDCは非常に複雑になり, 簡単化は困難

上式は

ｈ

と

ｙ

の値が一致しない組み合わせを示す

例

A

B

X1 X1 X2 X2 h1 y1 Z

2

1

2 x

x

h





z



x

1 

x

2 実現する時, SDCを求め, 回路Bを簡単化せよ

2

1

1 x

x

h





下の回路において, 回路Aが関数

を生成し, 回路Bが

h2 y2 図実現する回路

解

2 )

2

1 (

2 )

2

1 (

1 )

2

1 (

1 )

2

1 (

)

2

2 (

)

1

1 (

y

x

y

x

y

x

y

x

y

h

y

h

SDC



















*

x1

x2

y1

y2

SDCのカルノー図

(11)

2010/11/15 多段論理合成 61

解

*

x1

x2

y1

y2

SDCのカルノー図

*

1

*

x1

x2

y1

y2

1 zのカルノー図

1

2 y

y

z





となる

2010/11/15 多段論理合成 62

Observability Don’t Care (ODC)

• 回路Bが既存, 回路Aを

設計中とする

• 回路Bのため回路Aの出

力値が外部出力値zに影

響を与えない場合がある

A

B

X1 X1 X2 X3 X2 X3 h y Z

z の値に影響を与えないような回路Ｂの入力の集合を

Obsevability don’t care

という

1 )

(|

)

(|





z

y

z

y

ODC

2010/11/15 多段論理合成 63

例

2

3

2

1 x

y

x

y

x

z













3

1

2

1 x

x

h









を生成する時, ODCを求め,

下図のような回路において, 回路Bが関数

を生成し, 回路Aが

A

B

X1 X1 X2 X2 y1 Z X3 X3

回路Aを簡単化せよ

2010/11/15 多段論理合成 64

解

*

x1

x2

x3

ODCのカルノー図 3 2 1 3 2 1 ) 2 2 1 ( ) 3 2 1 3 2 1 ( 1 ) 2 2 1 ( ) 3 2 1 ( 1 ) (| ) (| x x x x x x x x x x x x x x x x x x x x y z y z ODC                         

*

1

1 x1

x2

x3

h のカルノー図

1

2010/11/15 多段論理合成 65

解

*

x1

x2

x3

回路Ａのカルノー図

*

1

3 x

h



となる

2010/11/15 多段論理合成 66

トランスダクション法

Transduction法

• 許容関数の概念を用いて, 回路を簡単化

する手法

• 1970年イリノイ大学の室賀教授らが考案

• 1990年代に, BDDによる論理関数表現法

が開発され, 実際の回路設計に使用され

た

(12)

2010/11/15 多段論理合成 67

トランスダクション法による回路

の簡単化

fd

fb

fa

 fc

=(0,0,1,1)

=(0,1,0,1)

=(0,0,0,1)

=(0,0,1,1)

fc

=(0,0,,)

a

b

c

_d

2010/11/15 多段論理合成 68

例：ＥＸＯＲ回路の簡単化

c

d

e

g

b

a

f

(0,0,1,1)

(0,1,0,1)

(1,0,1,0)

(1,1,0,0)

(0,0,1,0)

(0,1,0,0)

(0,1,1,0)

2010/11/15 多段論理合成 69

トランスダクション法

c

d

e

g

b

a

f

(0,0,1,1)

(0,1,0,1)

(,,1,0)

(,1,,0)

(0,0,1,0)

(0,1,0,0)

(0,1,1,0)



f

_c

=(1,0,1,0)である必要はなく, f

_c

=(,*,1,0)であればよい



この時, f

_c

*を f

_c

の

許容関数

という

2010/11/15 多段論理合成 70

トランスダクション法

e

g

b

a

(0,0,1,1)

(0,1,0,1)

(1,1,1,0)

(0,0,1,0)

(0,1,0,0)

(0,1,1,0)

h

共通な関数 f

_h

=(1,1,1,0)を用いると, 二個のイン

バータを1個のNANDゲートに置換できる

ブール関係

Boolean Relation

関係と関数

• 関係（Ｒｅｌａｔｉｏｎ）

– 直積

ＡＸＢ

の部分集合

• 関数（Ｆｕｎｃｔｉｏｎ）

– 関係の特別のもの

–

Ａ→Ｂ

(13)

2010/11/15 多段論理合成 73

例：加算器＋比較回路

• 二つの２ビットの数を加算 • 加算結果 > 3 ⇒ (w1,w0) = (0,1) • 加算結果 = 3 ⇒ (w1,w0) = (0,0) • 加算結果 < 3 ⇒ (w1,w0) = (1,0) を生成する

加算器

比較回路

x

₁

z

₀

z

₁

z

₂

x

₀

y

₁

y

₀

w

₀

w

₁ 図実現する回路 2010/11/15 74

2ビット加算器

の真理値表

0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 z2 0 1 1 0 1 1 0 1 1 0 0 z1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 y1 1 0 1 0 1 0 1 0 y0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 z0 x0 x1 2010/11/15 多段論理合成 75

比較回路の真理値表

1 1 1 1 0 0 0 0 w1 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 w2 z0 z1 z2 2010/11/15 多段論理合成 76

比較回路の真理値表

1 1 1 1 0 0 0 0 w1 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 w2 z0 z1 z2 比較回路の仕様

{000,001,010} は

同値類を形成

{011}も

同値類

{100,101,110,111}も

同値類を形成

77

2ビット加算器のブール関係による記述

{100,101,110,111} 1 1 1 1 {100,101,110,111} 0 1 1 1 {100,101,110,111} 0 1 0 1 {100,101,110,111} 1 1 0 1 {011} 0 0 1 1 {100,101,110,111} {011} {000,001,010} ｛100,101,110,111} {011} {000,001,010} {000,001,010} {011} {000,001,010} {000,001,010} {000,001,010} z2 z1 z0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 y1 1 0 1 0 1 0 1 0 y0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 x0 x1

入力0000の時,

出力は000,001,010のいずれ

でも可

入力に対して, 出力が一意

的に定まらない

ブール関係

2010/11/15 多段論理合成 78

ブール関係

• 最小表現を求める手法が開発されている

• 通常のドント・ケア手法よりも表現が簡単になる

ブール関係を満たす表現の簡単化の結果 0 0 0 0 1 1 1 z2 0 0 1 1 0 0 0 z1 -1 -1 -1 y1 -1 -1 1 y0 0 1 1 1 -1 1 -0 1 -0 -0 -1 0 1 -z0 x0 x1

(14)

2010/11/15 多段論理合成 79

タイミング最適化

2010/11/15 多段論理合成 80

論理設計の目標

• ハードウェアのコストの削減

– ゲート数

– 接続線数

• 遅延時間の削減

特に遅延時間を削減したい

2010/11/15 多段論理合成 81

遅延の要因

• 回路の段数

• ゲートの種類

• ファンアウト

• 配線長

回路の段数

について着目する

2010/11/15 多段論理合成 82

遅延最小化のモデル

•各ゲートの遅延時間は等しい

•配線遅延は無視できる

回路の遅延時間は,

信号が入力から出力まで

伝播する際に通過するゲートの最大数に比例.

回路の入出力間の経路上でゲート数が最大となる経路

クリティカル・パス

Critical Path

x

1 ２５３４６ Y Z W クリティカル・パス上のゲート数を回路の段数という上例では回路の段数＝５

回路の段数≠回路の遅延時間

となる場合があるしかし図５段論理回路

x

1 ２５３４６ 1 Z 1

xの変化が出力に伝播するためには

Z = Y = 1

例

５段論理回路

(15)

2010/11/15 多段論理合成 85

例

NANDゲートでは, 出力関数を変化させず定数1を

除去できるので, 下図のように変形できる

x

1 ２５３４６ Z

1 ゲート３の出力値は, xの値にかかわらず1

簡単化した５段論理回路 2010/11/15 多段論理合成 86

例

経路1, ２, ３, ５，６は決して

活性化されない

x

1 ２５３４６ Z

決して活性されない信号経路のことを

フォールス・パス（false path）

という

フォールス・パス 2010/11/15 多段論理合成 87

フォールス・パスの存在のために,

回路の遅延時間

遅延時間 ≦ 回路の段数×ゲートの遅延時間

となる