JPH03206563A - 階層論理分割方法及び階層論理処理装置 - Google Patents
階層論理分割方法及び階層論理処理装置Info
- Publication number
- JPH03206563A JPH03206563A JP2272260A JP27226090A JPH03206563A JP H03206563 A JPH03206563 A JP H03206563A JP 2272260 A JP2272260 A JP 2272260A JP 27226090 A JP27226090 A JP 27226090A JP H03206563 A JPH03206563 A JP H03206563A
- Authority
- JP
- Japan
- Prior art keywords
- logic
- elements
- logical
- mounted components
- functional elements
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/392—Floor-planning or layout, e.g. partitioning or placement
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Architecture (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は高速演算処理装置などの論理設計のための論理
分割方法に係り、特に、階層的に記述された論理構造に
適した自動論理分割方法及び論理分割処理装置に関する
。
分割方法に係り、特に、階層的に記述された論理構造に
適した自動論理分割方法及び論理分割処理装置に関する
。
論理分割とは、所期の論理演算を実行するための接続関
係におかれるべき多数の論理ゲートを、内部に含むこと
が可能な実装部品の最大搭載論理ゲート数、最大ピン数
の制約条件を満たしながら、例えばボード、モジュール
、ＬＩＳチップ等の実装部品に割り当てる作業であり、
従来から、これを電子計算機を用いて自動的に行なう方
法が種々提案されている。論理ゲートを自動的に割り当
てる方法は、論理ゲート間の接続情報にのみ注目して分
割を行う方法が一般的であり、結合度の高い論理ゲート
を順次まとめていく最大結合一最小非結合法（平野、平
川他：電子交換機用ＩＣパッケージ自動設計の一手法、
昭和４７年信学会全国大会論文集、ｐｌ２８８ （１９
７２））や、最初にいくつかの核を生成し、その核に対
して信号接続本数の多い順にゲートを許容数まで取り込
んでいくクラスタ成長法、アイ ニシオ力他：アン ア
８一 ブローチ トウー ゲート アサイニメント アンド
モジュール プレイスメント フォー プリンテイド
ワイヤリング ボーズ，アイ・イー・イー・イー トラ
ンザクション コンピュータ第Ｃ−２９巻、第８号、第
６８１頁から第６８８頁（１ ９ ８ ０ ） （Ｉ．
Ｎｉｓｈｉｏｋａ ｅｔ ａｌ ： ＡｎＡｐｐｒｏ
ａｃｈ ｔｏ Ｇａｔｅ Ａｓｓｉｇｎｍｅｎｔ ａｎ
ｄ ＭｏｄｕｌｅＰｌａｃｅｍｅｎｔ ｆｏｒ Ｐｒｉ
ｎｔｅｄ Ｗｉｒｉｎｇ Ｂｏａｒｄｓ， ＩＥＥＥＴ
ｒａｎｓ． Ｃｏｍｐｕｔ．， Ｖｏｌ．Ｃ−２９，
Ｎｏ．８， ｐｐ．６８１−６８８（１９８０） ）や
、接続情報を基に、論理ゲートをいくつかの機能グルー
プに分割し、機能グループ単位に実装単位へ割り付ける
マッピング法、ルソー，アール，エル：ア ヒューリス
ティク プ口シデエア ワオー ザ パーティショニン
グ アンドマッピング オブ コンピュータロジック
グラフス，アイ・イー・イー・イー トランザクション
ズ コンピュータ 第Ｃ−２０巻，第１２号，第１４５
５頁から第１４６２頁（１ ９ ７ １）（Ｒｕｓｓｏ
， Ｒ． Ｌ． ： Ａ Ｈｅｕｒｉｓｔｉｃ Ｐｒｏ
ｃｅｄｕｒｅ ｆｏｒｔｈｅ Ｐａｒｔｉｔｉｏｎｉｎ
ｇ ａｎｄ Ｍａｐｐｉｎｇ ｏｆ Ｃｏｍｐｕｔｅｒ
Ｌｏｇｉｃ Ｇｒａｐｈｓ， ＩＥＥＥ Ｔｒａｎｓ．
Ｃｏｍｐｕｔ．， Ｖｏｌ．Ｃ−２０，Ｎｏ．１２，
ｐｐ．１４５５−１４６２ （１９７１））などが知
られている。また、回路を機能分割する際に、階層的な
論理情報を利用する手法、ティー エス ペイネ他：オ
ートメイティド パーティショニング オブハイアラー
キ力ル スボシファイド デジタルシステム，プロシー
ディング 第１９回 デザイン オートメーション コ
ンファレンス 第１８２頁から第１９２頁（１９８２）
（Ｔ．Ｓ．Ｐａｙｎｅ， ｅｔ ａｌ．： Ａｕｔｏｍ
ａｔｅｄ Ｐａｒｔｉｔｉｏｎｉｎｇ ｏｆＨｉｅｒａ
ｒｃｈｉｃａｌ Ｓｐｅｃｉｆｉｅｄ Ｄｉｇｉｔａｌ
Ｓｙｓｔｅｍｓ， Ｐｒｏｃ．１９ｔｈ Ｄｅｓｉｇ
ｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆ．， ｐｐ．１８
２−１９２（１９８２） ）が発表されているがいずれ
も論理ゲートをすべて対象にして論理分割を行う。
係におかれるべき多数の論理ゲートを、内部に含むこと
が可能な実装部品の最大搭載論理ゲート数、最大ピン数
の制約条件を満たしながら、例えばボード、モジュール
、ＬＩＳチップ等の実装部品に割り当てる作業であり、
従来から、これを電子計算機を用いて自動的に行なう方
法が種々提案されている。論理ゲートを自動的に割り当
てる方法は、論理ゲート間の接続情報にのみ注目して分
割を行う方法が一般的であり、結合度の高い論理ゲート
を順次まとめていく最大結合一最小非結合法（平野、平
川他：電子交換機用ＩＣパッケージ自動設計の一手法、
昭和４７年信学会全国大会論文集、ｐｌ２８８ （１９
７２））や、最初にいくつかの核を生成し、その核に対
して信号接続本数の多い順にゲートを許容数まで取り込
んでいくクラスタ成長法、アイ ニシオ力他：アン ア
８一 ブローチ トウー ゲート アサイニメント アンド
モジュール プレイスメント フォー プリンテイド
ワイヤリング ボーズ，アイ・イー・イー・イー トラ
ンザクション コンピュータ第Ｃ−２９巻、第８号、第
６８１頁から第６８８頁（１ ９ ８ ０ ） （Ｉ．
Ｎｉｓｈｉｏｋａ ｅｔ ａｌ ： ＡｎＡｐｐｒｏ
ａｃｈ ｔｏ Ｇａｔｅ Ａｓｓｉｇｎｍｅｎｔ ａｎ
ｄ ＭｏｄｕｌｅＰｌａｃｅｍｅｎｔ ｆｏｒ Ｐｒｉ
ｎｔｅｄ Ｗｉｒｉｎｇ Ｂｏａｒｄｓ， ＩＥＥＥＴ
ｒａｎｓ． Ｃｏｍｐｕｔ．， Ｖｏｌ．Ｃ−２９，
Ｎｏ．８， ｐｐ．６８１−６８８（１９８０） ）や
、接続情報を基に、論理ゲートをいくつかの機能グルー
プに分割し、機能グループ単位に実装単位へ割り付ける
マッピング法、ルソー，アール，エル：ア ヒューリス
ティク プ口シデエア ワオー ザ パーティショニン
グ アンドマッピング オブ コンピュータロジック
グラフス，アイ・イー・イー・イー トランザクション
ズ コンピュータ 第Ｃ−２０巻，第１２号，第１４５
５頁から第１４６２頁（１ ９ ７ １）（Ｒｕｓｓｏ
， Ｒ． Ｌ． ： Ａ Ｈｅｕｒｉｓｔｉｃ Ｐｒｏ
ｃｅｄｕｒｅ ｆｏｒｔｈｅ Ｐａｒｔｉｔｉｏｎｉｎ
ｇ ａｎｄ Ｍａｐｐｉｎｇ ｏｆ Ｃｏｍｐｕｔｅｒ
Ｌｏｇｉｃ Ｇｒａｐｈｓ， ＩＥＥＥ Ｔｒａｎｓ．
Ｃｏｍｐｕｔ．， Ｖｏｌ．Ｃ−２０，Ｎｏ．１２，
ｐｐ．１４５５−１４６２ （１９７１））などが知
られている。また、回路を機能分割する際に、階層的な
論理情報を利用する手法、ティー エス ペイネ他：オ
ートメイティド パーティショニング オブハイアラー
キ力ル スボシファイド デジタルシステム，プロシー
ディング 第１９回 デザイン オートメーション コ
ンファレンス 第１８２頁から第１９２頁（１９８２）
（Ｔ．Ｓ．Ｐａｙｎｅ， ｅｔ ａｌ．： Ａｕｔｏｍ
ａｔｅｄ Ｐａｒｔｉｔｉｏｎｉｎｇ ｏｆＨｉｅｒａ
ｒｃｈｉｃａｌ Ｓｐｅｃｉｆｉｅｄ Ｄｉｇｉｔａｌ
Ｓｙｓｔｅｍｓ， Ｐｒｏｃ．１９ｔｈ Ｄｅｓｉｇ
ｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆ．， ｐｐ．１８
２−１９２（１９８２） ）が発表されているがいずれ
も論理ゲートをすべて対象にして論理分割を行う。
多数の論理ゲートを含む例えば大型計算機のような高速
論理演算処理装置の論理設計を行おうとする場合、扱う
データは百万ゲートに達する。論理ゲートを直接対象に
する従来の各自動論理分割では、百万ゲート間の接続関
係を調べることにな？、計算機の論理設計における論理
分割処理に時間がかかり過ぎ、実用的でない。
論理演算処理装置の論理設計を行おうとする場合、扱う
データは百万ゲートに達する。論理ゲートを直接対象に
する従来の各自動論理分割では、百万ゲート間の接続関
係を調べることにな？、計算機の論理設計における論理
分割処理に時間がかかり過ぎ、実用的でない。
本発明の目的は、大型計算機のような高速論理演算処理
装置の設計時間短縮するのに有用な、高速演算処理装置
を構成する多数の論理ゲートを実装部品に割り当てる方
法および装置を提供することである。
装置の設計時間短縮するのに有用な、高速演算処理装置
を構成する多数の論理ゲートを実装部品に割り当てる方
法および装置を提供することである。
本発明は、論理機能のまとまりに従って第１の階層構造
に配列された多数の論理機能構素の中から、分割処理の
対象となる論理機能要素を選択し、分割処理対象要素間
の結合の強さに従って上記第１の階層構造における分割
処理対象要素を２つ以上の要素群に分割し、その分割結
果に従って分割処理対象要素を第２の階層構造に再配列
する。この第２の階層構造における要素群のそれぞれは
、１つの実装部品に割り当てられるべき１つまたはそれ
以上の論理ゲートを代表する。
に配列された多数の論理機能構素の中から、分割処理の
対象となる論理機能要素を選択し、分割処理対象要素間
の結合の強さに従って上記第１の階層構造における分割
処理対象要素を２つ以上の要素群に分割し、その分割結
果に従って分割処理対象要素を第２の階層構造に再配列
する。この第２の階層構造における要素群のそれぞれは
、１つの実装部品に割り当てられるべき１つまたはそれ
以上の論理ゲートを代表する。
本発明の他の側面によれば、論理機能のまとまりとして
の第１の階層構造■この第１の階層構−１１− ？においては、１つのレベルの論理機能要素は少なくと
も１つの下位レベルの論理機能要素を包含し、各論理ゲ
ートは上記論理機能要素のいずれかｌつに含まれている
■に論理的に配列されて高速論理演算装置を構成する複
数個の論理ゲートを複数個の実装部品に割り当てる論理
分割処理装置は、上記高速論理演算装置の論理演算の階
層記述についてのおよび実装仕様についての初期データ
この実装仕様のデータは、複数個の実装部品の数、実装
部品の最大搭載ゲート数、上記論理機能要素の間の結合
の強さ、および上記各実装部品の最大搭載ピン数につい
てのデータを含む一を格納するための第１のメモリと、
上記第１のメモリから上記初期データを受けてそれを一
時記憶する入力部と、上記入力部に結合され，実装部品
の数と、上記各実装部品の最大搭載ゲート数とに基づい
て、上記第１の階層構造の論理機能要素の中から或る数
の論理機能要素を処理対象論理機能要素として選択する
手段と、上記入力部に結合され，上記処理対象論理機能
要素の間の結合の強さと、１２ー ？実装部品の最大搭載ピン数と、上記各実装部品の最大
搭載ゲート数とに基づいて、上記第１の階層階造の処理
対象論理機能要素を少なくとも２つの要素群に分類する
手段と、 上記分類手段に結合され、上記第１の階層構造の処理対
象論理機能要素を、論理機能のまとまりとしての第２の
階層構造■この第２の階層構造においては、前記処理対
象論理機能要素のすべてが上記複数個の要素群に分割さ
れる■に再配列されて各要素群が相互に異なる工つの実
装部品に物理的に割り付け可能な複数個の論理機能要素
に対応するようにする手段と、上記再配列する手段から
上記第２の階層構造についてのデータを受け、一時記憶
する出力部と、上記第２の階層構造についてのデータを
記憶するための第２のメモリと、を有する。
の第１の階層構造■この第１の階層構−１１− ？においては、１つのレベルの論理機能要素は少なくと
も１つの下位レベルの論理機能要素を包含し、各論理ゲ
ートは上記論理機能要素のいずれかｌつに含まれている
■に論理的に配列されて高速論理演算装置を構成する複
数個の論理ゲートを複数個の実装部品に割り当てる論理
分割処理装置は、上記高速論理演算装置の論理演算の階
層記述についてのおよび実装仕様についての初期データ
この実装仕様のデータは、複数個の実装部品の数、実装
部品の最大搭載ゲート数、上記論理機能要素の間の結合
の強さ、および上記各実装部品の最大搭載ピン数につい
てのデータを含む一を格納するための第１のメモリと、
上記第１のメモリから上記初期データを受けてそれを一
時記憶する入力部と、上記入力部に結合され，実装部品
の数と、上記各実装部品の最大搭載ゲート数とに基づい
て、上記第１の階層構造の論理機能要素の中から或る数
の論理機能要素を処理対象論理機能要素として選択する
手段と、上記入力部に結合され，上記処理対象論理機能
要素の間の結合の強さと、１２ー ？実装部品の最大搭載ピン数と、上記各実装部品の最大
搭載ゲート数とに基づいて、上記第１の階層階造の処理
対象論理機能要素を少なくとも２つの要素群に分類する
手段と、 上記分類手段に結合され、上記第１の階層構造の処理対
象論理機能要素を、論理機能のまとまりとしての第２の
階層構造■この第２の階層構造においては、前記処理対
象論理機能要素のすべてが上記複数個の要素群に分割さ
れる■に再配列されて各要素群が相互に異なる工つの実
装部品に物理的に割り付け可能な複数個の論理機能要素
に対応するようにする手段と、上記再配列する手段から
上記第２の階層構造についてのデータを受け、一時記憶
する出力部と、上記第２の階層構造についてのデータを
記憶するための第２のメモリと、を有する。
所期の論理演算が実行されるような接続関係にある多数
の論理ゲートを、最大搭載論理ゲート数、入出力ピン数
の最大値の決まった複数個の実装部品に割り付ける自動
論理分割において、すべての論理ゲート間の接続情報に
着目して分割を行うのではなく、論理機能のまとまりに
したがった階層記述を利用して分割処理対象論理機能要
素数を削減し、最終的に論理ゲートの実装部品への割り
当てのための処理時間の処縮をはがるものである。
の論理ゲートを、最大搭載論理ゲート数、入出力ピン数
の最大値の決まった複数個の実装部品に割り付ける自動
論理分割において、すべての論理ゲート間の接続情報に
着目して分割を行うのではなく、論理機能のまとまりに
したがった階層記述を利用して分割処理対象論理機能要
素数を削減し、最終的に論理ゲートの実装部品への割り
当てのための処理時間の処縮をはがるものである。
まず、高速論理演算装置、例えば大型計算機の実装系に
ついて第８図を用いて説明する。
ついて第８図を用いて説明する。
計算機のＣＰＵは、例えば、ボートエ１，モジュール１
２，ＬＳＩ１３の３階層に分けられて実装されている。
２，ＬＳＩ１３の３階層に分けられて実装されている。
ボートｌ１には複数個のモジュールｌ２が搭載されてお
り，モジュール１２には複数個のＬＳＩ１３が搭載され
る。ＬＳＩ１３にはゲート１４，フリップフロップ１５
等が含まれる３本発明は、計算機を構成する多数のゲー
ト１４，フリップフロップｌ５等の論理ゲートを複数個
のＬＳＩチップ、複数個のモジュールあるいは複数個の
ボートに割り当てる手法に関する。
り，モジュール１２には複数個のＬＳＩ１３が搭載され
る。ＬＳＩ１３にはゲート１４，フリップフロップ１５
等が含まれる３本発明は、計算機を構成する多数のゲー
ト１４，フリップフロップｌ５等の論理ゲートを複数個
のＬＳＩチップ、複数個のモジュールあるいは複数個の
ボートに割り当てる手法に関する。
第９図に計算機設計の手順の概要を示す。計算１５
機は、方式設計１１０，論理設計１１工，実装設計１１
２の過程を経て設計され、製品となる方式設計１１０で
は、計算機内部における種々の処理の手順を具体化し、
全体ブロック図を作戒する。
２の過程を経て設計され、製品となる方式設計１１０で
は、計算機内部における種々の処理の手順を具体化し、
全体ブロック図を作戒する。
論理設計１１１では、全体ブロック図をもとにして、計
算機内部の論理演算その他の処理を論理式で記述する。
算機内部の論理演算その他の処理を論理式で記述する。
また、計算機内部の論理演算その他の処理を論理のまと
まりをもとに複数のチップの論理演算機能に分割し、機
能レベルでの論理図を作或する。実装設計１１２では、
分割された論理演算機能を、複数個の論理機能要素、例
えばそれぞれ複数個の論理ゲートを収容し得る複数個の
ＬＳＩチップに割当て、各論理ゲートの配置、配線を行
う。以上の設計作業により、実際にＬＳＩチップやプリ
ント基板を製造するためのデータが作成できる。これら
のデータを用いて各部品の製造、組立を行い、計算機を
製品化する。本発明は、論理設計１１１における論理分
割を自動的に行うのに有用であり、計算機等の設計時間
が大幅に削減できるものである。
まりをもとに複数のチップの論理演算機能に分割し、機
能レベルでの論理図を作或する。実装設計１１２では、
分割された論理演算機能を、複数個の論理機能要素、例
えばそれぞれ複数個の論理ゲートを収容し得る複数個の
ＬＳＩチップに割当て、各論理ゲートの配置、配線を行
う。以上の設計作業により、実際にＬＳＩチップやプリ
ント基板を製造するためのデータが作成できる。これら
のデータを用いて各部品の製造、組立を行い、計算機を
製品化する。本発明は、論理設計１１１における論理分
割を自動的に行うのに有用であり、計算機等の設計時間
が大幅に削減できるものである。
尚、計算機の中心となるＣＰＵＩ６は、第１０図に示す
通り、例えばＧ Ｕ １ ６ １ （Ｇｅｎｅｒａｌ
Ｕｎｉｔ） ，Ｉ Ｕｌ ６ ２ （Ｉｎｓｔｒｕｃｔ
ｉｏｎ Ｕｎｉｃ）， ＦＵＩ ６ ３（Ｆｌｏａｔｉ
ｎｇ ｐｏｉｎｔ ｏｐｅｒａｔｉｏｎ Ｕｎｉｔ）を
備えており，ＧＵ１６１は例えばアダー１６１１やレジ
スタ１６ｌ２を備えている。このようにＣＰＵ１６はあ
るまとまりを持った論理が階層的に組み立てられている
。
通り、例えばＧ Ｕ １ ６ １ （Ｇｅｎｅｒａｌ
Ｕｎｉｔ） ，Ｉ Ｕｌ ６ ２ （Ｉｎｓｔｒｕｃｔ
ｉｏｎ Ｕｎｉｃ）， ＦＵＩ ６ ３（Ｆｌｏａｔｉ
ｎｇ ｐｏｉｎｔ ｏｐｅｒａｔｉｏｎ Ｕｎｉｔ）を
備えており，ＧＵ１６１は例えばアダー１６１１やレジ
スタ１６ｌ２を備えている。このようにＣＰＵ１６はあ
るまとまりを持った論理が階層的に組み立てられている
。
第１図は本発明の第１の実施例による論理分割処理装置
のブロック図である。論理分割処理装置１０７は入力部
１０１と処理対象論理機能要素の選択部１０２と処理対
象機能要素の統合部１０３と新階層構造の作或部１０４
と出力部１０５からなる。入力部１０１は磁気ディスク
，光ディスク等の記憶媒体に格納されている計算機論理
ファイル１００から、計算機論理に関する初期データ、
例えば論理演算の階層記述、実装仕様等のデータを読み
込み、処理対象要素の選択部１０２へ渡す。
のブロック図である。論理分割処理装置１０７は入力部
１０１と処理対象論理機能要素の選択部１０２と処理対
象機能要素の統合部１０３と新階層構造の作或部１０４
と出力部１０５からなる。入力部１０１は磁気ディスク
，光ディスク等の記憶媒体に格納されている計算機論理
ファイル１００から、計算機論理に関する初期データ、
例えば論理演算の階層記述、実装仕様等のデータを読み
込み、処理対象要素の選択部１０２へ渡す。
処理対象要素の選択部１０２は論理機能のまとまりに従
った第１の階層構造を利用して分割処理対象論理機能要
素の選択を行う。統合部１０３は、分割処理対象機能要
素間の結び付きの強弱を定量化しそれに応じて分割処理
対象論理要素の統合のための分類を行う。新階層構造の
作或部１０４は分類結果に応じて、第１の階層構造にお
ける論理機能のまとまりを修正し、階層構造を再構或（
第２の階層構造を生或）する。出理部１０５は第２の階
層構造についてのデータを作或部１０４から受け、その
データを磁気ディスク等の出カファイル１０６へ格納す
る。ここで、第１０図に示したように計算機論理ファイ
ル１００には、あるまとまりを持った論理が階層的に組
み立てられた形で格納されているため、アダーなどのい
ろいろな論理に使われる汎用の部品は一回のみ記述を行
えばよく、データファイル量を削減することができる。
った第１の階層構造を利用して分割処理対象論理機能要
素の選択を行う。統合部１０３は、分割処理対象機能要
素間の結び付きの強弱を定量化しそれに応じて分割処理
対象論理要素の統合のための分類を行う。新階層構造の
作或部１０４は分類結果に応じて、第１の階層構造にお
ける論理機能のまとまりを修正し、階層構造を再構或（
第２の階層構造を生或）する。出理部１０５は第２の階
層構造についてのデータを作或部１０４から受け、その
データを磁気ディスク等の出カファイル１０６へ格納す
る。ここで、第１０図に示したように計算機論理ファイ
ル１００には、あるまとまりを持った論理が階層的に組
み立てられた形で格納されているため、アダーなどのい
ろいろな論理に使われる汎用の部品は一回のみ記述を行
えばよく、データファイル量を削減することができる。
次に、論理機能のまとまりに従った階層記述を利用して
分割処理の対象とすべき論理機能要素の数を削減し、階
層分割による処理時間の削減をはかる論理分割処理装置
１０７の動作を以下で示す。
分割処理の対象とすべき論理機能要素の数を削減し、階
層分割による処理時間の削減をはかる論理分割処理装置
１０７の動作を以下で示す。
まず、入力となる階層的に記述された計算機論理につい
て、第２図を用いて説明する。階層構造はツリー（ｔｒ
ｅｅ）構造になっている四角のそれぞれが一つの論理機
能要素（以下単に「要素」）と呼ぶ。要素から下へ技分
かれしている要素は子供要素を表す。計算機論理（例え
ば第１０図に示すＣＰＵ１６に相当）ＺがＡ，Ｂ，Ｃか
ら構或されている時、最上位要素Ｚの子供要素（構或要
素）がＡ，Ｂ，Ｃ （例えば第１０図に示すＧＵ１６１
，ＩＵ１６２，ＦＵ１６３に相当）であるというように
、第２図のｔｒｅｅ構造で表すことができる。最上位要
素２のもつ論理ゲート数はＡ，Ｂ，Ｃのもつ論理ゲート
（以下単にゲート）数の和になり、Ｅのゲート数はＢｌ
，Ｂ２，Ｂ３，Ｂ４，Ｂ５のゲート数の和となるように
、表示できる。各四角の右上に要素の包含するゲート数
が示されている。
て、第２図を用いて説明する。階層構造はツリー（ｔｒ
ｅｅ）構造になっている四角のそれぞれが一つの論理機
能要素（以下単に「要素」）と呼ぶ。要素から下へ技分
かれしている要素は子供要素を表す。計算機論理（例え
ば第１０図に示すＣＰＵ１６に相当）ＺがＡ，Ｂ，Ｃか
ら構或されている時、最上位要素Ｚの子供要素（構或要
素）がＡ，Ｂ，Ｃ （例えば第１０図に示すＧＵ１６１
，ＩＵ１６２，ＦＵ１６３に相当）であるというように
、第２図のｔｒｅｅ構造で表すことができる。最上位要
素２のもつ論理ゲート数はＡ，Ｂ，Ｃのもつ論理ゲート
（以下単にゲート）数の和になり、Ｅのゲート数はＢｌ
，Ｂ２，Ｂ３，Ｂ４，Ｂ５のゲート数の和となるように
、表示できる。各四角の右上に要素の包含するゲート数
が示されている。
また、ｌつの四角のまとまりである要素毎に論理のまと
まりを持っているので、このようなｔｒｅｅ構造は、論
理機能のまとまりに従った階層構造を示しているともい
える。第２図において、実装部品の数、すなわち分割の
核となる要素の数Ｎは２である。
まりを持っているので、このようなｔｒｅｅ構造は、論
理機能のまとまりに従った階層構造を示しているともい
える。第２図において、実装部品の数、すなわち分割の
核となる要素の数Ｎは２である。
処理対象要素の選択部１０２について説明する。
入力部１０１より入力された計算機論理は処理対象要素
の選択部１０２にて論理機能のまとまりに従って、ある
基準（例えば以下に述べる基準）で対象とする要素を選
択し、選択した要素に対して処理を施すことで，論理構
造全体に対して分割処理（論理ゲートの割り当て処理）
を行う。ある数の要素が割り当てられるべき実装部品の
最大搭載ゲート数Ｇに近い数のゲートを含む要素Ｅを核
とし、この核となる要素に対して、ゲート数の小さい要
素を統合していく。そのため、各実装部品に割り当てら
れるべき代表的な要素すなわち核となる要素と、それに
統合される要素との２種類の分割を対象要素階層構造（
第１の階層構造）に配列された多数の要素の中から選択
する必要がある。
の選択部１０２にて論理機能のまとまりに従って、ある
基準（例えば以下に述べる基準）で対象とする要素を選
択し、選択した要素に対して処理を施すことで，論理構
造全体に対して分割処理（論理ゲートの割り当て処理）
を行う。ある数の要素が割り当てられるべき実装部品の
最大搭載ゲート数Ｇに近い数のゲートを含む要素Ｅを核
とし、この核となる要素に対して、ゲート数の小さい要
素を統合していく。そのため、各実装部品に割り当てら
れるべき代表的な要素すなわち核となる要素と、それに
統合される要素との２種類の分割を対象要素階層構造（
第１の階層構造）に配列された多数の要素の中から選択
する必要がある。
すなわち、ここでは以下の式を選択基準として選択を行
なう。ｇを要素の包含するゲート数とし、αを核となる
要素を決めるパラメータ、βを統合される要素を決める
パラメータとしたとき、１９ αＧ≦ｇ≦Ｇ （式１） を満足する要素は核となる要素として選択し、ｇ≦βＧ （式２） を満足する要素は核に統合される要素として選択する。
なう。ｇを要素の包含するゲート数とし、αを核となる
要素を決めるパラメータ、βを統合される要素を決める
パラメータとしたとき、１９ αＧ≦ｇ≦Ｇ （式１） を満足する要素は核となる要素として選択し、ｇ≦βＧ （式２） を満足する要素は核に統合される要素として選択する。
但し、Ｏ〈β〈α〈１とする。第２図において、Ｇ＝５
００００，α＝０．８，β＝０．１である。また、（式
１）（式２）のいずれにもあてはまらないが、子供要素
を持たない要素は、統合される要素とする。具体的な手
法を第３図のＰＡＤ図を用いて説明する。
００００，α＝０．８，β＝０．１である。また、（式
１）（式２）のいずれにもあてはまらないが、子供要素
を持たない要素は、統合される要素とする。具体的な手
法を第３図のＰＡＤ図を用いて説明する。
分割の核となる要素の数ｎが分割数Ｎ（すなわち実装部
品の数）に等しくなるか超えるまで、またはαがαの下
限値δに等しいか超えるまで手順６ｂ−１〜６ｂ−３が
繰り返される。分割の核となる要素を選択するために手
順６ｃ−２（若しくは６ｃ−１）の処理を施し、手順６
３−３，６ｃ一５１では統合される要素を選択する。尚
、（式２〇一 ｌ）に該当しなくても実装部品の核となる要素を人手で
指定することも可能である。６Ｃ−１がその場合を示し
ている。
品の数）に等しくなるか超えるまで、またはαがαの下
限値δに等しいか超えるまで手順６ｂ−１〜６ｂ−３が
繰り返される。分割の核となる要素を選択するために手
順６ｃ−２（若しくは６ｃ−１）の処理を施し、手順６
３−３，６ｃ一５１では統合される要素を選択する。尚
、（式２〇一 ｌ）に該当しなくても実装部品の核となる要素を人手で
指定することも可能である。６Ｃ−１がその場合を示し
ている。
第２図に示す第１の階層構造で具体的に説明すれば、ま
ず最上位要素２に対しては子供要素Ａ，Ｂ，Ｃを候補テ
ーブルに登録する（６ｂ−１）。
ず最上位要素２に対しては子供要素Ａ，Ｂ，Ｃを候補テ
ーブルに登録する（６ｂ−１）。
要素Ａは前述の（式１）より分割の核となる（６ｃ−２
）。要素Ｂは（式１），（式２）のいずれも満たさずか
つ子供要素をもっているので（６ｃ−４）−この要素Ｂ
に対し子供要素Ｂｌ，Ｂ２，Ｂ３，Ｂ４，Ｂ５を候補テ
ーブルに登録する（６ｃ−５２）。要素Ｃは前述の（式
１）により分割の核となる。同様の手順を繰返し、要素
Ｂｌ，Ｂ２’，Ｂ３は手順６Ｃ−３により統合される要
素となり、Ｂ５は手順６ｃ−５１により統合される要素
となる。Ｂ４は（式ｌ），（式２）のいずれも満たさず
また子供要素をもっているのでこの要素Ｂ４に対し、子
供要素Ｂ４．１，Ｂ４２を候補テーブルに登録する。Ｂ
４１，Ｂ４．２は手順６ｃ−３により統合される要素と
なる。処理対象要素として選択されたか、あるいは子供
要素を候補テーブルに登録した要素については候補テー
ブルから削除する（手順６ｄ）。このようにトップダウ
ン方式で、論理機能のまとまりに従って対象とする要素
を探し出していく。第２図の破線部分のように、分割対
象要素より下位の階層は直接、処理の対象にしないで分
割を行うため、大幅な処理量の削減ができることが解る
。
）。要素Ｂは（式１），（式２）のいずれも満たさずか
つ子供要素をもっているので（６ｃ−４）−この要素Ｂ
に対し子供要素Ｂｌ，Ｂ２，Ｂ３，Ｂ４，Ｂ５を候補テ
ーブルに登録する（６ｃ−５２）。要素Ｃは前述の（式
１）により分割の核となる。同様の手順を繰返し、要素
Ｂｌ，Ｂ２’，Ｂ３は手順６Ｃ−３により統合される要
素となり、Ｂ５は手順６ｃ−５１により統合される要素
となる。Ｂ４は（式ｌ），（式２）のいずれも満たさず
また子供要素をもっているのでこの要素Ｂ４に対し、子
供要素Ｂ４．１，Ｂ４２を候補テーブルに登録する。Ｂ
４１，Ｂ４．２は手順６ｃ−３により統合される要素と
なる。処理対象要素として選択されたか、あるいは子供
要素を候補テーブルに登録した要素については候補テー
ブルから削除する（手順６ｄ）。このようにトップダウ
ン方式で、論理機能のまとまりに従って対象とする要素
を探し出していく。第２図の破線部分のように、分割対
象要素より下位の階層は直接、処理の対象にしないで分
割を行うため、大幅な処理量の削減ができることが解る
。
次に、選択された処理対象要素の再配列のための分類を
行なう。統合部１０３について説明する。
行なう。統合部１０３について説明する。
まず、実装部品のそれぞれに核となる要素を割り当て、
次に、各核要素に論理的に結び付きの強い要素がそれに
統合されるように分類する。統合が進むにつれて核は核
要素群に成長する論理のまとまりの良さを「結合率」と
して定量化し、これをガイドラインとして統合のための
分類を行なう。
次に、各核要素に論理的に結び付きの強い要素がそれに
統合されるように分類する。統合が進むにつれて核は核
要素群に成長する論理のまとまりの良さを「結合率」と
して定量化し、これをガイドラインとして統合のための
分類を行なう。
ここでは、２つの要素ＥＸとＥＹとの間の結合率Ｒ ｘ
， ｖを例えば前のように定義する。
， ｖを例えば前のように定義する。
ここでｒｘ，ｙ：要素ＥＸとＥＹとの間の結合本数ＰＸ
：要素ＥＸの総結合本数（ピン数）ＰＹ ：要素ＥＹ
の総結合本数（ピン数）結合率は、例えば第４図に示す
ように要素Ｅｌ，Ｅ２，Ｅ３が相互に結合されていると
、要素Ｅｌ，Ｅ２との結合率は５／７、要素Ｅ１とＥ３
との結合率は１／７等のように結びつきの強弱を表現で
きる。
：要素ＥＸの総結合本数（ピン数）ＰＹ ：要素ＥＹ
の総結合本数（ピン数）結合率は、例えば第４図に示す
ように要素Ｅｌ，Ｅ２，Ｅ３が相互に結合されていると
、要素Ｅｌ，Ｅ２との結合率は５／７、要素Ｅ１とＥ３
との結合率は１／７等のように結びつきの強弱を表現で
きる。
次に、第２図に示したような第Ｉの階層構造に配列され
た処理対象要素の中の統合要素の統合を第５Ａ〜第５Ｃ
図を基に第６図を参照して説明する。まず、分割の核と
なる要素Ａとすべての統合される要素との統合率を計算
する（第６図手順９ｃ−１，９ｄ）。本例では、結合率
の初期値ＲＯ＝０．６０ （第６図手順９ａ−１）とし
たたＺ３− め核要素Ａに対し０．６０以上の結合率となる要素Ｂｌ
，Ｂ４１を統合する。統合を行う時は統合率の基準だけ
ではなく、例えば、統合された要素のゲート数の合計（
Σｇ）およびピン数の合計（Σｐ）が実装部品の最大搭
載ゲート数Ｇ、実装部品の最大搭載ピン数、Ｐをそれぞ
れ超えないように統合を行う（第６図手Ｊ＠９ａ−３）
。次に、分割の核となる要素Ｃと、核要素Ａに統合され
なかった要素Ｂ２，Ｂ３，Ｂ５，Ｂ４２との結合率を計
算し（第６図手ＪＩＩｉ９ｂ−１，９ｃ−１，９ｄ）、
０．６０以上の要素Ｂ５を要素Ｃに統合する（第５Ａ図
）（第６図手順９ ｃ−２， ９ ｃ−３）。次に、結
合率をΔＲ（例えば０．０５）下げて（第９図手順９ｂ
−２）残りの要素に対して同様の処理を繰り返す。その
結果、処理対象要素は、第５Ｂ図の状態を経て、第５Ｃ
図に示すように、要素Ａ，Ｂｌ，Ｂ２，Ｂ４１からなる
グループｌと、Ｃ，Ｂ５，Ｂ３，Ｂ４２からなる２に分
類される。
た処理対象要素の中の統合要素の統合を第５Ａ〜第５Ｃ
図を基に第６図を参照して説明する。まず、分割の核と
なる要素Ａとすべての統合される要素との統合率を計算
する（第６図手順９ｃ−１，９ｄ）。本例では、結合率
の初期値ＲＯ＝０．６０ （第６図手順９ａ−１）とし
たたＺ３− め核要素Ａに対し０．６０以上の結合率となる要素Ｂｌ
，Ｂ４１を統合する。統合を行う時は統合率の基準だけ
ではなく、例えば、統合された要素のゲート数の合計（
Σｇ）およびピン数の合計（Σｐ）が実装部品の最大搭
載ゲート数Ｇ、実装部品の最大搭載ピン数、Ｐをそれぞ
れ超えないように統合を行う（第６図手Ｊ＠９ａ−３）
。次に、分割の核となる要素Ｃと、核要素Ａに統合され
なかった要素Ｂ２，Ｂ３，Ｂ５，Ｂ４２との結合率を計
算し（第６図手ＪＩＩｉ９ｂ−１，９ｃ−１，９ｄ）、
０．６０以上の要素Ｂ５を要素Ｃに統合する（第５Ａ図
）（第６図手順９ ｃ−２， ９ ｃ−３）。次に、結
合率をΔＲ（例えば０．０５）下げて（第９図手順９ｂ
−２）残りの要素に対して同様の処理を繰り返す。その
結果、処理対象要素は、第５Ｂ図の状態を経て、第５Ｃ
図に示すように、要素Ａ，Ｂｌ，Ｂ２，Ｂ４１からなる
グループｌと、Ｃ，Ｂ５，Ｂ３，Ｂ４２からなる２に分
類される。
結合率Ｒをガイドラインにして分割を行なう場合の手順
について第６図を用いて詳細説明する。
について第６図を用いて詳細説明する。
２４
まず、結合率Ｒに人手で指定する初期値Ｒ。を設定する
（９ａ−１）。核となる要素の工つと、すべての要素と
の結合率を計算し（９ｃ−１，９ｄ）、結合率の大きい
順にソートする（９ｃ−２）。統合される要素のピン数
合計（Σｐ）≦最大搭載ピン数（Ｐ）、統合される要素
の搭載ゲート数合計（Σｇ）≦実装部品の最大搭載ゲー
ト数（Ｇ）の制約条件を満たし、かつ、結合率がＲ以上
の要素を結合する（９ｃ−３）。残りの核と、まだ統合
されていない要素との結合率を計算し、同様の制約条件
を満たし、かつ、結合率がＲ以上となる要素を統合する
（９ｃ−３）。次に、結合率をΔＲ小さくして（９ｂ−
２）．核と、どの核にも統合されていない要素に対して
同様の処理を繰り返す（９ａ−２）。結合率はＲ．，ｎ
で打ち切る。第５Ａ図の最初の統合の時、核がＡであっ
たのに対し、第５Ｂ図の２回目の統合では核がＡ，Ｂｌ
，Ｂ４１を含む要素群になったように統合によって核が
戒長ずる。そこで、統合を行う度に核のピン数（ΣＰ）
の更新を行う。どの核にも入らなかつた、統合される要
素があれば、それらをすべて、（Ｎ＋１）番目の実装部
品とする（９ａ−３）。
（９ａ−１）。核となる要素の工つと、すべての要素と
の結合率を計算し（９ｃ−１，９ｄ）、結合率の大きい
順にソートする（９ｃ−２）。統合される要素のピン数
合計（Σｐ）≦最大搭載ピン数（Ｐ）、統合される要素
の搭載ゲート数合計（Σｇ）≦実装部品の最大搭載ゲー
ト数（Ｇ）の制約条件を満たし、かつ、結合率がＲ以上
の要素を結合する（９ｃ−３）。残りの核と、まだ統合
されていない要素との結合率を計算し、同様の制約条件
を満たし、かつ、結合率がＲ以上となる要素を統合する
（９ｃ−３）。次に、結合率をΔＲ小さくして（９ｂ−
２）．核と、どの核にも統合されていない要素に対して
同様の処理を繰り返す（９ａ−２）。結合率はＲ．，ｎ
で打ち切る。第５Ａ図の最初の統合の時、核がＡであっ
たのに対し、第５Ｂ図の２回目の統合では核がＡ，Ｂｌ
，Ｂ４１を含む要素群になったように統合によって核が
戒長ずる。そこで、統合を行う度に核のピン数（ΣＰ）
の更新を行う。どの核にも入らなかつた、統合される要
素があれば、それらをすべて、（Ｎ＋１）番目の実装部
品とする（９ａ−３）。
この結果、第２図に第１の階層構造で示された選択され
た処理対象要素は、一般に複数個の要素群に結合／分類
される。
た処理対象要素は、一般に複数個の要素群に結合／分類
される。
次に、新階層構造の作戒部１０４について説明する。新
階層構造の作戊とは、分類によって親子関係（包含関係
）がくずれた階層構造を分類結果に基づいて新しい（第
２の）階層構造に再構成する手順である。
階層構造の作戊とは、分類によって親子関係（包含関係
）がくずれた階層構造を分類結果に基づいて新しい（第
２の）階層構造に再構成する手順である。
新階層構造の作成手順を第７Ａ図及び第７Ｂ図を用いて
説明する。第７Ａ図に示す階層構造は第２図を第５Ａ図
〜第５Ｃ図の例で分割手順を説明した階層構造と同一の
ものである。まず、第７Ａ図のｔｒｅｅ構造（階層構造
）において処理対象要素に第５Ｃ図に示された要素群の
分類番号を割り付ける。第５Ｃ図に示されるように、要
素群１に含まれる要素Ａ，Ｂｌ，Ｂ２，Ｂ４１に１を付
け、要素群２に含まれる要素Ｃ，Ｂ５，Ｂ３，Ｂ４２に
２を付ける。
説明する。第７Ａ図に示す階層構造は第２図を第５Ａ図
〜第５Ｃ図の例で分割手順を説明した階層構造と同一の
ものである。まず、第７Ａ図のｔｒｅｅ構造（階層構造
）において処理対象要素に第５Ｃ図に示された要素群の
分類番号を割り付ける。第５Ｃ図に示されるように、要
素群１に含まれる要素Ａ，Ｂｌ，Ｂ２，Ｂ４１に１を付
け、要素群２に含まれる要素Ｃ，Ｂ５，Ｂ３，Ｂ４２に
２を付ける。
次に、処理対象要素を１つ以上含む親要素（例えば要素
Ｂ ４． ）に対して番号付けを行う。これらの親要素
に対しては、原則として子供要素と同じ番号をつけるが
、２個以上の子供要素を持ち、かつそれらの番号が異な
る場合は各番号毎にその番号のつけられた要素のゲート
数の総和を求め、そのゲート数の総和が最も大きい番号
に対する要素以外の子供要素を切り捨て、ゲート数の総
和の一番大きい要素と同じ番号を付ける。第７Ａ図のｔ
ｒｅｅ構造において、Ｂ ４ １は２５００ゲート、Ｂ
４２は３５００ゲートであるから、Ｂ ４− １を切り
捨て、Ｂ４には番号２を付ける。Ａの下位階層とＣの下
位階層については、論理機能のまとまりが保存できてい
る。この方法でｔｒｅｅ構造の上位に向かって番号付け
を行う。Ｂ４は２、Ｂは２の番号が付けられる。次に、
同一の番号が合流する点の上位に分割対応要素ｚ２を挿
入する。或る１つの番号のすべての要素がｔｒｅｅから
切り放されている時は、最上位要素２の子供として分割
対応要素Ｚ１を挿入する。番号１の分割処理対象要素が
そ−２７− の例である。第５Ｂ図に示すｔｒｅｅ構造が再配列され
た、第２の階層構造である。論理分割処理装置１０７は
上記のように再構或した階層構造を出力部１０５より出
力する。
Ｂ ４． ）に対して番号付けを行う。これらの親要素
に対しては、原則として子供要素と同じ番号をつけるが
、２個以上の子供要素を持ち、かつそれらの番号が異な
る場合は各番号毎にその番号のつけられた要素のゲート
数の総和を求め、そのゲート数の総和が最も大きい番号
に対する要素以外の子供要素を切り捨て、ゲート数の総
和の一番大きい要素と同じ番号を付ける。第７Ａ図のｔ
ｒｅｅ構造において、Ｂ ４ １は２５００ゲート、Ｂ
４２は３５００ゲートであるから、Ｂ ４− １を切り
捨て、Ｂ４には番号２を付ける。Ａの下位階層とＣの下
位階層については、論理機能のまとまりが保存できてい
る。この方法でｔｒｅｅ構造の上位に向かって番号付け
を行う。Ｂ４は２、Ｂは２の番号が付けられる。次に、
同一の番号が合流する点の上位に分割対応要素ｚ２を挿
入する。或る１つの番号のすべての要素がｔｒｅｅから
切り放されている時は、最上位要素２の子供として分割
対応要素Ｚ１を挿入する。番号１の分割処理対象要素が
そ−２７− の例である。第５Ｂ図に示すｔｒｅｅ構造が再配列され
た、第２の階層構造である。論理分割処理装置１０７は
上記のように再構或した階層構造を出力部１０５より出
力する。
上に述べた論理分割処理装置１０７を用いた場合の処理
対象要素数の削減効果と論理分割処理時間の短縮効果に
ついて述べる。ゲート数が５５９６ゲートの計算機論理
に対して、分割条件として、２分割、最大搭載ゲート数
Ｇが２８００ゲート、最大搭載ピン数Ｐが５００α＝０
．２、β＝０．１とすると、階層構造上における最下位
のゲートを直接対象にせざるを得ない従来の方法では処
理対象要素数が５５９６に対して、本実施例では７２と
なった。削減比は工／７８となる。
対象要素数の削減効果と論理分割処理時間の短縮効果に
ついて述べる。ゲート数が５５９６ゲートの計算機論理
に対して、分割条件として、２分割、最大搭載ゲート数
Ｇが２８００ゲート、最大搭載ピン数Ｐが５００α＝０
．２、β＝０．１とすると、階層構造上における最下位
のゲートを直接対象にせざるを得ない従来の方法では処
理対象要素数が５５９６に対して、本実施例では７２と
なった。削減比は工／７８となる。
論理分割処理時間は１／６０００となった。
第８図に示すように計算機の内部がボード、モジュール
、ＬＳＩの３階層で構成されている場合は、第１図の装
置１０７の１０１〜１０５の動作を３回実行すると３階
層に分割できる。論理分割処理装置１０７で自動論理分
割を行った後は、第−２８ ９図に示すように配置，配線，デイレイチェックを行え
ばよく効率的に計算機を設計することが可能となる。
、ＬＳＩの３階層で構成されている場合は、第１図の装
置１０７の１０１〜１０５の動作を３回実行すると３階
層に分割できる。論理分割処理装置１０７で自動論理分
割を行った後は、第−２８ ９図に示すように配置，配線，デイレイチェックを行え
ばよく効率的に計算機を設計することが可能となる。
本発明は、以上説明したように、論理機能のまとまりに
従った階層記述を利用して分割処理対象数を削減できる
ので、論理設計の処理時間を短縮できる。
従った階層記述を利用して分割処理対象数を削減できる
ので、論理設計の処理時間を短縮できる。
第１図は本発明のｌ実施例を示すブロック図、第２図、
及び第３図は処理対象要素の選択の一例を示す図、第４
図，第５図、及び第６図は統合の一例を示す図、第７図
は新階層構造の作或の一例を示す図、第８図は計算機の
実装系を示す図、第９図は計算機の設計手順を示す図、
第１０図は計算機論理の特徴を示す図である。 符号の説明 １ｌ：ボード １２：モジュール １３：ＬＳＩ １４：ゲート １５：フリップフロップ １００ ：計算機論理 １０１ ：入力 １０２：処理対象要素の選択 １０３ ：統合 １０４：新階層構造の作戒 １０５ ：出力 １０６：出力ファイル １０７：論理分割処理装置 １１０：方式設計 １ｌ１：論理設計 １１２：実装設計 ３１一 情 ／ 図 ７図
及び第３図は処理対象要素の選択の一例を示す図、第４
図，第５図、及び第６図は統合の一例を示す図、第７図
は新階層構造の作或の一例を示す図、第８図は計算機の
実装系を示す図、第９図は計算機の設計手順を示す図、
第１０図は計算機論理の特徴を示す図である。 符号の説明 １ｌ：ボード １２：モジュール １３：ＬＳＩ １４：ゲート １５：フリップフロップ １００ ：計算機論理 １０１ ：入力 １０２：処理対象要素の選択 １０３ ：統合 １０４：新階層構造の作戒 １０５ ：出力 １０６：出力ファイル １０７：論理分割処理装置 １１０：方式設計 １ｌ１：論理設計 １１２：実装設計 ３１一 情 ／ 図 ７図
Claims (1)
- 【特許請求の範囲】 １、複数の論理ゲート及びその接続関係を表現した論理
機能を複数の論理機能要素に階層構造化して配列し、こ
れらの論理機能要素を最大搭載論理ゲート数及び最大入
出力ピン数の決まっている複数の実装部品に割り当てる
階層論理分割方法において、 上記論理機能要素のうち、論理ゲート数が第１の条件値
よりも大きく、かつ上記実装部品の少なくとも１つが内
部に含むことが可能な論理ゲート数の最大値より論理機
能要素、及び論理機能要素に含まれる論理ゲート数が第
２の条件値より小さい論理機能要素を上記複数の実装部
品のいずれか１つの割り当て、 それ以外の論理機能要素に対しては、階層構造化して配
列された次の下位レベルの論理機能要素のうち、上記第
２の条件値より小さい論理機能要素を上記複数の実装部
品のいずれか１つに割り当て、 上記第２の条件値より小さくない論理機能要素に対して
は次の下位レベルの論理機能要素について上記の処理を
繰り返すことを特徴とする階層論理分割方法。 ２、請求項１記載において、上記論理機能要素を複数の
実装部品のいずれかに割り当てるに際し、論理機能要素
の１つと実装部品の１つに既に割り当てられている論理
機能要素との間の結合本数を調べ、その結合本数と上記
１つの論理機能要素の全結合本数との比を第１の値とし
、上記結合本数と上記実装部品の１つに既に割り当てら
れている論理機能要素の全結合本数との比を第２の値と
し、これらの第１の値と第２の値のいずれか大きい値を
前記論理機能要素の結合の強さを表わす値とし、既に実
装部品に割り当てられた論理機能要素の各々に対する前
記論理機能要素の結合の強さを表わす値を求め、前記論
理機能要素の結合の強さを表わす値が最大値を示す既に
実装部品に割り当てられた論理機能要素と同じ実装部品
に対して前記論理機能要素の割り当てを行うことを特徴
とする階層論理分割方法。 ３、１つのレベルの論理機能要素は少なくとも１つの下
位レベルの論理機能要素を包含し、各論理ゲートは上記
論理機能要素のいずれか１つに含まれるように論理機能
をまとめて第１の階層構造を構成し、論理的に配列され
た複数の論理ゲートを複数の実装部品に割り当てる階層
論理分割方法において 上記複数の実装部品の数と、上記各実装部品の最大搭載
論理ゲート数とに基づいて、上記第１の階層構造の論理
機能要素の中から所定の数の論理機能要素を処理対象論
理機能要素として選択し、 上記処理対象論理機能要素の間の結合の強さと、上記各
実装部品の最大入出力ピン数と、上記各実装部品の最大
搭載論理ゲート数とに基づいて、上記第１の階層構造の
処理対象論理機能要素を少なくとも２つの要素群に分割
し、 第２の階層構造にて上記第１の階層構造の処理対象論理
機能要素のすべてを上記少なくとも２つの要素群に分割
して再配列し、各要素群が相互に異なる１つの実装部品
に物理的に割り付け可能なように複数の論理機能要素を
割り当てることを特徴とする階層論理分割方法。 ４、請求項３記載において、上記選択されるに際し、上
記論理機能要素のうち、論理ゲート数が上記実装部品の
最大搭載論理ゲート数に近い方からＮ個（Ｎは上記実装
部品の数）を核要素とし、それ以外に選択された論理機
能要素を上記各核要素に統合される統合要素とし、上記
分類するに際し、上記少なくとも２つの要素群はＮ個の
要素群であり、それぞれの要素群は、上記Ｎ個の核要素
及び、上記処理対象論理機能要素の間の結合の強さと上
記各実装部品の最大入出力ピン数と上記各実装部品の最
大搭載論理ゲート数と基づいて統合される統合要素とを
備えたことを特徴とする階層論理分割方法。 ５、複数の論理ゲート及びその接続関係を表現した論理
機能を複数の論理機能要素に階層構造化して配列し、こ
れらの論理機能要素及び複数の実装部品の最大搭載論理
ゲート数及び最大入出力ピン数を入力データとし、これ
らの論理機能要素を複数の実装部品に割り当て、その結
果を出力データとする論理分割処理装置において、上記
論理機能要素のうち、論理ゲート数が第１の条件値より
も大きくかつ上記実装部品の少なくとも１つが内部に含
むことが可能な論理ゲート数の最大値より論理機能要素
、及び論理機能要素に含まれる論理ゲート数が第２の条
件値より小さい論理機能要素を上記複数の実装部品のい
ずれか１つに割り当てる手段と、 それ以外の論理機能要素に対しては、階層構造化して配
列された次の下位レベルの論理機能要素のうち、上記第
２の条件値より小さい論理機能要素を上記複数の実装部
品のいずれか１つに割り当てる手段と、 上記第２の条件値より小さくない論理機能要素に対して
は次の下位レベルの論理機能要素について上記の処理を
繰り返す手段を備えたことを特徴とする論理分割処理装
置。 ６、１つのレベルの論理機能要素は少なくとも１つの下
位レベルの論理機能要素を包含し、各論理ゲートは上記
論理機能要素のいずれか１つに含まれるように論理機能
をまとめて第１の階層構造を構成し、論理的に配列され
て高速論理演算装置を構成する複数の論理ゲートを複数
の実装部品に割り当てる論理分割処理において、少なく
とも複数の実装部品の数、実装部品の最大搭載論理ゲー
ト数、前記論理機能要素の間の結合の強さ、および前記
各実装部品の最大入出力ピン数についてのデータを含み
、前記高速論理演算装置の実装を行なうのに必要な実装
仕様についての初期データを格納するための第１のメモ
リと、 上記第１のメモリから上記初期データを受けてそれを一
時記憶する入力部と、上記入力部に結合され、実装部品
の数と、上記各実装部品の最大搭載論理ゲート数とに基
づいて、上記第１の階層構造の論理機能要素の中から所
定の数の論理機能要素を処理対象論理機能要素として選
択する手段と、 上記入力部に結合され、上記処理対象論理機能要素の間
の結合の強さと、各実装部品の最大入出力ピン数と、上
記各実装部品の最大搭載論理ゲート数とに基づいて、上
記第１の階層構造の処理対象論理機能要素を少なくとも
２つの要素群に分類する手段と、 上記分割手段に結合され、第２の階層構造にて上記第１
の階層構造の処理対象論理機能要素のすべてを上記少な
くとも２つの要素群に分割して再配列し、各要素群が相
互に異なる１つの実装部品に物理的に割り付け可能なよ
うに複数の論理機能要素を割り当てる手段と、 上記再配列する手段から上記第２の階層構造についての
データを受け、一時記憶する出力部と、 上記第２の階層構造についてのデータを記憶するための
第２のメモリと、を有することを特徴とする論理分割処
理装置。 ７、請求項６記載において、上記選択手段は、上記論理
機能素子のうち、論理ゲート数が上記実装部品の最大搭
載論理ゲート数に近い方からＮ個（Ｎは上記実装部品の
数）を核要素とし、それ以外に選択された論理機能要素
を上記各核要素に統合される統合要素として選択するよ
うに構成され、上記分類手段は、上記少なくとも２つの
要素群はＮ個の要素群でありそれぞれの要素群は、上記
Ｎ個の核要素及び、上記処理対象論理機能要素の間の結
合の強さと上記各実装部品の最大入出力ピン数と上記各
実装部品の最大搭載論理ゲート数と基づいて統合される
統合要素とを備えたことを特徴とする論理分割処理装置
。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1-264917 | 1989-10-13 | ||
| JP26491789 | 1989-10-13 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03206563A true JPH03206563A (ja) | 1991-09-09 |
Family
ID=17409999
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2272260A Pending JPH03206563A (ja) | 1989-10-13 | 1990-10-12 | 階層論理分割方法及び階層論理処理装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5229953A (ja) |
| JP (1) | JPH03206563A (ja) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5471398A (en) * | 1991-07-01 | 1995-11-28 | Texas Instruments Incorporated | MTOL software tool for converting an RTL behavioral model into layout information comprising bounding boxes and an associated interconnect netlist |
| US5359538A (en) * | 1991-08-20 | 1994-10-25 | Vlsi Technology, Inc. | Method for regular placement of data path components in VLSI circuits |
| US5349536A (en) * | 1991-08-20 | 1994-09-20 | Vlsi Technology, Inc. | Method for optimally placing components of a VLSI circuit |
| US5465218A (en) * | 1993-02-12 | 1995-11-07 | Kabushiki Kaisha Toshiba | Element placement method and apparatus |
| US5508939A (en) * | 1993-06-10 | 1996-04-16 | At&T Corp. | Method of partitioning a circuit |
| US5544088A (en) * | 1993-06-23 | 1996-08-06 | International Business Machines Corporation | Method of I/O pin assignment in a hierarchial packaging system |
| JPH07249062A (ja) * | 1994-03-11 | 1995-09-26 | Hitachi Ltd | 論理回路の生成方法 |
| US5854752A (en) * | 1996-01-19 | 1998-12-29 | Ikos Systems, Inc. | Circuit partitioning technique for use with multiplexed inter-connections |
| US6212668B1 (en) | 1996-05-28 | 2001-04-03 | Altera Corporation | Gain matrix for hierarchical circuit partitioning |
| US6301694B1 (en) | 1996-09-25 | 2001-10-09 | Altera Corporation | Hierarchical circuit partitioning using sliding windows |
| US6598069B1 (en) * | 1999-09-28 | 2003-07-22 | International Business Machines Corporation | Method and apparatus for assigning resources to logical partition clusters |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| UST940008I4 (en) * | 1974-05-17 | 1975-11-04 | Automated logic mapping system | |
| UST944001I4 (ja) * | 1974-06-13 | 1976-03-02 | ||
| UST943001I4 (ja) * | 1974-06-13 | 1976-02-03 | ||
| JPS59154055A (ja) * | 1983-02-22 | 1984-09-03 | Hitachi Ltd | 論理回路基板上の素子配置方法 |
| US4908772A (en) * | 1987-03-30 | 1990-03-13 | Bell Telephone Laboratories | Integrated circuits with component placement by rectilinear partitioning |
| US4815003A (en) * | 1987-06-19 | 1989-03-21 | General Electric Company | Structured design method for high density standard cell and macrocell layout of VLSI chips |
-
1990
- 1990-10-12 US US07/596,509 patent/US5229953A/en not_active Expired - Fee Related
- 1990-10-12 JP JP2272260A patent/JPH03206563A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| US5229953A (en) | 1993-07-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Hanan et al. | A review of the placement and quadratic assignment problems | |
| EP0789311B1 (en) | System and method for emulating memory | |
| US6499134B1 (en) | Method of assigning integrated circuit I/O signals in an integrated circuit package | |
| US5778216A (en) | Method for hierarchical time drive circuit layout by rebudgeting timing constraints of plurality of logical blocks after placement | |
| US5526278A (en) | Method and apparatus for converting field-programmable gate array implementations into mask-programmable logic cell implementations | |
| EP1543449B1 (en) | Method for eliminating routing congestion in an ic layout | |
| JP3548070B2 (ja) | 多端子ネットを自動的に発生する方法及び装置並びに多端子ネット自動発生方法を実行するためのプログラムを記憶したプログラム記憶媒体 | |
| US6446239B1 (en) | Method and apparatus for optimizing electronic design | |
| US5640327A (en) | Apparatus and method for partitioning resources for interconnections | |
| US6002861A (en) | Method for performing simulation using a hardware emulation system | |
| US5455775A (en) | Computer design system for mapping a logical hierarchy into a physical hierarchy | |
| US5912820A (en) | Method and apparatus for distributing a clock tree within a hierarchical circuit design | |
| JPH0334444A (ja) | 電子的に連結される対象の相互接続費用を最小化する方法 | |
| EP1305744A1 (en) | Method and system for hierarchical metal-end, enclosure and exposure checking | |
| JPH03206563A (ja) | 階層論理分割方法及び階層論理処理装置 | |
| WO1997034316A2 (en) | Interconnection routing system | |
| JP2002518746A (ja) | 集積回路設計の機能検証 | |
| US6086625A (en) | Method and apparatus for designing a circuit by describing logic design information with a hardware description language | |
| US6526561B2 (en) | Database for designing integrated circuit device, and method for designing integrated circuit device | |
| JPH0587867B2 (ja) | ||
| Corrigan | A placement capability based on partitioning | |
| US5493509A (en) | Method of and apparatus for generating mask layouts | |
| US5815406A (en) | Method and system for designing a circuit using RC and timing weighting of nets | |
| US5930500A (en) | Parallel processor implementation of net routing | |
| US6564367B1 (en) | Logic dividing method, logic dividing system and recording medium for storing logic dividing program |