JPH0997281A - パストランジスタ論理設計方法 - Google Patents

Abstract

(57)【要約】 【課題】 低消費電力かつ高速で回路規模が小さいパス
トランジスタ論理回路を設計する方法を提供する。 【解決手段】 論理仕様から通常の論理ゲートから構成
される論理回路を生成するステップ２と、前記論理回路
の各入力信号の信号遷移確率を評価するステップ３と、
前記入力信号を信号遷移確率の高いものから低いものへ
順序付けするステップ４と、前記論理回路に対して、前
記入力信号の内の信号遷移確率の高いものから順にシャ
ノン展開処理を適用することにより、前記論理回路に対
応する２分決定グラフを生成するステップ５と、前記２
分決定グラフの各ノードをパストランジスタによる２入
力セレクタ回路に置き換えることによりテクノロジー独
立なパストランジスタ論理回路を生成するステップ６と
を有するパストランジスタ論理設計方法である。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はＬＳＩ等の回路の設
計を効率化する設計自動化技術に係わり、特に回路の機
能記述を基にパストランジスタ論理回路を生成する、プ
ロセステクノロジーに依存しない段階での論理設計方法
に関するものである。

【０００２】

【従来の技術】最近、従来広く使われてきたＣＭＯＳ論
理よりも高速、低消費電力、小面積という特長を持つパ
ストランジスタ論理が注目されてきている。

【０００３】一方、大規模化するＬＳＩの設計工数増大
の問題に対処するため、ハードウェア記述言語を用いて
ＬＳＩを機能記述し、自動論理合成装置を用いて論理回
路を自動設計するトップダウン設計手法が普及してき
た。機能記述からの自動論理合成技術は、このトップダ
ウン設計手法の鍵となる技術であり、従来から精力的に
研究開発が行われている。

【０００４】このようにトップダウン設計手法が広く普
及した現在、たとえ前述のパストランジスタ論理がＣＭ
ＯＳ論理よりも優れた特性を持つものであったとして
も、自動設計することができずに人手により注意深く設
計されなければならないのであれば、論理設計技術とし
て広く普及することはありえず、一部の特殊な回路に限
定して使用されるに留まるものと考えられる。

【０００５】従って、パストランジスタ論理の優れた特
性を活かしてＬＳＩの高性能化、低コスト化を図る上
で、その自動設計技術を確立することが不可欠である。

【０００６】従来のパストランジスタ論理設計方法の例
としては、例えば「Lean Integration: Achieving a Qu
antum Leap in Performance and Cost of Logic LSIs」
（IEEE 1994 Custom Integrated Circuits Conferenc
e）を挙げることができる。

【０００７】以下では上記文献に記載されている設計フ
ローを説明する。

【０００８】まず最初にハードウェア記述言語等で表現
された論理仕様から２分決定グラフを生成する。

【０００９】次に前記グラフのノードをパストランジス
タに置き換え、トランジスタネットワークを構成する。

【００１０】次にネットワーク内部の適正箇所に電位レ
ベルの回復と電流増幅を目的としたバッファの挿入を行
う。

【００１１】次に生成した回路にあらかじめ用意された
リーンセルを割り当て、ネットリストを出力する。

【００１２】以上の処理フローの内、最初の２ステップ
は特定のセルライブラリに依存しないテクノロジー独立
な処理であり、後の２ステップはテクノロジー依存の処
理である。

【００１３】

【発明が解決しようとする課題】本発明は上記の従来手
法の内、テクノロジー独立な処理における課題を解決し
ようとするものである。

【００１４】このような課題としては以下のようなもの
を挙げることができる。

【００１５】（１）低消費電力化 半導体集積回路技術の進歩に伴い１チップに集積可能な
素子数が数百万Trを越え、その結果ＬＳIの発熱が大き
な問題となってきている。また、携帯機器の市場拡大等
の環境変化に伴い、ＬＳＩの低消費電力化が重要課題と
なってきている。

【００１６】これはＣＭＯＳよりも低消費電力であるこ
とを特長とするパストランジスタ論理においても同様で
ある。

【００１７】（２）高速化 パストランジスタ論理はＣＭＯＳ論理と比べて高速であ
ると言われているが、実際の回路性能を決めるのは特定
のクリティカルパスの遅延である場合が多い。例え多く
のパスで平均的にＣＭＯＳ回路よりも高速であっても、
性能を決めるこれらのクリティカルパスの遅延が大きけ
れば回路としての性能は低くなってしまう。

【００１８】（３）回路規模削減 生成したＢＤＤの各ノードをパストランジスタに置き換
える従来の設計手法では、最終的に生成される回路規模
はＢＤＤのサイズに大きく依存する。一方ＢＤＤのサイ
ズはシャノン展開処理における入力信号順序に依存する
ことが知られている。従って回路規模を削減するために
は、入力信号順序を最適化する必要があるが、これは決
定困難な問題であり、「論理関数を表現する２分決定グ
ラフの最小化」（情報通信学会技術報告COMP91-15 p2
7）に記載されているように、現状では入力数が１７程
度を越えた場合に有効な手法は知られていない。

【００１９】現実的な回路では入力信号数は軽く１００
を越えてしまうため、このような回路の入力信号順序を
最適化することは不可能である。その結果ＢＤＤのサイ
ズは最適なものと比べて大きくなってしまい、最終的な
回路規模も増大してしまう。

【００２０】また、回路全体を一体のＢＤＤに変換する
方法が最小の回路を生成する保証は無い。

【００２１】本発明の目的は、論理仕様からＢＤＤを生
成する処理を改善することにより、従来のパストランジ
スタ論理設計手法では困難であった回路の低消費電力
化、高速化、回路規模削減を実現することにある。

【００２２】

【課題を解決するための手段】本発明の方法は、与えら
れた回路の論理仕様に基づいて、パストランジスタ論理
回路を設計する方法であって、前記論理仕様に基づいて
論理ゲートを含む論理回路を生成するステップと、前記
論理回路の各入力信号の信号遷移確率を評価するステッ
プと、前記入力信号を信号遷移確率の高いものから低い
ものへ順序付けするステップと、前記論理回路に対し
て、前記入力信号の内の信号遷移確率の高いものから順
にシャノン展開処理を適用することにより、前記論理回
路に対応する２分決定グラフを生成するステップと、前
記２分決定グラフの各ノードをパストランジスタによる
２入力セレクタ回路に置き換えることによりテクノロジ
ー独立なパストランジスタ論理回路を生成するステップ
とを包含し、前記信号遷移確率の高い入力信号と出力信
号との間の論理段数を削減することにより、生成した回
路の消費電力を削減することを特徴とする。これにより
上記目的が達成される。

