(57)【要約】【課題】配線混雑およびホールドタイムエラーの発生を低減したスキャンパスタイミング最適化装置を提供すること。【解決手段】領域内接続順序決定部１０３は、配置領域分割部１０２によって分割された領域内のスキャンパス回路の接続順序をランダムに決定する。そして、領域間接続順序決定部１０４は、配置領域分割部１０２によって分割された領域間の配線長が短くなるように、各領域間におけるスキャンパス回路の接続順序を決定する。したがって、局所的にスキャンパス間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となる。【選択図】        図４
2004185427.tif 000002
【特許請求の範囲】
【請求項１】
セルの配置領域を複数の領域に分割するための配置領域分割手段と、
前記配置領域分割手段によって分割された領域内のスキャンパス回路の接続順序をランダムに決定するための領域内接続順序決定手段と、
前記配置領域分割手段によって分割された領域間の配線長が短くなるように、各領域間におけるスキャンパス回路の接続順序を決定するための領域間接続順序決定手段とを含む、スキャンパスタイミング最適化装置。
【請求項２】
前記スキャンパスタイミング最適化装置はさらに、領域内接続順序決定手段によって決定されたスキャンパス回路の接続順序の中で、配線長が短くなっているスキャンパス回路の接続順序を入替えるための接続順序入替手段を含む、請求項１記載のスキャンパスタイミング最適化装置。
【請求項３】
スキャンパスが最短距離となるようにスキャンパス回路の接続順序を決定するための最短距離順序決定手段と、
前記最短距離順序決定手段によって決定されたスキャンパス回路の接続順序を所定の規則に従って入替えるための接続順序入替手段とを含むスキャンパスタイミング最適化装置。
【請求項４】
前記接続順序入替手段は、前記最短距離順序決定手段によって決定されたスキャンパス回路の接続順序のうち、第１の所定番目のスキャンパス回路から２つずつスキャンパス回路の接続順序を入替えた後、第２の所定番目のスキャンパス回路から２つずつスキャンパス回路の接続順序を入替える、請求項３記載のスキャンパスタイミング最適化装置。
【請求項５】
前記接続順序入替手段は、前記最短距離順序決定手段によって決定された接続順序のスキャンパス回路を複数の組に分け、それぞれの組の中でスキャンパス回路の接続順序を入替えた後、別の方法でスキャンパス回路を複数の組に分け、それぞれの組の中でスキャンパス回路の接続順序を入替える、請求項３記載のスキャンパスタイミング最適化装置。
【請求項６】
半導体装置内のセルを自動配置するための自動配置手段と、前記自動配置手段によって配置されたスキャンパス回路間の遅延時間が所定時間以上となるように所定の規則でスキャンパス回路の接続順序を決定するための接続順序決定手段とを含むスキャンパスタイミング最適化装置。
【請求項７】
前記接続順序決定手段は、一定距離以上で配置されたスキャンパス回路の中で最も近いスキャンパス回路を接続する、請求項６記載のスキャンパスタイミング最適化装置。
【請求項８】
前記接続順序決定手段は、スキャン端子間の遅延時間が一定遅延時間以上と見積もられたスキャンパス回路の組合わせの中で最も近いスキャンパス回路を接続する、請求項６記載のスキャンパスタイミング最適化装置。
【請求項９】
前記接続順序決定手段は、スキャン端子間における遅延時間がクロック到着時間差よりも一定時間以上大きくなるようにスキャンパス回路を接続する、請求項６記載のスキャンパスタイミング最適化装置。
【請求項１０】
前記接続順序決定手段は、スキャンパス回路間におけるクロック到着時間差が一定時間以上とならないようにスキャンパス回路を接続する、請求項６記載のスキャンパスタイミング最適化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体デバイスに搭載されるスキャンパス回路に関し、特に、スキャンパス回路における信号のタイミングが最適となるようにスキャンパス回路の接続順序を決定するスキャンパスタイミング最適化装置に関する。
【０００２】
【従来の技術】
近年、半導体デバイスの高速化、高集積化が進み、半導体デバイスのテストを容易にするためにスキャン方式のテスト回路が搭載されることが多くなってきている。従来のスキャン方式のテスト回路において、スキャンパス回路の接続順序を決定するのに、スキャンパス回路の配置情報を考慮せずに、スキャンパス回路を構成するフリップフロップ回路、ラッチ回路またはＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）等の順序回路（以下、総称してＦＦと略す。）のスキャン端子の接続順序を決定する方法と、スキャンパス回路の配置情報を考慮してＦＦのスキャン端子の接続順序を決定する方法とが用いられている。
【０００３】
スキャンパス回路の配置情報を考慮してＦＦのスキャン端子の接続順序を決定する方法に関連する技術の１つとして、特開平１０−３３５４７１号公報に開示された発明がある。この特開平１０−３３５４７１号公報に開示されたスキャンパスネットの配線方法においては、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）の回路情報等に基づきスタンダードセル等の配置設計を行ない、クロック遅延計算処理により、ＬＳＩ中の各ＦＦのクロックパスの遅延時間を見積る。そして、スキュー見積り処理により、各ＦＦの相互間のクロックスキューをそれぞれ算出する。
【０００４】
また、距離計算処理により、各ＦＦの相互間の距離を計算する。そして、経路選定処理により、距離ばかりでなく、クロックスキューを考慮して各ＦＦの接続順序を決定する。これにより、ホールドタイムエラーの発生確率を低減する。
【０００５】
【特許文献１】
特開平１０−３３５４７１号公報
【０００６】
【発明が解決しようとする課題】
しかし、上述したスキャンパス回路の配置情報を考慮せずに、ＦＦのスキャン端子の接続順序を決定する方法においては、スキャンパス回路を含む各セル間の配線混雑が発生し、配線収束しない場合があるといった問題点があった。
【０００７】
また、上述したスキャンパス回路の配置情報を考慮してＦＦのスキャン端子の接続順序を決定する方法においては、ＦＦのスキャン端子間の配線が最短となるように接続順序が決定されるため、データ転送時間が短か過ぎてホールドタイムエラーが発生する場合があった。この場合、ホールドタイムエラーを改善するためにスキャン端子間にバッファを挿入してタイミング改善を行なうことになるが、ホールドタイムエラー数が多い場合にはバッファ数が増大し、セルの配置不能や配線不能などが発生する場合があるといった問題点があった。
【０００８】
また、特開平１０−３３５４７１号公報に開示されたスキャンパスネットの配線方法においては、距離ばかりでなく、クロックスキューを考慮して各ＦＦの接続順序を決定しているため、全てのＦＦ間の距離およびクロックスキューを計算することになり、高速に各ＦＦ間の接続順序を決定するのが困難であるといった問題点があった。
【０００９】
本発明は、上記問題点を解決するためになされたものであり、その目的は、配線混雑およびホールドタイムエラーの発生を低減したスキャンパスタイミング最適化装置を提供することである。
【００１０】
【課題を解決するための手段】
本発明に係るスキャンパスタイミング最適化装置は、セルの配置領域を複数の領域に分割するための配置領域分割手段と、配置領域分割手段によって分割された領域内のスキャンパス回路の接続順序をランダムに決定するための領域内接続順序決定手段と、配置領域分割手段によって分割された領域間の配線長が短くなるように、各領域間におけるスキャンパス回路の接続順序を決定するための領域間接続順序決定手段とを含む。
【００１１】
【発明の実施の形態】
（第１の実施の形態）
まず、本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置を容易に理解できるように、配置情報を考慮せずにスキャンパス回路の接続順序を決定する方法と、配置情報を考慮してスキャンパス回路の接続順序を決定する方法とを説明する。
【００１２】
図１は、配置情報を考慮せずにスキャンパス回路の接続順序を決定する方法を説明するための図である。図１においては、セルの配置領域が領域１〜４に分割されているが、この領域に関係なしに任意のＦＦ間を接続するため、ＦＦ間の配線長が全体的に長くなっている。そのため、配線混雑が発生し，セル間の配線ができない場合がある。
【００１３】
図２は、配置情報を考慮して配線長が短くなるようにスキャンパス回路の接続順序を決定する方法を説明するための図である。全てのＦＦ間の配線長が短くなっているため、ＦＦ間のデータ転送時間が短くなり過ぎて、スキャンパス回路のホールドタイムエラーが発生する場合がある。
【００１４】
図３は、本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例を示すブロック図である。このスキャンパスタイミング最適化装置は、コンピュータ本体１、ディスプレイ装置２、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）４が装着されるＦＤドライブ３、キーボード５、マウス６、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）８が装着されるＣＤ−ＲＯＭ装置７およびネットワーク通信装置９を含む。
【００１５】
スキャンパスタイミング最適化装置を実現するプログラム（以下、スキャンパスタイミング最適化プログラムと呼ぶ。）は、ＦＤ４またはＣＤ−ＲＯＭ８等の記録媒体によって供給される。スキャンパスタイミング最適化プログラムがコンピュータ本体１によって実行されることにより、スキャンパス回路のタイミングの最適化が行なわれる。また、スキャンパスタイミング最適化プログラムは他のコンピュータよりネットワーク通信装置９を経由し、コンピュータ本体１に供給されてもよい。
【００１６】
コンピュータ本体１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２およびハードディスク１３を含む。ＣＰＵ１０は、ディスプレイ装置２、ＦＤドライブ３、キーボード５、マウス６、ＣＤ−ＲＯＭ装置７、ネットワーク通信装置９、ＲＯＭ１１、ＲＡＭ１２またはハードディスク１３との間でデータを入出力しながら処理を行う。ＦＤ４またはＣＤ−ＲＯＭ８に記録されたスキャンパスタイミング最適化プログラムは、ＣＰＵ１０によりＦＤドライブ３またはＣＤ−ＲＯＭ装置７を介して一旦ハードディスク１３に格納される。ＣＰＵ１０は、ハードディスク１３から適宜スキャンパスタイミング最適化プログラムをＲＡＭ１２にロードして実行することによって、スキャンパス回路のタイミングの最適化が行なわれる。
【００１７】
図４は、本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。このスキャンパスタイミング最適化装置は、半導体デバイス内のスキャンパス回路を含んだセルを自動配置する自動配置部１０１と、自動配置部１０１によって配置されたセルの配置領域を分割する配置領域分割部１０２と、配置領域分割部１０２によって分割された配置領域内にあるＦＦ間の接続順序を決定する領域内接続順序決定部１０３と、配置領域分割部１０２によって分割された配置領域間の接続順序を決定する領域間接続順序決定部１０４とを含む。
【００１８】
図５は、本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部１０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ１０１）。そして、配置領域分割部１０２は、自動配置部１０１によって配置されたセルの配置領域全体を一定領域に分割する（Ｓ１０２）。
【００１９】
図６は、本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。図６においては、配置領域内にＦＦ１〜ＦＦ１６の１６個のスキャンパス回路が含まれている。ステップＳ１０２の処理によって、図６に示すようにセルの配置領域全体が領域１〜４の４つの領域に分割されているが、分割数はこれに限られるものではない。また、図６においては、簡単のためにスキャンパス回路以外のセルは記載していない。
【００２０】
次に、領域内接続順序決定部１０３は、配置領域分割部１０２によって分割されたそれぞれの配置領域内において、ＦＦのスキャン端子の接続順序をランダムに決定する（Ｓ１０３）。たとえば、領域１においては、スキャンイン端子→ＦＦ４→ＦＦ１→ＦＦ２→ＦＦ３→ＦＦ５の順に接続順序が決定されている。図２に示す領域１と比較すると、ＦＦ間の配線長が全体的に長くなっていることが分かる。
【００２１】
最後に、領域間接続順序決定部１０４は、配置領域分割部１０２によって分割された領域間の配線長が最短となるように、各領域間におけるＦＦの接続順序を決定する（Ｓ１０４）。図６においては、各領域間の配線長が最短となるように、領域１のＦＦ５と領域２のＦＦ６とが接続され、領域２のＦＦ７と領域３のＦＦ９とが接続され、領域３のＦＦ１１と領域４のＦＦ１３とが接続されている。
【００２２】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、セルの配置領域を一定領域に分割し、分割された領域内でＦＦのスキャン端子の接続順序をランダムに決定すると共に、分割された領域間の配線長が最短となるように各領域内のＦＦの接続順序を決定するようにしたので、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００２３】
また、分割された領域内でＦＦのスキャン端子の接続順序をランダムに決定した後に、領域間の配線長が最短となるように各領域内のＦＦの接続順序を決定するようにしたので、配線長を計算するＦＦの組合わせの数を削減することができ、ＦＦの接続順序の決定に要する時間を短縮することが可能となった。
【００２４】
（第２の実施の形態）
本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００２５】
図７は、本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。図４に示す第１の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成と比較して、領域内接続順序決定部１０３によって決定されたＦＦの接続順序の中で配線長が最短となっているＦＦの接続順序を、他の接続順序と入替える接続順序入替部１０５が追加されている点のみが異なる。したがって、重複する構成および機能の詳細な説明は繰返さない。
【００２６】
図８は、本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。図５に示す第１の実施の形態におけるスキャンパスタイミング最適化装置のフローチャートと比較して、ステップＳ１０５が追加された点のみが異なる。したがって、重複する処理手順の詳細な説明は繰返さない。
【００２７】
ステップＳ１０５において、接続順序入替部１０５は、領域内接続順序決定部１０３によって決定されたＦＦの接続順序の中で、配線長が最短となっているＦＦの接続順序を他のＦＦの接続順序と入替える。
【００２８】
図９は、本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。図６に示す第１の実施の形態におけるスキャンパスタイミング最適化装置によって決定された接続順序において、たとえば、領域１におけるＦＦ１とＦＦ２との配線長、および領域３におけるＦＦ９とＦＦ１０との配線長が最短となっている。
【００２９】
図９においては、領域１における接続順序ＦＦ１→ＦＦ２→ＦＦ３が、ＦＦ２→ＦＦ３→ＦＦ１に入替えられて最短距離の配線をなくしている。同様に、領域３における接続順序ＦＦ９→ＦＦ１０→ＦＦ１２が、ＦＦ９→ＦＦ１２→ＦＦ１０に入替えられて最短距離の配線をなくしている。
【００３０】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、分割された領域内のＦＦの接続順序の中で、配線長が最短となっているＦＦの接続順序を他のＦＦの接続順序と入替えるようにしたので、局所的にＦＦ間の配線長をさらに長くすることができ、ホールドタイムエラーの発生をさらに低減することが可能となった。
【００３１】
（第３の実施の形態）
本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００３２】
図１０は、本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。このスキャンパスタイミング最適化装置は、半導体デバイス内のスキャンパス回路を含んだセルを自動配置する自動配置部２０１と、自動配置部２０１によって配置されたＦＦによって構成されるスキャンパスが最短距離となるようにＦＦの接続順序を決定する最短距離順序決定部２０２と、最短距離順序決定部２０２によって決定されたＦＦの接続順序を他の接続順序と入替える接続順序入替部２０３とを含む。
【００３３】
図１１は、本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部２０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ２０１）。そして、最短距離順序決定部２０２は、スキャンパスが最短となるように各ＦＦの接続順序を決定する（Ｓ２０２）。
【００３４】
最後に、接続順序入替部２０３は、最短距離順序決定部２０２によって決定された各ＦＦの接続順序を入替えて、スキャンパスの接続順序を決定する（Ｓ２０３）。
【００３５】
図１２は、本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。図１２においては、１０個のＦＦが含まれており、最短距離順序決定部２０２によって決定されたスキャンパスが最短距離となる接続順序が、ＦＦ１→ＦＦ２→ＦＦ３→ＦＦ４→ＦＦ５→ＦＦ６→ＦＦ７→ＦＦ８→ＦＦ９→ＦＦ１０となっている。
【００３６】
接続順序入替部２０３は、１回目の入替え処理として、１番目のＦＦから２つずつ順序を入替える。この入替え処理によって、ＦＦの接続順序が、ＦＦ２→ＦＦ１→ＦＦ４→ＦＦ３→ＦＦ６→ＦＦ５→ＦＦ８→ＦＦ７→ＦＦ１０→ＦＦ９となる。
【００３７】
次に、接続順序入替部２０３は、２回目の入替え処理として、２番目のＦＦから２つずつ順序を入替える。この入替え処理によって、ＦＦの接続順序が、ＦＦ２→ＦＦ４→ＦＦ１→ＦＦ６→ＦＦ３→ＦＦ８→ＦＦ５→ＦＦ１０→ＦＦ７→ＦＦ９となる。
【００３８】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、スキャンパスが最短距離となるようにＦＦの接続順序を決定し、１番目のＦＦから２つずつ順序を入替えた後、２番目のＦＦから２つずつ順序を入替えるようにしたので、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００３９】
また、スキャンパスが最短距離となるようにＦＦの接続順序を決定した後、ＦＦの接続順序を入替えるだけで各ＦＦ間の配線が行なえるので、短時間で集積度の高いレイアウト結果を得ることが可能となった。
【００４０】
（第４の実施の形態）
本発明の第４の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００４１】
また、本発明の第４の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成は、図１０に示す第３の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成と比較して、接続順序入替部２０３の機能が異なる点のみが異なる。したがって、重複する構成および機能の詳細な説明は繰返さない。なお、本実施の形態における接続順序入替部の参照符号を２０３’として説明する。
【００４２】
また、本発明の第４の実施の形態におけるスキャンパスタイミング最適化装置の処理手順は、図１１に示す第３の実施の形態におけるスキャンパスタイミング最適化装置の処理手順と比較して、ステップＳ２０３の処理が異なる点のみが異なる。したがって、重複する処理の詳細な説明は繰返さない。なお、本実施の形態におけるステップＳ２０３をステップＳ２０３’として説明する。
【００４３】
ステップＳ２０３’において、接続順序入替部２０３’は、最短距離順序決定部２０２によって決定された各ＦＦの接続順序を入替えて、スキャンパスの接続順序を決定する。
【００４４】
図１３は、本発明の第４の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。図１３においては、１０個のＦＦが含まれており、最短距離順序決定部２０２によって決定されたスキャンパスが最短距離となる接続順序が、ＦＦ１→ＦＦ２→ＦＦ３→ＦＦ４→ＦＦ５→ＦＦ６→ＦＦ７→ＦＦ８→ＦＦ９→ＦＦ１０となっている。
【００４５】
接続順序入替部２０３’は、１回目の入替え処理として、たとえば１番目のＦＦから３つずつの組に分け、それぞれの組の中でＦＦの順序を入替える。図１３においては、ＦＦ１，ＦＦ２，ＦＦ３の組の順序をＦＦ１，ＦＦ３，ＦＦ２に入替え、ＦＦ４，ＦＦ５，ＦＦ６の組の順序をＦＦ４，ＦＦ６，ＦＦ５に入替え、ＦＦ７，ＦＦ８，ＦＦ９の組の順序をＦＦ７，ＦＦ９，ＦＦ８に入替える。この入替え処理によって、ＦＦの接続順序が、ＦＦ１→ＦＦ３→ＦＦ２→ＦＦ４→ＦＦ６→ＦＦ５→ＦＦ７→ＦＦ９→ＦＦ８→ＦＦ１０となる。
【００４６】
次に、接続順序入替部２０３’は、２回目の入替え処理として、たとえば最初の２つのＦＦを除いてＦＦを３つずつの組に分け、それぞれの組の中でＦＦの順序を入替える。図１３においては、ＦＦ２，ＦＦ４，ＦＦ６の組の順序を逆にしてＦＦ６，ＦＦ４，ＦＦ２とし、ＦＦ５，ＦＦ７，ＦＦ９の組の順序を逆にしてＦＦ９，ＦＦ７，ＦＦ５とする。この入替え処理によって、ＦＦの接続順序がＦＦ１→ＦＦ３→ＦＦ６→ＦＦ４→ＦＦ２→ＦＦ９→ＦＦ７→ＦＦ５→ＦＦ８→ＦＦ１０となる。
【００４７】
なお、４つ以上のＦＦを組にしてＦＦの順序を入替えてもよいし、組の中のＦＦの順序の入替え方法はどのようなものであってもよい。たとえば、１つの組においては２個のＦＦの順序を入替え、他の組においては３個のＦＦの順序を入替えるようにしてもよいし、ある組において１回目は２個のＦＦの順序を入替え、２回目は３個のＦＦの順序を入替えるようにしてもよい。
【００４８】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、スキャンパスが最短距離となるようにＦＦの接続順序を決定し、複数の接続されたＦＦの組に分け、それぞれの組の中でＦＦの順序を入替えた後、さらに異なる方法で複数の接続されたＦＦの組に分け、それぞれの組の中でＦＦの順序を入替えるようにしたので、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００４９】
また、スキャンパスが最短距離となるようにＦＦの接続順序を決定した後、ＦＦの接続順序を入替えるだけで各ＦＦ間の配線が行なえるので、短時間で集積度の高いレイアウト結果を得ることが可能となった。
【００５０】
（第５の実施の形態）
本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００５１】
図１４は、本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。このスキャンパスタイミング最適化装置は、半導体デバイス内のスキャンパス回路を含んだセルを自動配置する自動配置部３０１と、自動配置部３０１によって配置されたＦＦの接続順序を決定する接続順序決定部３０２とを含む。
【００５２】
図１５は、本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部３０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ３０１）。そして、接続順序決定部３０２は、一定距離以上で配置されたＦＦの中で最も近いＦＦを接続する（Ｓ３０２）。
【００５３】
図１６は、本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。なお、図１６において、ＦＦ間の数字はＦＦ間の接続距離を示している。図１６に示すようにＦＦ１〜ＦＦ５が配置されている場合、距離が３以上で最も近いＦＦの接続順序は、ＦＦ１を始点にして、ＦＦ１→ＦＦ３→ＦＦ２→ＦＦ４→ＦＦ５となる。
【００５４】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、一定距離以上で配置されたＦＦの中で最も近いＦＦを接続するようにしたので、長配線を発生させずに、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００５５】
また、一定距離以上で配置されたＦＦの中で最も近いＦＦを接続するだけでスキャンパス回路の接続順序を決定できるので、短時間で集積度の高いレイアウト結果を得ることが可能となった。
【００５６】
（第６の実施の形態）
本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００５７】
また、本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成は、図１４に示す第５の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成と比較して、接続順序決定部３０２の機能が異なる点のみが異なる。したがって、重複する構成および機能の詳細な説明は繰返さない。なお、本実施の形態における接続順序決定部の参照符号を３０２ａとして説明する。
【００５８】
図１７は、本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部３０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ４０１）。そして、接続順序決定部３０２ａは、ＦＦのスキャン端子を駆動するセルの駆動能力を考慮して、一定遅延時間以上と見積もられるＦＦの組合わせの中で最も近いＦＦを接続する（Ｓ４０２）。
【００５９】
図１８は、本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。なお、図１８において、ＦＦ間の数字はＦＦ間のスキャン端子における遅延時間の見積もりを示している。図１８に示すようにＦＦ１〜ＦＦ５が配置されている場合、遅延時間の見積もりが３以上の組合わせで最も近いＦＦの接続順序は、ＦＦ１を始点にして、ＦＦ１→ＦＦ３→ＦＦ２→ＦＦ４→ＦＦ５となる。
【００６０】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、一定遅延時間以上と見積もられたＦＦの組合わせ中で最も近いＦＦを接続するようにしたので、長配線を発生させずに、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００６１】
また、一定遅延時間以上と見積もられたＦＦの組合わせの中で最も近いＦＦを接続するだけでスキャンパス回路の接続順序を決定できるので、短時間で集積度の高いレイアウト結果を得ることが可能となった。
【００６２】
（第７の実施の形態）
本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００６３】
また、本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成は、図１４に示す第５の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成と比較して、接続順序決定部３０２の機能が異なる点のみが異なる。したがって、重複する構成および機能の詳細な説明は繰返さない。なお、本実施の形態における接続順序決定部の参照符号を３０２ｂとして説明する。
【００６４】
図１９は、本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部３０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ５０１）。そして、接続順序決定部３０２ｂは、ＦＦへのクロックの到着時刻を考慮して、クロック到着時間差よりスキャンパスの遅延時間が一定時間以上大きくなるようにＦＦを接続する（Ｓ５０２）。なお、クロック到着時間差とは、接続されるスキャンパス回路において、（入力側のＦＦのクロック到着時刻−出力側のＦＦのクロック到着時刻）を指すものとする。
【００６５】
図２０は、本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。なお、図２０において、ＦＦ間の丸内の数字はＦＦ間のスキャン端子における遅延時間の見積もりを示しており、ＦＦに付された括弧内の数字はＦＦへのクロック到着時刻を示している。図２０に示すようにＦＦ１〜ＦＦ５が配置されている場合、ＦＦ間のスキャン端子における遅延時間が、クロック到着時間差よりも３以上大きくなるようにＦＦの接続順序を決定すると、ＦＦ１を始点にして、ＦＦ１→ＦＦ４→ＦＦ２→ＦＦ５→ＦＦ３となる。
【００６６】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、ＦＦ間のスキャン端子における遅延時間が、クロック到着時間差よりも一定時間以上大きくなるようにＦＦを接続するようにしたので、実施の形態６におけるスキャンパスタイミング最適化装置と比較して、さらにホールドタイムエラーの発生を低減することが可能となった。
【００６７】
（第８の実施の形態）
本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置の構成例は、図３に示す本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例と同様であるので、詳細な説明は繰返さない。
【００６８】
また、本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成は、図１４に示す第５の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成と比較して、接続順序決定部３０２の機能が異なる点のみが異なる。したがって、重複する構成および機能の詳細な説明は繰返さない。なお、本実施の形態における接続順序決定部の参照符号を３０２ｃとして説明する。
【００６９】
図２１は、本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。まず、自動配置部３０１は、スキャンパス回路を含むセルの自動配置を行なう（Ｓ６０１）。そして、接続順序決定部３０２ｃは、ＦＦへのクロック到着時刻を考慮して、入力側のＦＦのクロック到着時刻が出力側のＦＦのクロック到着時刻よりも一定時間以上遅くならないようにＦＦを接続する（Ｓ６０２）。
【００７０】
図２２は、本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。なお、図２２において、ＦＦに付された括弧内の数字はＦＦへのクロック到着時刻を示している。図２２に示すようにＦＦ１〜ＦＦ５が配置されている場合、クロック到着時間差（入力側のＦＦのクロック到着時刻−出力側のＦＦのクロック到着時刻）が２以上とならないようにＦＦの接続順序を決定すると、ＦＦ１を始点にして、ＦＦ１→ＦＦ２→ＦＦ４→ＦＦ５→ＦＦ３となる。
【００７１】
以上説明したように、本実施の形態におけるスキャンパスタイミング最適化装置によれば、クロック到着時間差が一定時間以上とならないようにＦＦを接続するようにしたので、長配線を発生させずに、局所的にＦＦ間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【００７２】
また、クロック到着時間差が一定時間以上とならないようにＦＦを接続するだけでスキャンパス回路の接続順序を決定できるので、短時間で集積度の高いレイアウト結果を得ることが可能となった。
【００７３】
今回開示された実施の形態は、すべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【００７４】
【発明の効果】
領域内接続順序決定手段が配置領域分割手段によって分割された領域内のスキャンパス回路の接続順序をランダムに決定し、領域間接続順序決定手段が配置領域分割手段によって分割された領域間の配線長が短くなるように、各領域間におけるスキャンパス回路の接続順序を決定するので、局所的にスキャンパス間の配線長を長くすることができ、配線混雑およびホールドタイムエラーの発生を低減することが可能となった。
【図面の簡単な説明】
【図１】配置情報を考慮せずにスキャンパス回路の接続順序を決定する方法を説明するための図である。
【図２】配置情報を考慮して配線長が短くなるようにスキャンパス回路の接続順序を決定する方法を説明するための図である。
【図３】本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の構成例を示すブロック図である。
【図４】本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。
【図５】本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図６】本発明の第１の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。
【図７】本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。
【図８】本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図９】本発明の第２の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。
【図１０】本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。
【図１１】本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図１２】本発明の第３の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。
【図１３】本発明の第４の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの配線順序を説明するための図である。
【図１４】本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置の機能的構成を示すブロック図である。
【図１５】本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図１６】本発明の第５の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。
【図１７】本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図１８】本発明の第６の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。
【図１９】本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図２０】本発明の第７の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。
【図２１】本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置の処理手順を説明するためのフローチャートである。
【図２２】本発明の第８の実施の形態におけるスキャンパスタイミング最適化装置によるＦＦの接続順序の決定を説明するための図である。
【符号の説明】
１  コンピュータ本体、２  ディスプレイ装置、３  ＦＤドライブ、４  ＦＤ、５  キーボード、６  マウス、７  ＣＤ−ＲＯＭ装置、８  ＣＤ−ＲＯＭ、９ネットワーク通信装置、１０  ＣＰＵ、１１  ＲＯＭ、１２  ＲＡＭ、１３  ハードディスク、１０１，２０１，３０１  自動配置部、１０２  配置領域分割部、１０３  領域内接続順序決定部、１０４  領域間接続順序決定部、１０５，２０３  接続順序入替部、２０２  最短距離順序決定部、３０２  接続順序決定部。
【図１】
2004185427.tif 000003
【図２】
2004185427.tif 000004
【図３】
2004185427.tif 000005
【図４】
2004185427.tif 000006
【図５】
2004185427.tif 000007
【図６】
2004185427.tif 000008
【図７】
2004185427.tif 000009
【図８】
2004185427.tif 000010
【図９】
2004185427.tif 000011
【図１０】
2004185427.tif 000012
【図１１】
2004185427.tif 000013
【図１２】
2004185427.tif 000014
【図１３】
2004185427.tif 000015
【図１４】
2004185427.tif 000016
【図１５】
2004185427.tif 000017
【図１６】
2004185427.tif 000018
【図１７】
2004185427.tif 000019
【図１８】
2004185427.tif 000020
【図１９】
2004185427.tif 000021
【図２０】
2004185427.tif 000022
【図２１】
2004185427.tif 000023
【図２２】
2004185427.tif 000024