(57)【要約】【課題】回路規模の増大によるデータ処理時間を短縮でき、処理データをデータベース等のデータに適用することが可能なデータ処理装置およびその方法、並びにプログラムを提供する。【解決手段】データ処理装置１０は、文字列を含む回路データを提供する回路データ提供部１１と、提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う置換処理部１３と、置換処理部で置換された整数値の回路データに対して、階層展開処理を含むデータ処理を行うデータ展開処理部１６とを有する。【選択図】図３
2010033492.tif 000002
【特許請求の範囲】
【請求項１】
文字列を含む回路データを提供する回路データ提供部と、
提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う置換処理部と、
上記置換処理部で置換された整数値の回路データに対して、階層展開処理を含むデータ処理を行うデータ展開処理部と
を有するデータ処理装置。
【請求項２】
上記置換処理部は、
階層ネット名の文字列を、階層名とネット名に分けてハッシュ関数に基づく処理を行って階層クラス先頭アドレスとネットクラス先頭アドレスとを個別に生成し、生成した当該アドレスを加算してハッシュ値にしてハッシュ関数に基づく処理により上記文字列に対応する上記整数値を得る
請求項１記載のデータ処理装置。
【請求項３】
上記置換処理部は回路データ中の文字列を写像した整数値にその元となる文字列との対応を記録する記憶部を有する
請求項１または２記載のデータ処理装置。
【請求項４】
上記データ展開処理部は、
階層を保持した回路データから階層を除去したネットリストの階層展開を行って回路データを作成する階層展開処理部を有し、
上記階層展開処理部は、
階層を跨いで直接繋がっているネットをグループ化するグループ化処理部と、
上記グループの中で最上位階層に存在するネットを探索することより、回路データを階層展開するネット探索部と、を含む
請求項１から３のいずれか一に記載のデータ処理装置。
【請求項５】
上記グループ化処理部は、
木構造を作成し、ネットをグループ化する
請求項４記載のデータ処理装置。
【請求項６】
上記ネット探索部は、
上記木構造を上位方向へトレースすることにより、最上位に位置するネットを求める
請求項４記載のデータ処理装置。
【請求項７】
上記ネット探索部は、
同じ階層に複数のネットが存在するときは、あらかじめ設定した順で最上位のネットを決定する
請求項６記載のデータ処理装置。
【請求項８】
上記ネット探索部は、
すべての回路素子データをリスト構造でつないでいき、リスト構造でつないだ素子データの端子に接続されているネットを最上位のネットに置換することにより、階層展開を行う
請求項６または７記載のデータ処理装置。
【請求項９】
文字列を含む回路データを提供部により提供する第１ステップと、
置換処理部で提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う第２ステップと、
上記第２ステップで置換された整数値の回路データに対して、データ展開処理部で階層展開処理を含むデータ処理を行う第３ステップと
を有するデータ処理方法。
【請求項１０】
上記第２ステップにおいては、
置換処理部で、階層ネット名の文字列を、階層名とネット名に分けてハッシュ関数に基づく処理を行って階層クラス先頭アドレスとネットクラス先頭アドレスとを個別に生成し、生成した当該アドレスを加算してハッシュ値にしてハッシュ関数に基づく処理により上記文字列に対応する上記整数値を得る
請求項９記載のデータ処理方法。
【請求項１１】
上記第３ステップにおいて、
階層を保持した回路データから階層を除去したネットリストの階層展開を行って回路データを作成するに際し、
処理部により、階層を跨いで直接繋がっているネットをグループ化し、
探索部により、上記グループの中で最上位階層に存在するネットを探索することより、回路データを階層展開する
請求項９または１０記載のデータ処理方法。
【請求項１２】
文字列を含む回路データを提供部により提供する第１ステップと、
置換処理部で提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う第２ステップと、
上記第２ステップで置換された整数値の回路データに対して、データ展開処理部で階層展開処理を含むデータ処理を行う第３ステップと
を含むデータ処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路の設計データ等を処理するデータ処理装置およびその方法、並びにプログラムに関するものである。
【背景技術】
【０００２】
半導体集積回路の設計ツールとして、各種ＥＤＡ(Electronic Design Automation)ツールが市販されている。
【０００３】
ＥＤＡツールにおいては、たとえば図１に示すように、回路データのネットリストの構文を解析し、ネットリストからネット接続情報を構築する機能を有する。
【０００４】
また、回路装置の特定素子の特性を再現することで回路シミュレーションの精度を向上させることが可能な方法が提案されている（たとえば特許文献１参照）。
【特許文献１】特開２００３−１６７９３７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところが、昨今の半導体集積回路の規模増大に伴い、市販ＥＤＡ(Electronic Design Automation)ツールの階層展開処理に要する処理時間とメモリ使用量が増大している。
すなわち、半導体集積回路の規模増大に伴いゲート数が増大し、図２に示すように、ネットリスト処理時間が指数関数的に増加している。
より具体的には、図１に示すように、“ネットリスト”から“ネット接続情報”を構築する際“文字列（ネット名)比較処理” が発生し、その処理時間が指数関数的に増加している。
【０００６】
また、この階層展開処理はさまざまな市販ＥＤＡツールの内部処理で使用されており、階層展開処理の処理速度の高速化、およびメモリ使用量の削減は、設計期間削減に繋がる重要なポイントになっている。
【０００７】
また、特許文献１に開示された方法は、文字列を対応する面積値に写像（変換）する。
そのため、面積値から文字列への逆写像（逆変換）はできない。
結果として、その面積値は識別子としての機能は持たず、データベース等のデータ処理に利用することはできないという不利益がある。
【０００８】
本発明は、回路規模の増大によるデータ処理時間を短縮でき、処理データをデータベース等のデータに適用することが可能なデータ処理装置およびその方法、並びにプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明の第１の観点のデータ処理装置は、文字列を含む回路データを提供する回路データ提供部と、提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う置換処理部と、上記置換処理部で置換された整数値の回路データに対して、階層展開処理を含むデータ処理を行うデータ展開処理部とを有する。
【００１０】
好適には、上記置換処理部は、階層ネット名の文字列を、階層名とネット名に分けてハッシュ関数に基づく処理を行って階層クラス先頭アドレスとネットクラス先頭アドレスとを個別に生成し、生成した当該アドレスを加算してハッシュ値にしてハッシュ関数に基づく処理により上記文字列に対応する上記整数値を得る。
【００１１】
好適には、上記置換処理部は回路データ中の文字列を写像した整数値にその元となる文字列との対応を記録する記憶部を有する。
【００１２】
好適には、上記データ展開処理部は、階層を保持した回路データから階層を除去したネットリストの階層展開を行って回路データを作成する階層展開処理部を有し、上記階層展開処理部は、階層を跨いで直接繋がっているネットをグループ化するグループ化処理部と、上記グループの中で最上位階層に存在するネットを探索することより、回路データを階層展開するネット探索部と、を含む。
【００１３】
好適には、上記グループ化処理部は、木構造を作成し、ネットをグループ化する。
【００１４】
好適には、上記ネット探索部は、上記木構造を上位方向へトレースすることにより、最上位に位置するネットを求める。
【００１５】
好適には、上記ネット探索部は、同じ階層に複数のネットが存在するときは、あらかじめ設定した順で最上位のネットを決定する。
【００１６】
好適には、上記ネット探索部は、すべての回路素子データをリスト構造でつないでいき、リスト構造でつないだ素子データの端子に接続されているネットを最上位のネットに置換することにより、階層展開を行う。
【００１７】
本発明の第２の観点のデータ処理方法は、文字列を含む回路データを提供部により提供する第１ステップと、置換処理部で提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う第２ステップと、上記第２ステップで置換された整数値の回路データに対して、データ展開処理部で階層展開処理を含むデータ処理を行う第３ステップとを有する。
【００１８】
本発明の第３の観点は、文字列を含む回路データを提供部により提供する第１ステップと、置換処理部で提供された回路データの文字列を整数値に写像し、全単射する置換処理を行う第２ステップと、上記第２ステップで置換された整数値の回路データに対して、データ展開処理部で階層展開処理を含むデータ処理を行う第３ステップとを含むデータ処理をコンピュータに実行させるプログラムである。
【００１９】
本発明によれば、文字列（識別子）を整数値に写像（全単射）する。このため、整数値から文字列（識別子）への逆写像が可能であり写像した整数値は識別子としての機能を持つ。結果として、データベース等のデータ処理に利用される。
【発明の効果】
【００２０】
本発明によれば、回路規模の増大によるデータ処理時間を短縮でき、処理データをデータベース等のデータに適用することができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施形態を図面に関連付けて説明する。
【００２２】
図３は、本発明の実施形態に係るデータ処理装置の構成例を示すブロック図である。
【００２３】
データ処理装置１０は、図３に示すように、回路データ提供部１１、構文解析処理部１２、置換処理部１３、記憶部１４、意味解析処理部１５、データ展開処理部１６、および処理結果出力部１７を有している。
【００２４】
回路データ提供部１１は、回路データを構文解析処理部１２に提供する。
回路データの提供は、たとえば回路データのデータベースから読み出す、あるいはキーボード等の入力部で入力する等により行われる。
【００２５】
回路データの構文解析処理部１２は、回路データ提供部１１から提供された回路データであるネットリスト、および、セルライブラリに対して構文解析を行い、識別子等の各データを記憶部１４に格納する。
なお、ここでの識別子とは、インスタンス名、ネット名等の文字列を示している。
【００２６】
置換処理部１３は、構文解析処理部１２で記憶部１４に格納された識別子（文字列）を整数値に写像し、文字列を整数値に置換する。
図４に、回路データ中の文字列（識別子）を整数に写像（全単射）した例を示す。
【００２７】
記憶部１４は、構文解析処理部１２で構文解析された回路データ中の文字列と置換処理部１３で写像した整数値との対応を記録する。
すなわち、記憶部１４は、回路データ中の文字列を整数値に写像する置換処理部１３で写像した整数値とその元となる文字列との対応を記録する。
【００２８】
回路データの意味解析処理部１５は、置換処理部１３で文字列を整数値に置換した回路データに対し、意味解析処理を行う。
【００２９】
データ展開処理部１６は、意味解析処理部１５で意味解析処理を行った回路データに対して階層展開処理等のデータ処理を行う。
【００３０】
処理結果出力部１７は、データ展開処理部１６の処理結果を出力する。
【００３１】
以上、本実施形態のデータ処理装置１０の基本構成について説明した。
次に、本実施形態のデータ処理装置１０における、識別子（文字列）を整数値に写像し、文字列を整数値に置換する処理、階層展開処理等の具体的な処理について説明する。
【００３２】
本実施形態のデータ処理装置１０においては、基本的に、“文字列（ネット名）”を“64bit 整数”に写像し、文字列では無く64bit 整数でネット接続判定処理を行う。
その結果、処理時間は、図５に示すように、ゲート数の増加に対し線形増加となる。
図５においては、比較例としてゲート数の増大に伴い、ネットリスト処理時間が指数関数的に増加している例を示している。
【００３３】
なお、ここで写像処理においては、同じ文字列であれば同じ整数値を取り、異なる文字列であれば異なる整数値を取る。
【００３４】
図６は、本実施形態に係る文字列を６４bit整数に高速写像する方法の概要を説明するための図である。
【００３５】
本実施形態のデータ処理装置１０は、図６に示すように、階層ネット名２０の文字列を、階層名２１とネット名２２に分けて処理を行う。
階層名２１は階層クラス管理部２３に与えられ、ネット名２２は各モジュール毎のネットクラス管理部２４に与えられる。
【００３６】
階層クラス管理部２３は、ハッシュ関数処理部２３１で与えられる階層名２１に対して所定のキー（ｋｅｙ）に基づく比較（検索）を高速に処理し、ハッシュテーブル２３２を通して階層クラス先頭アドレス２５を生成する。
このように、文字列を高速に比較（検索）するためデータをハッシュテーブル２３２で管理する。
【００３７】
ネットクラス管理部２４は、ハッシュ関数処理部２４１で与えられるネット名２２に対して所定のキー（ｋｅｙ）に基づく比較（検索）を高速に処理し、ハッシュテーブル２４２を通してネットクラス先頭アドレス２６を生成する。
このように、文字列を高速に比較（検索）するためデータをハッシュテーブル２４２で管理する。
【００３８】
階層クラス先頭アドレス２５およびネットクラス先頭アドレス２６は、階層ネットクラス管理部２７に与えられる。
【００３９】
階層ネットクラス管理部２７は、ハッシュ関数処理部２７１で与えられる階層クラス先頭アドレス２５およびネットクラス先頭アドレス２６のアドレスを加算してハッシュ値にする。アドレスを加算してハッシュ値にすると、処理時間が短く、衝突を効率良く回避することができる。
階層ネットクラス管理部２７は、ハッシュ関数処理部２７１で所定のキー（Ｋｅｙ）に基づく処理を行った後、ハッシュテーブル２７２を通して、文字列ではない６４bit整数を生成する。
【００４０】
図７は、本実施形態に係る文字列を６４bit整数に高速写像する他の方法の概要を説明するための図である。
【００４１】
文字列を６４bit整数に高速写像するには、図７に示すように、階層ネット文字列２１を階層名２１とネット名２２に分けて処理を行うことなく、階層ネットクラス管理部２７に直接与えて６４bit整数を得ることも可能である。
【００４２】
ただし、この場合、文字列が長いとハッシュ値算出に時間がかかるおそれがある。
また、データ数が多いと、衝突回数が増える、文字列比較処理も増えるおそれがある。
すなわち、階層ネット名２１をそのまま扱うと、図６の場合に比較して処理時間がかかるおそれがある。
したがって、高速処理を実現するには、図６に示す方法を採用することが望ましい。
【００４３】
以下に、本実施形態において適用可能な高速ハッシュ関数の一例について示す。
【００４４】
＜ハッシュ関数の定義＞
h( s, v ) =
set h0 ← init ( v )
for each character ci  in s,
set hi ← step( i, hi-1, ci )
return h = final( hm, v )
【００４５】
ここで、h ( s, v )は文字列、seed値を入力し得られるハッシュ値を示す。
v はseed 値を、s は入力文字列を、ci は文字列の先頭から i 番目の文字を、hi はi まで計算したハッシュ値を、m は文字列長を、それぞれ示している。
【００４６】
＜Sub関数の定義＞
init ( v ) =  0
step ( i, h, c ) = Pi × h + c 
final ( h, v ) = ( h || p ) || T  
【００４７】
ここで、v はseed 値を、h はハッシュ値を、c は文字を、Pi はたとえば65,587 (素数)を、p はたとえば3,001 (素数)を、T はテーブルサイズをそれぞれ示している。
【００４８】
このハッシュ関数は、たとえばVerilog 文字列を高速に処理できるハッシュ関数として形成されている。このようなハッシュ関数を形成したのは以下の理由による。
【００４９】
Verilog 文字列は、アルファベット部分は全く同じで数字のみが異なる文字列(NET1等)が多い、という通常のテキストとは異なる特徴がある。
そのため、C++ ライブラリベンダから提供されている一般のハッシュ関数では、良い特性を得ることができない。
良い特性を得るには、ハッシュ関数は、以下の要件を満たす必要がある。
【００５０】
１）似たデータから近いハッシュ値が生成されない。
２）あるデータとハッシュ値が等しい別のデータ（ハッシュ値の衝突)が容易に生成できない。
３）ハッシュ値に値域上の偏りがない。
【００５１】
この要件を満たすように、上述した、Verilog 文字列に対し優れた特性を示すハッシュ関数を形成している。
【００５２】
図８は、本実施形態のアルゴリズムと既存のアルゴリズムにおいて、階層展開後の有向グラフデータ構築に要する処理時を比較して示す図である。
【００５３】
図８において、ＡＡが既存のアルゴリズムを、ＢＡが本実施形態のアルゴリズムを示す。
図８の例では、ゲート規模として８００万ゲートおよび２０００万ゲートの場合の処理時を示している。
図８に示すように、本アルゴリズムＢを採用することで、既存のアルゴリズムＡの２５倍以上の高速化を実現することができる。
【００５４】
次に、階層を保持した回路データから階層展開された回路データを作成する処理について説明する。
【００５５】
本実施形態の回路データを階層展開する処理においては、階層を跨いで直接繋がっているネットをグループ化するグループ化処理と、そのグループの中で最上位階層に存在するネットを探索する探索処理とを含む。
【００５６】
図９は、本実施形態に係るネットリストの階層展開処理の機能ブロック図である。
【００５７】
このネットリストの階層展開処理部３０は、ネットリスト入力部３１、ネットリスト記憶部３２、素子データ抽出部３３、素子データ記憶部３４、置換部３５、グループ化処理部３６、最上位ネット記憶部３７、ネット探索部３８、およびネットリスト記憶部３９を有する。
【００５８】
素子データ抽出部３３は、ネットリスト記憶部３２に記憶されたネットリストから素子（リーフセル）データのみを抽出する。
素子データ抽出部３３は、抽出した素子データを素子データ記憶部３４に記憶する。
素子データ記憶部３４は、全ての素子データが記憶される。
【００５９】
置換部３５は、素子に接続されているネットを最上位階層に位置するネットに置き換える。
【００６０】
グループ化処理部３６は、階層を取り除いた時、直接接続しているネット（ワイヤー）をグループ化する。
【００６１】
最上位ネット記憶部３７は、グループ化処理部３６でグループ化されたネットグループとそのグループの最上位ネットが記憶する。
【００６２】
ネット探索部３８は、最上位ネット記憶部３７に記憶されているネットグループから最上位階層に位置するネットを探索し、探索して結果を最上位ネット記憶部３７に記憶する。
【００６３】
ネットリスト記憶部３９は、階層展開後のネットリストを記憶する。
なお、ネットリスト記憶部３９は、素子データ記憶部３４と同じ記憶部として形成することも可能である。
【００６４】
ここで、本実施形態に係るネットリストの階層展開処理を、具体例を挙げて説明する。
【００６５】
図１０は、本実施形態に係るネットリストの階層展開処理を説明するためのフローチャートである。
図１１〜図１６は、本実施形態に係るネットリストの階層展開処理を図解して示す図である。
図１１〜図１６において、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆはネット（ワイヤー）名を示している。
【００６６】
＜ステップＳＴ１＞
ステップＳＴ１においては、ネットリスト入力部３１により階層を保持したネットリストを入力し、ネットリスト記憶部３２に記憶する。
【００６７】
＜ステップＳＴ２＞
ステップＳＴ２において、グループ化処理部３６は、階層を取り除いた時、直接接続しているネットをグループ化する。
図１１を基に、ネットをグループ化した例が図１４、図１５、図１６に示されている。
グループ化とは、図１４〜図１６に示しように、木データ構造を作成して表現することである。
【００６８】
具体的には、図１４のネットＤの上位階層に接続しているのはネットＡであるので、図１４のようにネットＤの親のノードは、ネットＡで、ネットＡの子のノードはネットＤになるように木構造を構成する。
ネットＣは、ネットＡと同じ階層に位置しているが、同じ階層に複数のネットが存在する場合は、兄弟のノードとして構成する。
【００６９】
＜ステップＳＴ３＞
ステップＳＴ３において、ネット探索部３８が、木データ構造を上位方向へ探索することにより、グループ内で最上位階層に位置するネットを求める。
そして、図１４〜図１６に示すように、その最上位ネットの情報を各ノードにも持たせる。
図１４のグループ内で、最上位階層に位置しているネットは、ネットＡとネットＣである。
また、ネットＡとネットＣのように最上位階層に位置しているネットが複数ある場合の最上位ネットの決定方法は、図１１のネットＡのように直接外部ポートに接続されているネットをそのグループ内の最上位ネットとする。
条件が同じ場合は、アルファベット順で決定する。アルファベット順でなくても唯一のネットが求まれば問題はない。
【００７０】
＜ステップＳＴ４＞
ステップＳＴ４において、素子データ抽出部３３が、図１２に示すように、ネットリスト上に存在する全ての素子データを取り出す。
そして、素子データ記憶部３４に、図１２のようなイメージで素子データを記憶する。具体的には、素子とそれに接続されているネットをそのままの状態で、素子データ記憶部３４に記憶する。
素子データ抽出部３３は、ネットリスト上に存在する全ての素子データをピックアップする。全ての素子（それ以上、階層展開できない最下位のモジュール）データをリスト構造でつないでいく。この素子データには、その素子の端子とその端子に接続しているネットの情報も含んでいる。
【００７１】
＜ステップＳＴ５＞
ステップＳＴ５において、置換部３５が、その素子の端子に直接接続されているネットを最上位階層に位置しているネットと置換する。この際にネットをグループ化した情報を使用する。
図１２のネットＤの最上位階層に位置しているネットを、図１４のネットグループを参照して求めると、その結果は、ネットＡとなる。そして、ネットＤをネットＡに置き換える。
同様に、ネットＣの最上位ネットはネットＡなので、ネットＣをネットＡに置き換える。このように、すべての素子に繋がっているネットに対して、同じ処理を行う。結果は、図１３に示すようになる。
このように、素子の端子に直接接続されているネットを最上位のネットに置換する。
リスト構造でつないだ全ての素子データの端子に接続されているネットを最上位のネットに置換することにより、階層展開が実現できる。
【００７２】
以上の処理を行うことにより図１３に示すような階層展開後のデータを得ることができる。
【００７３】
そして、上記本実施形態に係る階層展開処理により、回路データ（ネットリストを含む）を扱う上で必要不可欠な階層展開処理を高速化し、メモリ使用量を削減することができる。
その結果、回路データの階層展開処理を必要としているＥＤＡツールの処理速度の高速化およびメモリ使用量の削減に寄与することができる。
【００７４】
次に、図３のデータ処理装置による全体的な動作を、図１７に関連付けて説明する。
図１７は、図３のデータ処理装置の基本的な動作概要を示すフローチャートである。
【００７５】
＜ステップＳＴ１１＞
まず、ステップＳＴ１１において、まず、回路データを読込み、構文解析処理を行い、各データを記憶部１４に格納する。
【００７６】
＜ステップＳＴ１２＞
次に、ステップＳＴ１２において、置換処理部１３が記憶部１４に格納した回路データ中の文字列を整数値に写像し、文字列を整数値に置換する。
その際、文字列と写像した整数値との対応を記憶部１４に記録する。
【００７７】
＜ステップＳＴ１３＞
次に、ステップＳＴ１３において、意味解析処理部１５が文字列を整数値に置換した回路データに対して、意味解析処理を行い、処理結果を記憶部１４に格納する。
【００７８】
＜ステップＳＴ１４＞
次に、ステップＳＴ１２およびステップＳＴ１３で記憶部１４に格納した各データに対し、上述したような階層展開処理等のデータ処理を行う。
【００７９】
＜ステップＳＴ１５＞
そして、ステップＳＴ１５において、ステップＳＴ１４のデータ処理結果をコンソールやファイルに出力する。
【００８０】
以上説明したように、本実施形態によれば、ＬＳＩ設計データ規模が増加した場合でも、回路データ中の文字列を整数値に変換（写像）した後にデータ処理を行う。このため、文字列処理に比べ整数処理は高速に処理できることから、処理時間の増加を低く抑えることが可能となる。
そして、上記本実施形態に係る階層展開処理により、回路データ（ネットリストを含む）を扱う上で必要不可欠な階層展開処理を高速化し、メモリ使用量を削減することができる。
その結果、回路データの階層展開処理を必要としているＥＤＡツールの処理速度の高速化およびメモリ使用量の削減に寄与することができる。
【００８１】
以下、本実施形態のように、文字列を整数値化する場合のより具体的な効果を、特許文献１(特開2003-167937号公報)のようにネット面を面積値に変換する方法を比較例として、図１８〜図２０に関連付けて説明する。
ここでは、説明の便宜上、下記 Verilog ネットリストを図１８のように表現する。
【００８２】
図１９（Ａ）に示すように、比較例では、ネット名(文字列)を面積値に置換する。
この場合、面積値であるため、面積値Ｓ１と 面積値Ｓ２は同じ値になる可能性がある。
面積値が同じになった場合、図１９（Ｂ）に示すように、ネット接続関係が変わってしまい、置換前のネット接続情報を保持することができない。
したがって、比較例では、ネット名を面積値に置換した後、再度、元のネット名に変換することはできない。
【００８３】
これに対して、本実施形態（本発明）では、図１９（Ｃ）に示すように、ネット名(文字列)を全単射した数値に置換する。
なお、ここでは説明の便宜上、ネット名（文字列）を全単射した数値をネット識別値と呼ぶこととする。
全単射した数値であるため、ネット識別値Ｎ１とネット識別値Ｎ２は必ず異なる数値になる。
そのため、本実施形態では、置換後も置換前のネット接続関係を保持することができる。
【００８４】
また、比較例では、図２０（Ａ）に示すように、ネット名を面積値に置換した後、再度、元のネット名に変換することはできない。
【００８５】
これに対して、本実施形態では、図２０（Ｂ）に示すように、ネット名をネット識別値に置換した後、再度、元のネット名に変換することができる。
すなわち、本実施形態では、ネット名（文字列）を全単射した数値に置換した後、全単射であるため、ネット識別値をネット名に逆変換することができる。
【００８６】
なお、以上詳細に説明した方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【００８７】
【図１】ＥＤＡツールにおいて、回路データのネットリストの構文を解析し、ネットリストからネット接続情報を構築する機能を示す図である。
【図２】半導体集積回路の規模増大に伴いゲート数が増大し、ネットリスト処理時間が指数関数的に増加することを説明するための図である。
【図３】本発明の実施形態に係るデータ処理装置の構成例を示すブロック図である。
【図４】回路データ中の文字列（識別子）を整数に写像（全単射）した例を示す図である。
【図５】本実施形態において、ゲート数の増加に対して処理時間は線形増加となることを示す図である。
【図６】本実施形態に係る文字列を６４bit整数に高速写像する方法の概要を説明するための図である。
【図７】本実施形態に係る文字列を６４bit整数に高速写像する他の方法の概要を説明するための図である。
【図８】本実施形態のアルゴリズムと既存のアルゴリズムにおいて、階層展開後の有向グラフデータ構築に要する処理時を比較して示す図である。
【図９】本実施形態に係るネットリストの階層展開処理の機能ブロック図である。
【図１０】本実施形態に係るネットリストの階層展開処理を説明するためのフローチャートである。
【図１１】本実施形態に係るネットリストの階層展開処理を図解して示す第１図である。
【図１２】本実施形態に係るネットリストの階層展開処理を図解して示す第２図である。
【図１３】本実施形態に係るネットリストの階層展開処理を図解して示す第３図である。
【図１４】本実施形態に係るネットリストの階層展開処理を図解して示す第４図である。
【図１５】本実施形態に係るネットリストの階層展開処理を図解して示す第５図である。
【図１６】本実施形態に係るネットリストの階層展開処理を図解して示す第６図である。
【図１７】図３のデータ処理装置の基本的な動作概要を示すフローチャートである。
【図１８】ネットリストを便宜的に示す図である。
【図１９】文字列を整数値化する場合の効果をより具体的に説明するための第１図である。
【図２０】文字列を整数値化する場合の効果をより具体的に説明するための第２図である。
【符号の説明】
【００８８】
１０・・・データ処理装置、１１・・・回路データ提供部、１２・・・構文解析処理部、１３・・・置換処理部、１４・・・記憶部、１５・・・意味解析処理部、１６・・・データ展開処理部、１７・・・処理結果出力部、３０・・・階層展開処理部、３１・・・ネットリスト入力部、３２・・・ネットリスト記憶部、３３・・・素子データ抽出部、３４・・・素子データ記憶部、３５・・・置換部、３６・・・グループ化処理部、３７・・・最上位ネット記憶部、３８・・・ネット探索部、３９・・・ネットリスト記憶部。
【図１】
2010033492.tif 000003
【図２】
2010033492.tif 000004
【図３】
2010033492.tif 000005
【図４】
2010033492.tif 000006
【図５】
2010033492.tif 000007
【図６】
2010033492.tif 000008
【図７】
2010033492.tif 000009
【図８】
2010033492.tif 000010
【図９】
2010033492.tif 000011
【図１０】
2010033492.tif 000012
【図１１】
2010033492.tif 000013
【図１２】
2010033492.tif 000014
【図１３】
2010033492.tif 000015
【図１４】
2010033492.tif 000016
【図１５】
2010033492.tif 000017
【図１６】
2010033492.tif 000018
【図１７】
2010033492.tif 000019
【図１８】
2010033492.tif 000020
【図１９】
2010033492.tif 000021
【図２０】
2010033492.tif 000022