【００２３】前記方法は、前記与えられた回路の入出力
信号間に許容される遅延時間を規定する遅延時間制約と
パストランジスタ論理回路の平均遅延時間に基づいて、
前記パストランジスタ論理回路に許容される段数を規定
する段数制約を計算するステップをさらに包含し、前記
論理回路の前記入力信号は、前記段数制約と前記信号遷
移確率とを考慮して順序付けられてもよい。

【００２４】前記段数制約は、前記信号遷移確率よりも
高い優先順位を有していてもよい。

【００２５】本発明の他の方法は、与えられた回路の論
理仕様に基づいて、パストランジスタ論理回路を設計す
る方法であって、前記論理仕様に基づいて論理ゲートを
含む論理回路を生成するステップと、前記与えられた回
路の入出力信号間に許容される遅延時間を規定する遅延
時間制約とパストランジスタ論理回路の平均遅延時間に
基づいて、前記パストランジスタ論理回路に許容される
段数を規定する段数制約を計算するステップと、前記段
数制約を考慮して、シャノン展開のための最適な入力信
号の順序を決定するステップと、前記論理回路に対し
て、前記入力信号の順序に従ってシャノン展開処理を適
用することにより、前記論理回路に対応する２分決定グ
ラフを生成するステップと、前記２分決定グラフの各ノ
ードをパストランジスタによる２入力セレクタ回路に置
き換えることによりテクノロジー独立なパストランジス
タ論理回路を生成するステップとを包含し、前記遅延時
間制約が与えられた入力信号と出力信号との間のパスト
ランジスタ段数を制限することにより、生成した回路が
与えられた遅延時間制約を満たすことを特徴とする。こ
れにより上記目的が達成される。

【００２６】本発明の他の方法は、与えられた回路の論
理仕様に基づいて、パストランジスタ論理回路を設計す
る方法であって、前記論理仕様に基づいて論理ゲートを
含む論理回路を生成するステップと、前記論理回路に論
理最適化処理を行い、冗長回路を削除するステップと、
分割された複数のサブ回路のそれぞれの入力信号の数を
考慮して、前記最適化された論理回路を複数のサブ回路
に分割するステップと、生成される２分決定グラフの最
小化を目的として、前記複数のサブ回路のそれぞれにつ
いてシャノン展開のための最適な入力信号の順序を決定
するステップと、前記複数のサブ回路のそれぞれについ
て、前記入力信号の順序に従ってシャノン展開処理を適
用することにより、前記論理回路に対応する２分決定グ
ラフを生成するステップと、前記複数のサブ回路のそれ
ぞれについて、前記２分決定グラフの各ノードをパスト
ランジスタによる２入力セレクタ回路に置き換えること
により、テクノロジー独立なパストランジスタ論理回路
を生成するステップとを包含し、個々のサブ回路の入力
信号の数を制限することにより最適な入力信号順序の決
定を可能にして、生成される回路を最小化することを特
徴とする。これにより上記目的が達成される。

【００２７】前記方法は、前記サブ回路の前記入力信号
のそれぞれの信号遷移確率を評価するステップをさらに
包含し、前記サブ回路の前記入力信号の順序は、前記信
号遷移確率に基づいて決定されてもよい。

【００２８】前記方法は、前記与えられた回路の入出力
信号間に許容される遅延時間を規定する遅延時間制約と
パストランジスタ論理回路の平均遅延時間に基づいて、
前記パストランジスタ論理回路に許容される段数を規定
する段数制約を計算するステップをさらに包含し、前記
サブ回路の前記入力信号の順序は、前記段数制約に基づ
いて決定されてもよい。

【００２９】前記方法は、前記与えられた回路の入出力
信号間に許容される遅延時間を規定する遅延時間制約と
パストランジスタ論理回路の平均遅延時間に基づいて、
前記パストランジスタ論理回路に許容される段数を規定
する段数制約を計算するステップをさらに包含し、前記
サブ回路の前記入力信号の順序は、前記段数制約と前記
信号遷移確率とに基づいて決定されてもよい。

【００３０】以下、作用を説明する。

【００３１】本発明は上記の構成を取ることにより、与
えられた論理仕様に対応したＢＤＤを生成する処理にお
いて、入力信号のうち遷移頻度の高いものから先にシャ
ノン展開し、遷移頻度の低いものを後でシャノン展開す
る。

【００３２】ＢＤＤでは先にシャノン展開した入力信号
に対応するノード程出力側に近くなるため、ＢＤＤの各
ノードをパストランジスタに変換した後では、遷移頻度
の高い入力ほど出力との間の論理段数が小さくなる。

【００３３】遷移頻度の高い入力信号と出力の間のパス
に含まれる内部信号も遷移頻度が高くなることが多いた
め、このようなパスの論理段数を削減することにより、
回路に含まれる全ての信号の遷移頻度の和を削減するこ
とができる。

【００３４】また、ＢＤＤは他のグラフと同様に根から
枝になるに従って広がっていくことが多いため、遷移確
率の高い入力に接続されるパストランジスタ数が少なく
なり、その意味でも全体の遷移頻度の和を削減できる。
これらの結果として回路の消費電力を低減することが可
能になる。

【００３５】また、本発明では与えられた入出力間の遅
延時間制約とあらかじめ求めておいたパストランジスタ
回路の平均遅延時間から、前記遅延時間制約に対応する
パストランジスタ段数制約を計算する。

【００３６】ＢＤＤの各ノードをパストランジスタに置
き換える本発明の設計方法では、ＢＤＤを生成する時の
シャノン展開の入力信号順序が入出力間のパストランジ
スタ段数に直接関係しているため、前記パストランジス
タ段数制約は入力信号順序の制約に置き換えることがで
きる。

