(57)【特許請求の範囲】
【請求項１】
設計支援装置の中央処理装置にて実行されるスキャンチェーン形成方法であって、
複数のデータ保持回路について各データ保持回路のスキャン端子間の配線長が最短となるようにスキャンチェーンを形成するスキャンチェーン形成工程と、
前記複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、
を含むことを特徴とするスキャンチェーン形成方法。
【請求項２】
前記算出工程の前に、前記スキャンチェーン上の前記複数のデータ保持回路に対して入力側から出力側に向かって順番に番号を付与する番号付与工程を含み、
前記算出工程は、前記複数のデータ保持回路のうち出力側のデータ保持回路から前記第１のデータ保持回路を選択する工程を含み、
前記選択工程は、前記第１の範囲内に配置されたデータ保持回路の中から、前記第１のデータ保持回路よりも入力側であって前記第１のデータ保持回路の番号に最も近い番号の付与されたデータ保持回路を選択する
ことを特徴とする請求項１に記載のスキャンチェーン形成方法。
【請求項３】
前記算出工程の前に、前記スキャンチェーン上の前記複数のデータ保持回路に対して入力側から出力側に向かって順番に番号を付与する番号付与工程を含み、
前記算出工程は、前記複数のデータ保持回路のうち入力側のデータ保持回路から前記第１のデータ保持回路を選択する工程を含み、
前記選択工程は、前記第１の範囲内に配置されたデータ保持回路の中から、前記第１のデータ保持回路よりも出力側であって前記第１のデータ保持回路の番号に最も近い番号の付与されたデータ保持回路を選択する
ことを特徴とする請求項１に記載のスキャンチェーン形成方法。
【請求項４】
前記算出工程は、
前記第１のデータ保持回路を中心とした、ホールドエラーの発生しない第１の座標の集合を算出する工程と、
前記第１のデータ保持回路を中心とした、セットアップエラーの発生しない第２の座標の集合を算出する工程と、を含むことを特徴とする請求項１〜３のいずれか１つに記載のスキャンチェーン形成方法。
【請求項５】
前記選択工程は、
前記第１の範囲内に選択候補となるデータ保持回路が存在しない場合において、
出力側のデータ保持回路から前記第１のデータ保持回路を選択するときには、前記第１のデータ保持回路よりも入力側であって前記第１の座標の集合の境界に最も近いデータ保持回路を選択する、又は、
入力側のデータ保持回路から前記第１のデータ保持回路を選択するときには、前記第１のデータ保持回路よりも出力側であって前記第１の座標の集合の境界に最も近いデータ保持回路を選択する
ことを特徴とする請求項４に記載のスキャンチェーン形成方法。
【請求項６】
中央処理装置を有する設計支援装置の前記中央処理装置に、
複数のデータ保持回路について各データ保持回路のスキャン端子間の配線長が最短となるようにスキャンチェーンを形成するスキャンチェーン形成工程と、
前記複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、
を実行させることを特徴とするプログラム。
【請求項７】
複数のデータ保持回路について各データ保持回路のスキャン端子間の配線長が最短となるようにスキャンチェーンを形成するスキャンチェーン形成手段と、
前記複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出手段と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択手段と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー手段と、
を有することを特徴とする設計支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スキャンチェーン形成方法、プログラム及び設計支援装置に関するものである。
【背景技術】
【０００２】
従来、ＬＳＩのテスト容易化設計（Design For Testability：ＤＦＴ）の一つとして、スキャンテスト法が知られている（例えば、特許文献１参照）。このスキャンテスト法では、論理回路中のフリップフロップ（ＦＦ）を外部から制御・観測するための経路（スキャンチェーン）が形成される。すなわち、論理回路中のＦＦがスキャンＦＦに置き換えられ、動作試験時には複数のスキャンＦＦが直列に接続されてスキャンチェーンが形成される。このスキャンチェーンの入力端子から試験信号を入力して順次この値をシフトすることによって、試験対象とする組み合わせ回路に所定の入力値を設定する。次に、設定された入力値によって得られた組み合わせ回路の出力値は再びスキャンチェーンによってシフトされて出力端子から出力される。そして、この出力された値を検証することで、試験対象の組み合わせ回路が正常に動作しているか否かを検証することができる。このようにして、複雑な回路で構成される集積回路の不良箇所を容易に特定することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２５８６９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、従来のスキャンチェーンは、スキャンＦＦの配置情報に基づいて各スキャンＦＦのスキャン端子間の配線長が最短となるように接続順序が決定されて形成される。但し、この場合には、スキャンＦＦ間の信号伝搬時間が短すぎてホールドエラーが発生する場合があった。このようなホールドエラーは、スキャン端子間に遅延素子を挿入して信号伝搬を遅延させてホールド時間を確保することで改善することができる。しかし、この方法では、ホールドエラー数が増加するに連れて遅延素子数が増加し、回路の複雑化や消費電力の増大といった問題を招く。
【０００５】
また、各スキャンＦＦのスキャン端子間の配線長が一定の距離以上になれば、スキャンＦＦ間の信号伝搬に長い時間を要するため、上記ホールドエラーは発生しない。しかし、スキャンＦＦ間の信号伝搬時間が長くなりすぎると、セットアップエラーが発生する。このようなセットアップエラーは、各スキャンＦＦに入力されるクロック信号の周波数を低くすることで改善することができる。しかし、この方法では、試験時間が長くなり試験コストが増大するという問題がある。
【課題を解決するための手段】
【０００６】
本発明の一観点によれば、複数のデータ保持回路について各データ保持回路のスキャン端子間の配線長が最短となるようにスキャンチェーンを形成するスキャンチェーン形成工程と、前記複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、前記第１の範囲内に配置されたデータ保持回路の中から、前記スキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、を含む。
【発明の効果】
【０００７】
本発明の一観点によれば、タイミングエラーを解消しつつも、遅延素子の増加及び試験コストの増大を抑制することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】設計支援装置の概略構成図。
【図２】（ａ）、（ｂ）リオーダー処理前後のスキャンチェーンを示す回路図。
【図３】スキャンチェーンのリオーダー処理を説明するためのフローチャート。
【図４】スキャンチェーンのリオーダー処理を説明するためのフローチャート。
【図５】スキャンチェーンのリオーダー処理を説明するためのフローチャート。
【図６】（ａ）、（ｂ）第１の適用例のリオーダー処理を説明するための説明図。
【図７】（ａ）、（ｂ）第１の適用例のリオーダー処理を説明するための説明図。
【図８】（ａ）、（ｂ）第２の適用例のリオーダー処理を説明するための説明図。
【図９】（ａ）、（ｂ）第２の適用例のリオーダー処理を説明するための説明図。
【図１０】第２の適用例のリオーダー処理を説明するための説明図。
【図１１】（ａ）、（ｂ）第３の適用例のリオーダー処理を説明するための説明図。
【図１２】（ａ）、（ｂ）第３の適用例のリオーダー処理を説明するための説明図。
【図１３】（ａ）、（ｂ）第３の適用例のリオーダー処理を説明するための説明図。
【図１４】（ａ）、（ｂ）第３の適用例のリオーダー処理を説明するための説明図。
【発明を実施するための形態】
【０００９】
以下、一実施形態を図面に従って説明する。図１は、本実施形態のレイアウト設計装置の概略構成図である。
図１に示すように、設計支援装置１０は、例えば一般的な設計支援装置（ＣＡＤ：Computer Aided Design）である。この設計支援装置１０は、中央処理装置（ＣＰＵ）１１と、メモリ１２と、記憶装置１３と、表示装置１４と、入力装置１５と、ドライブ装置１６とを含む。これら各装置１１，１３，１４，１５，１６及びメモリ１２は、バス１７を介して相互に接続されている。
【００１０】
ＣＰＵ１１は、メモリ１２を利用してプログラムを実行し、スキャンチェーンを形成するのに必要な処理（スキャンチェーンのリオーダー処理等）を実現する。メモリ１２には、スキャンチェーン形成の機能を提供するために必要なプログラムとデータが格納される。このメモリ１２としては、通常、キャッシュ・メモリ、システム・メモリ及びディスプレイ・メモリ等を含む。
【００１１】
表示装置１４は、レイアウト表示、パラメータ入力画面等の表示に用いられる。この表示装置１４としては、例えばＣＲＴ，ＬＣＤ，ＰＤＰ等（図示略）が用いられる。入力装置１５は、ユーザからの要求や指示、パラメータの入力に用いられる。この入力装置１５としては、例えばキーボード及びマウス装置等が用いられる。
【００１２】
記憶装置１３は、通常、磁気ディスク装置、光ディスク装置、光磁気ディスク装置等を含む。この記憶装置１３には、スキャンチェーンを形成するためのプログラム（以下、プログラム）及び各種のデータファイル（以下、ファイル）が格納される。ＣＰＵ１１は、入力装置１５による指示に応答してプログラムや各種ファイルに格納されるデータを適宜メモリ１２へ転送し、それを逐次実行する。なお、記憶装置１３は、データベースとしても使用される。
【００１３】
ＣＰＵ１１が実行するプログラムは、記憶媒体１８にて提供される。ドライブ装置１６は、記憶媒体１８を駆動し、その記憶内容にアクセスする。ＣＰＵ１１は、ドライブ装置１６を介して記憶媒体１８からプログラムを読み出し、それを記憶装置１３にインストールする。
【００１４】
記憶媒体１８としては、メモリカード、フレキシブルディスク、光ディスク（例えばＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭなど）、光磁気ディスク（例えばＭＯ，ＭＤなど）等、任意のコンピュータ読取り可能な記憶媒体を使用することができる。この記憶媒体１８に、上述のプログラムを格納しておき、必要に応じて、メモリ１２にロードして使用することもできる。
【００１５】
なお、記憶媒体１８には、通信媒体を介してアップロード又はダウンロードされたプログラムを記録した媒体、ディスク装置を含む。さらに、コンピュータによって直接実行可能なプログラムを記録した記憶媒体だけでなく、一旦他の記憶媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記憶媒体や、暗号化されたり、圧縮されたりしたプログラムを記録した記憶媒体も含む。
【００１６】
図２は、スキャンチェーンの一例を示すブロック図である。
図２（ａ）に示すスキャンチェーン上には、スキャンフリップフロップ（スキャンＦＦ）１ａ〜１ｆが含まれる。これら各スキャンＦＦ１ａ〜１ｆは、スキャンイン端子ＳＩ及びスキャンアウト端子ＳＯ（総称して「スキャン端子」ともいう。）を備えている。また、各スキャンＦＦ１ａ〜１ｆは、動作試験時において、各スキャンＦＦのスキャンアウト端子ＳＯがスキャン配線を通じて次段のスキャンＦＦのスキャンイン端子ＳＩに接続され、多数のスキャンＦＦが直列に接続されている。具体的には、図２（ａ）に示すスキャンチェーンでは、多数のスキャンＦＦ１ａ〜１ｆが、入力端子Ｔｉから出力端子Ｔｏに向かってスキャンＦＦ１ａ→１ｂ→１ｃ→１ｄ→１ｅ→１ｆの順に直列に接続されている。そして、動作試験時には、各スキャンＦＦ１ａ〜１ｆは、クロック端子（図示略）に入力されるクロック信号に基づいて、スキャンイン端子ＳＩに入力されるデータをラッチしてスキャンアウト端子ＳＯから出力することにより、シフトレジスタとして動作する。
【００１７】
なお、通常動作時には、各スキャンＦＦ１ａ〜１ｆに設けられる切換機能により、スキャンイン端子ＳＩとスキャンアウト端子ＳＯとの接続が遮断され、各スキャンＦＦ１ａ〜１ｆがそれぞれ他の論理回路と接続される。
【００１８】
ここで、図２（ｂ）は、図２（ａ）に示すスキャンチェーンにおけるスキャンＦＦ１ｃ，１ｄ間で発生するホールドエラーを解消するために、スキャンチェーンのリオーダー処理（つなぎ順の変更処理）を行った後のスキャンチェーンを示すものである。すなわち、リオーダー処理後のスキャンチェーンでは、図２（ａ）に示すつなぎ順を、入力端子Ｔｉから出力端子Ｔｏに向かってスキャンＦＦ１ａ→１ｃ→１ｂ→１ｄ→１ｅ→１ｆとなるようにつなぎ替えてホールドエラーを解消している。
【００１９】
次に、このようなホールドエラーやセットアップエラーを解消しつつスキャンチェーンを形成する方法の概略を図３に従って説明する。
まず、ＣＰＵ１１は、論理回路の配置及び配線を実行し、論理回路中のスキャンＦＦの配置情報に基づいて各スキャンＦＦ１ａ〜１ｆのスキャン端子間の配線長が最短となるようにスキャンチェーンを形成する（ステップＳ１）。なお、図２（ａ）に示すスキャンチェーンは、このステップＳ１で形成されたスキャンチェーンである。
【００２０】
続いて、ＣＰＵ１１は、ステップＳ１で形成したスキャンチェーンに対してタイミング解析処理（例えば、Static timing analysis：ＳＴＡ）を実行する（ステップＳ２）。このタイミング解析処理でスキャンチェーン内にタイミングエラー（ホールドエラー又はセットアップエラー）が発生した場合には（ステップＳ３でＹＥＳ）、ＣＰＵ１１は、スキャンチェーンのリオーダー処理を実行する（ステップＳ４）。
【００２１】
次に、ＣＰＵ１１は、リオーダー処理後のスキャンチェーンに対してタイミング解析処理を再度実行する（ステップＳ５）。このタイミング解析処理でスキャンチェーン内にタイミングエラーが発生した場合には（ステップＳ６でＹＥＳ）、ＣＰＵ１１は、予め設定された所定回数だけリオーダー処理を実行したか否かを判定する（ステップＳ７）。このとき、リオーダー処理の回数が所定回数に達していない場合には（ステップＳ７でＮＯ）、上記ステップＳ４〜Ｓ６の処理が繰り返し実行される。一方、リオーダー処理の回数が所定回数に達した場合には（ステップＳ７でＹＥＳ）、スキャンチェーンのレイアウト処理を終了する。
【００２２】
なお、タイミング解析処理でスキャンチェーン内にタイミングエラーが発生していない場合には（ステップＳ３，Ｓ６でＮＯ）、ホールドタイミング及びセットアップタイミングが正常なタイミングに収束したものとしてスキャンチェーンのレイアウト処理を終了する。
【００２３】
次に、上記ステップＳ４におけるスキャンチェーンのリオーダー処理の具体的処理を図４及び図５に従って説明する。はじめに、図６及び図７に示す第１の適用例（図２（ａ）に示すスキャンチェーンから図２（ｂ）に示すスキャンチェーンに変更する適用例）を併せ参照して説明する。
【００２４】
まず、ＣＰＵ１１は、リオーダー処理前のスキャンチェーン上の各スキャンＦＦに対して、入力側から出力側に向かって順番（昇順）に番号を付与する（ステップＳ１１：番号付与工程）。具体的には、図６（ａ）に示すリオーダー処理前のスキャンチェーンでは、先の図２（ａ）と同様に、各スキャンＦＦ１ａ〜１ｆが入力端子Ｔｉから出力端子Ｔｏに向かって、スキャンＦＦ１ａ→１ｂ→１ｃ→１ｄ→１ｅ→１ｆという順序で接続されている。このため、この場合には、スキャンＦＦ１ａ，１ｂ，１ｃ，１ｄ，１ｅ，１ｆにそれぞれ「１」、「２」、「３」、「４」、「５」、「６」という番号が付与される（図６（ａ）の各スキャンＦＦ内の数字参照）。なお、このリオーダー処理前のスキャンチェーンに対して付与された初期番号情報は、記憶装置１３に記憶される。
【００２５】
次に、ＣＰＵ１１は、上記タイミング解析処理でタイミングエラーが発生したスキャンＦＦのうち任意の１つのスキャンＦＦを、リオーダー処理の対象となる対象スキャンＦＦ（第１のデータ保持回路）として選択する（ステップＳ１２）。本例では、ＣＰＵ１１は、出力側のスキャンＦＦからタイミングエラーが発生したか否かを判定し、はじめにタイミングエラーの発生したスキャンＦＦを選択する。具体的には、ＣＰＵ１１は、スキャンＦＦ１ｆ→１ｅ→１ｄ→１ｃ→１ｂ→１ａの順番でタイミングエラーが発生したか否かを判定する。この場合には、スキャンＦＦ１ｃ，１ｄ間でタイミングエラー（ホールドエラー）が発生しているため（図６（ａ）の破線矢印参照）、スキャンＦＦ１ｄが対象スキャンＦＦとして選択されることになる。
【００２６】
続いて、ＣＰＵ１１は、対象スキャンＦＦ１ｄを基点（基準）として、ホールドエラーが発生しない最小伝搬遅延時間Ｄｍｉｎを算出する（ステップＳ１３）。ここで、この最小伝搬遅延時間Ｄｍｉｎは、スキャンＦＦのホールドタイムをＴｈとし、クロックスキューをＣｓとすると、
Ｄｍｉｎ＝Ｔｈ＋Ｃｓ
によって算出することができる。すなわち、スキャンＦＦ内部の信号遅延ＤｉｎとスキャンＦＦ間の配線遅延Ｄｌｉｎｅとの合計値が最小伝搬遅延時間Ｄｍｉｎ（＝Ｔｈ＋Ｃｓ）よりも小さいときにホールドエラーが発生する。次いで、ＣＰＵ１１は、算出した最小伝搬遅延時間ＤｍｉｎをスキャンＦＦ間距離（具体的には、スキャンＦＦのスキャン端子間距離）に換算する（ステップＳ１４）。この換算したスキャンＦＦ間距離よりも離れた座標に配置されたスキャンＦＦと対象スキャンＦＦ１ｄとがスキャン配線で接続される際には、ホールドエラーが発生しない。すなわち、これらステップＳ１３，Ｓ１４において、対象スキャンＦＦ１ｄを基点（中心）とした、ホールドエラーの発生しない座標の集合Ｘ１（第１の座標の集合）を得ることができる。
【００２７】
次に、ＣＰＵ１１は、対象スキャンＦＦ１ｄを基点（基準）として、セットアップエラーが発生しない最大伝搬遅延時間Ｄｍａｘを算出する（ステップＳ１４）。ここで、この最大伝搬遅延時間Ｄｍａｘは、クロック周期をＴとし、スキャンＦＦのセットアップタイムをＴｓとすると、
Ｄｍａｘ＝Ｔ−Ｔｓ＋Ｃｓ
によって算出することができる。すなわち、スキャンＦＦ内部の信号遅延ＤｉｎとスキャンＦＦ間の配線遅延Ｄｌｉｎｅとの合計値が最大伝搬遅延時間Ｄｍａｘよりも大きいときにセットアップエラーが発生する。続いて、ＣＰＵ１１は、算出した最大伝搬遅延時間ＤｍａｘをスキャンＦＦ間距離（具体的には、スキャンＦＦのスキャン端子間距離）に換算する。この換算したスキャンＦＦ間距離よりも近い座標に配置されたスキャンＦＦと対象スキャンＦＦ１ｄとがスキャン配線で接続される際には、セットアップエラーが発生しない。すなわち、これらステップＳ１５，Ｓ１６において、対象スキャンＦＦ１ｄを基点（中心）とした、セットアップエラーの発生しない座標の集合Ｘ２（第２の座標の集合）を得ることができる。これにより、ホールドエラーの発生しない座標の集合Ｘ１とセットアップエラーの発生しない座標の集合Ｘ２との双方に含まれる座標の集合Ｘ３、すなわち対象スキャンＦＦ１ｄを中心とした、タイミングエラーの発生しない座標の集合Ｘ３を得ることができる。ここで、本例のようにスキャン配線の配線角が任意の角度を取る場合には、図６に示すように、座標集合Ｘ３が円形となる。なお、第２の適用例のようにスキャン配線の配線角が直角のみの場合には、図８に示すように、座標集合Ｘ３がひし形となる。このような座標集合Ｘ３内に配置されるスキャンＦＦが、対象スキャンＦＦ１ｄにとってスキャン配線を接続した際にタイミングエラーが発生しないスキャンＦＦの選択候補となる。なお、スキャンＦＦ間距離及び基点は、スキャンＦＦのスキャン端子やスキャンＦＦの配置座標から考える。また、上記最小伝搬遅延時間Ｄｍｉｎや最大伝搬遅延時間Ｄｍａｘの算出に必要な各パラメータ（クロックスキューＣｓ等）の数値は、設計に使用されるテクノロジやレイアウトなどによって変わる。
【００２８】
次に、図５のステップＳ１７において、ＣＰＵ１１は、対象スキャンＦＦ１ｄのつなぎ先の選択候補となるスキャンＦＦが存在するか否かを判定する。具体的には、本例では上記ステップＳ１２で出力側のスキャンＦＦからタイミングエラーが発生しているか否かを判定しているため、スキャンＦＦ１ｄよりも入力側のスキャンＦＦ１ａ〜１ｃの中に選択候補となるスキャンＦＦが存在するか否かを判定する。ここでは、図６（ａ）に示すように、座標集合Ｘ３（第１の範囲）内にスキャンＦＦ１ｂが配置されているため、選択候補となるスキャンＦＦが存在すると判定される（ステップＳ１７でＹＥＳ）。続いて、本例では座標集合Ｘ３の適用によるリオーダー処理が出力側から実行されているため（ステップＳ１８でＹＥＳ）、ステップＳ１９に移る。このステップＳ１９において、ＣＰＵ１１は、選択候補のスキャンＦＦのうち、対象スキャンＦＦ１ｄから入力側に向かって最大番号の選択候補スキャンＦＦ（ここでは、スキャンＦＦ１ｂ）を選択する（選択工程）。ここで、対象スキャンＦＦ１ｄから入力側に向かって最も近い番号の選択候補スキャンＦＦを選択するのは、上記ステップＳ１で形成されたスキャンチェーンのつなぎ順をできる限り保持した状態でリオーダー処理を実行するためである。
【００２９】
次に、ＣＰＵ１１は、対象スキャンＦＦ１ｄとステップＳ１９で選択した選択候補スキャンＦＦ１ｂとを接続するようにスキャンＦＦのつなぎ順を変更する、つまり対象スキャンＦＦ１ｄのリオーダー処理を実行する（ステップＳ２０：リオーダー工程）。すなわち、ＣＰＵ１１は、図６（ｂ）に示すように、スキャンＦＦ１ｄのスキャンイン端子のつなぎ先を、スキャンＦＦ１ｃからスキャンＦＦ１ｂのスキャンアウト端子に変更する。これにより、出力側からスキャンＦＦ１ｆ→１ｅ→１ｄ→１ｂの順番でつなぎ順が確定される。さらに、ＣＰＵ１１は、上記つなぎ順の変更に伴って、スキャンＦＦ１ａ〜１ｃのつなぎ順を、上記ステップＳ１で形成されたスキャンチェーンのつなぎ順をできる限り保持するように変更する（変更工程）。すなわち、ＣＰＵ１１は、スキャンＦＦ１ａ，１ｂ，１ｃのつなぎ順を、つなぎ順が未確定のスキャンＦＦ１ａ，１ｃについて初期番号が入力側から小さい順となるように、つまりスキャンＦＦ１ａ→１ｃ→１ｂとなるように変更する。なお、図６（ｂ）においては、上述のようにリオーダー処理に伴って接続が変更された配線、すなわちリオーダー候補の配線を破線矢印で示している。
【００３０】
次に、ＣＰＵ１１は、つなぎ順の変更された全てのスキャンＦＦ（ここでは、スキャンＦＦ１ａ〜１ｄ）に座標集合Ｘ３を適用してリオーダー処理を実行した否かを判定する（ステップＳ２１）。ここでは、スキャンＦＦ１ａ〜１ｃについては、未だ座標集合Ｘ３が適用されていないため（ステップＳ２１でＮＯ）、ステップＳ１１に戻り、それらスキャンＦＦ１ａ〜１ｃに対して座標集合Ｘ３を適用する。すなわち、上記ステップＳ２０でつなぎ順の変更された全てのスキャンＦＦ１ａ〜１ｃ（リオーダー候補の配線）についてタイミングエラーが発生しないことを確認する。
【００３１】
具体的には、ＣＰＵ１１は、ステップＳ１１において、つなぎ順の変更された後のスキャンチェーンの各スキャンＦＦに対して、入力端子Ｔｉ側から出力端子Ｔｏ側に向かって順番に番号を付与する。ここでは、図７（ａ）に示すように、スキャンＦＦ１ａ，１ｃ，１ｂ，１ｄ，１ｅ，１ｆにそれぞれ「１」、「２」、「３」、「４」、「５」、「６」という番号が付与される。なお、図７以降の図面におけるスキャンＦＦ中に示された括弧内の数字は、上記ステップＳ１で形成されたスキャンチェーンに対して付与された初期番号である。
【００３２】
次に、ＣＰＵ１１は、つなぎ順の変更されたスキャンＦＦ１ａ〜１ｃのうち、最も出力側のスキャンＦＦ１ｂを対象スキャンＦＦ１ｂとして選択する（ステップＳ１２）。その後、ＣＰＵ１１は、このスキャンＦＦ１ｂを中心とした、タイミングエラーの発生しない座標集合Ｘ３を算出する（ステップＳ１３〜Ｓ１６：算出工程）。この座標集合Ｘ３内に配置されたスキャンＦＦのうち、対象スキャンＦＦ１ｂよりも入力側のスキャンＦＦ１ａ，１ｃが選択候補となる（ステップＳ１７でＹＥＳ）。ＣＰＵ１１は、これら選択候補スキャンＦＦ１ａ，１ｃのうち最大番号の付与されたスキャンＦＦ１ｃをつなぎ先のスキャンＦＦとして選択する（ステップＳ１９）。このように、対象スキャンＦＦ１ｂのリオーダー候補の配線のつなぎ先であるスキャンＦＦ１ｃがつなぎ先のスキャンＦＦとして選択されたことにより、これらスキャンＦＦ１ｂ，１ｃではタイミングエラーが発生しないと判断することができる。そして、ＣＰＵ１１は、図７（ａ）に示すように、対象スキャンＦＦ１ｂのスキャンイン端子のつなぎ先を、スキャンＦＦ１ｃのスキャンアウト端子に確定する（ステップＳ２０）。
【００３３】
同様に、スキャンＦＦ１ｃについても座標集合Ｘ３の適用を実施し（ステップＳ１１〜Ｓ２０）、図７（ｂ）に示すように、対象スキャンＦＦ１ｃのスキャンイン端子のつなぎ先を、スキャンＦＦ１ａのスキャンアウト端子に確定する。
【００３４】
このように、つなぎ順の変更された全てのスキャンＦＦに対して座標集合Ｘ３の適用が終了すると（ステップＳ２１でＹＥＳ）、ＣＰＵ１１は、タイミングエラーの発生した全てのスキャンＦＦに対して座標集合Ｘ３の適用が終了したかを判定する（ステップＳ２２）。ここでは、タイミングエラーの発生した全てのスキャンＦＦ１ｃ，１ｄに対して座標集合Ｘ３の適用が終了しているため（ステップＳ２２でＹＥＳ）、スキャンチェーンのリオーダー処理を終了する。
【００３５】
このようなリオーダー処理によって、図６（ａ）に示すリオーダー処理前のつなぎ順（スキャンＦＦ１ａ→１ｂ→１ｃ→１ｄ→１ｅ→１ｆ）が、図７（ｂ）に示すつなぎ順（スキャンＦＦ１ａ→１ｃ→１ｂ→１ｄ→１ｅ→１ｆ）に変更される。このとき、つなぎ順が変更されたスキャンＦＦ１ａ，１ｂ，１ｃ，１ｄでは、タイミングエラー（ホールドエラー及びセットアップエラー）の発生しない座標集合Ｘ３を適用させてつなぎ先が確定されているため、タイミングエラーが解消されている。したがって、このリオーダー処理により、ホールドエラー及びセットアップエラーの解消されたスキャンチェーンが形成される。換言すると、スキャンＦＦ間に遅延素子を挿入することなく、スキャンＦＦ間のつなぎ順を変更するのみで、ホールドエラー及びセットアップエラーを解消することができる。
【００３６】
なお、上記リオーダー処理後のスキャンチェーンに対するタイミング解析処理でタイミングエラーが発生する場合には、リオーダー処理回数が所定回数に達するまでは上述と同様のリオーダー処理が繰り返し実行される。
【００３７】
次に、第２の適用例におけるスキャンチェーンのリオーダー処理を図８〜図１０に従って説明する。なお、図８（ａ）は、図３のステップＳ１で形成されたリオーダー処理前のスキャンチェーンを示している。このスキャンチェーンでは、各スキャンＦＦ２ａ〜２ｇが入力端子Ｔｉから出力端子Ｔｏに向かって、スキャンＦＦ２ａ→２ｂ→２ｃ→２ｄ→２ｅ→２ｆ→２ｇという順序で接続されており、スキャンＦＦ２ｂ，２ｃ間でホールドエラーが発生している。
【００３８】
まず、ＣＰＵ１１は、図８（ａ）に示すように、スキャンＦＦ２ａ，２ｂ，２ｃ，２ｄ，２ｅ，２ｆ，２ｇにそれぞれ「１」、「２」、「３」、「４」、「５」、「６」、「７」という初期番号を付与する（ステップＳ１１）。なお、このリオーダー処理前のスキャンチェーンに対して付与された初期番号情報は、記憶装置１３に記憶される。
【００３９】
次に、ＣＰＵ１１は、タイミングエラーが発生したスキャンＦＦのうち任意の１つのスキャンＦＦを対象スキャンＦＦとして選択する（ステップＳ１２）。本例では、ＣＰＵ１１は、入力側のスキャンＦＦからタイミングエラーが発生しているか否かを判定し、はじめにタイミングエラーの発生しているスキャンＦＦを選択する。具体的には、ＣＰＵ１１は、スキャンＦＦ２ａ→２ｂ→２ｃ→２ｄ→２ｅ→２ｆ→２ｇの順番でタイミングエラーが発生しているか否かを判定する。この場合には、スキャンＦＦ２ｂ，２ｃ間でホールドエラーが発生しているため（破線矢印参照）、スキャンＦＦ２ｂが対象スキャンＦＦとして選択されることになる。
【００４０】
続いて、対象スキャンＦＦ２ｂを中心とした、ホールドエラーの発生しない座標集合Ｘ１とセットアップエラーの発生しない座標集合Ｘ２を算出することにより、タイミングエラーの発生しない座標集合Ｘ３を算出する（ステップＳ１３〜Ｓ１６）。
【００４１】
次に、ＣＰＵ１１は、対象スキャンＦＦ２ｂのつなぎ先の選択候補となるスキャンＦＦが存在するか否かを判定する（ステップＳ１７）。具体的には、本例では上記ステップＳ１２で入力側のスキャンＦＦからタイミングエラーが発生しているか否かを判定しているため、スキャンＦＦ２ｂよりも出力側のスキャンＦＦ２ｃ〜２ｇの中に選択候補スキャンＦＦが存在するか否かを判定する。ここでは、図８（ａ）に示すように、座標集合Ｘ３内にスキャンＦＦ２ｆが配置されているため、選択候補となるスキャンＦＦが存在すると判定される（ステップＳ１７でＹＥＳ）。続いて、本例では座標集合Ｘ３の適用によるリオーダー処理が入力側から実行されているため（ステップＳ１８でＮＯ）、ＣＰＵ１１は、選択候補スキャンＦＦのうち、対象スキャンＦＦ２ｂから出力側に向かって最小番号の選択候補スキャンＦＦ（ここでは、スキャンＦＦ２ｆ）を選択する（ステップＳ２３）。ここで、対象スキャンＦＦ２ｂから出力側に向かって最も近い番号の選択候補スキャンＦＦを選択するのは、上記ステップＳ１で形成されたスキャンチェーンのつなぎ順をできる限り保持した状態でリオーダー処理を実行するためである。
【００４２】
次に、ＣＰＵ１１は、対象スキャンＦＦ２ｂと上記ステップＳ１９で選択した選択候補スキャンＦＦ２ｆとを接続するように、スキャンＦＦのつなぎ順を変更する（ステップＳ２０）。すなわち、ＣＰＵ１１は、図８（ｂ）に示すように、スキャンＦＦ２ｂのスキャンアウト端子のつなぎ先を、スキャンＦＦ２ｃからスキャンＦＦ２ｆのスキャンイン端子に変更する。この変更に伴って、スキャンＦＦ２ｃ〜２ｇのつなぎ順が、つなぎ順の未確定なスキャンＦＦ２ｃ〜２ｅ，２ｇについて初期番号が入力側から小さい順となるように、つまりスキャン２ｆ→２ｃ→２ｄ→２ｅ→２ｇとなるように変更される（変更箇所は破線矢印参照）。なお、このときのつなぎ順の変更は、上記タイミング解析処理でタイミングエラーの発生が検出されていないスキャン配線（スキャンパス）は極力修正しないように実行される、とも言える。
【００４３】
次に、ＣＰＵ１１は、つなぎ順の変更されたスキャンＦＦ２ｆに対して座標集合Ｘ３を適用することにより、スキャンＦＦ２ｆ，２ｃ間でタイミングエラーが発生しないことを確認する。具体的には、図８（ｂ）に示すスキャンチェーン上のスキャンＦＦ２ａ，２ｂ，２ｆ，２ｃ，２ｄ，２ｅ，２ｇに対して、「１」、「２」、「３」、「４」、「５」、「６」、「７」という番号を付与する（図９（ａ）参照）。続いて、スキャンＦＦ２ｆを中心とした座標集合Ｘ３を算出し、スキャンＦＦ２ｆのつなぎ先であるスキャンＦＦ２ｃが座標集合Ｘ３内に配置されているか否かを確認する（ステップＳ１２〜Ｓ１７）。しかし、ここでは、スキャンＦＦ２ｃが座標集合Ｘ３内に配置されていないため、スキャンＦＦ２ｆ，２ｃ間ではホールドエラーが発生すると判定される。そこで、ＣＰＵ１１は、座標集合Ｘ３内に配置された選択候補スキャンＦＦ２ｅを、対象スキャンＦＦ２ｆのつなぎ先のスキャンＦＦとして選択する。
【００４４】
続いて、ＣＰＵ１１は、図９（ａ）に示すように、スキャンＦＦ２ｆのスキャンアウト端子のつなぎ先を、スキャンＦＦ２ｃからスキャンＦＦ２ｅのスキャンイン端子に変更する。この変更に伴って、スキャンＦＦ２ｃ〜２ｅ，２ｇのつなぎ順が、つなぎ順の未確定なスキャンＦＦ２ｃ，２ｄ，２ｇについて初期番号が入力側から小さい順となるように、つまりスキャンＦＦ２ｅ→２ｃ→２ｄ→２ｇとなるように変更される（変更箇所は破線矢印参照）。
【００４５】
次に、ＣＰＵ１１は、つなぎ順の変更されたスキャンＦＦ２ｅに対して座標集合Ｘ３を適用することにより、スキャンＦＦ２ｅ，２ｃ間でタイミングエラーが発生しないことを確認する（ステップＳ１１〜Ｓ１９）。ここでは、図９（ｂ）に示すように、スキャンＦＦ２ｅを中心とした座標集合Ｘ３内にスキャンＦＦ２ｃが含まれるため、ＣＰＵ１１は、スキャンＦＦ２ｅのスキャンアウト端子のつなぎ先を、スキャンＦＦ２ｃのスキャンイン端子に確定する（ステップＳ２０）。同様に、ＣＰＵ１１は、スキャンＦＦ２ｄに対して座標集合Ｘ３を適用し、図１０に示すように、スキャンＦＦ２ｄのスキャンアウト端子のつなぎ先を、スキャンＦＦ２ｇのスキャンイン端子に確定する（ステップＳ１１〜Ｓ２０）。なお、スキャンＦＦ２ｃ，２ｄ間は、リオーダー処理前からつなぎ順が変更されておらず、リオーダー処理前からタイミングエラーが発生していないため、このスキャンＦＦ２ｃに対して座標集合Ｘ３は適用されない。
【００４６】
以上の処理により、つなぎ順が変更された全てのスキャンＦＦ及びタイミングエラーの発生した全てのスキャンＦＦに対して座標集合Ｘ３の適用が終了するため（ステップＳ２１，Ｓ２２でＹＥＳ）、ＣＰＵ１１はスキャンチェーンのリオーダー処理を終了する。
【００４７】
このようなリオーダー処理によって、スキャンＦＦ２ａ→２ｂ→２ｃ→２ｄ→２ｅ→２ｆ→２ｇのつなぎ順（図８（ａ）参照）が、スキャンＦＦ２ａ→２ｂ→２ｆ→２ｅ→２ｃ→２ｄ→２ｇ（図１０参照）となるように変更される。これにより、ホールドエラー及びセットアップエラーの解消されたスキャンチェーンが形成される。
【００４８】
最後に、第３の適用例におけるスキャンチェーンのリオーダー処理を図１１〜図１４に従って説明する。なお、図１１（ａ）は、図３のステップＳ１で形成されたリオーダー処理前のスキャンチェーンを示している。このスキャンチェーンでは、各スキャンＦＦ３ａ〜３ｈが入力端子Ｔｉから出力端子Ｔｏに向かって、スキャンＦＦ３ａ→３ｂ→３ｃ→３ｄ→３ｅ→３ｆ→３ｇ→３ｈという順序で接続されている。また、このスキャンチェーンでは、スキャンＦＦ３ｃ，３ｄ間及びスキャンＦＦ３ｆ，３ｇ間でホールドエラーが発生している（破線矢印参照）。
【００４９】
まず、ＣＰＵ１１は、図１１（ａ）に示すように、スキャンＦＦ３ａ，３ｂ，３ｃ，３ｄ，３ｅ，３ｆ，３ｇ，３ｈにそれぞれ「１」、「２」、「３」、「４」、「５」、「６」、「７」、「８」という初期番号を付与する（ステップＳ１１）。なお、このリオーダー処理前のスキャンチェーンに対して付与された初期番号情報は、記憶装置１３に記憶される。
【００５０】
次に、ＣＰＵ１１は、第１の適用例と同様に、出力側のスキャンＦＦから座標集合Ｘ３の適用によるリオーダー処理を実行する。具体的には、ＣＰＵ１１は、スキャンＦＦ３ｈ→３ｇ→３ｆ→３ｅ→３ｄ→３ｃ→３ｂ→３ａの順番でタイミングエラーが発生しているか否かを判定する。この場合には、スキャンＦＦ３ｆ，３ｇ間でホールドエラーが発生しているため（破線矢印参照）、ＣＰＵ１１は、スキャンＦＦ３ｇを対象スキャンＦＦとして選択する（ステップＳ１２）。
【００５１】
続いて、対象スキャンＦＦ３ｇを中心とした、ホールドエラーの発生しない座標集合Ｘ１とセットアップエラーの発生しない座標集合Ｘ２を算出することにより、タイミングエラーの発生しない座標集合Ｘ３を算出する（ステップＳ１３〜Ｓ１６）。
【００５２】
次に、図１１（ａ）示すように、対象スキャンＦＦ３ｇよりも入力側のスキャンＦＦ３ｄ，３ｅが座標集合Ｘ３内に配置されているため、選択候補スキャンＦＦが存在すると判定される（ステップＳ１７でＹＥＳ）。続いて、本例では座標集合Ｘ３の適用が出力側から実行されているため（ステップＳ１８でＹＥＳ）、選択候補のスキャンＦＦ３ｄ（番号：４）とスキャンＦＦ３ｅ（番号：５）のうち最大番号の選択候補スキャンＦＦ３ｅを選択する（ステップＳ２３）。
【００５３】
次いで、ＣＰＵ１１は、図１１（ｂ）に示すように、対象スキャンＦＦ３ｇのスキャンイン端子のつなぎ先を、スキャンＦＦ３ｆからスキャン３ｅのスキャンアウト端子に変更する。この変更に伴って、スキャンＦＦ３ｄ〜３ｇのつなぎ順が、つなぎ順の未確定なスキャンＦＦ３ｄ，３ｆについて初期番号が入力側から小さい順となるように、つまりスキャンＦＦ３ｄ→３ｆ→３ｅ→３ｇとなるように変更される（破線矢印参照）。
【００５４】
次に、ＣＰＵ１１は、つなぎ順の変更されたスキャンＦＦ３ｅに対して座標集合Ｘ３を適用することにより、スキャンＦＦ３ｅ，３ｆ間でタイミングエラーが発生しないことを確認する（ステップＳ１１〜Ｓ１９）。ここでは、図１２（ａ）に示すように、スキャンＦＦ３ｅを中心とした座標集合Ｘ３内にスキャンＦＦ３ｆが含まれるため、スキャンＦＦ３ｅのスキャンイン端子のつなぎ先が、スキャンＦＦ３ｆのスキャンアウト端子に確定される（ステップＳ２０）。同様に、スキャンＦＦ３ｆに対して座標集合Ｘ３が適用され、図１２（ｂ）に示されるように、スキャンＦＦ３ｆのスキャンイン端子のつなぎ先が、スキャンＦＦ３ｄのスキャンアウト端子に確定される（ステップＳ１１〜Ｓ２０）。
【００５５】
このような処理により、つなぎ順の変更された全てのスキャンＦＦ３ｅ，３ｆに対して座標集合Ｘ３の適用が終了する（ステップＳ２１でＹＥＳ）。但し、上述したように、本例のスキャンチェーンでは、スキャンＦＦ３ｃ，３ｄ間でもタイミングエラーが発生しているため（ステップＳ２２でＮＯ）、ＣＰＵ１１は、ステップＳ１１に戻ってスキャンＦＦ３ｃ，３ｄ間のリオーダー処理を実行する。
【００５６】
まず、ＣＰＵ１１は、図１３（ａ）に示すように、スキャンＦＦ３ａ，３ｂ，３ｃ，３ｄ，３ｆ，３ｅ，３ｇ，３ｈにそれぞれ「１」、「２」、「３」、「４」、「５」、「６」、「７」、「８」という番号を付与する（ステップＳ１１）。
【００５７】
次に、スキャンＦＦ３ｃ，３ｄ間でタイミングエラーが発生しているため（破線矢印参照）、出力側のスキャンＦＦ３ｄが対象スキャンＦＦとして選択される（ステップＳ１２）。続いて、ＣＰＵ１１は、対象スキャンＦＦ３ｄを中心とした座標集合Ｘ３を算出する（ステップＳ１３〜Ｓ１６）。
【００５８】
次に、ＣＰＵ１１は、対象スキャンＦＦ３ｄのつなぎ先の選択候補となるスキャンＦＦが存在するか否かを判定する（ステップＳ１７）。このとき、スキャンＦＦ３ｄよりも入力側のスキャンＦＦ３ａ〜３ｃの中で座標集合Ｘ３内に配置されているスキャンＦＦが存在しないため、選択候補となるスキャンＦＦが存在しないと判定される（ステップＳ１７でＮＯ）。すると、図５に示すステップＳ２４において、ＣＰＵ１１は、スキャンＦＦ３ｄよりも入力側のスキャンＦＦ３ａ〜３ｃの中で座標集合Ｘ１の境界線に最も近いスキャンＦＦ（ここでは、スキャンＦＦ３ｂ）をつなぎ先のスキャンＦＦに選択する。より具体的には、ＣＰＵ１１は、スキャンＦＦ３ｄよりも入力側のスキャンＦＦ３ａ〜３ｃの中で座標集合Ｘ１の境界線に最も近く、且つスキャン配線のつなぎ替えが行われていないスキャンＦＦを選択する。なお、第２の適用例のように入力側のスキャンＦＦから座標集合Ｘ３を適用する場合には、対象スキャンＦＦよりも出力側のスキャンＦＦの中で座標集合Ｘ１の境界線に最も近く、且つスキャン配線のつなぎ替えが行われていないスキャンＦＦが選択される。
【００５９】
続いて、ＣＰＵ１１は、図１３（ｂ）に示すように、対象スキャンＦＦ３ｄのスキャンイン端子のつなぎ先を、スキャンＦＦ３ｃからスキャンＦＦ３ｂのスキャンアウト端子に変更する（ステップＳ２０）。この変更に伴って、スキャンＦＦ３ａ〜３ｄのつなぎ順が、つなぎ順の未確定なスキャンＦＦ３ａ，３ｃについて初期番号が入力側から小さい順となるように、つまりスキャンＦＦ３ａ→３ｃ→３ｂ→３ｄとなるように変更される（破線矢印参照）。
【００６０】
次に、ＣＰＵ１１は、つなぎ順の変更されたスキャンＦＦ３ｂに対して座標集合Ｘ３を適用することにより、スキャンＦＦ３ｂ，３ｃ間でタイミングエラーが発生しないことを確認する（ステップＳ１１〜Ｓ１９）。ここでは、図１４（ａ）に示すように、対象スキャンＦＦ３ｂを中心とした座標集合Ｘ３内にスキャンＦＦ３ｃが含まれるため、スキャンＦＦ３ｂのスキャンイン端子のつなぎ先が、スキャンＦＦ３ｃのスキャンアウト端子に確定される（ステップＳ２０）。同様に、スキャンＦＦ３ｃに対して座標集合Ｘ３が適用され、図１４（ｂ）に示されるように、スキャンＦＦ３ｃのスキャンイン端子のつなぎ先が、スキャンＦＦ３ａのスキャンアウト端子に確定される（ステップＳ１１〜Ｓ２０）。
【００６１】
以上の処理により、つなぎ順が変更された全てのスキャンＦＦ及びタイミングエラーの発生した全てのスキャンＦＦに対して座標集合Ｘ３の適用が終了するため（ステップＳ２１，Ｓ２２でＹＥＳ）、スキャンチェーンのリオーダー処理を終了する。
【００６２】
このようなリオーダー処理によって、スキャンＦＦ３ａ→３ｂ→３ｃ→３ｄ→３ｅ→３ｆ→３ｇ→３ｈのつなぎ順（図１１（ａ）参照）が、スキャンＦＦ３ａ→３ｃ→３ｂ→３ｄ→３ｆ→３ｅ→３ｇ→３ｈのつなぎ順（図１４（ｂ）参照）に変更される。このリオーダー処理後のスキャンチェーンに対するタイミング解析処理（図３のステップＳ５）でタイミングエラーが発生する場合（例えば、上記スキャンＦＦ３ｂ，３ｄ間でタイミングエラーが発生する場合）には、リオーダー処理回数が所定回数に達するまで上述と同様のリオーダー処理が繰り返し実行される。なお、最小伝搬遅延時間Ｄｍｉｎを算出する際にマージンを設定している場合には、スキャンＦＦ３ｄを中心とした座標集合Ｘ３内にスキャンＦＦ３ｂが配置されていなくとも、タイミング解析処理でタイミングエラーが発生しない場合もある。
【００６３】
以上説明した本実施形態によれば、以下の効果を奏することができる。
（１）タイミングエラーが発生した対象スキャンＦＦを中心とした、タイミングエラーの発生しない座標集合Ｘ３内に配置されたスキャンＦＦの中から、リオーダー処理前のスキャンチェーンのつなぎ順を極力保持するように１つのスキャンＦＦを選択する。そして、その選択したスキャンＦＦと対象スキャンＦＦを接続するようにつなぎ順を変更するようにした。これにより、タイミングエラーの発生しない位置に配置されたスキャンＦＦと対象スキャンＦＦが接続されるため、対象スキャンＦＦにおけるタイミングエラーを解消することができる。すなわち、スキャンＦＦ間に遅延素子を挿入することなく、スキャンＦＦ間のつなぎ順を変更するのみでホールドエラーの解消あるいはエラー値の縮小を図ることができる。このとき、ホールドエラーのみならず、セットアップエラーも発生しない位置に配置されたスキャンＦＦがつなぎ先として選択されるため、スキャンＦＦ間のつなぎ順を変更するのみでセットアップエラーも解消することができる。このため、各スキャンＦＦに入力されるクロック信号の周波数を低くする必要がなく、試験時間及び試験コストの増大を抑制することができる。
【００６４】
（２）さらに、対象スキャンＦＦのつなぎ先を、各スキャンＦＦのスキャン端子間の配線長が最短となるように形成されたリオーダー処理前のスキャンチェーンのつなぎ順を極力保持するように選択するようにした。これにより、つなぎ順の変更処理が進んだ際に、対象スキャンＦＦから離れた位置（具体的には、対象スキャンＦＦを中心とした座標の集合Ｘ２よりも離れた位置）に配置されたスキャンＦＦしかつなぎ先として残らない、という状況を回避することができる。したがって、リオーダー処理後のスキャンチェーンでセットアップエラーが発生することを好適に抑制することができる。
【００６５】
（３）第１及び第３の適用例では、出力側のスキャンＦＦから座標集合Ｘ３の適用によるリオーダー処理を実行するようにした。これにより、ホールドエラーを入力側のスキャンＦＦに送ることができる。このため、入力端子Ｔｉから入力される試験信号のタイミング調整によって上記ホールドエラーを解消することもできる。
【００６６】
（他の実施形態）
なお、上記実施形態は、これを適宜変更した以下の態様にて実施することもできる。
・上記実施形態におけるステップＳ７を省略してもよい。この場合には、例えば１回のみリオーダー処理（ステップＳ４）を実行するようにしてもよい。
【００６７】
・上記実施形態におけるステップＳ２４を省略してもよい。この場合には、例えばステップＳ１７において選択候補となるスキャンＦＦが存在しないときに、つなぎ順を変更せずに以降の処理を実行するようにしてもよい。
【００６８】
・上記実施形態のステップＳ１１において、スキャンチェーン上の各スキャンＦＦに対して、入力側から出力側に向かって降順に番号を付与するようにしてもよい。
・上記実施形態において、最小伝搬遅延時間Ｄｍｉｎや最大伝搬遅延時間Ｄｍａｘを算出する際にマージンを設定するようにしてもよい。
【００６９】
・上記実施形態において、最小伝搬遅延時間Ｄｍｉｎや最大伝搬遅延時間ＤｍａｘをスキャンＦＦ間距離に換算せずに、これら各遅延時間Ｄｍｉｎ，Ｄｍａｘをそのまま選択候補スキャンＦＦを探索するのに利用してもよい。すなわち、最小伝搬遅延時間Ｄｍｉｎ及び最大伝搬遅延時間Ｄｍａｘから、対象スキャンＦＦを中心とした、タイミングエラーの発生しない第１の範囲を算出するようにしてもよい。
【００７０】
・上記実施形態において、スキャンチェーンのリオーダー処理を実行した後のタイミング解析処理でタイミングエラーが残っている場合に、そのタイミングエラーの発生しているスキャンＦＦ間に遅延素子を挿入するようにしてもよい。これにより、ホールドエラーを解消するために挿入する遅延素子の数を削減しながら、ホールドエラーを解消することができる。
【００７１】
・上記実施形態において、フリップフロップ以外のデータ保持回路でスキャンチェーンを形成する場合にも応用可能である。
上記各実施形態に関し、以下の付記を開示する。
【００７２】
（付記１）
設計支援装置の中央処理装置にて実行されるスキャンチェーン形成方法であって、
複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記各データ保持回路のスキャン端子間の配線長が最短となるように形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、
を含むことを特徴とするスキャンチェーン形成方法。
【００７３】
（付記２）
前記算出工程の前に、前記スキャンチェーン上の前記複数のデータ保持回路に対して入力側から出力側に向かって順番に番号を付与する番号付与工程を含み、
前記算出工程は、前記複数のデータ保持回路のうち出力側のデータ保持回路から前記第１のデータ保持回路を選択する工程を含み、
前記選択工程は、前記第１の範囲内に配置されたデータ保持回路の中から、前記第１のデータ保持回路よりも入力側であって前記第１のデータ保持回路の番号に最も近い番号の付与されたデータ保持回路を選択する
ことを特徴とする付記１に記載のスキャンチェーン形成方法。
【００７４】
（付記３）
前記算出工程の前に、前記スキャンチェーン上の前記複数のデータ保持回路に対して入力側から出力側に向かって順番に番号を付与する番号付与工程を含み、
前記算出工程は、前記複数のデータ保持回路のうち入力側のデータ保持回路から前記第１のデータ保持回路を選択する工程を含み、
前記選択工程は、前記第１の範囲内に配置されたデータ保持回路の中から、前記第１のデータ保持回路よりも出力側であって前記第１のデータ保持回路の番号に最も近い番号の付与されたデータ保持回路を選択する
ことを特徴とする付記１に記載のスキャンチェーン形成方法。
【００７５】
（付記４）
前記算出工程は、
前記第１のデータ保持回路を中心とした、ホールドエラーの発生しない第１の座標の集合を算出する工程と、
前記第１のデータ保持回路を中心とした、セットアップエラーの発生しない第２の座標の集合を算出する工程と、を含むことを特徴とする付記１〜３のいずれか１つに記載のスキャンチェーン形成方法。
【００７６】
（付記５）
前記選択工程は、
前記第１の範囲内に選択候補となるデータ保持回路が存在しない場合において、
出力側のデータ保持回路から前記第１のデータ保持回路を選択するときには、前記第１のデータ保持回路よりも入力側であって前記第１の座標の集合の境界に最も近いデータ保持回路を選択する、又は、
入力側のデータ保持回路から前記第１のデータ保持回路を選択するときには、前記第１のデータ保持回路よりも出力側であって前記第１の座標の集合の境界に最も近いデータ保持回路を選択する
ことを特徴とする付記４に記載のスキャンチェーン形成方法。
【００７７】
（付記６）
前記第１の座標の集合を算出する工程は、
前記第１のデータ保持回路を基点として前記ホールドエラーの発生しない最小伝搬遅延時間を算出する工程と、
前記最小伝搬遅延時間を前記データ保持回路のスキャン端子間距離に換算する工程とを含み、
前記第２の座標の集合を算出する工程は、
前記第１のデータ保持回路を基点として前記セットアップエラーの発生しない最大伝搬遅延時間を算出する工程と、
前記最大伝搬遅延時間を前記データ保持回路のスキャン端子間距離に換算する工程とを含むことを特徴とする付記４に記載のスキャンチェーン形成方法。
【００７８】
（付記７）
前記リオーダー工程は、
前記選択工程で選択されたデータ保持回路と前記第１のデータ保持回路との接続によってつなぎ順が未確定となるデータ保持回路のつなぎ順を、前記各データ保持回路のスキャン端子間の配線長が最短となるように形成されたスキャンチェーンのつなぎ順をできる限り保持するように変更する変更工程を含むことを特徴とする付記１〜６のいずれか１つに記載のスキャンチェーン形成方法。
【００７９】
（付記８）
前記変更工程においてつなぎ順の変更されたデータ保持回路について、該データ保持回路を前記第１のデータ保持回路とし、前記第１の範囲を利用して前記タイミングエラーが発生しないことを確認する工程を含むことを特徴とする付記７に記載のスキャンチェーン形成方法。
【００８０】
（付記９）
設計支援装置により実行されるプログラムであって、
複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記各データ保持回路のスキャン端子間の配線長が最短となるように形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、
を含むことを特徴とするプログラム。
【００８１】
（付記１０）
複数のデータ保持回路のうちタイミングエラーの発生した第１のデータ保持回路を基準としてタイミングエラーの発生しない第１の範囲を算出する算出工程と、
前記第１の範囲内に配置されたデータ保持回路の中から、前記各データ保持回路のスキャン端子間の配線長が最短となるように形成されたスキャンチェーンのつなぎ順を保持するように１つのデータ保持回路を選択する選択工程と、
前記選択したデータ保持回路と前記第１のデータ保持回路とを接続するようにつなぎ順を変更するリオーダー工程と、
を実行することを特徴とする設計支援装置。
【符号の説明】
【００８２】
１０  設計支援装置
１１  中央処理装置
１ａ〜１ｆ，２ａ〜２ｇ，３ａ〜３ｈ  スキャンフリップフロップ（データ保持回路）
ＳＩ  スキャンイン端子（スキャン端子）
ＳＯ  スキャンアウト端子（スキャン端子）
【図１】
0005447209.tif 000002
【図２】
0005447209.tif 000003
【図３】
0005447209.tif 000004
【図４】
0005447209.tif 000005
【図５】
0005447209.tif 000006
【図６】
0005447209.tif 000007
【図７】
0005447209.tif 000008
【図８】
0005447209.tif 000009
【図９】
0005447209.tif 000010
【図１０】
0005447209.tif 000011
【図１１】
0005447209.tif 000012
【図１２】
0005447209.tif 000013
【図１３】
0005447209.tif 000014
【図１４】
0005447209.tif 000015