JP2601177B2 - 同期論理回路における最適クロック周期の決定方法 - Google Patents
同期論理回路における最適クロック周期の決定方法Info
- Publication number
- JP2601177B2 JP2601177B2 JP5331689A JP33168993A JP2601177B2 JP 2601177 B2 JP2601177 B2 JP 2601177B2 JP 5331689 A JP5331689 A JP 5331689A JP 33168993 A JP33168993 A JP 33168993A JP 2601177 B2 JP2601177 B2 JP 2601177B2
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- clock period
- path
- optimal
- latch
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 19
- 230000001360 synchronised effect Effects 0.000 title claims description 10
- 230000000116 mitigating effect Effects 0.000 claims description 2
- 238000013461 design Methods 0.000 description 23
- 230000006870 function Effects 0.000 description 6
- 238000005457 optimization Methods 0.000 description 6
- 238000013459 approach Methods 0.000 description 5
- 238000004519 manufacturing process Methods 0.000 description 5
- 238000004422 calculation algorithm Methods 0.000 description 4
- 230000015572 biosynthetic process Effects 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 3
- 239000011159 matrix material Substances 0.000 description 3
- 238000003786 synthesis reaction Methods 0.000 description 3
- 238000002474 experimental method Methods 0.000 description 2
- 238000004590 computer program Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 238000005530 etching Methods 0.000 description 1
- 230000011218 segmentation Effects 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
- 230000001960 triggered effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Description
【０００１】
【産業上の利用分野】この発明は同期論理半導体回路の
製造に関し、より詳細には、同期論理回路の設計を、そ
の機能に影響を与えずに、その動作に必要なクロック期
間を低減するように変更する方法に関する。
製造に関し、より詳細には、同期論理回路の設計を、そ
の機能に影響を与えずに、その動作に必要なクロック期
間を低減するように変更する方法に関する。
【０００２】
【従来の技術および解決すべき課題】回路の動作の逐次
ステップを同期させるためにクロックを利用するような
種類の電子回路の動作において、クロック期間をできる
だけ短くして（タイミング最適化）、所定時間に実行さ
れ得るクロックサイクルの数を増加させ、よって所定動
作を達成する時間を減少させるか、あるいは所定時間に
発生され得る情報の量を増加させるかすることが望まし
い。
ステップを同期させるためにクロックを利用するような
種類の電子回路の動作において、クロック期間をできる
だけ短くして（タイミング最適化）、所定時間に実行さ
れ得るクロックサイクルの数を増加させ、よって所定動
作を達成する時間を減少させるか、あるいは所定時間に
発生され得る情報の量を増加させるかすることが望まし
い。
【０００３】そのようなクロック回路の最重要クラス
は、組合せ論理ゲートと、通常ラッチと記されるクロッ
クフリップフロップの相互連結によって形成される同期
論理回路である。特にＶＬＳＩサイズのそのような回路
は、現在、コンピュータツールによって設計される。そ
のような設計は、代表的に、タイミング最適化に殆ど関
心を払わずに、論理合成によって行われておりり、タイ
ミング最適化に対する関心は、通常、後の別の再設計段
のために残されている。そのような再タイミング段に対
して、様々なアプローチが提案されてきた。一般に、代
表的なアプローチは、設計において、それぞれがテスト
ステップを従えた、小さい再タイミング変化の繰返しを
伴い、それは最適条件が達成される前に多くの試行を伴
うことができる。そのような再タイミング方法は時間浪
費である。
は、組合せ論理ゲートと、通常ラッチと記されるクロッ
クフリップフロップの相互連結によって形成される同期
論理回路である。特にＶＬＳＩサイズのそのような回路
は、現在、コンピュータツールによって設計される。そ
のような設計は、代表的に、タイミング最適化に殆ど関
心を払わずに、論理合成によって行われておりり、タイ
ミング最適化に対する関心は、通常、後の別の再設計段
のために残されている。そのような再タイミング段に対
して、様々なアプローチが提案されてきた。一般に、代
表的なアプローチは、設計において、それぞれがテスト
ステップを従えた、小さい再タイミング変化の繰返しを
伴い、それは最適条件が達成される前に多くの試行を伴
うことができる。そのような再タイミング方法は時間浪
費である。
【０００４】設計中の特定回路において、実際に実現さ
れ得る最適タイミングがどんなものであるかについての
情報が不足しているために、通常、一連の小さい増分的
変化をさせることが必要になっている。
れ得る最適タイミングがどんなものであるかについての
情報が不足しているために、通常、一連の小さい増分的
変化をさせることが必要になっている。
【０００５】
【課題を解決するための手段】本発明は、目的の回路機
能に対する最適クロック期間を有する同期論理回路の製
造に関する。発明の特徴は、同期論理回路設計の最適再
タイミングを達成する方法である。
能に対する最適クロック期間を有する同期論理回路の製
造に関する。発明の特徴は、同期論理回路設計の最適再
タイミングを達成する方法である。
【０００６】より特定すれば、本発明は、過去における
ように初期機能回路設計で開始し、新規方法で、この機
能回路設計によって可能な最適クロック期間を決定し、
そして次に、そのような最適クロック期間を与えるよう
に初期回路設計を変更する、再タイミングを最適化する
方法を含んでいる。別の様相からは、この発明は、製造
しようとする回路を設計するために改良技術を利用する
ことによって、同期論理回路を作る方法として見ること
ができる。
ように初期機能回路設計で開始し、新規方法で、この機
能回路設計によって可能な最適クロック期間を決定し、
そして次に、そのような最適クロック期間を与えるよう
に初期回路設計を変更する、再タイミングを最適化する
方法を含んでいる。別の様相からは、この発明は、製造
しようとする回路を設計するために改良技術を利用する
ことによって、同期論理回路を作る方法として見ること
ができる。
【０００７】このために、設計方法は以下の通りであ
る。先ず、１つ以上の予備段において、既知の技術によ
って、回路に予定された論理を与える回路の予備設計が
準備されており、そしてこの段では冗長性はほぼ取り除
かれ、そして利用できる技術によって組合せ経路は実用
の限度まで短縮されているので、発明によって提供され
る最適再タイミング技術に対する設計の準備はできてい
る。次いで、この予備回路設計は組合せ論理ゲートとラ
ッチの相互連結として特定され、次いで、その回路にと
っての最適クロック期間が新規アプローチ、すなわち、
経路区分と予め特定された遅延との相互連結として回路
を見ること、および経路区分の経路グラフを準備するこ
とを含むアプローチによって決定される。経路区分は、
ラッチ、一次入力、あるいは一次出力によって限定され
た回路の部分である。回路のゲートに集中する従来の再
タイミングアプローチとは異なり、この経路区分計画は
ラッチに集中する。最適クロック期間問題の決定は、整
散線形プログラム（ＩＬＰ）として公式化される。ＩＬ
Ｐによって最小クロック期間を決定し、その期間の間、
回路にはクリティカル経路もサイクルもない。クリティ
カル経路もサイクルもない場合、そしてその場合のみ、
回路は所定のクロック期間を達成するよう再タイムでき
ることは明らかである。ＩＬＰへの最適解は、対応する
線形プログラム（ＬＰ）緩和の最適解から決定される。
最適クロック期間が一旦、見つかると、ラッチを再配置
して最適クロック期間で動作を達成するように回路設計
を変更することは、既知の方法を使用して実行される。
最後に、最適クロック期間回路が設計されて、そのよう
な設計を含むチップの製造は通常の方法で実行される。
る。先ず、１つ以上の予備段において、既知の技術によ
って、回路に予定された論理を与える回路の予備設計が
準備されており、そしてこの段では冗長性はほぼ取り除
かれ、そして利用できる技術によって組合せ経路は実用
の限度まで短縮されているので、発明によって提供され
る最適再タイミング技術に対する設計の準備はできてい
る。次いで、この予備回路設計は組合せ論理ゲートとラ
ッチの相互連結として特定され、次いで、その回路にと
っての最適クロック期間が新規アプローチ、すなわち、
経路区分と予め特定された遅延との相互連結として回路
を見ること、および経路区分の経路グラフを準備するこ
とを含むアプローチによって決定される。経路区分は、
ラッチ、一次入力、あるいは一次出力によって限定され
た回路の部分である。回路のゲートに集中する従来の再
タイミングアプローチとは異なり、この経路区分計画は
ラッチに集中する。最適クロック期間問題の決定は、整
散線形プログラム（ＩＬＰ）として公式化される。ＩＬ
Ｐによって最小クロック期間を決定し、その期間の間、
回路にはクリティカル経路もサイクルもない。クリティ
カル経路もサイクルもない場合、そしてその場合のみ、
回路は所定のクロック期間を達成するよう再タイムでき
ることは明らかである。ＩＬＰへの最適解は、対応する
線形プログラム（ＬＰ）緩和の最適解から決定される。
最適クロック期間が一旦、見つかると、ラッチを再配置
して最適クロック期間で動作を達成するように回路設計
を変更することは、既知の方法を使用して実行される。
最後に、最適クロック期間回路が設計されて、そのよう
な設計を含むチップの製造は通常の方法で実行される。
【０００８】
【実施例】設計方法は通常の方法で開始する。既知のコ
ンピュータプログラムを利用して、先ず、所望の論理を
完成する回路設計が準備される。この初期設計はなお洗
練されて、大抵の冗長性を取り除き、かつ回路の組合せ
区分の幾つかの長さを低減させた後、この設計は発明の
特徴が利用されている点に到達する。この点において、
次のステップは、利用できる回路の最適クロック期間を
見つけることである。
ンピュータプログラムを利用して、先ず、所望の論理を
完成する回路設計が準備される。この初期設計はなお洗
練されて、大抵の冗長性を取り除き、かつ回路の組合せ
区分の幾つかの長さを低減させた後、この設計は発明の
特徴が利用されている点に到達する。この点において、
次のステップは、利用できる回路の最適クロック期間を
見つけることである。
【０００９】当該回路の最適クロック期間を見つけるた
めに、先ず、回路の経路グラフを準備する。そのような
経路グラフにおいて、回路は経路区分の相互連結と見な
される。経路区分は、ラッチ、一次入力、あるいは一次
出力の組合せによって、その２つの末端で限定されてい
る回路の一部分である。経路グラフにおいて、回路の一
次入力および一次出力はすべて、共通の点ｌ0 で表さ
れ、そして回路の各ラッチｌi は、経路グラフにおける
別の点ｌi で表される。ラッチｌi からｌj への組合せ
路がある場合、この経路グラフは、ラッチｌi からラッ
チｌj への最大経路遅延に等しい重みを有する、点ｌi
から点ｌj への弧を持っている。この経路遅延は経路長
と類似していると見なすことができて、２つの用語は交
換可能に使用される。ｌi が一次入力であれば、ｌ0 か
らｌj への弧がある。同様に、ｌjが一次出力であれ
ば、ｌi からラッチｌj への弧がある。一次入力と一次
出力間の組合せ路は、これらの経路における遅延は再タ
イミングによって低減することができないので、経路グ
ラフには含まれていない。同様な理由のために、ラッチ
出力からその入力への経路遅延である自己ループ遅延は
どれも、グラフには含まれない。
めに、先ず、回路の経路グラフを準備する。そのような
経路グラフにおいて、回路は経路区分の相互連結と見な
される。経路区分は、ラッチ、一次入力、あるいは一次
出力の組合せによって、その２つの末端で限定されてい
る回路の一部分である。経路グラフにおいて、回路の一
次入力および一次出力はすべて、共通の点ｌ0 で表さ
れ、そして回路の各ラッチｌi は、経路グラフにおける
別の点ｌi で表される。ラッチｌi からｌj への組合せ
路がある場合、この経路グラフは、ラッチｌi からラッ
チｌj への最大経路遅延に等しい重みを有する、点ｌi
から点ｌj への弧を持っている。この経路遅延は経路長
と類似していると見なすことができて、２つの用語は交
換可能に使用される。ｌi が一次入力であれば、ｌ0 か
らｌj への弧がある。同様に、ｌjが一次出力であれ
ば、ｌi からラッチｌj への弧がある。一次入力と一次
出力間の組合せ路は、これらの経路における遅延は再タ
イミングによって低減することができないので、経路グ
ラフには含まれていない。同様な理由のために、ラッチ
出力からその入力への経路遅延である自己ループ遅延は
どれも、グラフには含まれない。
【００１０】説明するために、図１の回路１０を考えて
みる。それにはａ，ｂ，ｃおよびｄと称する４つの一次
入力と、ｅと称する１つの一次出力がある。回路のラッ
チはｌ1 ，ｌ2 およびｌ3 と称される。競争を避けるた
めに、フィードバック連結は、ラッチを通じてのみ許容
される。全ラッチは単一クロックによって駆動され、そ
してラッチングは、常に正あるいは常に負のいずれで
も、クロックパルスの同じエッチングによって、常にト
リガされる、と考えられる。また、各ゲートは同じユニ
ット伝播遅延を持つものとする。入力端子ａはインバー
タ１１に供給し、その出力はラッチｌ1 に与えられ、そ
してラッチｌ1 の出力はＯＲゲート１２への１入力を与
えている。ＯＲゲート１２の一方はＡＮＤゲート１３へ
の１入力を与えており、そのもう一方の入力は入力端子
ｂである。ＡＮＤゲート１３の出力はラッチｌ3 に与え
られ、その出力はＡＮＤゲート１５への入力を与え、そ
してＡＮＤゲート１５の出力はＯＲゲート１６への入力
を与えている。入力端子ｃはＯＲゲート１６のもう一方
の入力を与え、ＯＲゲート１６の出力はＡＮＤゲート１
７への１入力を与え、ＡＮＤゲート１７の出力は出力端
子ｅに与えられている。ＡＮＤゲート１７のもう一方の
入力は入力端子αによって与えられている。ＡＮＤゲー
ト１５の出力はまた、ラッチｌ2 への入力としてフィー
ドバックされ、ラッチｌ2 の出力はインバータ１９への
入力として与えられ、インバータ１９の出力はＯＲゲー
ト１２およびＡＮＤゲート１５両方の入力として与えら
れている。
みる。それにはａ，ｂ，ｃおよびｄと称する４つの一次
入力と、ｅと称する１つの一次出力がある。回路のラッ
チはｌ1 ，ｌ2 およびｌ3 と称される。競争を避けるた
めに、フィードバック連結は、ラッチを通じてのみ許容
される。全ラッチは単一クロックによって駆動され、そ
してラッチングは、常に正あるいは常に負のいずれで
も、クロックパルスの同じエッチングによって、常にト
リガされる、と考えられる。また、各ゲートは同じユニ
ット伝播遅延を持つものとする。入力端子ａはインバー
タ１１に供給し、その出力はラッチｌ1 に与えられ、そ
してラッチｌ1 の出力はＯＲゲート１２への１入力を与
えている。ＯＲゲート１２の一方はＡＮＤゲート１３へ
の１入力を与えており、そのもう一方の入力は入力端子
ｂである。ＡＮＤゲート１３の出力はラッチｌ3 に与え
られ、その出力はＡＮＤゲート１５への入力を与え、そ
してＡＮＤゲート１５の出力はＯＲゲート１６への入力
を与えている。入力端子ｃはＯＲゲート１６のもう一方
の入力を与え、ＯＲゲート１６の出力はＡＮＤゲート１
７への１入力を与え、ＡＮＤゲート１７の出力は出力端
子ｅに与えられている。ＡＮＤゲート１７のもう一方の
入力は入力端子αによって与えられている。ＡＮＤゲー
ト１５の出力はまた、ラッチｌ2 への入力としてフィー
ドバックされ、ラッチｌ2 の出力はインバータ１９への
入力として与えられ、インバータ１９の出力はＯＲゲー
ト１２およびＡＮＤゲート１５両方の入力として与えら
れている。
【００１１】対応する経路グラフは図２に示される。３
つの点ｌ1 ，ｌ2 およびｌ3 は３つのラッチに対応す
る。点ｌ0 は回路のすべての一次入力および出力に対応
する。点ｌ0 から点ｌ1 までには重み１の弧があるが、
それはその最も近い一次入力からラッチｌ1 までの経路
区分の回路に沿った経路遅延は１だからである。同様
に、ラッチｌ2 から回路沿いに一次出力までの経路区分
の遅延は４であるので、経路グラフは、４の重みのあ
る、点ｌ2 からｌ0 までの弧を持っている。回路の他の
経路区分を表す弧の重みは同様に導出される。
つの点ｌ1 ，ｌ2 およびｌ3 は３つのラッチに対応す
る。点ｌ0 は回路のすべての一次入力および出力に対応
する。点ｌ0 から点ｌ1 までには重み１の弧があるが、
それはその最も近い一次入力からラッチｌ1 までの経路
区分の回路に沿った経路遅延は１だからである。同様
に、ラッチｌ2 から回路沿いに一次出力までの経路区分
の遅延は４であるので、経路グラフは、４の重みのあ
る、点ｌ2 からｌ0 までの弧を持っている。回路の他の
経路区分を表す弧の重みは同様に導出される。
【００１２】回路のラッチを位置替えして、回路の経路
遅延を変更することができる。位置替えすることによっ
て組合せ論理を横断してラッチが移動することを伴う。
ラッチが組合せ論理を横断して前方に動く場合、そのラ
ッチから発する全経路の経路遅延は低減される。ラッチ
の運動の方向は、ラッチを通る信号の流れに関して定め
られる。信号流と同じ方向にラッチが動く場合には、そ
れは前方に動いたのである。ラッチが信号流と反対の方
向に動く場合には、それは後方に動いたことになる。ｘ
i を、ラッチｌi が前方に移動した時間単位の数とす
る。ｘi が負である場合、ラッチは−ｘi の時間単位、
後方に動いたことになる。一次入力および出力の運動は
ｘ0 で表される。一次入力および出力は動かすことがで
きないので、明らかに、ｘ0 ＝０、しかしｘ1 ，ｘ2 お
よびｘ3 をそれぞれ、ラッチｌ1 ，ｌ2 およびｌ3 の運
動とする。
遅延を変更することができる。位置替えすることによっ
て組合せ論理を横断してラッチが移動することを伴う。
ラッチが組合せ論理を横断して前方に動く場合、そのラ
ッチから発する全経路の経路遅延は低減される。ラッチ
の運動の方向は、ラッチを通る信号の流れに関して定め
られる。信号流と同じ方向にラッチが動く場合には、そ
れは前方に動いたのである。ラッチが信号流と反対の方
向に動く場合には、それは後方に動いたことになる。ｘ
i を、ラッチｌi が前方に移動した時間単位の数とす
る。ｘi が負である場合、ラッチは−ｘi の時間単位、
後方に動いたことになる。一次入力および出力の運動は
ｘ0 で表される。一次入力および出力は動かすことがで
きないので、明らかに、ｘ0 ＝０、しかしｘ1 ，ｘ2 お
よびｘ3 をそれぞれ、ラッチｌ1 ，ｌ2 およびｌ3 の運
動とする。
【００１３】次に、クロック期間の下限は次のような考
えから容易に決定することができる。再タイミングによ
って、一次入力と出力間の経路遅延を低減することはで
きない。また、自己ループ遅延も再タイミングによって
変更することはできない。一次入力と一次出力間の最長
経路区分における経路遅延をＤc とする。また、回路の
いずれのラッチに対する最大自己ループ遅延でもＤs と
する。Ｄc とＤs の両方とも、回路の信号数において線
形になっている時間計算量において、計算することがで
きる。明らかに、再タイミングによって達成し得る最適
クロック期間がφopt である場合には、φopt ≧最大
（Ｄc ，Ｄs ）である。最大（Ｄc ，Ｄs）はφL で表
される。
えから容易に決定することができる。再タイミングによ
って、一次入力と出力間の経路遅延を低減することはで
きない。また、自己ループ遅延も再タイミングによって
変更することはできない。一次入力と一次出力間の最長
経路区分における経路遅延をＤc とする。また、回路の
いずれのラッチに対する最大自己ループ遅延でもＤs と
する。Ｄc とＤs の両方とも、回路の信号数において線
形になっている時間計算量において、計算することがで
きる。明らかに、再タイミングによって達成し得る最適
クロック期間がφopt である場合には、φopt ≧最大
（Ｄc ，Ｄs ）である。最大（Ｄc ，Ｄs）はφL で表
される。
【００１４】グラフにおける最長経路区分の遅延によっ
て決定された回路の現在のクロック期間をφとする。ｌ
i からｌj までの弧を考えてみる。ラッチｌi とｌj を
動かすことによって、点ｌi とｌj 間の弧の重みを変更
する。ラッチｌi とｌj がそれぞれ、ｘi とｘj の時間
単位だけ運動する場合、弧の重みはｄijからｘj −ｘi
＋ｄijへと変化する。ｘj −ｘi ＋ｄijを再タイム弧の
重みとする。ε時間単位の低減が必要とされる場合、す
べての再タイム弧の重みが多くてもφ−εになるよう
に、ラッチを位置替えしなければならない。また、εを
最大化して、最小の可能クロック期間を達成することも
望ましい。ラッチ運動ならびにεは整数値のみである。
εの最大値を計算するために、次の整数線形プログラム
ＩＬＰを式で示して、εの最大値を得る。
て決定された回路の現在のクロック期間をφとする。ｌ
i からｌj までの弧を考えてみる。ラッチｌi とｌj を
動かすことによって、点ｌi とｌj 間の弧の重みを変更
する。ラッチｌi とｌj がそれぞれ、ｘi とｘj の時間
単位だけ運動する場合、弧の重みはｄijからｘj −ｘi
＋ｄijへと変化する。ｘj −ｘi ＋ｄijを再タイム弧の
重みとする。ε時間単位の低減が必要とされる場合、す
べての再タイム弧の重みが多くてもφ−εになるよう
に、ラッチを位置替えしなければならない。また、εを
最大化して、最小の可能クロック期間を達成することも
望ましい。ラッチ運動ならびにεは整数値のみである。
εの最大値を計算するために、次の整数線形プログラム
ＩＬＰを式で示して、εの最大値を得る。
【００１５】 問題ＩＬＰ Ｍａｘｉｍｉｚｅ ε Ｓｕｂｊｅｃｔ ｔｏ ｘｉ−ｘｉ＋ε≦φ−ｄｉｊ ： ｌｉ→ｌｊ ∈ Ｅ ε≦φ−φＬ 全変数は整数である （弧の重みであるｄｉｊと、ラッチの移動量である
Ｘｉ、Ｘｊと、クロック周期の下限値であるφＬ，を制
約条件としてεの最大値を得るプログラム）
Ｘｉ、Ｘｊと、クロック周期の下限値であるφＬ，を制
約条件としてεの最大値を得るプログラム）
【００１６】明らかに、ε≧φ−φL という制約は余分
である。ＩＬＰはこの制約無しでも、解くことができ
る。εの最適値がφ−φL を超える場合、最適クロック
の期間はφL である。そこで、εの最適値は、再タイミ
ングによって達成することができる最大の可能クロック
期間低減に対応することが確立される。
である。ＩＬＰはこの制約無しでも、解くことができ
る。εの最適値がφ−φL を超える場合、最適クロック
の期間はφL である。そこで、εの最適値は、再タイミ
ングによって達成することができる最大の可能クロック
期間低減に対応することが確立される。
【００１７】φが回路の現在のクロック期間である場
合、φopt は再タイミングによって達成できる最適クロ
ック期間であり、そしてεはＩＬＰに対する最適解であ
る場合、φopt ＝φ−εである。
合、φopt は再タイミングによって達成できる最適クロ
ック期間であり、そしてεはＩＬＰに対する最適解であ
る場合、φopt ＝φ−εである。
【００１８】回路のどんなクリティカル経路またはサイ
クルでも、経路グラフのサイクルに対応する。さらに、
経路グラフのクリティカルサイクルは、回路のクリティ
カル経路またはサイクルに対応する。経路グラフでは、
クロック期間φ−εにおいて、クリティカルサイクルは
無いということを示せば十分であろう。その理由は、経
路グラフにクリティカルサイクルが無いということは、
回路が、クロック期間φ−εにおいてクリティカル経路
またはサイクルを持たないということを意味するからで
ある。回路がクリティカルサイクルまたは経路を持たな
い場合、それは常に再タイムされて、クロック期間φ−
εを達成できることは明らかである。
クルでも、経路グラフのサイクルに対応する。さらに、
経路グラフのクリティカルサイクルは、回路のクリティ
カル経路またはサイクルに対応する。経路グラフでは、
クロック期間φ−εにおいて、クリティカルサイクルは
無いということを示せば十分であろう。その理由は、経
路グラフにクリティカルサイクルが無いということは、
回路が、クロック期間φ−εにおいてクリティカル経路
またはサイクルを持たないということを意味するからで
ある。回路がクリティカルサイクルまたは経路を持たな
い場合、それは常に再タイムされて、クロック期間φ−
εを達成できることは明らかである。
【００１９】ＩＬＰの最適解を考える場合、経路グラフ
にはφ−εのクロック期間におけるクリティカルサイク
ルはない。それは、経路グラフのどの弧でも、多くても
φ−εの再タイムされた弧の重みを持っているからであ
る。従って、再タイム経路グラフにはクリティカルサイ
クルは無い。
にはφ−εのクロック期間におけるクリティカルサイク
ルはない。それは、経路グラフのどの弧でも、多くても
φ−εの再タイムされた弧の重みを持っているからであ
る。従って、再タイム経路グラフにはクリティカルサイ
クルは無い。
【００２０】任意の整数線形プログラムを解くことは、
難問である。それはＮＰハード問題に属す。しかし、Ｉ
ＬＰは特定の種類の整数線形プログラムであり、そして
最適解はかなり速やかに決定することができる。ＩＬＰ
の線形プログラム緩和を考えてみる。線形プログラム緩
和における目的関数および制約はＩＬＰと同一である。
しかし、変数ｘ0 ，ｘ1 ，・・・，ｘk およびεは整数
であるという制約を取り除いてみる。そこで、それらは
実数値をとることができる。この線形プログラム緩和問
題はＬＰと称される。
難問である。それはＮＰハード問題に属す。しかし、Ｉ
ＬＰは特定の種類の整数線形プログラムであり、そして
最適解はかなり速やかに決定することができる。ＩＬＰ
の線形プログラム緩和を考えてみる。線形プログラム緩
和における目的関数および制約はＩＬＰと同一である。
しかし、変数ｘ0 ，ｘ1 ，・・・，ｘk およびεは整数
であるという制約を取り除いてみる。そこで、それらは
実数値をとることができる。この線形プログラム緩和問
題はＬＰと称される。
【００２１】 問題ＬＰ Ｍａｘｉｍｉｚｅ ε Ｓｕｂｊｅｃｔ ｔｏ ｘｉ−ｘｉ＋ε≦φ−ｄｉｊ ： ｌｉ→ｌｊ ∈ Ｅ ε≦φ−φＬ 全変数は自由である （弧の重みであるｄｉｊと、ラッチの移動量である
Ｘｉ、Ｘｊと、クロック周期の下限値であるφＬを制約
条件としてεの最大値を得るプログラム）
Ｘｉ、Ｘｊと、クロック周期の下限値であるφＬを制約
条件としてεの最大値を得るプログラム）
【００２２】εLPがＬＰ問題に対する最適解である場
合、［εLP］はＩＬＰ問題に対する最適解である。
合、［εLP］はＩＬＰ問題に対する最適解である。
【００２３】ＩＬＰにおける変数は整数であると限られ
ているので、ＩＬＰの最適解は、上記から、ＬＰの最適
解によって限定される。ＬＰ解を超えない最大整数は
［εLP］である。変数ｘ0 ，ｘ1 ，・・・，ｘk に対す
る１組の整数値があり、それに対するＩＬＰの目的関数
は値［εLP］をとる、ということは明らかになってい
る。
ているので、ＩＬＰの最適解は、上記から、ＬＰの最適
解によって限定される。ＬＰ解を超えない最大整数は
［εLP］である。変数ｘ0 ，ｘ1 ，・・・，ｘk に対す
る１組の整数値があり、それに対するＩＬＰの目的関数
は値［εLP］をとる、ということは明らかになってい
る。
【００２４】ｘ0 ，ｘ1 ，・・・，ｘk を、ＬＰ問題に
対する最適解εLPに対応する１組の値とする。変数のう
ちのどれも整数値をとり得ないことに注目されたい。Ｌ
Ｐ問題のこの制約組にε＝［εLP］を代入する場合、す
べての制約不等式はなお満足される。ＬＰ制約を下記の
不等式組に書き直すことができる。
対する最適解εLPに対応する１組の値とする。変数のう
ちのどれも整数値をとり得ないことに注目されたい。Ｌ
Ｐ問題のこの制約組にε＝［εLP］を代入する場合、す
べての制約不等式はなお満足される。ＬＰ制約を下記の
不等式組に書き直すことができる。
【００２５】
【数３】 １ｉ→１ｊ∈Ｅ：ｘｊ−ｘｉ≦φ−ｄij−［εLP］
【００２６】φ、ｄij及び［εLP］は整数であるので、
すべての不等式の右辺は整数である。左辺の制約マトリ
ックスはユニモジュラである。ユニモジュラとは、各行
に一つずつ１があり各列に一つずつ１がある行列又は、
行列式が１になる行列のことである。従って、整数可能
解があり得るし、そしてそれは、ベルマン・フォードア
ルゴリズムあるいは、「組み合わせ最適化アルゴリズム
及び複雑性」と題する、Ｃ．Ｈ．パパディミトリオ（Ｐ
ａｐａ ｄｉｍｉｔｒｉｏ）とＫ．スタイグリッツ（Ｓ
ｔｅｉｇｌｉｔｚ）による刊行物（プレンティホール
（１９８２）、イングルウッド グリックス、ニュージ
ャージ）に記述された種類の最低コストネットワーク流
れ法を利用して、決定することができる。ＩＬＰはま
た、この整数解に対する［εLP］の最大値をとる。
すべての不等式の右辺は整数である。左辺の制約マトリ
ックスはユニモジュラである。ユニモジュラとは、各行
に一つずつ１があり各列に一つずつ１がある行列又は、
行列式が１になる行列のことである。従って、整数可能
解があり得るし、そしてそれは、ベルマン・フォードア
ルゴリズムあるいは、「組み合わせ最適化アルゴリズム
及び複雑性」と題する、Ｃ．Ｈ．パパディミトリオ（Ｐ
ａｐａ ｄｉｍｉｔｒｉｏ）とＫ．スタイグリッツ（Ｓ
ｔｅｉｇｌｉｔｚ）による刊行物（プレンティホール
（１９８２）、イングルウッド グリックス、ニュージ
ャージ）に記述された種類の最低コストネットワーク流
れ法を利用して、決定することができる。ＩＬＰはま
た、この整数解に対する［εLP］の最大値をとる。
【００２７】前述のことから見れば、φL の初期クロッ
ク期間を有する回路が与えられる場合、最適再タイム回
路を得るための高速アルゴリズムは、下記のステップか
ら成る。 １．経路グラフを構成し、φL を決定する。 ２．ＬＰ問題を構成する。制約セットは経路グラフの弧
ごとに１つの不等式を持つ。従って、ＬＰは｜Ｅ｜制約
および｜Ｖ｜変数を持つ。 ３．基準線形プログラミング技術を利用して、ＬＰを解
く。εLPを目的関数の最適値とする。 ４．既知の再タイミング技術を利用して、［εLP］のク
ロック期間を達成するように、回路を再タイムする。
ク期間を有する回路が与えられる場合、最適再タイム回
路を得るための高速アルゴリズムは、下記のステップか
ら成る。 １．経路グラフを構成し、φL を決定する。 ２．ＬＰ問題を構成する。制約セットは経路グラフの弧
ごとに１つの不等式を持つ。従って、ＬＰは｜Ｅ｜制約
および｜Ｖ｜変数を持つ。 ３．基準線形プログラミング技術を利用して、ＬＰを解
く。εLPを目的関数の最適値とする。 ４．既知の再タイミング技術を利用して、［εLP］のク
ロック期間を達成するように、回路を再タイムする。
【００２８】それから、再タイム回路は低減したクロッ
ク期間で動作する。次いで、開発された原理は特定の場
合に適用することができる。再び、図１の回路１０を考
えてみる。動作に必要なそのクロック期間はφ＝４であ
り、それはラッチｌ2 から一次出力ｅまで、この長さの
経路があるからである。一次入力ｃから一次出力ｅま
で、２の経路遅延を有する組合せ路があるので、最適ク
ロック期間の下限は２である。さらに、ラッチｌ2 は２
の自己ループ遅延を持つ。従って、φL ＝２。
ク期間で動作する。次いで、開発された原理は特定の場
合に適用することができる。再び、図１の回路１０を考
えてみる。動作に必要なそのクロック期間はφ＝４であ
り、それはラッチｌ2 から一次出力ｅまで、この長さの
経路があるからである。一次入力ｃから一次出力ｅま
で、２の経路遅延を有する組合せ路があるので、最適ク
ロック期間の下限は２である。さらに、ラッチｌ2 は２
の自己ループ遅延を持つ。従って、φL ＝２。
【００２９】図２に示される回路１０に対する経路グラ
フは７つの弧を有し、従って７つの経路遅延制約があ
る。回路１０に対するＬＰ問題は、以下のように特定さ
れる。 Maximize ε Subject to ｘ1 −ｘ0 ＋ε≦３ ｘ3 −ｘ1 ＋ε≦２ ｘ0 −ｘ3 ＋ε≦１ ｘ3 −ｘ0 ＋ε≦３ ｘ3 −ｘ2 ＋ε≦１ ｘ2 −ｘ3 ＋ε≦３ ｘ0 −ｘ2 ＋ε≦０ ε≦２ 全変数は自由である。
フは７つの弧を有し、従って７つの経路遅延制約があ
る。回路１０に対するＬＰ問題は、以下のように特定さ
れる。 Maximize ε Subject to ｘ1 −ｘ0 ＋ε≦３ ｘ3 −ｘ1 ＋ε≦２ ｘ0 −ｘ3 ＋ε≦１ ｘ3 −ｘ0 ＋ε≦３ ｘ3 −ｘ2 ＋ε≦１ ｘ2 −ｘ3 ＋ε≦３ ｘ0 −ｘ2 ＋ε≦０ ε≦２ 全変数は自由である。
【００３０】多くの入手可能な線形プログラミング商用
パッケージのどれかを利用してＬＰを解く場合、εの最
適値は２であることが分かる。従って、最適クロック期
間φopt ＝φ−ε＝４−２＝２。回路１０に対して可能
な最適クロック期間は２であるということを知っていれ
ば、回路設計者にとって、２のクロック期間を達成する
ように回路を再タイムすることは、比較的簡単なことで
ある。図３は、機能的には回路１０と同等であるが、２
のクロック期間のみを必要とする再タイム回路２０を示
す。以下で説明するように、コンピュータを使用して再
タイミングを実行するために各種のツールを利用するこ
とができる。
パッケージのどれかを利用してＬＰを解く場合、εの最
適値は２であることが分かる。従って、最適クロック期
間φopt ＝φ−ε＝４−２＝２。回路１０に対して可能
な最適クロック期間は２であるということを知っていれ
ば、回路設計者にとって、２のクロック期間を達成する
ように回路を再タイムすることは、比較的簡単なことで
ある。図３は、機能的には回路１０と同等であるが、２
のクロック期間のみを必要とする再タイム回路２０を示
す。以下で説明するように、コンピュータを使用して再
タイミングを実行するために各種のツールを利用するこ
とができる。
【００３１】しかし、例示した実施例を形成する比較的
簡単な回路において、２ユニットのクロック期間は最適
であるだけでなく、実行可能であることを知っている熟
練の設計者であれば、図３に示された所望の最適再タイ
ム構造を達成するための予備設計において必要な変化
を、コンピュータを必要としないで、速やかに決定する
ことができるであろう。図３の回路２０では、ゲートは
図１の回路１０における対応ゲートより１０だけ高位の
番号を付けられており、そしてＯＲゲート２２の出力と
ＡＮＤゲート２５への１入力間にラッチｌ4 が挿入さ
れ、そしてＡＮＤゲート２５の出力と、インバータ２９
へのフィードバックループとＯＲゲート２６への１入力
の両者との間にラッチｌ5 が挿入されている。この構造
は、２ユニットに遅延のあるクロック期間で動作するよ
うになっている。
簡単な回路において、２ユニットのクロック期間は最適
であるだけでなく、実行可能であることを知っている熟
練の設計者であれば、図３に示された所望の最適再タイ
ム構造を達成するための予備設計において必要な変化
を、コンピュータを必要としないで、速やかに決定する
ことができるであろう。図３の回路２０では、ゲートは
図１の回路１０における対応ゲートより１０だけ高位の
番号を付けられており、そしてＯＲゲート２２の出力と
ＡＮＤゲート２５への１入力間にラッチｌ4 が挿入さ
れ、そしてＡＮＤゲート２５の出力と、インバータ２９
へのフィードバックループとＯＲゲート２６への１入力
の両者との間にラッチｌ5 が挿入されている。この構造
は、２ユニットに遅延のあるクロック期間で動作するよ
うになっている。
【００３２】この提案された最適再タイミング技術は、
ＣOR（ｃｏｍｐｕｔｅ ｏｐｔｉｍａｌ ｒｅｔｉｍｉ
ｎｇ）と称するＣプログラミング言語プログラムで実現
されている。このプロトタイプ実現は、２ステップから
成り、（１）最適クロック期間の計算、および（２）最
適クロック期間に対する可能再タイミングを計算するこ
とである。ＣORの最適クロック期間計算ステップにおい
ては、ＣＰＥＸ最適化，Ｉｎｃ．インクラインヴィレッ
ジ，ＮＶ８９４５１−９４３６から入手可能なＣＰＬＥ
Ｘと称する商用線形プログラミングパッケージを利用し
て、線形プログラムを解くことができる。最適クロック
期間に対する実現可能再タイミングは、ユニット遅延再
タイミングツールを利用して決定されるが、このツール
は、「合成および最適化を利用する順序回路設計」と題
する論文（１９９２年１０月、コンピュータ設計につい
てのＩＥＥＥ Ｃｏｎｆ．にて公開，３２８〜３３３ペ
ージ）で説明された論理合成フレームワークＳＩＳの部
分である。ＳＩＳの再タイミングツールは反復緩和アル
ゴリズムを実行しており、それは所定クロック期間にお
ける実行可能再タイミングを得るための最も速い既知の
方法である。
ＣOR（ｃｏｍｐｕｔｅ ｏｐｔｉｍａｌ ｒｅｔｉｍｉ
ｎｇ）と称するＣプログラミング言語プログラムで実現
されている。このプロトタイプ実現は、２ステップから
成り、（１）最適クロック期間の計算、および（２）最
適クロック期間に対する可能再タイミングを計算するこ
とである。ＣORの最適クロック期間計算ステップにおい
ては、ＣＰＥＸ最適化，Ｉｎｃ．インクラインヴィレッ
ジ，ＮＶ８９４５１−９４３６から入手可能なＣＰＬＥ
Ｘと称する商用線形プログラミングパッケージを利用し
て、線形プログラムを解くことができる。最適クロック
期間に対する実現可能再タイミングは、ユニット遅延再
タイミングツールを利用して決定されるが、このツール
は、「合成および最適化を利用する順序回路設計」と題
する論文（１９９２年１０月、コンピュータ設計につい
てのＩＥＥＥ Ｃｏｎｆ．にて公開，３２８〜３３３ペ
ージ）で説明された論理合成フレームワークＳＩＳの部
分である。ＳＩＳの再タイミングツールは反復緩和アル
ゴリズムを実行しており、それは所定クロック期間にお
ける実行可能再タイミングを得るための最も速い既知の
方法である。
【００３３】表１は、幾つかのＩＳＣＡＳ’８９および
ＭＣＮＣ順序ベンチマーク回路での実験結果を示す。全
結果は、Ｓｐａｒｃ２ワークステーションにおいてＣOR
を実行することによって得られたものである。すべての
回路が、ＳＩＳのｔｅｃｈ−ｄｅｃｏｍｐ−ａ２プログ
ラムを利用して、２入力ＮＡＮＤゲートのみから成る回
路に変換されている。ｔｅｃｈ−ｄｅｃｏｍｐ利用後に
得た回路が、この実験にとっての初期回路である。回路
のゲート数およびラッチ数は、それぞれ、ゲートおよび
ＦＦの欄に示されている。このデータは、回路のサイズ
についての考えを与えるために記載されている。
ＭＣＮＣ順序ベンチマーク回路での実験結果を示す。全
結果は、Ｓｐａｒｃ２ワークステーションにおいてＣOR
を実行することによって得られたものである。すべての
回路が、ＳＩＳのｔｅｃｈ−ｄｅｃｏｍｐ−ａ２プログ
ラムを利用して、２入力ＮＡＮＤゲートのみから成る回
路に変換されている。ｔｅｃｈ−ｄｅｃｏｍｐ利用後に
得た回路が、この実験にとっての初期回路である。回路
のゲート数およびラッチ数は、それぞれ、ゲートおよび
ＦＦの欄に示されている。このデータは、回路のサイズ
についての考えを与えるために記載されている。
【００３４】どの回路に対しても、２つの実験を行っ
た。最適再タイム回路は、ＣORならびにＳＩＳの最適再
タイミングツールを利用して、独立的に得られる。クロ
ック期間の欄では、初期の欄で回路の初期クロック期間
が示される。ＣORによって決定された最適クロック期間
は、最適の欄で示される。これらの値は、ＳＩＳの再タ
イミングツールによって報告された最適クロック期間と
一致する。ＣＰＵsecsの欄では、ＳＩＳの再タイミング
ツールのための計算時間（ＣＰＵ秒）を報告している。
ｃｌｍａおよびｃｌｍｂのような幾つかの大規模回路に
対しては、３日間以上実行された後、ＳＩＳの実行は打
ち切られている。ＣORのためのＣＰＵ時間は３つの欄で
示されている。ＣＰＬＥＸの欄では、最適クロック期間
を決定するために線形プログラムを解くのに費やした時
間量が示されている。ＣＰＵ秒より小さい計算時間は０
で示される。最適クロック期間が一旦、決定されると、
実現可能再タイミングを決定するために、ＳＩＳの再タ
イミングツールが利用される。欄ＳＩＳは、実現可能再
タイミングを決定するのに必要なＣＰＵ秒の数を示す。
ＣORのためのＣＰＬＥＸとＳＩＳ時間の和は、総計の欄
に示されている。
た。最適再タイム回路は、ＣORならびにＳＩＳの最適再
タイミングツールを利用して、独立的に得られる。クロ
ック期間の欄では、初期の欄で回路の初期クロック期間
が示される。ＣORによって決定された最適クロック期間
は、最適の欄で示される。これらの値は、ＳＩＳの再タ
イミングツールによって報告された最適クロック期間と
一致する。ＣＰＵsecsの欄では、ＳＩＳの再タイミング
ツールのための計算時間（ＣＰＵ秒）を報告している。
ｃｌｍａおよびｃｌｍｂのような幾つかの大規模回路に
対しては、３日間以上実行された後、ＳＩＳの実行は打
ち切られている。ＣORのためのＣＰＵ時間は３つの欄で
示されている。ＣＰＬＥＸの欄では、最適クロック期間
を決定するために線形プログラムを解くのに費やした時
間量が示されている。ＣＰＵ秒より小さい計算時間は０
で示される。最適クロック期間が一旦、決定されると、
実現可能再タイミングを決定するために、ＳＩＳの再タ
イミングツールが利用される。欄ＳＩＳは、実現可能再
タイミングを決定するのに必要なＣＰＵ秒の数を示す。
ＣORのためのＣＰＬＥＸとＳＩＳ時間の和は、総計の欄
に示されている。
【００３５】一例として、回路ｓ３８５８４を考えてみ
る。この回路には、２７，７１０の論理ゲートと、１，
４２４のラッチがある。回路の初期クロック期間は３７
である。再タイミングによって達成され得る最適クロッ
ク期間は３４である。この発明を利用しなければ、ＳＩ
Ｓの再タイミングツールは、最適再タイム回路を得るた
めに１１５，２２５ＣＰＵ秒を必要とした。それに対し
て、発明の方法では６２秒を必要とするのみであった。
特に、最適クロック期間は、１１秒かけるのみで線形プ
ログラムを解くことによって計算され、そして残りの５
１秒は、実現可能再タイミングを決定するためにＳＩＳ
の再タイミングツールによって必要とされた。
る。この回路には、２７，７１０の論理ゲートと、１，
４２４のラッチがある。回路の初期クロック期間は３７
である。再タイミングによって達成され得る最適クロッ
ク期間は３４である。この発明を利用しなければ、ＳＩ
Ｓの再タイミングツールは、最適再タイム回路を得るた
めに１１５，２２５ＣＰＵ秒を必要とした。それに対し
て、発明の方法では６２秒を必要とするのみであった。
特に、最適クロック期間は、１１秒かけるのみで線形プ
ログラムを解くことによって計算され、そして残りの５
１秒は、実現可能再タイミングを決定するためにＳＩＳ
の再タイミングツールによって必要とされた。
【００３６】この表で報告された実験結果は、明らか
に、提案された技術の卓越性を示している。ＣORの性能
は、ほとんど全ての回路に対するＳＩＳの再タイミング
ツールに比べて数桁、高速である。
に、提案された技術の卓越性を示している。ＣORの性能
は、ほとんど全ての回路に対するＳＩＳの再タイミング
ツールに比べて数桁、高速である。
【００３７】回路に対する最適設計が一旦、実現される
と、回路を製造するために従来技術を利用することがで
きる。
と、回路を製造するために従来技術を利用することがで
きる。
【００３８】なお、説明した特定の実施例は、発明の基
本原理を示したに過ぎないことを理解されたい。
本原理を示したに過ぎないことを理解されたい。
【図面の簡単な説明】
【図１】発明を説明するために、その最適クロック期間
を見つけようとする同期論理回路である。
を見つけようとする同期論理回路である。
【図２】図１に示される回路のための経路グラフであ
る。
る。
【図３】発明の設計特徴に従って再タイムされた後の、
図１の機能同等回路である。
図１の機能同等回路である。
【図４】発明によって可能にされた最適再タイミングの
時間を計算する際の改良を示す表を示す図である。
時間を計算する際の改良を示す表を示す図である。
１０ 回路 １１ インバータ １２，１６ ＯＲゲート １３，１５，１７ ＡＮＤゲート
Claims (1)
- 【請求項１】論理ゲートとクロックラッチとが相互接続
された同期論理回路の最適クロック周期を決定する方法
において、 一定の機能を有し、各々がその末端においてラッチ、一
次入力又は一次出力の組み合わせによって限定されてい
る複数の経路区分を含む前記同期論理回路を予備設計す
るステップと、 前記各ラッチは個別の点とし、前記一次入力と前記一次
出力はまとめて別の点とし、前記経路区分は経路グラフ
の弧とし、前記経路区分の遅延を各々の弧の重みとして
各々表した経路グラフを生成するステップと、 前記経路グラフにおける最長経路区分の遅延を求めるス
テップと、前記弧の重み、ラッチの移動量およびクロックの周期の
下限値を制約条件として 前記経路グラフの線形プログラ
ム緩和問題に、対する最適値から最適クロック周期を決
定するステップとから構成されることを特徴とする同期
論理回路における最適クロック周期の決定方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US7378793A | 1993-06-08 | 1993-06-08 | |
| US08/073787 | 1993-06-08 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06348778A JPH06348778A (ja) | 1994-12-22 |
| JP2601177B2 true JP2601177B2 (ja) | 1997-04-16 |
Family
ID=22115798
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5331689A Expired - Fee Related JP2601177B2 (ja) | 1993-06-08 | 1993-12-27 | 同期論理回路における最適クロック周期の決定方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5555188A (ja) |
| JP (1) | JP2601177B2 (ja) |
Families Citing this family (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2601168B2 (ja) * | 1993-03-30 | 1997-04-16 | 日本電気株式会社 | 順次回路をリタイミングする方法および再設計する方法 |
| US5822217A (en) * | 1995-12-13 | 1998-10-13 | Synopsys, Inc. | Method and apparatus for improving circuit retiming |
| US5910898A (en) * | 1995-12-14 | 1999-06-08 | Viewlogic Systems, Inc. | Circuit design methods and tools |
| US5999716A (en) * | 1996-06-27 | 1999-12-07 | Matsushita Electric Industrial Co., Ltd. | LSI layout design method capable of satisfying timing requirements in a reduced design processing time |
| US5963728A (en) * | 1996-08-14 | 1999-10-05 | International Business Machines Corporation | Method to partition clock sinks into nets |
| US6442739B1 (en) * | 1998-05-01 | 2002-08-27 | Cadence Design Systems, Inc. | System and method for timing abstraction of digital logic circuits |
| US6282695B1 (en) | 1998-12-16 | 2001-08-28 | International Business Machines Corporation | System and method for restructuring of logic circuitry |
| US6460166B1 (en) | 1998-12-16 | 2002-10-01 | International Business Machines Corporation | System and method for restructuring of logic circuitry |
| US6339835B1 (en) | 1999-06-10 | 2002-01-15 | International Business Machines Corporation | Pseudo-anding in dynamic logic circuits |
| US6775339B1 (en) | 1999-08-27 | 2004-08-10 | Silicon Graphics, Inc. | Circuit design for high-speed digital communication |
| US7031420B1 (en) | 1999-12-30 | 2006-04-18 | Silicon Graphics, Inc. | System and method for adaptively deskewing parallel data signals relative to a clock |
| US6701496B1 (en) | 2000-07-20 | 2004-03-02 | Silicon Graphics, Inc. | Synthesis with automated placement information feedback |
| US7333516B1 (en) | 2000-07-20 | 2008-02-19 | Silicon Graphics, Inc. | Interface for synchronous data transfer between domains clocked at different frequencies |
| US6839856B1 (en) | 2000-07-20 | 2005-01-04 | Silicon Graphics, Inc. | Method and circuit for reliable data capture in the presence of bus-master changeovers |
| US6779072B1 (en) | 2000-07-20 | 2004-08-17 | Silicon Graphics, Inc. | Method and apparatus for accessing MMR registers distributed across a large asic |
| US6703908B1 (en) | 2000-07-20 | 2004-03-09 | Silicon Graphic, Inc. | I/O impedance controller |
| US6684373B1 (en) | 2000-07-20 | 2004-01-27 | Silicon Graphics, Inc. | Optimize global net timing with repeater buffers |
| US6831924B1 (en) | 2000-07-20 | 2004-12-14 | Silicon Graphics, Inc. | Variable mode bi-directional and uni-directional computer communication system |
| US6681293B1 (en) | 2000-08-25 | 2004-01-20 | Silicon Graphics, Inc. | Method and cache-coherence system allowing purging of mid-level cache entries without purging lower-level cache entries |
| US20020091983A1 (en) * | 2001-01-08 | 2002-07-11 | Andreev Alexander E. | Optimal clock timing schedule for an integrated circuit |
| US7356793B2 (en) * | 2004-07-12 | 2008-04-08 | International Business Machines Corporation | Genie: a method for classification and graphical display of negative slack timing test failures |
| US7120888B2 (en) * | 2004-07-12 | 2006-10-10 | International Business Machines Corporation | Method, system and storage medium for determining circuit placement |
| US7327167B2 (en) * | 2005-04-28 | 2008-02-05 | Silicon Graphics, Inc. | Anticipatory programmable interface pre-driver |
| US7353485B1 (en) * | 2005-08-10 | 2008-04-01 | Xilinx, Inc. | Method of flexible clock placement for integrated circuit designs using integer linear programming |
| US9058451B2 (en) * | 2013-03-05 | 2015-06-16 | Synopsys, Inc. | Automatic synthesis of complex clock systems |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3617714A (en) * | 1969-04-15 | 1971-11-02 | Bell Telephone Labor Inc | Method of minimizing the interconnection cost of linked objects |
| US4263651A (en) * | 1979-05-21 | 1981-04-21 | International Business Machines Corporation | Method for determining the characteristics of a logic block graph diagram to provide an indication of path delays between the blocks |
| US5005136A (en) * | 1988-02-16 | 1991-04-02 | U.S. Philips Corporation | Silicon-compiler method and arrangement |
| US4970664A (en) * | 1988-06-10 | 1990-11-13 | Kaiser Richard R | Critical path analyzer with path context window |
| US5003487A (en) * | 1988-06-28 | 1991-03-26 | International Business Machines Corporation | Method and apparatus for performing timing correction transformations on a technology-independent logic model during logic synthesis |
| US5210700A (en) * | 1990-02-20 | 1993-05-11 | International Business Machines Corporation | Automatic delay adjustment for static timing analysis |
| US5287289A (en) * | 1990-04-13 | 1994-02-15 | Hitachi, Ltd. | Logic synthesis method |
| US5262959A (en) * | 1990-12-07 | 1993-11-16 | Hewlett-Packard Co. | Representation and processing of hierarchical block designs |
| US5282147A (en) * | 1991-08-02 | 1994-01-25 | International Business Machines Corporation | Method and apparatus for optimizing a logic network |
-
1993
- 1993-12-27 JP JP5331689A patent/JP2601177B2/ja not_active Expired - Fee Related
-
1994
- 1994-12-27 US US08/365,971 patent/US5555188A/en not_active Expired - Fee Related
Non-Patent Citations (1)
| Title |
|---|
| 情報処理学会第４２回全国大会講演論文集 ６−１４２〜１４３頁 １Ｊ−６ 平塚憲晴他「順序回路のラッチ再割当て手法」 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH06348778A (ja) | 1994-12-22 |
| US5555188A (en) | 1996-09-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2601177B2 (ja) | 同期論理回路における最適クロック周期の決定方法 | |
| Sapatnekar | Timing | |
| Gregory et al. | SOCRATES: A system for automatically synthesizing and optimizing combinational logic | |
| US9223917B2 (en) | Polynomial synthesis | |
| US6023568A (en) | Extracting accurate and efficient timing models of latch-based designs | |
| US5448497A (en) | Exploiting multi-cycle false paths in the performance optimization of sequential circuits | |
| Pasandi et al. | SFQmap: A technology mapping tool for single flux quantum logic circuits | |
| US7945880B1 (en) | Constraint based retiming of synchronous circuits | |
| Testa et al. | Logic synthesis for established and emerging computing | |
| US5790830A (en) | Extracting accurate and efficient timing models of latch-based designs | |
| Pasandi et al. | A dynamic programming-based, path balancing technology mapping algorithm targeting area minimization | |
| Li et al. | Multi-phase clocking for multi-threaded gate-level-pipelined superconductive logic | |
| Sze et al. | Path based buffer insertion | |
| Tsai et al. | Multilevel logic synthesis for arithmetic functions | |
| Peng et al. | Spars: A full flow quantum-dot cellular automata circuit design tool | |
| Ashar et al. | Exploiting multi-cycle false paths in the performance optimization of sequential circuits | |
| Maheshwari et al. | Optimizing large multiphase level-clocked circuits | |
| US6725248B1 (en) | Decimation filter and signal processing method using the same | |
| Veneris et al. | Design rewiring using ATPG | |
| Malik et al. | Performance optimization of pipelined logic circuits using peripheral retiming and resynthesis | |
| US11303281B2 (en) | Efficient pipelined architecture for superconducting single flux quantum logic circuits utilizing dual clocks | |
| Mahzoon et al. | Polynomial formal verification of general tree-like circuits | |
| Bund et al. | Optimal metastability-containing sorting via parallel prefix computation | |
| EP0870253A1 (en) | Method for reducing power consumption of switching nodes in a circuit | |
| Cheng | Single clock partial scan |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19961126 |
|
| LAPS | Cancellation because of no payment of annual fees |