【００３７】全ての遅延時間制約について対応するパス
トランジスタ段数制約を求めた後、これらの制約を満た
す入力信号のシャノン展開順序を決定する。このように
して求めた順序に従ってシャノン展開してＢＤＤを生成
し、それをパストランジスタ回路に変換した結果は、前
記パストランジスタ段数制約を満たしている。引続き行
われるテクノロジー依存処理において注意深く設計する
ことにより、与えられた遅延制約を満たした回路を設計
することができる。

【００３８】また、本発明ではＢＤＤのサイズを最小化
するための最適入力信号順序決定の困難さを考慮して、
最初に論理仕様から通常の論理回路に変換する段階で、
複数のサブ回路に分割しておく。ここで各サブ回路の入
力数はあらかじめ決められた数以下になるように注意し
て分割する。

【００３９】このような設計方法では、回路全体は１つ
のＢＤＤとはならず、複数のＢＤＤ間では論理の冗長性
を取り除くことができないため、サブ回路に分割する前
に通常の論理回路の段階であらかじめ論理最適化処理を
かけておく。

【００４０】このようにして入力数の制限されたサブ回
路では、シャノン展開の入力変数順序を最適化すること
が可能で個々のサブ回路に対応するＢＤＤのサイズを最
小化することができる。

【００４１】一方、回路全体を１つのＢＤＤに変換する
場合には、最適な入力変数順序を見つけることができず
ＢＤＤのサイズが最小化されない可能性が高いため、サ
ブ回路に分割した方が全体として最終的なパストランジ
スタ回路の規模も小さくなる。

【００４２】また、回路によっては一体のＢＤＤに変換
した後パストランジスタ論理回路を生成するよりも、複
数のＢＤＤから構成されるネットワークに変換した後パ
ストランジスタ論理回路に変換した方が回路規模が小さ
くなる場合も多い。

【００４３】

【発明の実施の形態】以下、図面を参照しながら本発明
の実施の形態を説明する。

【００４４】（実施の形態１）図１は本発明によるパス
トランジスタ論理設計方法の処理の流れを示すための処
理フロー図である。

【００４５】図中、論理仕様１は設計しようとする回路
の論理的仕様を、ハードウェア記述言語や論理式といっ
たフォーマットで記述したものである。

【００４６】図４はハードウェア記述言語ｖｅｒｉｌｏ
ｇＨＤＬを用いた機能記述の例である。これはａとｂと
いう２つの４ビットの入力の値を加えた結果をｙに出力
する４ビット加算器の動作を記述している。本実施の形
態は組合せ回路であり、ＢＤＤを用いる本発明の設計方
法で直接処理することが可能である。しかし順序回路も
組合せ回路とフリップフロップに分割することが可能で
あるため、その組合せ回路部分に対して本発明の設計方
法を適用することができる。

【００４７】図５は前記４ビット加算器の出力ｙの最上
位ビットｙ３を表現する論理式の一例である。ここで”
＆”は論理積、”｜”は論理和、”＠”は排他的論理和
を表わす演算子である。論理式も前記の機能記述と同
様、論理仕様の一例である。あるいは、論理仕様は他の
形式で表現されてもよい。

【００４８】ステップ２ではハードウェア記述言語（Ｈ
ＤＬ）による機能記述や論理式といった論理仕様を基に
して、通常のゲートから構成される論理回路を生成す
る。本ステップには人手で論理設計する方法や論理合成
ツールを用いる方法があり、いずれの方法でもよいが、
本実施の形態では後者を取る。

【００４９】図６は図５で示した論理式からステップ２
の処理により生成した論理回路の一例である。ここでは
ＡＮＤやＯＲといった論理ゲートのネットワークにより
回路が表現されている。本実施の形態ではこの１出力論
理回路を例として説明していくが、多出力論理回路であ
っても基本的には同じように扱うことができる。

【００５０】ステップ３では、ステップ２で生成された
論理回路の各入力の信号遷移確率の評価を行う。通常、
論理回路はクロックに同期して動作する同期式で設計さ
れる場合がほとんどである。この場合回路中の全ての信
号はクロックに同期して値が決定され、あるクロックサ
イクルでは値が前サイクルとは変化し、別のクロックサ
イクルでは前サイクルの値を保持することになる。信号
遷移確率とは値が変化するクロックサイクル数を全クロ
ックサイクル数で割ったもので定義される。

【００５１】論理回路中の各信号の消費電力は、（数
１）で与えられる。（数２）という関係があるので、各
信号の消費電力は前記信号遷移確率に比例することがわ
かる。回路全体の消費電力は回路の各信号の消費電力の
総和になるため、回路を低消費電力化するには回路の各
信号の信号遷移確率を低減することが課題となる。

【００５２】

【数１】Ｐ＝(1/2)・Ｃ・Ｖｄｄ²・ＳＷＲ Ｃ：信号の負荷容量、Ｖｄｄ：回路の電源電圧、ＳＷ
Ｒ：信号の単位時間当りの遷移回数

【００５３】

【数２】ＳＷＲ＝ＳＴＲ／Ｔｃｙｃｌｅ ＳＴＲ：信号遷移確率、Ｔｃｙｃｌｅ：クロックサイク
ル時間 前記論理回路が設計しようとする回路全体である場合に
は、その入力は全体回路の外部入力であり、その信号遷
移確率は回路に入力される信号の仕様により決定され
る。しかし、通常回路は階層的に設計され、サブ回路毎
に論理設計されることが多い。この場合にはサブ回路の
入力の信号遷移確率は回路全体の外部入力に与えられる
信号の仕様と前記サブ回路に接続される周辺のサブ回路
の論理により概略決定される。この信号遷移確率を評価
するにはいくつかの手法があるが、本実施の形態では論
理シミュレーションにより評価する。

【００５４】図７に論理シミュレーションにおいて入力
信号に与えるテストベクタの一例を示す。各行が１つの
ベクタで、あるクロックサイクルに入力に与えられる信
号を記述している。ベクタの各数字は位置で対応する入
力信号の値を表わしている。最初の行が第１クロックサ
イクルのベクタで、次の行が第２クロックサイクルのベ
クタというように順番に記述している。

【００５５】各クロックサイクルの入力値が決まると、
それから論理演算することにより、各クロックサイクル
における回路の各内部信号値が決定される。各クロック
サイクルの信号値を１つ前のサイクルの値と比較すれ
ば、信号が変化したか否かが決まるので、信号遷移確率
を算出できる。この内部信号の中にはサブ回路の入力信
号も含まれているので、これによりサブ回路の入力の信
号遷移確率が得られることになる。

【００５６】この論理シミュレーションによる方法で信
号遷移確率を精度よく評価するためには、実際に使用さ
れる状況を正しく反映した適切なテストベクタを準備す
る必要がある。

【００５７】ステップ４ではステップ３で評価した各入
力の信号遷移確率が高いものから順に入力信号を順序付
ける。図８に順序付けられた入力信号のリストを示す。

【００５８】ステップ５ではステップ２で生成した論理
回路に対して、ステップ４で決定した順序に従ってシャ
ノン展開を実行して２分決定グラフ（ＢＤＤ）を生成す
る。

【００５９】論理関数ｆの入力変数ｐによるシャノン展
開とは、ｆにおける入力ｐを１に固定した論理関数をｆ
[p=1]、ｆにおける入力ｐを０に固定した論理関数をｆ
[p=0]で表わす時、（数３）に示す等式が成立すること
を利用して、左辺を右辺に変換する。左辺の論理はｐが
１ならばｆ＝ｆ[p=1]、ｐが０ならばｆ＝ｆ[p=0]という
２者択一論理になっていることがわかる。ステップ２で
生成した論理回路は、（数４）の論理関数に対応してい
る。順序に従って、y3をa0でシャノン展開すると、（数
５）および（数６）となり、（数７）と展開される。

【００６０】

【数３】ｆ＝ｐ＆ｆ[p=1]｜＾ｐ＆ｆ[p=0] ”＆”：論理積、”｜”：論理和、”＾”：論理反転

【００６１】

【数４】y3 = ((a0&b0&(a1|b1)|(a1&b1))&b2 |(a0&b0&
(a1|b1)|(a1&b1)|b2)&a2) @ a3 @ b3

【００６２】

【数５】y3[a0=1] = ((b0&(a1|b1)|(a1&b1))&b2 |(b0&
(a1|b1)|(a1&b1)|b2)&a2) @ a3 @ b3

【００６３】

【数６】y3[a0=0] = ((a1&b1&b2) | ((a1&b1)|b2)&a2)
@ a3 @ b3

【００６４】

【数７】y3 = a0 & y3[a0=1] | ^a0 & y3[a0=0] さらに引き続いてb0でシャノン展開すると、（数８）と
なる。一方、y3[a0=0]はb0を含まないので、シャノン展
開の必要はない。従って、（数９）と展開される。

【００６５】

【数８】y3[a0=1][b0=1] = ((a1|b1|(a1&b1))&b2 |(a1|
b1|(a1&b1)|b2)&a2) @ a3 @ b3 y3[a0=1][b0=0] = ((a1&b1&b2) | ((a1&b1)|b2)&a2) @
a3 @ b3

【００６６】

【数９】y3 = a0 & b0 & y3[a0=1][b0=1] | a0 & ^b0 &
y3[a0=1][b0=0]| ^a0 & y3[a0=0] さらに引き続いて、a1、b1、a2、b2、a3、b3についてシ
ャノン展開を実行する。

【００６７】図９にこのようにして生成されたＢＤＤを
示す。ＢＤＤの非終端ノード（丸いノード）はノード中
に記述された入力変数でシャノン展開された１つの論理
関数に対応している。各ノードから上方に延びるエッジ
は出力エッジで、そのノードが表わす論理関数を上方の
ノードに伝える。一方、各ノードから下方に延びるエッ
ジには１と書かれたもの（１エッジ）と０と書かれたも
の（０エッジ）がある。前者はシャノン展開における入
力変数を１に固定した論理関数に対応するノードに接続
され、後者は入力変数を０に固定した論理関数に対応す
るノードに接続される。

【００６８】すなわち、一番上のノード３１は論理回路
の出力y3に対応している。ノード３２はy3の論理関数に
おいて入力変数a0を１に固定した論理関数に対応してい
る。また、終端ノード（四角いノード）には１と記述さ
れたものと０と記述されたものがあるが、それぞれ論理
定数１と０に対応している。ノード３５は０エッジが定
数１に接続され、１エッジが定数０に接続されているの
で、対応する論理関数は、（数１０）であることがわか
る。同様にノード３６は論理関数b3に対応している。ノ
ード３３に対応する論理関数は、（数１１）である。

【００６９】

【数１０】b3 & 0 | ^b3 & 1 = ^b3

【００７０】

【数１１】a3 & ^b3 | ^a3 & b3 = a3 @ b3 ステップ６ではステップ５で生成したＢＤＤをパストラ
ンジスタ論理回路に変換する。前述したようにＢＤＤの
各ノードは２者択一論理であり、一方、パストランジス
タ論理は２入力セレクタを基本として構成されるため、
図１０に示す変換をＢＤＤの各ノードに適用することに
より、対応するパストランジスタ回路を得ることができ
る。

【００７１】図１１に図９のＢＤＤから変換したパスト
ランジスタ論理回路を示す。図１１より信号遷移確率が
高いa0やb0のような入力程、出力y3までのパストランジ
スタ段数が小さく、逆にa3やb3のように信号遷移確率の
低い入力では出力までのパストランジスタ段数が大きく
なっており、低消費電力化されていることがわかる。

【００７２】実際には図１１のように多くのパストラン
ジスタを直列に接続することはできず、適当な箇所に電
位の回復と電流増幅のためのバッファを挿入する必要が
あるが、それは本発明に係わるテクノロジー独立な論理
設計ステップではなく、それに続くテクノロジー依存の
論理設計ステップで処理されることになる。従って最終
的なパストランジスタ論理回路における入出力間のパス
トランジスタ段数や内部信号の単位時間当りの遷移回数
はこの段階では見積ることはできないが、各入力から出
力までの相対的な距離は最終的な回路においても保存さ
れる。

【００７３】図１２は、本実施の形態のように信号遷移
確率による入力信号の順序付けを行わずに、「計算機上
でのＢＤＤの処理技法」（情報処理 vol.34 No.5 p59
3）に記載されているように、出力を制御する力の強い
入力から先に、また、局所計算性のある入力どうしを近
い順にシャノン展開していくという方法（このようにす
ると生成されるＢＤＤの規模が小さくなることが報告さ
れている。）を取った場合に、ステップ２で生成した論
理回路をＢＤＤに変換した結果である。

【００７４】図１３に図１２のＢＤＤから変換したパス
トランジスタ論理回路を示す。図１３より、本実施の形
態による結果（図１１）に比べて信号遷移確率が高いa0
やb0のような入力から出力y3までのパストランジスタ段
数が大きくなっていることがわかる。前述したように、
信号遷移確率が高い入力から出力に至るパスに含まれる
内部信号は遷移頻度が高くなるため、図１３の結果は本
実施の形態による結果に比べて消費電力が大きくなる。

【００７５】実際、「Technology Decomposition and M
apping Targeting Low Power Dissipation」(30th IEEE
Design Automation Conference p68)に記載された方法
で両者の回路中に含まれる全信号の信号遷位確率の和を
見積った結果、本実施の形態の結果が11.4であるのに対
して、図１３の結果は16.6と３割程度削減されているこ
とがわかり、本実施の形態の方法が消費電力低減に大き
な効果を持つことがわかる。

【００７６】（実施の形態２）図２は本発明によるパス
トランジスタ論理設計方法の処理の流れを示すための処
理フロー図である。本実施の形態の論理仕様１と通常ゲ
ートによる論理回路を生成するステップ２は前記実施の
形態１のものと同様であるため、ここでは説明を省略す
る。

【００７７】通常、論理回路設計においては、与えられ
た論理仕様１を満足させる必要があるが、それだけでは
なく、回路が満たすべき遅延時間制約１３を与えられる
ことが多い。本実施の形態のような組合せ回路設計では
遅延時間制約は図１４に示されるように入力から出力ま
での最大遅延値で与えられるのが普通である。

【００７８】ここでは入力a0から出力y3までの遅延が2.
0ns以下、入力b0から出力y3までの遅延が1.5ns以下でな
ければならないことが記述されている。a0、b0以外の入
力に対する遅延制約は与えられていない。遅延制約とし
ては全入力から全出力までの最大遅延値の形式で与えら
れることも多いが、例えば特定の入力信号が他の入力信
号よりも遅れる等の理由で、本例のように特定の入力に
対して遅延制約を与えることも実際の設計ではよく行わ
れる。

【００７９】ステップ１４では与えられた遅延時間制約
を元に、入出力間のパストランジスタ段数制約を計算す
る。そのためにはあらかじめ何らかの方法でパストラン
ジスタ１段当りの平均遅延時間を求めておく必要があ
る。通常、これらの値は設計しようとする回路の性質に
より変動するため、できるだけ多くの回路について統計
を取ることにより、信頼性の高い値を得ておくことが重
要である。

【００８０】ここでは仮にパストランジスタ１段当り平
均0.4nsの遅延値であることがあらかじめ求められてい
るものとすると、a0からy3までがパストランジスタ５段
以内、b0からy3までがパストランジスタ３段以内という
段数制約を計算することができる。

【００８１】ステップ１５ではステップ１４の結果得ら
れた各入力の段数制約を考慮しながら入力変数の順序付
けを行う。本発明に係わるパストランジスタ論理設計方
法ではＢＤＤの構造が最終的な回路の構造に反映される
という特徴があるので、シャノン展開における入力変数
の順序により、生成される回路の入出力間の段数を調整
することが可能である。

【００８２】本実施の形態ではa0とb0以外の入力の遅延
制約が与えられていないため、a0とb0の段数制約を満た
した上で、前記「計算機上でのＢＤＤの処理技法」記載
の方法を用いて入力変数を決定するものとする。

【００８３】図１５に本ステップで決定された入力変数
順序を示す。図５に示した論理式より明かなように、a3
とb3、a2とb2、a1とb1、a0とb0は論理式の中でペアとし
て表れており、局所計算性があるため、順番を続けてい
る。また、前記の順に出力を制御する力が強いため、基
本的にはこの順番に従うが、a0とb0は段数制約があるの
で、それを考慮してb0を３番目にa0を４番目に持ってき
ている。

【００８４】ステップ１６では実施の形態１のステップ
５と同様に、ステップ１５で決定した変数順序に従って
論理回路をシャノン展開してＢＤＤを生成する。図１６
に生成されたＢＤＤを示す。

【００８５】ステップ１７では実施の形態１のステップ
６と同様に、ステップ１６で生成したＢＤＤをパストラ
ンジスタ論理回路に変換する。図１７に生成されたパス
トランジスタ論理回路１８を示す。

【００８６】図１７より入力a0から出力y3のパストラン
ジスタ段数は４段であり、入力b0から出力y3のパストラ
ンジスタ段数が３段になっていることがわかる。回路の
遅延は、本発明に係わるテクノロジー独立の論理設計ス
テップからテクノロジー依存の論理設計ステップを経て
レイアウト設計が終わった後でないと正確に評価するこ
とはできないが、与えられた遅延時間制約からパストラ
ンジスタ論理段数を計算するステップ１４において、十
分な設計マージンを組み込んでおくことにより、与えら
れた遅延時間制約を満足することは可能である。

【００８７】それに対して、遅延制約を考慮しないでシ
ャノン展開の入力変数順序を決定した場合に対応する図
１３に示す結果では、入力a0およびb0から出力y3までの
パストランジスタ段数が７段になっており、１段当りの
平均遅延時間が0.4nsであることを考えると遅延制約を
満たしておらず、実際には使えない回路である可能性が
高い。

【００８８】（実施の形態３）図３は本発明によるパス
トランジスタ論理設計方法の処理の流れを示すための処
理フロー図である。本実施の形態は本来、回路全体とし
ては最適にＢＤＤに変換できないような大規模な回路に
有効であるが、ここでは簡単のために、実施の形態１お
よび実施の形態２と同じく図５に示した論理仕様に基づ
いて説明する。

【００８９】通常ゲートによる論理回路を生成するステ
ップ２は前記実施の形態１のものと同様であるため、こ
こでは説明を省略する。

【００９０】ステップ２３では、ステップ２で生成され
た論理回路に対して論理最適化処理を適用することによ
り、回路に含まれる論理的冗長性を取り除いておく。

【００９１】本実施例において論理最適化処理を行なう
理由は、本実施例では論理回路を分割してそれぞれの部
分回路ごとに独立にパストランジスタ回路に変換するた
め、部分回路間に論理的冗長性が存在した場合、それが
最後まで残ってしまうためである。

【００９２】回路全体をＢＤＤに変換する従来手法で
は、変換されたＢＤＤは元の論理回路の構造には依存し
ない（論理とシャノン展開における入力順により一意的
に決定される）ので本ステップは不必要である。

【００９３】図６に示した論理回路が論理仕様１を元に
ステップ２とステップ２３を行なうことにより生成され
た論理回路である。（実施の形態１および実施の形態２
の説明では触れなかったが、図６の論理回路は論理最適
化処理を行った結果である。）ステップ２４では生成さ
れた論理回路を複数のサブ回路に分割する。

【００９４】ここでは、論理合成処理の内テクノロジー
独立な論理にセルを割り付けるテクノロジーマッピング
処理において従来よく用いられてきた、ファンアウト２
以上の内部信号（図６では信号ｉ）で回路を分割する手
法を用いる。

【００９５】さらに分割された各サブ回路の入力数を調
べて、それがある決められた値よりも大きい場合にはさ
らに回路分割を行ない、入力数が制限値内に収まるまで
分割を繰り返す。ここでの制限値としてはシャノン展開
処理における入力信号順の最適化が可能な入力数を用い
る。

【００９６】図６の論理回路では入力数が８であるた
め、本来は回路分割する必要はないのであるが、説明の
ために信号ｉで回路を２分割することとする。

【００９７】この時、分割された２つのサブ回路の論理
関数は（数１２）および（数１３）で表される。

【００９８】

【数１２】 i = ^( (a0 & b0 & (a1 | b1)) | (a1 & b1) )

【００９９】

【数１３】 y3 = (((^i | b2) & a2) | (^i & b2)) @ a3 @ b3 ステップ２５では、例えば「論理関数を表現する２分決
定グラフの最小化」（信学技法 COMP 91-15 p27）に記
載されたような手法を用いて最適な入力順序を決定す
る。あらかじめステップ２４の回路分割により各サブ回
路の入力数が制限されているために、前記手法による入
力変数順の決定が可能になっている。ここでは図１８に
示すように入力順が決定されたものとする。

【０１００】ステップ２６では、ステップ２５で決定さ
れた入力順に従って、各サブ回路をシャノン展開してＢ
ＤＤに変換する。本ステップは基本的に実施の形態１に
おけるステップ５の処理を各サブ回路毎に繰り返すだけ
であるから、ここでは説明を省略する。

【０１０１】本ステップで生成されるような複数のＢＤ
Ｄをネットワーク状に接続した論理表現は、全体として
はもはやＢＤＤではなくなるために、一般的なＢＤＤの
応用に対しては適用することができないが、本発明のよ
うにＢＤＤを直接的に論理回路に変換するような手法で
はトータルのＢＤＤノードの削減の目的で効果的に用い
ることができる。

【０１０２】図１９に生成されたＢＤＤを示す。

【０１０３】ステップ２７では、実施の形態１のステッ
プ６と同様に、ステップ２６で生成したＢＤＤをパスト
ランジスタ論理回路に変換する。図２０に生成されたパ
ストランジスタ論理回路を示す。

【０１０４】（実施の形態４）図２１は本発明によるパ
ストランジスタ論理設計方法の処理の流れを示すための
処理フロー図である。本実施の形態の論理仕様１と通常
ゲートによる論理回路を生成するステップ２および各入
力の信号遷移確率を評価するステップ３は前記実施の形
態１のものと同様であるため、ここでは説明を省略す
る。本実施の形態においても図８に示す信号遷移確率が
得られたものとする。

【０１０５】図２４は本実施の形態における遅延時間制
約２１０である。ここでは入力a3から出力y3までの遅延
が1.2ns以下、入力b3から出力y3までの遅延が1.7ns以下
でなければならないことが記述されている。

【０１０６】入出力間のパストランジスタ段数制約を計
算するステップ１４は前記実施の形態２のものと同様で
あるため詳細な説明は省略するが、パストランジスタ１
段当り平均0.4nsの遅延である場合、前記遅延時間制約
からa3からy3までがパストランジスタ３段以内、b3から
y3までの遅延が４段以内と計算できる。

【０１０７】ステップ２１１では、ステップ３の結果得
られた各入力の信号遷移確率とステップ１４の結果得ら
れた入出力間のパストランジスタ段数制約を考慮しなが
ら入力変数の順序付けを行なう。

【０１０８】本実施の形態では遅延制約を満たした回路
を生成することが必須で、その上で消費電力を最小化す
ることを目的としているため、前記a3とb3に係わるパス
トランジスタ段数制約を満たした上で、信号遷移確率が
高いものから順に入力信号を順序付ける。このように、
パストランジスタ段数制約は、信号遷移確率よりも高い
優先順位を有している。図２５に順序付けられた入力信
号のリストを示す。

【０１０９】論理回路をシャノン展開してＢＤＤを生成
するステップ５とＢＤＤをパストランジスタ論理回路に
変換するステップ６は前記実施の形態１と同様であるた
め、ここでは説明を省略する。

【０１１０】以上述べたように本実施の形態の設計方法
を用いれば、与えられた遅延制約を満たした上で消費電
力の小さいパストランジスタ回路を生成することができ
る。

【０１１１】（実施の形態５）図２２は本発明によるパ
ストランジスタ論理設計方法の処理の流れを示すための
処理フロー図である。本実施の形態の論理仕様１と通常
ゲートによる論理回路を生成するステップ２、論理最適
化ステップ２３および回路分割ステップ２４は前記実施
の形態３のものと同様であるため、ここでは説明を省略
する。

【０１１２】ステップ２２１ではステップ２４で分割し
た各サブ回路の入力信号に係わる信号遷移確率を評価す
るが、これも実施の形態１のステップ３と同様に論理シ
ミュレーションを用いて行なうことができる。

【０１１３】ステップ２２２では各サブ回路毎に前記信
号遷移確率が大きいものから小さいものへと入力変数の
順序付けを行なう。本ステップも実施の形態１のステッ
プ４と同様にして行なうことができる。

【０１１４】なお、本実施の形態では低消費電力化を目
的として、信号遷移確率に基づいて入力変数順序を決定
しているが、実際の回路設計では低消費電力化と回路規
模最小化が両立しない場合も多い。このような場合には
両者のトレードオフを考慮しながら入力信号を順序付け
する必要があり、本発明はそのような場合も含んでい
る。

【０１１５】本実施の形態の各サブ回路をシャノン展開
してＢＤＤを生成するステップ２６と各サブ回路毎にＢ
ＤＤをパストランジスタ論理回路に変換するステップ２
７は前記実施の形態３のものと同様であるため、説明は
省略する。

【０１１６】以上述べたような本実施の形態の設計方法
を用いれば、大規模な論理回路に対しても消費電力の小
さいパストランジスタ回路を生成することができる。

【０１１７】（実施の形態６）図２３は本発明によるパ
ストランジスタ論理設計方法の処理の流れを示すための
処理フロー図である。本実施の形態の論理仕様１と通常
ゲートによる論理回路を生成するステップ２、論理最適
化ステップ２３および回路分割ステップ２４は前記実施
の形態３のものと同様であるため、ここでは説明を省略
する。

【０１１８】また、遅延時間制約１３として図１４に示
す実施の形態２と同じものが与えられているものとす
る。

【０１１９】ステップ２３１では前記遅延時間制約１３
に基づいてステップ２４で分割された各サブ回路の入出
力間のパストランジスタ段数制約を計算する。ここでは
まず実施の形態２のステップ１４と同様の方法で全体回
路での入出力間段数制約を計算し、次に得られた段数制
約を各サブ回路に振り分けるという方法を取る。

【０１２０】図１５に示したように、全体回路ではa0か
らy3が５段以内、b0からy3が３段以内という段数制約が
得られる。これをサブ回路間で遅延制約のバランスを取
るように振り分けると、（数１２）に対応するサブ回路
ではa0からiが３段以内、ｂ０からｉが１段以内、一方
（数１３）に対応するサブ回路ではiからy3が２段以内
という段数制約になる。

【０１２１】なお、遅延時間制約から各サブ回路の入出
力間の段数制約を計算する方法には上に示したもの以外
にも様々な方法があるが、本発明はそのようなものも含
んでいる。

【０１２２】ステップ２３２では、実施の形態２のステ
ップ１５と同様の方法で、各サブ回路毎に前記段数制約
を考慮した入力信号の順序付けを行なう。図２６に本ス
テップの結果得られた入力順序を示す。

【０１２３】本実施の形態の各サブ回路をシャノン展開
してＢＤＤを生成するステップ２６と各サブ回路毎にＢ
ＤＤをパストランジスタ論理回路に変換するステップ２
７は前記実施の形態３のものと同様であるからここでは
説明を省略する。

【０１２４】なお、実施の形態５（図２２）と実施の形
態６（図２３）とを組み合わせて、各サブ回路の入力信
号の順序を信号遷移確率と段数制約とに基づいて決定す
るようにしてもよい。

【０１２５】

【発明の効果】以上説明したように、本発明を用いれ
ば、与えられた論理仕様から以下に示すような特長を持
つパストランジスタ回路を合成することが可能である。

【０１２６】（１）信号遷移確率の高い入力ほど出力と
の間のパストランジスタ段数が小さくなるため、遷移確
率の高い信号が長く伝搬せず、回路全体として遷移確率
の和が小さく、低消費電力化される。

【０１２７】（２）遅延時間制約が与えられた入出力間
のパストランジスタ段数が遅延制約値に基づいて制限さ
れる。クリティカルパスとなる入出力間に遅延制約を与
えることにより、回路の高速動作が実現される。

【０１２８】（３）入力数が多いために、従来の設計手
法では最適化できず、不必要に大きくなってしまうよう
な回路に対しても、実用的な回路サイズを実現する。

【図面の簡単な説明】

【図１】本発明の実施の形態１におけるパストランジス
タ論理設計方法の処理フロー図である。

【図２】本発明の実施の形態２におけるパストランジス
タ論理設計方法の処理フロー図である。

【図３】本発明の実施の形態３におけるパストランジス
タ論理設計方法の処理フロー図である。

【図４】本発明のパストランジスタ論理設計方法を説明
するための機能記述を示す図である。

【図５】本発明のパストランジスタ論理設計方法を説明
するための論理式を示す図である。

【図６】本発明の実施の形態１により論理式から生成さ
れた論理回路図である。

【図７】本発明の実施の形態１において信号遷移確率を
評価するのに必要なテストベクタを示す図である。

【図８】本発明の実施の形態１において信号遷移確率に
基づき入力を順序付けした結果を示す図である。

【図９】本発明の実施の形態１において論理回路から生
成されたＢＤＤを示す図である。

【図１０】本発明の実施の形態１においてＢＤＤからパ
ストランジスタ論理回路への変換を示す図である。

【図１１】本発明の実施の形態１においてＢＤＤから変
換されたパストランジスタ論理回路図である。

【図１２】従来手法を用いて決定された入力順で論理回
路から生成されたＢＤＤを示す図である。

【図１３】従来手法を用いて生成されたＢＤＤから変換
されたパストランジスタ論理回路図である。

【図１４】本発明の実施の形態２における遅延制約の例
を示す図である。

【図１５】本発明の実施の形態２においてパストランジ
スタ段数制約を考慮して入力を順序付けした結果を示す
図である。

【図１６】本発明の実施の形態２において論理回路から
生成されたＢＤＤを示す図である。

【図１７】本発明の実施の形態２においてＢＤＤから変
換されたパストランジスタ論理回路図である。

【図１８】本発明の実施の形態３において各サブ回路毎
にＢＤＤサイズが最小になるように入力を順序付けした
結果を示す図である。

【図１９】本発明の実施の形態３において論理回路から
生成されたＢＤＤを示す図である。

【図２０】本発明の実施の形態３においてＢＤＤから変
換されたパストランジスタ論理回路図である。

【図２１】本発明の実施の形態４におけるパストランジ
スタ論理設計方法の処理フロー図である。

【図２２】本発明の実施の形態５におけるパストランジ
スタ論理設計方法の処理フロー図である。

【図２３】本発明の実施の形態６におけるパストランジ
スタ論理設計方法の処理フロー図である。

【図２４】本発明の実施の形態４における遅延制約の例
を示す図である。

【図２５】本発明の実施の形態４においてパストランジ
スタ段数制約と信号遷移確率を考慮して入力を順序付け
した結果を示す図である。

【図２６】本発明の実施の形態６において各サブ回路毎
にパストランジスタ段数制約を考慮して入力を順序付け
した結果を示す図である。

【符号の説明】

１ 論理仕様 ２ 通常のゲートによる論理回路を生成 ３ 各入力の信号遷移確率の評価 ４ 各入力を信号遷移確率で順序付け ５ 論理回路をシャノン展開してＢＤＤを生成 ６ ＢＤＤをパストランジスタ論理回路に変換 ７ パストランジスタ論理回路

Claims (8)

【特許請求の範囲】
1. 【請求項１】 与えられた回路の論理仕様に基づいて、
   パストランジスタ論理回路を設計する方法であって、 前記論理仕様に基づいて論理ゲートを含む論理回路を生
   成するステップと、 前記論理回路の各入力信号の信号遷移確率を評価するス
   テップと、 前記入力信号を信号遷移確率の高いものから低いものへ
   順序付けするステップと、 前記論理回路に対して、前記入力信号の内の信号遷移確
   率の高いものから順にシャノン展開処理を適用すること
   により、前記論理回路に対応する２分決定グラフを生成
   するステップと、 前記２分決定グラフの各ノードをパストランジスタによ
   る２入力セレクタ回路に置き換えることによりテクノロ
   ジー独立なパストランジスタ論理回路を生成するステッ
   プとを包含し、 前記信号遷移確率の高い入力信号と出力信号との間の論
   理段数を削減することにより、生成した回路の消費電力
   を削減することを特徴とするパストランジスタ論理設計
   方法。
2. 【請求項２】 前記与えられた回路の入出力信号間に許
   容される遅延時間を規定する遅延時間制約とパストラン
   ジスタ論理回路の平均遅延時間に基づいて、前記パスト
   ランジスタ論理回路に許容される段数を規定する段数制
   約を計算するステップをさらに包含し、 前記論理回路の前記入力信号は、前記段数制約と前記信
   号遷移確率とを考慮して順序付けられる、請求項１に記
   載のパストランジスタ論理設計方法。
3. 【請求項３】 前記段数制約は、前記信号遷移確率より
   も高い優先順位を有している、請求項２に記載のパスト
   ランジスタ論理設計方法。
4. 【請求項４】 与えられた回路の論理仕様に基づいて、
   パストランジスタ論理回路を設計する方法であって、 前記論理仕様に基づいて論理ゲートを含む論理回路を生
   成するステップと、 前記与えられた回路の入出力信号間に許容される遅延時
   間を規定する遅延時間制約とパストランジスタ論理回路
   の平均遅延時間に基づいて、前記パストランジスタ論理
   回路に許容される段数を規定する段数制約を計算するス
   テップと、 前記段数制約を考慮して、シャノン展開のための最適な
   入力信号の順序を決定するステップと、 前記論理回路に対して、前記入力信号の順序に従ってシ
   ャノン展開処理を適用することにより、前記論理回路に
   対応する２分決定グラフを生成するステップと、 前記２分決定グラフの各ノードをパストランジスタによ
   る２入力セレクタ回路に置き換えることによりテクノロ
   ジー独立なパストランジスタ論理回路を生成するステッ
   プとを包含し、 前記遅延時間制約が与えられた入力信号と出力信号との
   間のパストランジスタ段数を制限することにより、生成
   した回路が与えられた遅延時間制約を満たすことを特徴
   とするパストランジスタ論理設計方法。
5. 【請求項５】 与えられた回路の論理仕様に基づいて、
   パストランジスタ論理回路を設計する方法であって、 前記論理仕様に基づいて論理ゲートを含む論理回路を生
   成するステップと、 前記論理回路に論理最適化処理を行い、冗長回路を削除
   するステップと、 分割された複数のサブ回路のそれぞれの入力信号の数を
   考慮して、前記最適化された論理回路を複数のサブ回路
   に分割するステップと、 生成される２分決定グラフの最小化を目的として、前記
   複数のサブ回路のそれぞれについてシャノン展開のため
   の最適な入力信号の順序を決定するステップと、 前記複数のサブ回路のそれぞれについて、前記入力信号
   の順序に従ってシャノン展開処理を適用することによ
   り、前記論理回路に対応する２分決定グラフを生成する
   ステップと、 前記複数のサブ回路のそれぞれについて、前記２分決定
   グラフの各ノードをパストランジスタによる２入力セレ
   クタ回路に置き換えることにより、テクノロジー独立な
   パストランジスタ論理回路を生成するステップとを包含
   し、 個々のサブ回路の入力信号の数を制限することにより最
   適な入力信号順序の決定を可能にして、生成される回路
   を最小化することを特徴とするパストランジスタ論理設
   計方法。
6. 【請求項６】 前記サブ回路の前記入力信号のそれぞれ
   の信号遷移確率を評価するステップをさらに包含し、 前記サブ回路の前記入力信号の順序は、前記信号遷移確
   率に基づいて決定される、請求項５に記載のパストラン
   ジスタ論理設計方法。
7. 【請求項７】 前記与えられた回路の入出力信号間に許
   容される遅延時間を規定する遅延時間制約とパストラン
   ジスタ論理回路の平均遅延時間に基づいて、前記パスト
   ランジスタ論理回路に許容される段数を規定する段数制
   約を計算するステップをさらに包含し、 前記サブ回路の前記入力信号の順序は、前記段数制約に
   基づいて決定される、請求項５に記載のパストランジス
   タ論理設計方法。
8. 【請求項８】 前記与えられた回路の入出力信号間に許
   容される遅延時間を規定する遅延時間制約とパストラン
   ジスタ論理回路の平均遅延時間に基づいて、前記パスト
   ランジスタ論理回路に許容される段数を規定する段数制
   約を計算するステップをさらに包含し、 前記サブ回路の前記入力信号の順序は、前記段数制約と
   前記信号遷移確率とに基づいて決定される、請求項６に
   記載のパストランジスタ論理設計方法。