[go: up one dir, main page]

JP6365273B2 - テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置 - Google Patents

テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置 Download PDF

Info

Publication number
JP6365273B2
JP6365273B2 JP2014243552A JP2014243552A JP6365273B2 JP 6365273 B2 JP6365273 B2 JP 6365273B2 JP 2014243552 A JP2014243552 A JP 2014243552A JP 2014243552 A JP2014243552 A JP 2014243552A JP 6365273 B2 JP6365273 B2 JP 6365273B2
Authority
JP
Japan
Prior art keywords
test pattern
pattern generation
flip
flop
clock
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.)
Active
Application number
JP2014243552A
Other languages
English (en)
Other versions
JP2016109427A (ja
Inventor
大輔 丸山
大輔 丸山
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2014243552A priority Critical patent/JP6365273B2/ja
Priority to US14/938,000 priority patent/US9772377B2/en
Publication of JP2016109427A publication Critical patent/JP2016109427A/ja
Application granted granted Critical
Publication of JP6365273B2 publication Critical patent/JP6365273B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01R—MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES
    • G01R31/00—Arrangements for testing electric properties; Arrangements for locating electric faults; Arrangements for electrical testing characterised by what is being tested not provided for elsewhere
    • G01R31/28—Testing of electronic circuits, e.g. by signal tracer
    • G01R31/317—Testing of digital circuits
    • G01R31/3181—Functional testing
    • G01R31/3183—Generation of test inputs, e.g. test vectors, patterns or sequences
    • G01R31/318342—Generation of test inputs, e.g. test vectors, patterns or sequences by preliminary fault modelling, e.g. analysis, simulation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/32—Circuit design at the digital level
    • G06F30/33—Design verification, e.g. functional simulation or model checking
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/32—Circuit design at the digital level
    • G06F30/33—Design verification, e.g. functional simulation or model checking
    • G06F30/3308—Design verification, e.g. functional simulation or model checking using simulation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/398—Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G06F9/5022—Mechanisms to release resources
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01R—MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES
    • G01R31/00—Arrangements for testing electric properties; Arrangements for locating electric faults; Arrangements for electrical testing characterised by what is being tested not provided for elsewhere
    • G01R31/28—Testing of electronic circuits, e.g. by signal tracer
    • G01R31/317—Testing of digital circuits
    • G01R31/3181—Functional testing
    • G01R31/3183—Generation of test inputs, e.g. test vectors, patterns or sequences
    • G01R31/318314—Tools, e.g. program interfaces, test suite, test bench, simulation hardware, test compiler, test program languages
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/394—Routing

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • Tests Of Electronic Circuits (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Description

本発明は、テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置に関する。
従来、半導体集積回路の設計フローにおいて設計された対象回路のテストパターン生成をする際に、テストパターン生成時間の短縮化を図るために、対象回路を複数の回路に分割して複数のコンピュータで並列にテストパターンを生成する場合がある。
例えば、対象回路を複数のＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）にマッピングする際に、各ＦＰＧＡにマッピングされる回路のゲート数が均等となるように対象回路を分割する技術が公知である（例えば、以下特許文献１参照。）。
また、従来、対象回路に複数のクロックドメインがあり、クロックドメイン間においてデータ転送経路が混在しない場合に、スキャン機能付きの記憶素子に対してデータ転送方向とは逆順にクロック信号を供給する技術が公知である（例えば、以下特許文献２参照。）。
特開２０００−２０７４４５号公報 国際公開第９８／４９５７６号
しかしながら、従来技術では、対象回路に含まれる複数のブロックをゲート数などの回路の規模に基づき分割すると、特定の分割回路に特定のブロックが偏在する場合がある。この場合、分割回路間の特性が不均等になるという問題点がある。
１つの側面では、本発明は、分割回路間の特性の均等化を図ることができるテストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置を提供することを目的とする。
本発明の一態様面によれば、テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てるテストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置が提案される。
本発明の一側面によれば、分割回路間の特性の均等化を図ることができる。
図１は、本発明にかかるテストパターン生成装置による一動作例を示す説明図である。 図２は、テストパターン生成装置のハードウェア構成例を示すブロック図である。 図３は、テストパターン生成装置の機能的構成例を示すブロック図である。 図４は、受けＦＦマクロ内部の入力側の冗長ゲートの削除例を示す説明図である。 図５は、送りＦＦマクロ内部の出力側ディレーゲート削除例を示す説明図である。 図６は、テストパターン生成装置による冗長ディレーゲート削除処理手順例を示すフローチャートである。 図７は、図６で示したクロックパスのトレース処理（ステップＳ６０４）の詳細な説明を示すフローチャートである。 図８は、クロックパス上のネットのフォワードトレース例を示す説明図である。 図９は、図６で示したデータパスフォワード処理（ステップＳ６０５）の詳細な説明を示すフローチャートである。 図１０は、図６で示したデータパスバックワード処理（ステップＳ６０７）の詳細な説明を示すフローチャートである。 図１１は、ドライバネットとゲートの入力例を示す説明図である。 図１２は、図６で示した受けＦＦマクロ内部入力削除処理（ステップＳ６０６）の詳細な説明を示すフローチャートである。 図１３は、図６で示した送りＦＦマクロ内部出力削除処理（ステップＳ６０８）の詳細な説明を示すフローチャートである。 図１４は、ブロック情報の特徴抽出例を示す説明図である。 図１５は、分類結果と分配間隔例を示す説明図である。 図１６は、分配例を示す説明図である。 図１７は、ブロックのグルーピング例を示す説明図である。 図１８は、分配間隔決定方法のコード例を示す説明図である。 図１９は、分配間隔の決定例を示す説明図である。 図２０は、ブロック分配例を示す説明図である。 図２１は、テストパターン生成装置による回路分割リスト生成処理手順例を示すフローチャートである。 図２２は、図２１で示したブロック情報ソート処理（ステップＳ２１０２）の詳細な説明を示すフローチャートである。 図２３は、図２１で示したブロック情報グループ認識処理（ステップＳ２１０３）の詳細な説明を示すフローチャートである。 図２４は、図２１で示した分配間隔決定処理（ステップＳ２１０６）の詳細な説明を示すフローチャートである。 図２５は、図２１で示した詳細位置集合決定処理（ステップＳ２１０７）の詳細な説明を示すフローチャートである。 図２６は、図２１で示した回路分割リスト作成処理（ステップＳ２１０８）の詳細な説明を示すフローチャート（その１）である。 図２７は、図２１で示した回路分割リスト作成処理（ステップＳ２１０８）の詳細な説明を示すフローチャート（その２）である。 図２８は、ドメイン間の信号の受け渡し領域のＡＴＰＧとクロックパルスの印加順序例を示す説明図である。 図２９は、故障識別およびクロック印加順序例を示す説明図である。 図３０は、クロックマージによるパターン削減例を示す説明図である。 図３１は、テストパターン生成装置によるクロック印加順序決定処理手順例を示すフローチャートである。
以下に添付図面を参照して、本発明にかかるテストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置の実施の形態を詳細に説明する。
図１は、本発明にかかるテストパターン生成装置による一動作例を示す説明図である。テストパターン生成装置１００は、半導体集積回路の設計時におけるテストパターン生成を支援するコンピュータである。本実施の形態における対象回路、複数のブロック、分割回路などは、実際の回路ではなく、コンピュータ上における回路モデルであり、ネットリストなどの回路情報が示す回路である。
従来、テストパターン生成の対象回路に含まれる複数のブロックを分割して複数のコンピュータに割り当てて並列処理によってシミュレーションを行う場合がある。各コンピュータの負荷が均等であると、計算時間を短縮することができる。近年、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）部、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などの規模がＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の規模に対して大きくなっており、場合によっては同程度の規模を持つこともある。そのため、ゲート数により複数のブロックを分割する場合、例えば第１の分割回路にはＩ／Ｏ部のみが割り当てられ、第２の分割回路にはＣＰＵのみが割り当てられるような、機能や構成が同じようなブロックが特定の分割回路に偏在する場合がある。そのため、分割回路間において特性が不均等になるという問題点がある。
例えば、特定の分割回路に機能や構成が同じブロックが偏在する場合、クロックドメインなどが分割回路間で異なる可能性がある。複数の分割回路を並列処理しても、分割回路に含まれるブロックのクロックドメイン等の特性が異なると動作する回路部分も異なってくるため、分割回路間でシミュレーション等の処理時間にも差がつくことなる。従って最も処理の遅い分割回路の終了待ちによる並列処理全体の効率低下が発生することになる。
そこで、本実施の形態では、テストパターン生成装置１００は、規模および機能に関する特徴量の近さに基づきブロックをグループ化し、分割回路の分割数とグループのブロック数の比率に基づきグループの各ブロックを分割回路に割り当てる。これにより、分割回路間の特性の均等化を図ることができる。
まず、テストパターン生成装置１００は、複数のブロック１０３の各々について、回路情報１０１に基づくブロック１０３のサイズに関する第１特徴量と、回路情報１０１に基づくブロック１０３の機能に関する第２特徴量と、を取得する。複数のブロック１０３は、テストパターン生成の対象回路１０２に含まれる。回路情報１０１は、対象回路１０２のゲートおよびゲート間の接続関係を示す。回路情報１０１は、例えば、ネットリストである。回路情報は、Ｖｅｒｉｌｏｇ ＨＤＬ（Ｈａｒｄｗａｒｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ）やＶＨＤＬなどによって、もしくはそれら設計言語で記述された論理を特定のＣＡＤシステム用の回路データベースに展開した、ゲートレベルで記述される。
第１特徴量は、例えば、ネット数である。ゲートの数とゲートの端子の数とを合わせた数をネット数と称する。そしてゲートの入力端子を入力ネット、ゲートの出力端子を出力ネット、または単にネットと称する。第２特徴量は、例えば、所定の種類のゲートの数である。所定の種類としては、例えば、スキャンフリップフロップ数である。フリップフロップはＦＦ（Ｆｌｉｐ Ｆｌｏｐ）とも記載する。
取得形式としては、テストパターン生成装置１００は、例えば、回路情報１０１に基づいて、ブロック１０３から第１特徴量と第２特徴量を抽出することによって第１特徴量と第２特徴量を取得してもよい。また、テストパターン生成装置１００は、例えば、記憶装置から第１特徴量と第２特徴量を読み出すことにより第１特徴量と第２特徴量を取得してもよいし、ネットワークを介して他の装置から第１特徴量と第２特徴量を取得してもよい。
図１の例では、対象回路１０２には、ブロック１０３−１〜８まである。ブロック１０３−１とブロック１０３−２とは例えばＩ／Ｏ部である。ブロック１０３−３とブロック１０３−４とブロック１０３−６とブロック１０３−７はコアである。ブロック１０３−５とブロック１０３−８はＲＡＭである。ブロック１０３−１のネット数は「１００００」であり、スキャンＦＦ数は「１００」である。
つぎに、テストパターン生成装置１００は、取得した第１特徴量が第１所定範囲内であり、かつ取得した第２特徴量が第２所定範囲内であるブロック１０３が同一のグループ１０４となるように、複数のブロック１０３を複数のグループ１０４に分類する。第１所定範囲と第２所定範囲は、設計者やテストパターン作成者などの利用者によって予め定められる。図１の例では、グループ１０４−１にはブロック１０３−３と、ブロック１０３−４と、ブロック１０３−６と、ブロック１０３−７と、が分類される。グループ１０４−２にはブロック１０３−１と、ブロック１０３−２と、が分類される。グループ１０４−３には、ブロック１０３−５と、ブロック１０３−８と、が分類される。
そして、テストパターン生成装置１００は、複数のグループ１０４の各々について、グループ１０４に含まれるブロック１０３の数と分割数との比率に基づいて、グループ１０４に含まれるブロック１０３の各々を、分割数の複数の分割回路１０５のいずれかに割り当てる。分割数は、複数のブロック１０３を分割する数である。分割数は、並列化可能なコンピュータの数などに基づき利用者によって予め定められる。
グループ１０４−１はブロック１０３の数が４であり、分割数が４である。そのため、テストパターン生成装置１００は、分割回路１０５の各々にグループ１０４−１に含まれるブロック１０３を１つずつ割り当てる。グループ１０４−２はブロック１０３の数が２であり、分割数が４である。そのため、テストパターン生成装置１００は、分割回路１０５−１と、分割回路１０５−３とにブロック１０３を１つずつ割り当てる。グループ１０４−３はブロック１０３の数が２であり、分割数が４である。テストパターン生成装置１００は、例えばネット数に基づいて分割回路１０５−２と分割回路１０５−４とにブロック１０３を１つずつ割り当てる。
このように、機能や規模が近いブロック１０３同士をグループ化し、グループ１０４に含まれるブロック１０３の数と分割数との比率によってブロック１０３を割り当てる。これにより、分割回路１０５間の特性の均等化を図ることができる。
（テストパターン生成装置１００のハードウェア構成例）
図２は、テストパターン生成装置のハードウェア構成例を示すブロック図である。図２において、テストパターン生成装置１００は、ＣＰＵ２０１と、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２０２と、ＲＡＭ２０３と、ディスクドライブ２０４と、ディスク２０５と、を有する。テストパターン生成装置１００は、Ｉ／Ｆ（Ｉｎｔｅｒ／Ｆａｃｅ）２０６と、入力装置２０７と、出力装置２０８と、を有する。また、各部はバス２００によってそれぞれ接続される。
ここで、ＣＰＵ２０１は、テストパターン生成装置１００の全体の制御を司る。ＲＯＭ２０２は、ブートプログラムなどのプログラムを記憶する。ＲＡＭ２０３は、ＣＰＵ２０１のワークエリアとして使用される。ディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがってディスク２０５に対するデータのリード／ライトを制御する。ディスク２０５は、ディスクドライブ２０４の制御で書き込まれたデータを記憶する。ディスク２０５としては、磁気ディスク、光ディスクなどが挙げられる。
Ｉ／Ｆ２０６は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク２０９に接続され、このネットワーク２０９を介して他の装置に接続される。そして、Ｉ／Ｆ２０６は、ネットワーク２０９と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０６には、例えばモデムやＬＡＮアダプタなどを採用することができる。
入力装置２０７は、キーボード、マウス、タッチパネルなど利用者の操作により、各種データの入力を行うインターフェースである。また、入力装置２０７は、カメラから画像や動画を取り込むこともできる。また、入力装置２０７は、マイクから音声を取り込むこともできる。出力装置２０８は、ＣＰＵ２０１の指示により、データを出力するインターフェースである。出力装置２０８には、ディスプレイやプリンタなどが挙げられる。
（テストパターン生成装置１００の機能的構成例）
図３は、テストパターン生成装置の機能的構成例を示すブロック図である。テストパターン生成装置１００は、取得部３０１と、クロックパストレース部３０２と、データパストレース部３０３と、取得部３０４と、分類部３０５と、割当部３０６と、故障カウント部３０７と、印加順序決定部３０８と、対象外化決定部３０９と、を有する。取得部３０１から対象外化決定部３０９までの制御部の処理は、例えば、図２に示すＣＰＵ２０１がアクセス可能なＲＯＭ２０２、ＲＡＭ２０３、ディスク２０５などの記憶装置に記憶されたプログラムにコーディングされる。そして、ＣＰＵ２０１が記憶装置から該プログラムを読み出して、プログラムにコーディングされた処理を実行する。これにより、制御部の処理が実現される。また、制御部の処理結果は、例えば、ＲＡＭ２０３、ＲＯＭ２０２、ディスク２０５などの記憶装置に記憶される。
各制御部については、冗長ディレーゲート削除と、ブロック分割と、クロックマージと、の３つの処理に分けて説明する。従来技術では、対象回路をゲートレベルでモデル化する際に、ユニットディレー方式でのレース防止のためにマクロと呼ばれる部品レベルで冗長なディレーゲートを挿入しておく場合がある。この場合、本来はレースが存在しないパスにも余分なディレーゲートが挿入されることになり回路モデルが肥大化するという問題がある。そこで、本実施の形態では、制御部は、冗長ディレーゲート削除の処理を行う。また、従来技術では、テストパターン生成のために対象回路に含まれる複数のブロックをゲート数などの回路の規模に基づき分割すると、特定の分割回路に特定のブロックが偏在する場合がある。この場合、分割回路間の特性が不均等になるという問題点がある。そこで、本実施の形態では、制御部は、ブロック分割の処理を行う。さらに、従来技術では、複数のクロックが存在する場合でもスキャン後に印加するクロックを1発に限定する場合がある。この場合、試験されていない回路に対しては改めてスキャンとクロック印加を行う必要がありテストパターンが増加するという問題がある。そこで、本実施の形態では、制御部は、クロックマージの処理を行う。
＜冗長ディレーゲート削除＞
まず、冗長ディレーゲートを削除する例について説明する。従来、回路モデルをゲートモデルで作成する際に、作成方法に起因して回路モデルが大きくなる場合がある。テストパターンを生成する際には、回路モデルとしてはゲートモデルを用い、シミュレーション方式としてはユニットディレー方式を用いることがある。ゲートモデルにおいて発生したレースは解消しなければならない。
ゲートモデルにおけるレースの解消方法としては、レースが発生したデータパスにディレーゲートを挿入、送りＦＦのクロックパスにディレーゲートを挿入、受けＦＦのクロックパスのディレーゲートを削除などが挙げられる。クロックパスを修正すると他のパスへも影響があるため、データパスにディレーゲートを挿入する解消方法が実現容易である。
また、回路モデルの設計はマクロと呼ばれる部品を組み上げて行われる。従ってデータラインに使用されるマクロにディレーゲートを挿入しておき回路モデルを組み上げた際にレースが発生しないようすることが考えられる。そして特にデータパスの起点やデータパスの終点となるＦＦマクロの内部にディレーゲートが挿入される場合がある。
しかしながら、レースが発生しないようなデータパスにおいては余分なディレーゲートが挿入されることになる。また、特に近年の高速なプロセッサでのスキュー調整や微細化に伴うラインディレーの増加などにより実際の回路におけるディレーと、ユニットディレー方式のように単純にゲート段数で表したディレーと、の乖離が大きくなる。そのため、ゲートモデルでのレース解消のためのディレーゲート挿入による回路モデルが大きくなるという問題点がある。ユニットディレー方式であれば、回路モデルに含まれるゲートの数が多いほど、論理シミュレータによるシミュレーションに時間がかかる。
そこで、本実施の形態では、ゲート段数に基づいてレースが発生しないと判定されたＦＦマクロから冗長なディレーを削除する。これにより、回路モデルの肥大化の抑制を図る。
まず、取得部３０１は、テストパターン生成の対象回路のゲートおよびゲート間の接続関係を示す第１回路情報を取得する。第１回路情報はゲートレベルで記述されたネットリストである。第１回路情報は、例えば、回路情報３４１である。
つぎに、そして、クロックパストレース部３０２は、ブロックに含まれるＦＦにクロック信号を供給するクロック端子からＦＦまでの間にあるクロックパス上のゲートの数を特定する。データパストレース部３０３は、ＦＦからフォワード方向にあるＦＦまでの間のデータパス上のゲート数を導出する。データパストレース部３０３は、導出したゲートの数と、クロックパストレース部３０２によって導出されたゲートの数と、の差分値を導出する。該ＦＦは、第１回路情報が示す対象回路内のブロックに含まれるＦＦであって、ＦＦマクロの一部である、該ＦＦマクロは前記レース対策のためにマクロ内部においてデータパスとなり得るデータ入力側とデータ出力側に挿入された複数の冗長なディレーゲートを有する。データ入力側とは例えばＦＦが有するＤ端子であり、データ出力側とは例えばＦＦが有するＱ端子である。また、データパストレース部３０３は、差分値に基づいてＦＦマクロ内部の冗長なディレーゲートを削除したＦＦマクロを含む対象回路のゲートおよびゲート間の接続関係を示す第２回路情報を生成する。ここでの第２回路情報は、例えば、回路情報３４２である。
また、データパストレース部３０３とは、ＦＦから、バックワード方向にあるＦＦまでの間のデータパス上のゲート数を導出する。クロックパストレース部３０２は、ブロックに含まれるＦＦにクロック信号を供給するクロック端子からＦＦまでの間にあるクロックパス上のゲートの数を導出する。データパストレース部３０３は、導出したゲートの数と、クロックパストレース部３０２によって導出されたゲートの数と、の差分値を導出する。該ＦＦは、第１回路情報が示す対象回路内のブロックに含まれるＦＦであって、ＦＦマクロの一部である、該ＦＦマクロは前記レース対策のためにマクロ内部においてデータパスとなり得るデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートを有する。そして、データパストレース部３０３は、ＦＦマクロ内部の冗長なディレーゲートを削除したＦＦマクロを含む対象回路のゲートおよびゲート間の接続関係を示す第２回路情報を生成する。ここでの第２回路情報は、例えば、回路情報３４２である。
クロックパストレース部３０２は、例えば、クロックドメインの各々について、トーナメント計算によるクロックパスごとのゲート段数の上限値とゲート段数の下限値を特定する。そして、データパストレース部３０３は、到達したＦＦマクロからデータパスのフォワードトレースを行う。または、データパストレース部３０３は、到達したＦＦマクロからデータパスのバックワードトレースを行う。ここでは、データパストレース部３０３は、フォワードトレースを行うような受けＦＦマクロ内部の入力側の冗長ゲートを削除する処理と、バックワードトレースを行うような送りＦＦマクロ内部の出力側の冗長ゲートを削除する処理と、を行う。
そのため、データパストレース部３０３は、受けＦＦマクロ内部の入力側の冗長ゲートを削除する処理についてのゲート段数算出部３１１と、送りクロックドメイン記録部３１２と、受けＦＦマクロ内部入力削除部３１３と、を有する。また、データパストレース部３０３は、バックワードトレースを行うような送りＦＦマクロ内部の出力側の冗長ゲートを削除する処理についてのゲート段数算出部３２１と、受けクロックドメイン記録部３２２と、送りＦＦマクロ内部出力削除部３２３と、を有する。
まず、受けＦＦマクロ内部の入力側の冗長ゲートを削除する処理の詳細について説明する。
図４は、受けＦＦマクロ内部の入力側の冗長ゲートの削除例を示す説明図である。クロックパストレース部３０２は、例えば、ブロックに含まれる選択されたＦＦマクロについて、ブロックに含まれるクロック端子からＦＦマクロのクロック端子までの間のクロックパス上のゲート段数の上限値とゲート段数の下限値を特定する。
例えば、ＦＦマクロａについての上限値はｃｍａｘ［ＣＫａ］であり、ＦＦマクロａについての下限値はｃｍｉｎ［ＣＫａ］である。例えば、ＦＦマクロｂについての上限値はｃｍａｘ［ＣＫｂ］であり、ＦＦマクロｂについての下限値はｃｍｉｎ［ＣＫｂ］である。例えば、ＦＦマクロｃについての上限値はｃｍａｘ［ＣＫｃ］であり、ＦＦマクロｃについての下限値はｃｍｉｎ［ＣＫｃ］である。クロックパストレース部３０２によるクロックパスのトレース処理の詳細例については図７に示す。
クロックパストレース部３０２は、ブロックに含まれるクロック端子を始点としてブロックに含まれるＦＦマクロのクロック端子を終点としてゲート段数を算出する。クロックパストレース部３０２は、例えば、ｃｍｉｎとｃｍａｘとのクロックパス用にテーブルを用意する。クロックパストレース部３０２は、現在のゲートの出力端子を「ｏ」として現在のゲートの入力端子を「ｉ」とした場合に、以下のように最小値、最大値のトーナメントを行いながらｃｍｉｎとｃｍａｘとを更新する。
・ｃｍｉｎ［ｏ］＝ｍｉｎ（ｃｍｉｎ［ｉ］）＋１
・ｃｍａｘ［ｏ］＝ｍａｘ（ｃｍａｘ［ｉ］）＋１
また、ｃｍａｘ、ｃｍｉｎのそれぞれにはクロックパスが分岐または合流するような場合に、クロックパストレース部３０２は、通過するゲートの段数の下限と上限の範囲を決定する。
また、クロックパストレース部３０２は、選択されたＦＦマクロについてのクロックパスのゲート段数を特定してもよいし、ブロックに含まれるクロック端子からすべてのＦＦマクロに到達するまで順にトレースしてもよい。
データパストレース部３０３は、到達したＦＦマクロからデータパスのフォワードトレースを行う。上述したように、データパストレース部３０３は、ゲート段数算出部３１１と、送りクロックドメイン記録部３１２と、受けＦＦマクロ内部入力削除部３１３と、を有する。
具体的に、ゲート段数算出部３１１は、例えば、データパスフォワードトレース処理を行うことによりデータパスごとのゲート段数の下限値を算出する。例えば、ゲート段数算出部３１１は、クロックトレースが到達したＦＦを起点として次段のＦＦの入力を終点とするフォワードトレースを行う。
ゲート段数算出部３１１は、データパス用に要素数のテーブルｄｍｉｎ［］を用意する。そして、ゲート段数算出部３１１は、トレース段数の初期値は各ＦＦのクロック端子の段数ｃｍｉｎ［ＣＫ］とする。ゲート段数算出部３１１は、現在のトレースのゲート出力端子を「ｏ」とし、ゲート入力端子を「ｉ」とした場合に、以下のように最小トーナメントを行いながらｄｍｉｎを更新する。
・ｄｍｉｎ［ｏ］＝ｍｉｎ（ｄｍｉｎ［ｉ］）＋１
このフォワードトレースでは、ゲート段数算出部３１１は、ｄｍｉｎとしてパスが分岐または合流するような場合に通過ゲート段数の下限を決定する。
また、送りクロックドメイン記録部３１２は、対象となるＦＦに供給されるクロックの識別情報を記録する。送りクロックドメイン記録部３１２は、例えば、ドメインマーカｓ［ＦＦ出力のネット番号］に対象のクロック番号を記録する。ここで、ゲート段数算出部３１１と送りクロックドメイン記録部３１２との処理の詳細例については、図９に示す。
受けＦＦマクロ内部入力削除部３１３は、トレースが終了した後に、クロックパスのトレースが到達したすべてのＦＦのクロック端子とデータ入力端子とについてレース余裕を算出する。レース余裕は以下式（１）によって算出可能である。以下式（１）におけるＤはデータ入力端子を示し、ＣＫはクロック端子を示す。
レース余裕＝ｄｍｉｎ［Ｄ］−ｃｍａｘ［ＣＫ］・・・（１）
レース余裕は、データパスの中でゲート段数の下限値と、クロックパスの中でデータ段数の上限値と、の差分値である。そのため、レース余裕が正の値であれば、レースは存在しないことを示す。受けＦＦマクロ内部入力削除部３１３は、ＦＦマクロのデータ入力端子に挿入されているディレーゲートをレース余裕以下の段数を上限として削除する。
図４の例では、削除対象ディレーゲートがＦＦマクロｃの場合、データパスについてのゲート段数は、ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］と、ｄｍｉｎ［ｂ］＋ｃｍｉｎ［ＣＫｂ］と、がある。ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］の方が小さいため、受けＦＦマクロ内部入力削除部３１３は、下限値として、ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］を選択する。また、クロックパスの中でデータ段数の上限値は、ｃｍａｘ［ＣＫｃ］である。そのため、ＦＦマクロｃについてのレース余裕ＲＭは、「ｃｍｉｎ［ＣＫａ］＋ｄｍｉｎ［ａ］＋ｄｍｉｎ［ｃ］−ｃｍａｘ［ＣＫｃ］」によって導出される。
つぎに、バックワードトレースを行うような送りＦＦマクロ内部の出力側の冗長ゲートを削除する処理について説明する。
図５は、送りＦＦマクロ内部の出力側ディレーゲート削除例を示す説明図である。クロックパストレース部３０２は、例えば、ブロックに含まれる選択されたＦＦマクロについて、ブロックに含まれるクロック端子からＦＦマクロのクロック端子までの間のクロックパス上のゲート段数の上限値とゲート段数の下限値を特定する。
例えば、ＦＦマクロａについての上限値はｃｍａｘ［ＣＫａ］であり、ＦＦマクロａについての下限値はｃｍｉｎ［ＣＫａ］である。例えば、ＦＦマクロｂについての上限値はｃｍａｘ［ＣＫｂ］であり、ＦＦマクロｂについての下限値はｃｍｉｎ［ＣＫｂ］である。例えば、ＦＦマクロｃについての上限値はｃｍａｘ［ＣＫｃ］であり、ＦＦマクロｃについての下限値はｃｍｉｎ［ＣＫｃ］である。クロックパストレース部３０２によるクロックパスのトレース処理の詳細例については図７に示す。
ゲート段数算出部３２１は、例えば、データパス用にテーブルｄｍｉｎ［］を用意する。ゲート段数算出部３２１は、クロックトレースが到達したＦＦのデータ入力端子を起点として前段のＦＦのデータ出力端子を終点とするバックワードトレースを行う。ゲート段数算出部３２１は、トレース段数の初期値はＦＦのクロック端子とデータ入力端子とする。トレースのゲート出力端子を「ｏ」とし、ファンアウト先の入力端子を「ｉ」とした場合に、以下のように最小トーナメントを行いながらｄｍｉｎを更新する。
・ｄｍｉｎ［ｏ］＝ｍｉｎ（ｄｍｉｎ［ｉ］）＋１
このバックワードトレースでは、ゲート段数算出部３２１は、ｄｍｉｎとしてパスが分岐または合流するような場合に通過ゲート段数の下限を決定する。
また、受けクロックドメイン記録部３２２は、対象となるＦＦに供給されるクロックの識別情報を記録する。受けクロックドメイン記録部３２２は、例えば、ドメインマーカｒ［ＦＦ出力のネット番号］に対象のクロック番号を記録する。ここで、ゲート段数算出部３２１と受けクロックドメイン記録部３２２との処理の詳細例については、図１０に示す。
送りＦＦマクロ内部出力削除部３２３は、トレースが終了した後に、クロックパスのトレースが到達したすべてのＦＦのクロック端子とデータ出力端子とについてレース余裕を算出する。レース余裕は以下式（２）によって算出可能である。以下式（２）におけるＱはデータ出力端子を示し、ＣＫはクロック端子を示す。
レース余裕＝ｄｍｉｎ［Ｑ］−ｃｍａｘ［ＣＫ］・・・（２）
レース余裕は、データパスのうちでゲート段数の下限値と、クロックパスのうちでゲート段数の上限値と、の差分値である。レース余裕が正の値であれば、レースは存在しないことを示す。送りＦＦマクロ内部出力削除部３２３は、ＦＦマクロのデータ入力端子に挿入されているディレーゲートをレース余裕以下の段数を上限として削除する。
図５の例では、削除対象ディレーゲートがＦＦマクロｃの場合、データパスについてのゲート段数は、ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］と、ｄｍｉｎ［ｂ］＋ｃｍｉｎ［ＣＫｂ］と、がある。ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］の方が小さいため、送りＦＦマクロ内部出力削除部３２３は、下限値として、ｄｍｉｎ［ａ］＋ｃｍｉｎ［ＣＫａ］を選択する。また、クロックパスの中でデータ段数の上限値は、ｃｍａｘ［ＣＫｃ］である。そのため、ＦＦマクロｃについてのレース余裕ＲＭは、「ｃｍｉｎ［ＣＫａ］＋ｄｍｉｎ［ａ］＋ｄｍｉｎ［ｃ］−ｃｍａｘ［ＣＫｃ］」によって導出される。
（テストパターン生成装置１００による冗長ディレーゲート削除処理手順例）
図６は、テストパターン生成装置による冗長ディレーゲート削除処理手順例を示すフローチャートである。テストパターン生成装置１００は、ドメインマーカを初期化する（ステップＳ６０１）。例えば、テストパターン生成装置１００は、ｓ［＊］＝｛ｎｉｌ｝、ｒ［＊］＝｛ｎｉｌ｝とする。
つぎに、テストパターン生成装置１００は、未処理のクロックドメインがあるか否かを判断する（ステップＳ６０２）。未処理のクロックドメインがあると判断された場合（ステップＳ６０２：Ｙｅｓ）、テストパターン生成装置１００は、未処理のクロックドメインのいずれかを処理対象に選択する（ステップＳ６０３）。テストパターン生成装置１００は、クロックパスをトレースする（ステップＳ６０４）。
テストパターン生成装置１００は、データパスをフォワードトレースする（ステップＳ６０５）。つぎに、テストパターン生成装置１００は、受けＦＦマクロ内部入力の削除を行う（ステップＳ６０６）。そして、テストパターン生成装置１００は、データパスをバックワードトレースする（ステップＳ６０７）。つづいて、テストパターン生成装置１００は、送りＦＦマクロ内部出力の削除を行い（ステップＳ６０８）、一連の処理を終了する。
ステップＳ６０２において、未処理のクロックドメインがないと判断された場合（ステップＳ６０２：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図７は、図６で示したクロックパスのトレース処理（ステップＳ６０４）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、クロックパス段数テーブルを初期化する（ステップＳ７０１）。ステップＳ７０１では、例えば、テストパターン生成装置１００は、「ｃｍｉｎ［＊］＝∞」、「ｃｍａｘ［＊］＝−∞」とする。つぎに、テストパターン生成装置１００は、「ネット番号＝クロック端子」、「最小段数＝０」、「最大段数＝０」とする（ステップＳ７０２）。テストパターン生成装置１００は、｛ネット番号、最小段数、最大段数｝をスタックにプッシュする（ステップＳ７０３）。
テストパターン生成装置１００は、スタックが空であるか否かを判断する（ステップＳ７０４）。スタックが空でないと判断された場合（ステップＳ７０４：Ｎｏ）、テストパターン生成装置１００は、｛ネット番号、最小段数、最大段数｝をスタックからポップする（ステップＳ７０５）。テストパターン生成装置１００は、最小段数がｃｍｉｎ［ネット番号］であり、かつ最大段数がｃｍａｘ［ネット番号］であるか否かを判断する（ステップＳ７０６）。
最小段数がｃｍｉｎ［ネット番号］であり、かつ最大段数がｃｍａｘ［ネット番号］であると判断された場合（ステップＳ７０６：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ７０４へ戻る。最小段数がｃｍｉｎ［ネット番号］でない、または最大段数がｃｍａｘ［ネット番号］でないと判断された場合（ステップＳ７０６：Ｎｏ）、テストパターン生成装置１００は、「ｃｍｉｎ［ネット番号］＝最小段数」、「ｃｍａｘ［ネット番号］＝最大段数」とする（ステップＳ７０７）。
つぎに、テストパターン生成装置１００は、ネットがＦＦの出力であるか否かを判断する（ステップＳ７０８）。ネットがＦＦの出力であると判断された場合（ステップＳ７０８：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ７０４へ戻る。ネットがＦＦの出力でないと判断された場合（ステップＳ７０８：Ｎｏ）、テストパターン生成装置１００は、ネットがゲート入力であるか否かを判断する（ステップＳ７０９）。ゲート入力とは、ゲートの入力端子である。ネットがゲート入力であるかを判断することは、入力ネットであるかを判断することである。
ネットがゲート入力であると判断された場合（ステップＳ７０９：Ｙｅｓ）、テストパターン生成装置１００は、「ネット番号＝ゲート出力」、「最小段数＝最小段数＋１」、「最大段数＝最大段数＋１」とする（ステップＳ７１０）。テストパターン生成装置１００は、｛ネット番号、最小段数、最大段数｝をスタックにプッシュし（ステップＳ７１１）、ステップＳ７０４へ戻る。一方、ネットがゲート入力でないと判断された場合（ステップＳ７０９：Ｎｏ）、テストパターン生成装置１００は、「最小段数＝ｍｉｎ（ｃｍｉｎ［ｉ］）＋１」、「最大段数＝ｍａｘ（ｃｍａｘ［ｉ］）＋１」とする（ステップＳ７１２）。ステップＳ７１２でのｉはゲートのすべての入力端子である。
テストパターン生成装置１００は、ゲート出力のファンアウトのうち未処理があるか否かを判断する（ステップＳ７１３）。ゲート出力のファンアウトのうち未処理があると判断された場合（ステップＳ７１３：Ｙｅｓ）、テストパターン生成装置１００は、未処理のファンアウトから１つのファンアウトｆを選択する（ステップＳ７１４）。そして、テストパターン生成装置１００は、｛ｆ、最小段数、最大段数｝をスタックにプッシュし（ステップＳ７１５）、ステップＳ７１３へ戻る。
ゲート出力のファンアウトのうち未処理がないと判断された場合（ステップＳ７１３：Ｎｏ）、テストパターン生成装置１００は、ステップＳ７０４へ戻る。また、ステップＳ７０４において、スタックが空であると判断された場合（ステップＳ７０４：Ｙｅｓ）、テストパターン生成装置１００は、一連の処理を終了する。
図８は、クロックパス上のネットのフォワードトレース例を示す説明図である。図８には、クロックパス上にあるＧ１，Ｇ２，Ｇ３を例に示す。例えば、図８では、ネットａ→ｃ→ｄ→ｆの順でフォワードトレースされる様子を示す。まず、開始状態としてネットａがスタックにプッシュされる。
つぎに、テストパターン生成装置１００は、スタックからネットａをポップすることによりネットａを処理対象ネットとする。ネットａは２入力ＡＮＤのゲートＧ１の入力ネットである。そのため、テストパターン生成装置１００は、ゲートＧ１の出力のネットｃをネット番号に設定してスタックにプッシュする。そして、テストパターン生成装置１００は、最小段数と最大段数を１加算してスタックにプッシュする。
つぎに、テストパターン生成装置１００は、スタックからネットｃをポップすることによりネットｃを処理対象ネットとする。ネットｃは２入力ＡＮＤのゲートＧ１の出力ネットである。そのため、テストパターン生成装置１００は、ネットｃのファンアウト先であるゲートＧ２の入力ネットｄと、ゲートＧ３の入力ネットｇをスタックにプッシュする。また、テストパターン生成装置１００は、ゲートＧ１のすべての入力端子ａ，ｂを参照する。そして、テストパターン生成装置１００は、最小段数と最大段数を計算してスタックにプッシュする。
つぎに、テストパターン生成装置１００は、スタックからネットｄをポップすることにより処理対象ネットとする。テストパターン生成装置１００は、ネットｄについてネットａと同様の処理を行う。
つぎに、テストパターン生成装置１００は、スタックからネットｇをポップすることにより処理対象ネットとする。テストパターン生成装置１００は、ネットｇについてネットａと同様の処理を行う。このようにしてフォワードトレースが行われる。
図９は、図６で示したデータパスフォワード処理（ステップＳ６０５）の詳細な説明を示すフローチャートである。テストパターン生成装置１００は、データパス段数テーブルを初期化する（ステップＳ９０１）。ステップＳ９０１では、例えば、テストパターン生成装置１００は「ｄｍｉｎ［＊］＝∞」とする。
テストパターン生成装置１００は、クロックパスの到達したＦＦについて、「ネット番号＝ＦＦの出力」、「最小段数＝ｃｍｉｎ［ＦＦのｃｋ］」、｛ネット番号、最小段数｝をスタックにプッシュする（ステップＳ９０２）。そして、テストパターン生成装置１００は、スタックが空であるか否かを判断する（ステップＳ９０３）。スタックが空でないと判断された場合（ステップＳ９０３：Ｎｏ）、テストパターン生成装置１００は、｛ネット番号、最小段数｝をスタックからポップする（ステップＳ９０４）。
テストパターン生成装置１００は、ドメインマーカｓ［ネット番号］にクロック番号を追加する（ステップＳ９０５）。テストパターン生成装置１００は、最小段数がｄｍｉｎ［ネット番号］であるか否かを判断する（ステップＳ９０６）。最小段数がｄｍｉｎ［ネット番号］であると判断された場合（ステップＳ９０６：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ９０３へ戻る。最小段数がｄｍｉｎ［ネット番号］でないと判断された場合（ステップＳ９０６：Ｎｏ）、テストパターン生成装置１００は、「ｄｍｉｎ［ネット番号］＝最小段数」とする（ステップＳ９０７）。
テストパターン生成装置１００は、ネットがＦＦの入力であるか否かを判断する（ステップＳ９０８）。ネットがＦＦの入力であると判断された場合（ステップＳ９０８：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ９０３へ戻る。ネットがＦＦの入力でないと判断された場合（ステップＳ９０８：Ｎｏ）、テストパターン生成装置１００は、ネットがゲート入力であるか否かを判断する（ステップＳ９０９）。ネットがゲート入力であると判断された場合（ステップＳ９０９：Ｙｅｓ）、テストパターン生成装置１００は、「ネット番号＝ゲート出力」、「最小段数＝最小段数＋１」とする（ステップＳ９１０）。テストパターン生成装置１００は、｛ネット番号、最小段数｝をスタックにプッシュし（ステップＳ９１１）、ステップＳ９０３へ戻る。
一方、ネットがゲート入力でないと判断された場合（ステップＳ９０９：Ｎｏ）、テストパターン生成装置１００は、「最小段数＝ｍｉｎ（ｄｍｉｎ［ｉ］）＋１」とする（ステップＳ９１２）。ステップＳ９１２におけるｉは、ゲートのすべての入力端子である。つぎに、テストパターン生成装置１００は、ゲート出力のファンアウトのうち未処理があるか否かを判断する（ステップＳ９１３）。
ゲート出力のファンアウトのうち未処理がないと判断された場合（ステップＳ９１３：Ｎｏ）、テストパターン生成装置１００は、ステップＳ９０３へ戻る。ゲート出力のファンアウトのうち未処理があると判断された場合（ステップＳ９１３：Ｙｅｓ）、テストパターン生成装置１００は、未処理のファンアウトから１つのファンアウトｆを選択する（ステップＳ９１４）。テストパターン生成装置１００は、｛ｆ、最小段数｝をスタックにプッシュし（ステップＳ９１５）、ステップＳ９１３へ戻る。
また、ステップＳ９０３において、スタックが空であると判断された場合（ステップＳ９０３：Ｙｅｓ）、テストパターン生成装置１００は、一連の処理を終了する。
図１０は、図６で示したデータパスバックワード処理（ステップＳ６０７）の詳細な説明を示すフローチャートである。テストパターン生成装置１００は、データパス段数テーブルの初期化を行う（ステップＳ１００１）。ステップＳ１００１において、テストパターン生成装置１００は、例えば、「ｄｍｉｎ［＊］＝∞」とする。つぎに、テストパターン生成装置１００は、クロックパスの到達したＦＦについて、「ネット番号＝ＦＦの入力」、「最小段数＝−ｃｍｉｎ［ＦＦのＣＫ］」、｛ネット番号、最小段数｝をスタックにプッシュする（ステップＳ１００２）。
テストパターン生成装置１００は、スタックが空であるか否かを判断する（ステップＳ１００３）。スタックが空でないと判断された場合（ステップＳ１００３：Ｎｏ）、テストパターン生成装置１００は、｛ネット番号、最小段数｝をスタックからポップする（ステップＳ１００４）。テストパターン生成装置１００は、ドメインマーカｒ［ネット番号］にクロック番号を追加する（ステップＳ１００５）。
つぎに、テストパターン生成装置１００は、最小段数がｄｍｉｎ［ネット番号］であるか否かを判断する（ステップＳ１００６）。最小段数がｄｍｉｎ［ネット番号］であると判断された場合（ステップＳ１００６：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ１００３へ戻る。最小段数がｄｍｉｎ［ネット番号］でないと判断された場合（ステップＳ１００６：Ｎｏ）、テストパターン生成装置１００は、「ｄｍｉｎ［ネット番号］＝最小段数」とする（ステップＳ１００７）。
つぎに、テストパターン生成装置１００は、ネットがＦＦの出力であるか否かを判断する（ステップＳ１００８）。ネットがＦＦの出力であると判断された場合（ステップＳ１００８：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ１００３へ戻る。一方、ネットがＦＦの出力でないと判断された場合（ステップＳ１００８：Ｎｏ）、テストパターン生成装置１００は、ネットがゲート入力であるか否かを判断する（ステップＳ１００９）。ネットがゲート入力であると判断された場合（ステップＳ１００９：Ｙｅｓ）、テストパターン生成装置１００は、「ネット番号＝ドライバネット」、「最小段数＝最小段数＋１」とする（ステップＳ１０１０）。テストパターン生成装置１００は、｛ネット番号、最小段数｝をスタックにプッシュし（ステップＳ１０１１）、ステップＳ１００３へ戻る。
一方、ネットがゲート入力でないと判断された場合（ステップＳ１００９：Ｎｏ）、テストパターン生成装置１００は、「最小段数＝ｍｉｎ（ｄｍｉｎ［ｆ］）＋１」とする（ステップＳ１０１２）。ステップＳ１０１２におけるｆは、ゲート出力のすべてのファンアウト先である。つぎに、テストパターン生成装置１００は、ゲートの入力ネットのうち未処理のネットがあるか否かを判断する（ステップＳ１０１３）。
ゲートの入力ネットのうち未処理のネットがあると判断された場合（ステップＳ１０１３：Ｙｅｓ）、テストパターン生成装置１００は、未処理の入力ネットから１つの入力ネットｉを選択する（ステップＳ１０１４）。テストパターン生成装置１００は、｛ｉ、最小段数｝をスタックにプッシュし（ステップＳ１０１５）、ステップＳ１０１３へ戻る。
一方、ゲートの入力ネットのうち未処理のネットがないと判断された場合（ステップＳ１０１３：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１００３に戻る。ステップＳ１００３において、スタックが空であると判断された場合（ステップＳ１００３：Ｙｅｓ）、テストパターン生成装置１００は、一連の処理を終了する。
図１１は、ドライバネットとゲートの入力例を示す説明図である。ステップＳ１００９においてネットがゲート入力であると判断された場合に、ステップＳ１０１０において「ネット番号＝ドライバネット」とする際のドライバネットとは、レシーバである入力ネットをドライブするネットであるため、前段の出力ネットである。
また、ステップＳ１００９においてネットがゲート入力でないと判断された場合とは、すなわち、ネットがゲート出力であると判断された場合である。この場合に、ステップＳ１０１３においてゲートの入力ネットのうち未処理のネットがあるか否かを判断する際のゲートの入力ネットについて説明する。ネットｃが着目するゲート出力の場合、ネットｃのゲートであるＧ１の入力ネットであるａとｂが入力ネットである。
例えば、テストパターン生成装置１００は、ネットｃが着目するゲート出力の場合、ネットｃのファンアウト先であるネットｄ，ｇのｄｍｉｎを用いてネットｃでの最小段数を算出する。そして、テストパターン生成装置１００は、算出した最小段数ｄｍｉｎ［ｃ］と、ネットｃのゲートであるＧ１の入力ネットであるａとｂとを共に｛ａ、ｄｍｉｎ［ｃ］｝、｛ｂ，ｄｍｉｎ［ｃ］｝のようにスタックにプッシュする。
図１２は、図６で示した受けＦＦマクロ内部入力削除処理（ステップＳ６０６）の詳細な説明を示すフローチャートである。テストパターン生成装置１００は、回路内部のＦＦのうち未処理のＦＦがあるか否かを判断する（ステップＳ１２０１）。回路内部のＦＦのうち未処理のＦＦがあると判断された場合（ステップＳ１２０１：Ｙｅｓ）、テストパターン生成装置１００は、未処理のＦＦから１つのＦＦを処理対象として選択する（ステップＳ１２０２）。
つぎに、テストパターン生成装置１００は、ＦＦのＤ端子にトレースが到達したか否かを判断する（ステップＳ１２０３）。ＦＦのＤ端子にトレースが到達していないと判断された場合（ステップＳ１２０３：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１２０１へ戻る。一方、ＦＦのＤ端子にトレースが到達したと判断された場合（ステップＳ１２０３：Ｙｅｓ）、テストパターン生成装置１００は、［レース余裕＝ｄｍｉｎ［Ｄ］−ｃｍａｘ［ＣＫ］」とする（ステップＳ１２０４）。
そして、テストパターン生成装置１００は、「削除開始ネット＝ＦＦマクロのＤ入力」とする（ステップＳ１２０５）。テストパターン生成装置１００は、「削除終了の候補ネット＝削除開始ネット」とする（ステップＳ１２０６）。テストパターン生成装置１００は、「削除段数＝０」とする（ステップＳ１２０７）。テストパターン生成装置１００は、削除終了の候補ゲートがバッファであるか否かを判断する（ステップＳ１２０８）。削除終了の候補ゲートがバッファであると判断された場合（ステップＳ１２０８：Ｙｅｓ）、テストパターン生成装置１００は、削除候補のゲートを１段フォワードトレースし、「削除段数＋＝２」とする（ステップＳ１２０９）。削除段数を２加算するのは、入力分と出力分である。
そして、テストパターン生成装置１００は、削除段数＞レース余裕であるか否かを判断する（ステップＳ１２１０）。削除段数＞レース余裕であると判断された場合（ステップＳ１２１０：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ１２０８へ戻る。削除段数＞レース余裕でないと判断された場合（ステップＳ１２１０：Ｎｏ）、テストパターン生成装置１００は、削除終了の候補ネット＝削除候補のゲート出力とし（ステップＳ１２１１）、ステップＳ１２０８へ戻る。
一方、ステップＳ１２０８において、削除終了の候補ゲートがバッファでないと判断された場合（ステップＳ１２０８：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１２１２へ移行する。テストパターン生成装置１００は、削除開始ネットが削除終了の候補ネットと一致しないか否かを判断する（ステップＳ１２１２）。削除開始ネットが削除終了の候補ネットと一致しないと判断された場合（ステップＳ１２１２：Ｙｅｓ）、テストパターン生成装置１００は、削除開始〜終了候補のディレーゲートを削除し（ステップＳ１２１３）、ステップＳ１２０１へ戻る。削除開始ネットが削除終了の候補ネットと一致すると判断された場合（ステップＳ１２１２：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１２０１へ戻る。
ステップＳ１２０１において、回路内部のＦＦのうち未処理のＦＦがないと判断された場合（ステップＳ１２０１：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図１３は、図６で示した送りＦＦマクロ内部出力削除処理（ステップＳ６０８）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、回路内部のＦＦのうち未処理のＦＦがあるか否かを判断する（ステップＳ１３０１）。回路内部のＦＦのうち未処理のＦＦがあると判断された場合（ステップＳ１３０１：Ｙｅｓ）、テストパターン生成装置１００は、未処理のＦＦから１つのＦＦを処理対象として選択する（ステップＳ１３０２）。
テストパターン生成装置１００は、ＦＦのＱ端子にトレースが到達したか否かを判断する（ステップＳ１３０３）。ＦＦのＱ端子にトレースが到達していないと判断された場合（ステップＳ１３０３：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１３０１へ戻る。ＦＦのＱ端子にトレースが到達したと判断された場合（ステップＳ１３０３：Ｙｅｓ）、テストパターン生成装置１００は、「レース余裕＝ｄｍｉｎ［Ｑ］−ｃｍｉｎ［ＣＫ］」とする（ステップＳ１３０４）。テストパターン生成装置１００は、削除開始ネット＝ＦＦマクロのＱ出力とする（ステップＳ１３０５）。
つぎに、テストパターン生成装置１００は、「削除終了の候補ネット＝削除開始ネット」とする（ステップＳ１３０６）。テストパターン生成装置１００は、「削除段数＝０」とする（ステップＳ１３０７）。テストパターン生成装置１００は、削除終了の候補ゲートがバッファであるか否かを判断する（ステップＳ１３０８）。削除終了の候補ゲートがバッファであると判断された場合（ステップＳ１３０８：Ｙｅｓ）、テストパターン生成装置１００は、削除候補のゲートを１段バックワードトレースし、「削除段数＋＝２」とする（ステップＳ１３０９）。削除段数に２を加算するのは、入力分と出力分である。
つぎに、テストパターン生成装置１００は、削除段数＞レース余裕であるか否かを判断する（ステップＳ１３１０）。削除段数＞レース余裕であると判断された場合（ステップＳ１３１０：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ１３０８へ戻る。削除段数＞レース余裕でないと判断された場合（ステップＳ１３１０：Ｎｏ）、テストパターン生成装置１００は、「削除終了の候補ネット＝削除候補のゲート入力」とし（ステップＳ１３１１）、ステップＳ１３０８へ戻る。
一方、ステップＳ１３０８において、削除終了の候補ゲートがバッファでないと判断された場合（ステップＳ１３０８：Ｎｏ）、テストパターン生成装置１００は、削除開始ネットが削除終了の候補ネットと一致していないかを判断する（ステップＳ１３１２）。削除開始ネットが削除終了の候補ネットと一致していないと判断された場合（ステップＳ１３１２：Ｙｅｓ）、テストパターン生成装置１００は、削除開始〜終了候補のディレーゲートを削除し（ステップＳ１３１３）、ステップＳ１３０１へ戻る。
また、削除開始ネットが削除終了の候補ネットと一致していると判断された場合（ステップＳ１３１２：Ｎｏ）、テストパターン生成装置１００は、ステップＳ１３０１へ戻る。また、ステップＳ１３０１において、回路内部のＦＦのうち未処理のＦＦがないと判断された場合（ステップＳ１３０１：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
＜ブロック分割＞
つぎに、対象回路に含まれるブロックを分割する例について説明する。従来技術、複数のブロックを分割して複数のコンピュータに割り当てて並列処理によってテストパターン生成を行う場合がある。並列処理では処理時間を短縮するために各コンピュータの負荷を均等にする必要がある。近年、Ｉ／Ｏ部やＲＡＭなどの高機能化に伴う規模の増大のため、Ｉ／Ｏ部やＲＡＭがＣＰＵと同程度の規模を持つこともある。そのため、ゲート数によって複数のブロックを分割する場合に、第１の分割回路にはＩ／Ｏ部のみが割り当てられ、第２の分割回路にはＣＰＵのみが割り当てられるような、機能や構成が同じブロックが特定の分割回路に偏在する場合があるという問題点がある。
特定の分割回路に機能や構成が同じブロックが偏在する場合、クロックドメインなどが分割回路間で異なる可能性がある。複数の分割回路を並列処理しても、分割回路に含まれるブロックのクロックドメイン等の特性が異なると動作する回路部分も異なってくるため、分割回路間でシミュレーション等の処理時間にも差がつくことなる。従って最も処理の遅い分割回路の終了待ちによる並列処理全体の効率低下が発生することになる。
そこで、本実施の形態では、テストパターン生成装置１００は、規模および機能に関する特徴量の近さに基づきブロックをグループ化し、分割数とグループのブロック数の比率に基づき各ブロックを分割回路に割り当てる。これにより、分割回路間の特性の均等化を図ることができる。
また、従来技術では分割回路の規模の見積もりを、分割回路に含むと選択したブロックの規模を足し合わせることで行うことがある。しかしながら実際の回路分割では論理的に完結させる必要があり、分割回路に含めると選択したブロック以外であっても、クロック系など制御回路や隣接するブロックからの接続は分割回路に含める必要がある。そのためブロックによっては、この接続部分が見積もりからの誤差となり、分割回路規模等の特性に偏り生じるという問題点がある。
そこで、本実施の形態では、テストパターン生成装置１００は、ブロックの観測点であるスキャンＦＦから前段のスキャンＦＦまでの接続範囲をバックトレースして求めたブロック間接続のネット数の合計値が最小となるようにグループに含まれるブロックを割り当てる。これにより、分割後の回路規模の見積精度の向上を図ることができる。これにより、より分割回路間の特性の均等化を図ることができる。
まず、取得部３０４は、例えば、設計の対象回路内のゲートやゲート間の接続関係を示す回路情報を取得する。ここでの回路情報は、回路情報３４２とするが、回路情報３４１であってもよい。回路情報３４２はネットリストである。ネットリストは、例えば、ゲートレベルなどによって記述される。取得形式としては、例えば、取得部３０４は、ネットワーク２０９を介して他の装置から回路情報３４２を取得してもよい。または、例えば、取得部３０４は、ＲＡＭ２０３、ＲＯＭ２０２、ディスク２０５などの記憶装置から回路情報３４２を読み出すことによって回路情報３４２を取得してもよい。
また、取得部３０４は、対象回路に含まれる複数のブロックの各々について、回路情報３４２に基づくブロックのサイズに関する第１特徴量と、回路情報３４２に基づくブロックの機能に関する第２特徴量と、を取得する。第１特徴量は、例えば、ネット数である。第２特徴量は、例えば、スキャンＦＦの数である。
また、取得部３０４は、ブロックの各々について、回路情報３４２に基づくブロックに含まれるＦＦから、ＦＦの前段にあるＦＦまでの間のパスに関する第３特徴量を取得する。第３特徴量は、例えば、トレースネット数である。トレースネット数とは、ブロックの観測点であるスキャンＦＦから前段のスキャンＦＦまでの接続範囲をバックトレースして求めたブロック間接続のネット数である。
具体的に、取得部３０４は、例えば、ブロックの各々について、階層名、ネット数、スキャンＦＦ数、トレースネット数を示すブロック情報を取得する。ブロック情報は、例えば、以下の通りである。
・ブロック情報｛ネット数、スキャンＦＦ数、トレースネット数｝
取得形式としては、例えば、取得部３０４は、ネットワーク２０９を介して他の装置から取得してもよい。または、例えば、取得部３０４は、ＲＡＭ２０３、ＲＯＭ２０２、ディスク２０５などの記憶装置からブロック情報を読み出すことによってブロック情報を取得してもよい。または、例えば、取得部３０４は、回路情報３４２に基づいて、ブロックの各々について、ネット数、スキャンＦＦ数、トレースネット数を抽出してもよい。
図１４は、ブロック情報の特徴抽出例を示す説明図である。対象回路１４００には、複数のブロック１４０１−１〜３０が含まれる。例えばブロック１４０１−１は、ネット数がＮａであり、スキャンＦＦ数がＳａである。また、例えば、ブロック１４０１−４は、ネット数がＮａであり、スキャンＦＦ数がＳａである。また、例えば、ブロック１４０１−６は、ネット数がＮｄであり、スキャンＦＦ数がＳｄである。また、例えばブロック１４０１−７は、ネット数がＮｂであり、スキャンＦＦ数がＳｂである。また、例えばブロック１４０１−２７は、ネット数がＮｃであり、スキャンＦＦ数がＳｃである。また、ネット数については、Ｎａ＞Ｎｂ＞Ｎｃ＞Ｎｄの関係とする。スキャンＦＦ数については、Ｓａ≠Ｓｂ≠Ｓｃ≠Ｓｄの関係とする。理解の容易化のために、図１４の下側では、ネット数とスキャンＦＦ数が同一のブロック１４０１に同一のハッチングを付してある。
分類部３０５は、第１特徴量が第１所定範囲内であり、第２特徴量が第２所定範囲内であるブロック１４０１同士を同一のグループとなるように、複数のブロック１４０１を、複数のブロック１４０１の数より少ない複数のグループに分類する。第１所定範囲と第２所定範囲は利用者によって予め定められる。分類部３０５は、例えば、複数のブロック１４０１を、ブロック情報に含まれるネット数の差が第１所定範囲内であり、かつスキャンＦＦ数の差が第２所定範囲内であるブロック情報を同一のグループとなるように複数のブロック１４０１を分類する。指定範囲については、設計者やテストパターン作成者などの利用者によって予め指定される範囲である。また、分類部３０５は、各特徴量に差がないブロック情報を同一のグループとなるように分類してもよい。また、分類部３０５による詳細なグルーピングについては、図２２と図２３に示す。各グループを示すグループ情報は例えば以下の通りである。
・グループ情報｛分類されたブロック情報，分類されたブロック情報｝
図１４を例に挙げると、分類部３０５は、ブロック１４０１−１とブロック１４０１−２とブロック１４０１−４とブロック１４０１−５とを同一のグループに分類する。他のグループについては図１５に分類結果を示す。
割当部３０６は、複数のグループの各々について、グループに含まれるブロック１４０１の数と分割数との比率に基づいて、グループに含まれるブロック１４０１の各々を分割数の複数の分割回路１６００のうちのいずれかに割り当てる。また、割当部３０６は、グループの各々について、グループに含まれるブロック１４０１の各々を比率に応じた間隔と、複数の分割回路の各々に付された異なる順序と、によってグループに含まれるブロックを割り当てる。また、比率に応じた間隔は分配間隔とも称する。割当部３０６は、分配間隔と順序とによって複数の分割回路に割り当てた場合における複数の分割回路の各々についての第３特徴量の合計値が最小となるように、グループに含まれるブロックを割り当てる。本実施の形態では、割り当てることを分配とも称する。上述したように、第３特徴量はトレースネット数である。割当部３０６は、具体的に、分配間隔決定部３３１と、分配先決定部３３２と、を有する。
分配間隔決定部３３１は、例えば、グループに含まれるブロック１４０１の数と分割数との比率に基づいて、グループに含まれるブロック１４０１を複数の分割回路１６００を並べた場合に等間隔に分配するための分配間隔を決定する。分割数については、例えば、設計者やテストパターン作成者などの利用者によって入力装置２０７を介して指定される。
例えば分割数が１６であり、グループに含まれるブロック１４０１の数が２，４，８，１６のように、分割数に対してグループに含まれるブロック１４０１の数が端数を持たない場合について説明する。分配間隔決定部３３１は、分配間隔を分割数／グループに含まれるブロック１４０１の数とする。これにより、グループ内に含まれるブロック１４０１が分割回路１６００に偏在することによって分割回路１６００間の機能に偏りが発生することを抑制できる。分割回路１６００間の機能の偏りを抑制することによって複数の分割回路１６００について並列処理によってテストパターン生成を行った場合に、テストパターン生成時間の偏りを抑制でき、テストパターン生成時間の短縮を図ることができる。
また、割当部３０６は、例えば、分割数をグループに含まれるブロック１４０１の数で割った時に余りがある場合、グループに含まれるブロック１４０１のうちの余りの数のブロック１４０１を複数の分割回路１６００と異なる分割回路１６００に割り当てる。本実施の形態では、分割数に対してグループに含まれるブロック１４０１の数が端数を持つ場合には、余剰分についての分割回路１６００を用意することとする。分割数に対してグループに含まれるブロック１４０１の数が端数を持つ場合、分配間隔決定部３３１は、グループに含まれるブロック１４０１の数から余剰分を引いた数を新たにブロック１４０１の数とする。分配間隔決定部３３１は、ブロック１４０１の数と分割数との最大公約数が１でない場合には、分配間隔を分割数／ｇに決定する。分配間隔決定部３３１は、ブロック１４０１の数と分割数との最大公約数が１である場合には、さらにブロック１４０１を余剰分とする処理と、最大公約数が１である場合における分配間隔を決定する処理と、を繰り返す。分配間隔決定部３３１による詳細な処理例は、後述する図２４に示す。
図１５は、分類結果と分配間隔例を示す説明図である。図１５（１）には分類結果例を示し、図１５（２）には分配間隔例を示す。
図１５（１）に示すように、グループ１５０１−１は、ブロック１４０１−１と、ブロック１４０１−２と、ブロック１４０１−４と、ブロック１４０１−５とを含む。図１５（１）に示すように、グループ１５０１−２は、ブロック１４０１−７〜ブロック１４０１−２２を含む。図１５（１）に示すように、グループ１５０１−３は、ブロック１４０１−２３〜ブロック１４０１−３０を含む。図１５（１）に示すように、グループ１５０１−４は、ブロック１４０１−３とブロック１４０１−６とを含む。
図１５（２）に示すように、グループ１５０１−１に含まれるブロック１４０１の数は４であり、分割数が１６であるため、グループ１５０１−１の分配間隔は４である。図１５（２）に示すように、グループ１５０１−２に含まれるブロック１４０１の数は１６であり、分割数が１６であるため、グループ１５０１−２の分配間隔は１である。
図１５（２）に示すように、グループ１５０１−３に含まれるブロック１４０１の数は８であり、分割数が１６であるため、グループ１５０１−３の分配間隔は２である。図１５（２）に示すように、グループ１５０１−４に含まれるブロック１４０１の数は２であり、分割数が１６であるため、グループ１５０１−４の分配間隔は８である。
分配先決定部３３２は、複数のグループ１５０１から未分配のグループ１５０１を１つ選択する。ここでは、複数の分割回路１６００の各々に順序があることとする。そして、分配先決定部３３２は、選択したグループ１５０１に含まれるブロック１４０１を決定された分配間隔ごとに複数の分割回路１６００に分配させた場合に、分割回路１６００の各々の第３特徴量の合計値が最も小さくなる分配先を決定する。分配先決定部３３２は、分配先の決定結果を回路分割リスト３４５としてＲＯＭ２０２、ＲＡＭ２０３、ディスク２０５などの記憶装置に記憶する。
図１６は、分配例を示す説明図である。図１６（ａ）には、グループ１５０１−１に含まれるブロック１４０１の分配例を示す。図１６（ｂ）には、グループ１５０１−２に含まれるブロック１４０１の分配例を示す。図１６（ｃ）には、グループ１５０１−３に含まれるブロック１４０１の分配例を示す。図１６（ｄ）には、グループ１５０１−４に含まれるブロック１４０１の分配例を示す。
まず、グループ１５０１−１については、分配間隔が４であるため、分配先は、（１，５，９，１３）、（２，６，１０，１４）、（３，７，１１，１５）、（４，８，１２，１６）である。なお、（ ）内の各数値は分割回路１６００を識別する番号であり、この番号によって複数の分割回路１６００は順序付けられてある。
分配先決定部３３２は、例えば、各分配先に分配させた場合におけるトレースネット数の合計値を算出する。トレースネット数の合計値は累積トレースネット数とも称する。グループ１５０１−１を選択した段階では、いずれも分配されていないため、いずれの分配先に分配しても累積トレースネット数は同じである。そのため、図１６（ａ）に示すように、分配先決定部３３２は、グループ１５０１−１について分配先を（１，５，９，１３）に決定する。
つぎに、図１６（ｂ）に示すように、分配先決定部３３２は、グループ１５０１−２の分配間隔は１６であるため、グループ１５０１に含まれるブロック１４０１をすべての分割回路１６００に均等に割り当てる。
グループ１５０１−３については、分配間隔は２であるため、分配先は（１，３，５，７，９，１１，１３，１５）、（２，４，６，８，１０，１２，１４，１６）である。（１，５，９，１３）にすでにグループ１５０１−１に含まれるブロック１４０１が分配されているため、累積トレースネット数が多くなる。そのため、図１６（ｃ）に示すように、分配先決定部３３２は、グループ１５０１−３についての分配先を（２，４，６，８，１０，１２，１４，１６）に決定する。
グループ１５０１−４については、分配間隔は８であるため、分配先は（１，９）、（２，１０）、（３，１１）、（４，１２）、（５，１３）、（６，１４）、（７，１５）、（８，１６）である。累積トレースネット数が最も小さくなる分配先は（３，１１）、（７，１５）である。そのため、図１６（ｄ）に示すように、分配先決定部３３２は、グループ１５０１−４についての分配先を（３，１１）に決定する。
つぎに、より具体的な例を用いて各処理について説明する。
図１７は、ブロックのグルーピング例を示す説明図である。まず、図１７（ａ）に示すように、取得部３０４は、ブロック１７００の各々について、ネット数と、スキャンＦＦ数と、トレースネット数との３つの特徴量を有するブロック情報を取得する。
つぎに、図１７（ｂ）に示すように、分類部３０５は、ネット数を第１キーとし、スキャンＦＦ数を第２キーとして第１キーが第２キーより優先されるようにブロック情報を降順にソートする。これにより、特徴量の等価や類似判定の容易化を図ることができる。
そして、図１７（ｃ）に示すように、分類部３０５は、ソートされたブロック情報を上位から順に選択する。そして、分類部３０５は、ネット数が所定範囲内であり、スキャンＦＦ数が所定範囲内であるブロック１７００を同一のグループ１７０１に分類する。グループ１７０１−１はブロック１７００−７〜ブロック１７００−１０を有する。グループ１７０１−２はブロック１７００−１〜ブロック１７００−４を有する。グループ１７０１−３はブロック１７００−５とブロック１７００−６とを有する。
図１８は、分配間隔決定方法のコード例を示す説明図である。コード１８００には、分割数が１６の場合における分配間隔の決定処理がコーディングされてある。コード１８００中に記述の「ｗｉｄｔｈ」が分配間隔である。コード１８００中に記述の「ｅｘｔｒａ」が余剰数である。コード１８００に示すように、分配間隔決定部３３１は、グループ１７０１に含まれるブロック１７００のうち余剰分のブロック１７００については余剰の分割回路に分配させるように分配間隔を決定する。分配間隔決定部３３１は、分配間隔を、分割数とグループ１７０１内のブロック１７００の数との最大公約数に基づいて決定する。
図１９は、分配間隔の決定例を示す説明図である。ここでは分割数が１６の場合の例について説明する。図１９（１）には、グループ１７０１に含まれるブロック１７００数に応じた分配間隔と余剰数とを示す。「ｗｉｄｔｈ」が分配間隔であり、「ｅｘｔｒａ」が余剰数であり、「［数値］」が分配先である。［１７］は余剰分の分割回路１９００である。
図１９（２）には、グループ１７０１内のブロック１７００数に応じた分配間隔と分配例を示す。例えば、グループ１７０１内のブロック１７００数が１であると、分配間隔が０であり、余剰数が１であるため、ブロック１７００の分配先は余剰の分割回路１９００−１７となる。
また、例えばグループ１７０１内のブロック１７００数が５であると、分配間隔が４であり、余剰数が１となる。そのため、ブロック１７００の分配先は分割回路１９００−１、分割回路１９００−５、分割回路１９００−９、分割回路１９００−１３、余剰の分割回路１９００−１７となる。
また、図１７に示したグループ１７０１−１とグループ１７０１−２との分配間隔は４であり、グループ１７０１−３の分配間隔は８となる。
図２０は、ブロック分配例を示す説明図である。つぎに、分配先決定部３３２は、ブロック１７００の分配間隔に基づいてグループ１７０１に含まれるブロック１７００を複数の分割回路１９００に分配させた場合に分割回路１９００に分配されたブロック１７００のトレースネット数の合計値を導出する。これにより、分割回路１９００間の回路規模の均等化を図ることができる。図２０においてブロック１７００とグループ１７０１との符号を省略する。
図２０（ａ）に示すように、まだいずれのグループ１７０１についても分割回路１９００にブロック１７００を分配していないため、分割回路１９００ごとの累積トレースネット数には０が設定されてある。
まず、グループ１７０１−１に含まれるブロック１７００を複数の分割回路１９００に分配させた場合、分配間隔が４であるため、分配先は（１，５，９，１３）、（２，６，１０，１４）、（３，７，１１，１５）となる。いずれの分配先であっても累積トレースネット数は同じであるため、図２０（ｂ）に示すように、分配先決定部３３２は、グループ１７０１−１に含まれるブロック１７００の分配先を（１，５，９，１３）に決定する。
つぎに、グループ１７０１−２の分配間隔は４であるため、グループ１７０１−２についても分配先は、グループ１７０１−１と同様に、（１，５，９，１３）、（２，６，１０，１４）、（３，７，１１，１５）となる。つぎに、図２０（ｃ）に示すように、分配先決定部３３２は、グループ１７０１−２に含まれるブロック１７００を分配させた場合における累積トレースネット数を算出する。
グループ１７０１−２についての分配先を（１，５，９，１３）とした場合の（１，５，９，１３）の累積トレースネット数は、（２２，６３７，１４５， ２２，６３７，９７３， ２２，６１６，１５２， ２２，６１８，３１４）である。グループ１７０１−２についての分配先を（２，６，１０，１４）とした場合の（２，６，１０，１４）の累積トレースネット数は、（１０，１１０，４１０， １０，１１０，６４３， １０，０９８，６４７， １０，０９９，８７０）である。グループ１７０１−２についての分配先を（３，７，１１，１５）とした場合の（３，７，１１，１５）の累積トレースネット数は、（１０，１１０，４１０， １０，１１０，６４３， １０，０９８，６４７， １０，０９９，８７０）である。
（２，６，１０，１４）と（３，７，１１，１５）との場合に累積トレースネット数が小さくなるため、分配先決定部３３２は、グループ１７０１−２についての分配先を（２，６，１０，１４）に決定する。図２０（ｃ）には、グループ１７０１−２に含まれるブロック１７００を（２，６，１０，１４）に分配させた場合の累積トレースネット数を示す。
グループ１７０１−３についても同様に、分配先決定部３３２は分配先を（３，１１）に決定する。図２０（ｄ）にはグループ１７０１−３に含まれるブロック１７００を（３，１１）に分配させた場合の累積トレースネット数を示す。以上のように、分配先決定部３３２は、すべてのグループ１７０１に対してグループ１７０１に含まれるブロック１７００の分配先を決定する。
（テストパターン生成装置１００による回路分割リスト生成処理手順例）
図２１は、テストパターン生成装置による回路分割リスト生成処理手順例を示すフローチャートである。まず、テストパターン生成装置１００は、ブロック情報を取得する（ステップＳ２１０１）。つぎに、テストパターン生成装置１００は、ブロック情報のソート処理を行う（ステップＳ２１０２）。そして、テストパターン生成装置１００は、ブロック情報のグループ認識処理を行う（ステップＳ２１０３）。
つづいて、テストパターン生成装置１００は、未処理のグループがあるか否かを判断する（ステップＳ２１０４）。未処理のグループがあると判断された場合（ステップＳ２１０４：Ｙｅｓ）、テストパターン生成装置１００は、未処理のグループからいずれかのグループを処理対象として選択する（ステップＳ２１０５）。そして、テストパターン生成装置１００は、分配間隔の決定処理を行う（ステップＳ２１０６）。つぎに、テストパターン生成装置１００は、詳細位置集合の決定処理を行う（ステップＳ２１０７）。
つづいて、テストパターン生成装置１００は、回路分割リストの作成処理を行い（ステップＳ２１０８）、ステップＳ２１０４へ戻る。一方、ステップＳ２１０４において、未処理のグループがないと判断された場合（ステップＳ２１０４：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図２２は、図２１で示したブロック情報ソート処理（ステップＳ２１０２）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、ブロック情報をネット数により降順にソートする（ステップＳ２２０１）。つぎに、テストパターン生成装置１００は、開始位置←ブロック情報の先頭位置とする（ステップＳ２２０２）。
そして、テストパターン生成装置１００は、終了位置←開始位置とする（ステップＳ２２０３）。つぎに、テストパターン生成装置１００は、直前のネット数←終了位置のネット数とする（ステップＳ２２０４）。テストパターン生成装置１００は、終了位置のネット数と直前のネット数が同じであるか否かを判断する（ステップＳ２２０５）。
終了位置のネット数と直前のネット数が同じであると判断された場合（ステップＳ２２０５：Ｙｅｓ）、テストパターン生成装置１００は、終了位置を更新し（ステップＳ２２０６）、ステップＳ２２０５へ戻る。終了位置のネット数と直前のネット数が同じでないと判断された場合（ステップＳ２２０５：Ｎｏ）、テストパターン生成装置１００は、開始位置≦ｉ＜終了位置の範囲にあるブロック情報［ｉ］をスキャンＦＦ数で降順にソートする（ステップＳ２２０７）。
つぎに、テストパターン生成装置１００は、未処理のブロック情報があるか否かを判断する（ステップＳ２２０８）。未処理のブロック情報があると判断された場合（ステップＳ２２０８：Ｙｅｓ）、テストパターン生成装置１００は、開始位置←終了位置の次とし（ステップＳ２２０９）、ステップＳ２２０３へ戻る。未処理のブロック情報がないと判断された場合（ステップＳ２２０８：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図２３は、図２１で示したブロック情報グループ認識処理（ステップＳ２１０３）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、開始位置←ブロック情報の先頭位置とする（ステップＳ２３０１）。つぎに、テストパターン生成装置１００は、終了位置←開始位置とする（ステップＳ２３０２）。
そして、テストパターン生成装置１００は、直前のネット数←終了位置のネット数、直前のスキャンＦＦ数←終了位置のスキャンＦＦ数とする（ステップＳ２３０３）。つぎに、テストパターン生成装置１００は、終了位置のネット数と直前のネット数の差が第１所定範囲以内であるか否かを判断する（ステップＳ２３０４）。終了位置のネット数と直前のネット数の差が第１所定範囲以内でないと判断された場合（ステップＳ２３０４：Ｎｏ）、テストパターン生成装置１００は、ステップＳ２３０７へ移行する。
終了位置のネット数と直前のネット数の差が第１所定範囲以内であると判断された場合（ステップＳ２３０４：Ｙｅｓ）、テストパターン生成装置１００は、終了位置のスキャンＦＦ数と直前のスキャンＦＦ数の差が第２所定範囲以内であるか否かを判断する（ステップＳ２３０５）。終了位置のスキャンＦＦ数と直前のスキャンＦＦ数の差が第２所定範囲以内であると判断された場合（ステップＳ２３０５：Ｙｅｓ）、テストパターン生成装置１００は、終了位置を更新し（ステップＳ２３０６）、ステップＳ２３０４へ戻る。
一方、終了位置のスキャンＦＦ数と直前のスキャンＦＦ数の差が第２所定範囲以内でないと判断された場合（ステップＳ２３０５：Ｎｏ）、テストパターン生成装置１００は、開始位置≦ｉ＜終了位置の範囲にあるブロック情報［ｉ］を一つのグループとして登録する（ステップＳ２３０７）。テストパターン生成装置１００は、未処理のブロック情報があるか否かを判断する（ステップＳ２３０８）。
未処理のブロック情報があると判断された場合（ステップＳ２３０８：Ｙｅｓ）、テストパターン生成装置１００は、開始位置←終了位置の次とし（ステップＳ２３０９）、ステップＳ２３０２へ戻る。未処理のブロック情報がないと判断された場合（ステップＳ２３０８：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図２４は、図２１で示した分配間隔決定処理（ステップＳ２１０６）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、分配間隔＝０、余剰数＝０とする（ステップＳ２４０１）。つぎに、テストパターン生成装置１００は、処理対象のグループが孤立グループであるか否かを判断する（ステップＳ２４０２）。ステップＳ２４０２においてテストパターン生成装置１００は、具体的に、ブロック数が１であるか否かを判断することにより孤立グループであるか否かを判断する。
孤立グループであると判断された場合（ステップＳ２４０２：Ｙｅｓ）、テストパターン生成装置１００は、余剰数＝１とし（ステップＳ２４０３）、一連の処理を終了する。孤立グループでないと判断された場合（ステップＳ２４０２：Ｎｏ）、テストパターン生成装置１００は、ブロック数に端数がなしかを判断する（ステップＳ２４０４）。ステップＳ２４０４において、テストパターン生成装置１００は、具体的に、「分割数％ブロック数」が０であるか否かを判断する。
ブロック数に端数がないと判断された場合（ステップＳ２４０４：Ｙｅｓ）、テストパターン生成装置１００は、分配間隔＝分割数／ブロック数とし（ステップＳ２４０５）、一連の処理を終了する。ブロック数に端数があると判断された場合（ステップＳ２４０４：Ｎｏ）、テストパターン生成装置１００は、「ブロック数＝ブロック数−余剰数」とする（ステップＳ２４０６）。
テストパターン生成装置１００は、ブロックなしか否かを判断する（ステップＳ２４０７）。ステップＳ２４０７において、テストパターン生成装置１００は、ブロック数が０であるか否かを判断することによってブロックなしか否かを判断する。ブロックなしと判断された場合（ステップＳ２４０７：Ｙｅｓ）、テストパターン生成装置１００は、一連の処理を終了する。一方、ブロックありと判断された場合（ステップＳ２４０７：Ｎｏ）、テストパターン生成装置１００は、ブロック数と分割数の最大公約数ｇを算出する（ステップＳ２４０８）。
つぎに、テストパターン生成装置１００は、共通の約数を持つか否かを判断する（ステップＳ２４０９）。ステップＳ２４０９において、テストパターン生成装置１００は、例えば、ｇが１でないかを判断する。共通の約数を持たないと判断された場合（ステップＳ２４０９：Ｎｏ）、テストパターン生成装置１００は、余剰数＝余剰数＋１とし（ステップＳ２４１１）、ステップＳ２４０６へ戻る。共通の約数を持つと判断された場合（ステップＳ２４０９：Ｙｅｓ）、テストパターン生成装置１００は、分配間隔＝分割数／ｇとし（ステップＳ２４１０）、一連の処理を終了する。
図２５は、図２１で示した詳細位置集合決定処理（ステップＳ２１０７）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、「詳細位置集合＝空」とする（ステップＳ２５０１）。つぎに、テストパターン生成装置１００は、分配間隔があるか否かを判断する（ステップＳ２５０２）。ステップＳ２５０２において、テストパターン生成装置１００は、例えば、分配間隔が０でないかを判断する。
分配間隔がないと判断された場合（ステップＳ２５０２：Ｎｏ）、テストパターン生成装置１００は、ステップＳ２５１１へ移行する。分配間隔があると判断された場合（ステップＳ２５０２：Ｙｅｓ）、テストパターン生成装置１００は、繰り返し数＝分割数／分配間隔、メンバー数＝ブロック数／繰り返し数とする（ステップＳ２５０３）。つぎに、テストパターン生成装置１００は、ｒ＝０とする（ステップＳ２５０４）。テストパターン生成装置１００は、ｒ＜繰り返し数であるか否かを判断する（ステップＳ２５０５）。ｒ＜繰り返し数であると判断された場合（ステップＳ２５０５：Ｙｅｓ）、テストパターン生成装置１００は、「ｎ＝１」とする（ステップＳ２５０６）。
つぎに、テストパターン生成装置１００は、ｎ≦メンバー数であるか否かを判断する（ステップＳ２５０７）。ｎ≦メンバー数であると判断された場合（ステップＳ２５０７：Ｙｅｓ）、テストパターン生成装置１００は、ｍを詳細位置集合に追加する（ステップＳ２５０８）。ステップＳ２５０８におけるｍは「（ｒ＊分配間隔）＋ｎ」である。つぎに、テストパターン生成装置１００は、「ｎ＝ｎ＋１」とし（ステップＳ２５０９）、ステップＳ２５０７へ戻る。
一方、ステップＳ２５０７において、ｎ≦メンバー数でないと判断された場合（ステップＳ２５０７：Ｎｏ）、テストパターン生成装置１００は、「ｒ＝ｒ＋１」とし（ステップＳ２５１０）、ステップＳ２５０５へ戻る。
一方、ステップＳ２５０５において、ｒ＜繰り返し数でないと判断された場合（ステップＳ２５０５：Ｎｏ）、テストパターン生成装置１００は、「ｎ＝１」とする（ステップＳ２５１１）。つぎに、テストパターン生成装置１００は、ｎ≦余剰数であるか否かを判断する（ステップＳ２５１２）。ｎ≦余剰数であると判断された場合（ステップＳ２５１２：Ｙｅｓ）、テストパターン生成装置１００は、ｍを詳細位置集合に追加する（ステップＳ２５１３）。ステップＳ２５１３におけるｍは「分割数＋ｎ」である。つぎに、テストパターン生成装置１００は、ｎ＝ｎ＋１とし（ステップＳ２５１４）、ステップＳ２５１２へ戻る。
ステップＳ２５１２において、ｎ≦余剰数でないと判断された場合（ステップＳ２５１２：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
図２６および図２７は、図２１で示した回路分割リスト作成処理（ステップＳ２１０８）の詳細な説明を示すフローチャートである。まず、テストパターン生成装置１００は、最小オフセット＝０、最小総トレースネット数＝∞とする（ステップＳ２６０１）。テストパターン生成装置１００は、オフセット＝０とする（ステップＳ２６０２）。
テストパターン生成装置１００は、オフセット＜分割数であるか否かを判断する（ステップＳ２６０３）。オフセット＜分割数であると判断された場合（ステップＳ２６０３：Ｙｅｓ）、テストパターン生成装置１００は、総トレースネット数＝０とする（ステップＳ２６０４）。テストパターン生成装置１００は、ｉ＝０とする（ステップＳ２６０５）。テストパターン生成装置１００は、ｉ＜ブロック数であるか否かを判断する（ステップＳ２６０６）。
ｉ＜ブロック数であると判断された場合（ステップＳ２６０６：Ｙｅｓ）、テストパターン生成装置１００は、回路位置＝（オフセット＋位置集合［ｉ］）％分割数とする（ステップＳ２６０７）。テストパターン生成装置１００は、総トレースネット数＝分割回路［回路位置］の累積トレースネット数＋ブロック［ｉ］のトレースネット数とする（ステップＳ２６０８）。つぎに、テストパターン生成装置１００は、「ｉ＝ｉ＋１」とし（ステップＳ２６０９）、ステップＳ２６０６へ戻る。
ステップＳ２６０６において、ｉ＜ブロック数でないと判断された場合（ステップＳ２６０６：Ｎｏ）、テストパターン生成装置１００は、総トレースネット数＜最小総トレースネット数であるか否かを判断する（ステップＳ２６１０）。総トレースネット数＜最小総トレースネット数であると判断された場合（ステップＳ２６１０：Ｙｅｓ）、テストパターン生成装置１００は、最小総トレースネット数＝総トレースネット数とする（ステップＳ２６１１）。テストパターン生成装置１００は、最小オフセット＝オフセットとし（ステップＳ２６１２）、ステップＳ２６１３へ移行する。
一方、ステップＳ２６１０において、総トレースネット数＜最小総トレースネット数でないと判断された場合（ステップＳ２６１０：Ｎｏ）、テストパターン生成装置１００は、オフセット＝オフセット＋１とし（ステップＳ２６１３）、ステップＳ２６０３へ戻る。
ステップＳ２６０３において、オフセット＜分割数でないと判断された場合（ステップＳ２６０３：Ｎｏ）、テストパターン生成装置１００は、ｉ＝０とする（ステップＳ２７０１）。テストパターン生成装置１００は、ｉ＜ブロック数であるか否かを判断する（ステップＳ２７０２）。ｉ＜ブロック数であると判断された場合（ステップＳ２７０２：Ｙｅｓ）、テストパターン生成装置１００は、回路位置＝（最小オフセット＋位置集合［ｉ］）％分割数とする（ステップＳ２７０３）。
テストパターン生成装置１００は、分割回路［回路位置］の累積トレースネット数＋＝ブロック［ｉ］のトレースネット数とする（ステップＳ２７０４）。そして、テストパターン生成装置１００は、回路分割リスト［回路位置］にブロック［ｉ］を登録する（ステップＳ２７０５）。つぎに、テストパターン生成装置１００は、「ｉ＝ｉ＋１」とし（ステップＳ２７０６）、ステップＳ２７０２へ戻る。また、ステップＳ２７０２において、ｉ＜ブロック数でないと判断された場合（ステップＳ２７０２：Ｎｏ）、テストパターン生成装置１００は、一連の処理を終了する。
＜クロックマージ＞
最後に、複数のクロックパルスをマージする例について説明する。近年、プロセッサには複数のクロックドメインを有する場合がある。複数のクロックドメインが存在する場合にもスキャンＦＦにスキャン後にＡＴＰＧ（Ａｕｔｏｍａｔｉｃ Ｔｅｓｔ Ｐａｔｔｅｒｎ Ｇｅｎｅｒａｔｏｒ）によって印加されるクロックパルスが１パルスに制限される場合がある。例えば、スキャン後に２発クロックパルスを対象回路に印加すると、１発目のクロックパルスによりスキャンＦＦのステートが更新される。このため、クロックドメイン間の渡り部分で正確なテスト生成を行うためには、スキャンＦＦの前段も更新の対象としなければならない。
複数のクロックドメインが存在する際に、スキャニング後に１発ずつクロックパルスを対象回路に印加する場合には、試験されていない回路に対しては改めてスキャンとクロック印加を行うため、テストパターンが増加するという問題点がある。上述したように、従来、テストパターン生成の対象回路に複数のクロックドメインがあり、クロックドメイン間においてデータ転送経路が混在しない場合に、スキャンＦＦに対してデータ転送方向とは逆順にクロック信号を供給する技術がある。
しかしながら、データ転送方向が複数ある場合に、単発のクロックでのＡＴＰＧが想定する動作と一致しないため、ＡＴＰＧでは故障を検出できない場合がある。そのため、従来通り印加を行うために、テストパターンが増加するという問題点がある。
本実施の形態では、テストパターン生成装置１００は、データ転送方向の各々についての故障の数を特定し、特定した故障の数の比較によってテストパターン生成時のデータ転送方向を決定する。そして、本実施の形態では、テストパターン生成装置１００は、決定したデータ転送方向と逆の方向についての故障をＡＴＰＧの一時的に対象外化することを示す情報を出力する。これにより、ＡＴＰＧが適用可能な範囲を大きくできるため、テストパターンの削減を図ることができる。
図２８は、ドメイン間の信号の受け渡し領域のＡＴＰＧとクロックパルスの印加順序例を示す説明図である。ここでは、対象回路には第１クロックドメインとしてクロックドメインＡと、第１クロックドメインと異なる第２クロックドメインとしてクロックドメインＢとがあるとする。図２８には、クロックドメインＡからクロックドメインＢへデータ信号を受け渡す場合について、観測用ＦＦのデータ入力である０故障を検出する例を挙げる。
クロックの印加の順番がクロックドメインＡ→クロックドメインＢの順であると、クロックドメインＡのクロックＡの印加によってＦＦａとＦＦｂのスキャン値が更新される。そのため、ＦＦａとＦＦｂとの設定ステートが故障観測前に更新される。
一方、クロックの印加の順番がクロックドメインＢ→クロックドメインＡの順であると、クロックドメインＢのクロックＢの印加によって観測用ＦＦスキャン値が更新される。その後、クロックドメインＡのクロックＡの印加によってＦＦａとＦＦｂのスキャン値が更新される。このように、ＦＦａとＦＦｂとの設定ステートが故障観測後に更新される。したがって、クロックドメインＢ→クロックドメインＡの順であると、観測用ＦＦへのデータ信号の０故障を検出するためのテストパターンを作成可能である。
故障カウント部３０７は、第１クロックドメインに属するＦＦから第２クロックドメインに属するＦＦへ信号が受け渡される場合における第１数を特定する。第１数は第１クロックドメインに属するＦＦから第２クロックドメインに属するＦＦまでの間のデータパス上の故障の数である。この故障は（Ａ→Ｂ）故障とも称する。
また、故障カウント部３０７は、第２クロックドメインに属するＦＦから第１クロックドメインに属するＦＦへ信号が受け渡される場合における第２数を特定する。第２数は、第２クロックドメインに属するＦＦから第１クロックドメインに属するＦＦまでの間のデータパス上の故障の数である。この故障は（Ｂ→Ａ）故障とも称する。
故障カウント部３０７は、例えば、故障の各々について、上述のドメインマーカｓ［故障のネット番号］にクロックドメインＡが存在し、かつドメインマーカｒ［故障のネット番号］にクロックドメインＢが存在するか否かを判断する。故障カウント部３０７は、例えば、いずれにも存在すると判断した場合、（Ａ→Ｂ）故障であると判断して故障カウンタＦ＿ＡＢをカウントアップする。カウント終了後の故障カウンタＦ＿ＡＢの結果が第１数となる。
また、故障カウント部３０７は、例えば、故障の各々について、ドメインマーカｓ［故障のネット番号］にクロックドメインＢが存在し、かつドメインマーカｒ［故障のネット番号］にクロックドメインＡが存在するか否かを判断する。故障カウント部３０７は、例えば、いずれにも存在すると判断した場合、（Ｂ→Ａ）故障であると判断して故障カウンタＦ＿ＢＡをカウントアップする。カウント終了後の故障カウンタＦ＿ＢＡの値が第２数となる。
印加順序決定部３０８は、第１数と第２数との比較に基づいて、クロックドメインＡのクロックＡとクロックドメインＢのクロックＢとの入力順を決定する。印加順序決定部３０８は、例えば、第１数が第２数よりも大きい場合、クロックドメインＢのクロックＢからクロックドメインＡのクロックＡの順を入力順に決定する。一方、印加順序決定部３０８は、例えば、第２数が第１数よりも大きい場合、クロックドメインＡのクロックＡからクロックドメインＢのクロックＢの順を入力順に決定する。第１数と第２数とが同一値である場合は、いずれの順であってもよい。また、印加順序決定部３０８は、入力順の決定結果をクロック印加順序情報３４７としてＲＡＭ２０３、ＲＯＭ２０２、ディスク２０５などの記憶装置に記憶する。
つぎに、対象外化決定部３０９は、ゲートの端子の各々についての故障のうち、決定した入力順と逆の順序によって検出可能な故障を示す情報を生成する。対象外化決定部３０９は、例えば、クロックＡからクロックＢの順を入力順に決定した場合、（Ａ→Ｂ）故障を一時的にＡＴＰＧの対象外とすることを示す対象外故障識別情報３４６を生成する。対象外化決定部３０９は、例えば、クロックＢからクロックＡの順を入力順に決定した場合、（Ｂ→Ａ）故障を一時的にＡＴＰＧの対象外とすることを示す対象外故障識別情報３４６を生成する。一時的に対象外とするとは、決定された入力順によって検出可能な故障についてのＡＴＰＧを作成中に対象外とすることを示す。
図２９は、故障識別およびクロック印加順序例を示す説明図である。図２９の例では、印加順序決定部３０８は、（Ｂ→Ａ）故障の第２数が（Ａ→Ｂ）故障の第１数よりも多いいため、クロックの印加順をクロックＡからクロックＢに決定する。また、対象外化決定部３０９は、クロックドメインＡに属するＦＦ（Ａ）からクロックドメインＢに属するＦＦ（Ｂ）までの間にあるデータパス上のゲート群についての故障をＡＴＰＧの一時対象外化とすることを示す対象外故障識別情報３４６を生成する。また、対象外化決定部３０９は、対象外故障識別情報３４６をＲＡＭ２０３、ＲＯＭ２０２、ディスク２０５などの記憶装置に記憶する。
図３０は、クロックマージによるパターン削減例を示す説明図である。図３０（ａ）にクロックドメインがＡとＢとの２つの場合における信号の受け渡し例を示す。信号の受け渡しは（Ａ→Ａ）、（Ｂ→Ｂ）、（Ａ→Ｂ）、（Ｂ→Ａ）の４通りである。
図３０（ａ）においては、面積が故障数であり、換言するとクロック印加数を表す。従来では、クロック印加数は、単純にクロックドメインＡのクロックＡとクロックドメインＢのクロックＢとの和となる。そのため、図３０（ｂ）に示すように、従来におけるクロック印加数は、｛（Ａ→Ａ）の数＋（Ｂ→Ａ）の数＋（Ｂ→Ｂ）の数＋（Ａ→Ｂ）の数｝である。
一方、本実施の形態では、（Ｂ→Ａ）の故障数＞（Ａ→Ｂ）の故障数であるため、クロック印加順はクロックドメインＡのクロックＡからクロックドメインＢのクロックＢの順となる。そして、マージクロック（Ａ→Ｂ）により、故障｛（Ａ→Ａ）＋（Ｂ→Ａ）｝と故障｛（Ｂ→Ｂ）｝がテスト対象となる。したがって、クロック印加数は、マージクロックにおける印加数と、（Ａ→Ｂ）における印加数との和となる。このため、クロック印加数は、ｍａｘ｛（Ａ→Ａ）の数＋（Ｂ→Ｂ）の数，（Ｂ→Ｂ）の数｝＋（Ａ→Ｂ）の数となる。ｍａｘ｛（Ａ→Ａ）の数＋（Ｂ→Ａ）の数，（Ｂ→Ｂ）の数｝は、（Ａ→Ａ）の数＋（Ｂ→Ａ）の数と、（Ｂ→Ｂ）の数と、のうち大きい方の数である。そのため、図３０（ｃ）の例では、（Ｂ→Ｂ）の数が削減可能となる。
（テストパターン生成装置１００によるクロック印加順序決定処理手順例）
図３１は、テストパターン生成装置によるクロック印加順序決定処理手順例を示すフローチャートである。ここでのクロック印加順序決定処理については、テストパターンを作成する度に実行されてもよい。まず、テストパターン生成装置１００は、故障カウンタを初期化する（ステップＳ３１０１）。ステップＳ３１０１において、テストパターン生成装置１００は、例えば、故障カウンタＦ＿ＡＢを０にする。また、ステップＳ３１０１において、テストパターン生成装置１００は、故障カウンタＦ＿ＢＡを０にする。Ｆ＿ＡＢはクロックＡからクロックＢへの信号の受け渡しにおける故障カウンタである。Ｆ＿ＢＡはクロックＢからクロックＡへの信号の受け渡しにおける故障カウンタである。
テストパターン生成装置１００は、未処理の仮定故障があるか否かを判断する（ステップＳ３１０２）。未処理の仮定故障があると判断された場合（ステップＳ３１０２：Ｙｅｓ）、テストパターン生成装置１００は、未処理の仮定故障からいずれかの仮定故障を処理対象として選択する（ステップＳ３１０３）。
テストパターン生成装置１００は、仮定故障ｆは検出済であるか否かを判断する（ステップＳ３１０４）。仮定故障ｆは検出済みであると判断された場合（ステップＳ３１０４：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ３１０２へ戻る。一方、仮定故障ｆは検出済みでないと判断された場合（ステップＳ３１０４：Ｎｏ）、テストパターン生成装置１００は、ネット番号←ｆの仮定されるネットとする（ステップＳ３１０５）。テストパターン生成装置１００は、ｓ［ネット番号］にＡが存在し、かつｒ［ネット番号］にＢが存在するか否かを判断する（ステップＳ３１０６）。ｓ［ネット番号］にＡが存在し、かつｒ［ネット番号］にＢが存在すると判断された場合（ステップＳ３１０６：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ３１０８へ移行する。ｓ［ネット番号］にＡが存在しない、またはｒ［ネット番号］にＢが存在しないと判断された場合（ステップＳ３１０６：Ｎｏ）、テストパターン生成装置１００は、Ｆ＿ＡＢ＝Ｆ＿ＡＢ＋１とする（ステップＳ３１０７）。
つぎに、テストパターン生成装置１００は、ｓ［ネット番号］にＢが存在し、かつｒ［ネット番号］にＡが存在するか否かを判断する（ステップＳ３１０８）。ｓ［ネット番号］にＢが存在し、かつｒ［ネット番号］にＡが存在すると判断された場合（ステップＳ３１０８：Ｙｅｓ）、テストパターン生成装置１００は、ステップＳ３１０２へ戻る。一方、ｓ［ネット番号］にＢが存在しない、またはｒ［ネット番号］にＡが存在しないと判断された場合（ステップＳ３１０８：Ｎｏ）、テストパターン生成装置１００は、「Ｆ＿ＢＡ＝Ｆ＿ＢＡ＋１」とし（ステップＳ３１０９）、ステップＳ３１０２に戻る。
ステップＳ３１０２において、未処理の仮定故障がないと判断された場合（ステップＳ３１０２：Ｎｏ）、テストパターン生成装置１００は、Ｆ＿ＡＢ＞Ｆ＿ＢＡであるか否かを判断する（ステップＳ３１１０）。Ｆ＿ＡＢ＞Ｆ＿ＢＡであると判断された場合（ステップＳ３１１０：Ｙｅｓ）、テストパターン生成装置１００は、印加順＝Ｂ→Ａとする（ステップＳ３１１１）。テストパターン生成装置１００は、渡りＢ→Ａ故障をＡＴＰＧの一時対象外化し（ステップＳ３１１２）、一連の処理を終了する。
つぎに、Ｆ＿ＡＢ＞Ｆ＿ＢＡでないと判断された場合（ステップＳ３１１０：Ｎｏ）、テストパターン生成装置１００は、印加順＝Ａ→Ｂとする（ステップＳ３１１３）。そして、テストパターン生成装置１００は、渡りＡ→Ｂ故障をＡＴＰＧの一時対象外化し（ステップＳ３１１４）、一連の処理を終了する。
以上説明したように、テストパターン生成装置１００は、規模および機能に関する各特徴量の類似度に基づきグループ化した各ブロックについて、分割数とグループのブロック数の比率に基づき各ブロックを分割回路に割り当てる。すなわち、回路内の各ブロックの規模および機能に関する各特徴量の類似度に基づくグループのブロック数と分割回路の数との比率に基づき、グループの各ブロックを分割回路に割り当てることで、分割回路の特性の均等化を図る。これにより、特徴量が近いブロックが同じ分割回路に偏在しないようにでき、分割回路間の特性の均等化を図ることができる。
また、テストパターン生成装置１００は、比率に応じた間隔と複数の分割回路に付された順序とによって複数の分割回路に割り当てた場合におけるブロックの接続関係に関する第３特徴量の合計値が最小となるように、グループに含まれるブロックを割り当てる。これにより、ブロックの接続関係による分割後の分割回路間の規模のばらつきの低減を図ることができる。
また、テストパターン生成装置１００は、分割数をグループに含まれるブロックの数で割った時に余りがある場合、グループに含まれるブロックのうちの余りの数のブロックを複数の分割回路と異なる分割回路に割り当てる。余剰分のブロックの数は少ない可能性が高いため、余剰分のブロックを複数の分割回路に分配せずに異なる分割回路に割り当てることにより、分割回路による並列処理時に全体の性能の向上を図ることができる。
また、第２特徴量は、ブロックに含まれるスキャンＦＦの数である。これにより、機能や構成が近いと推定されるブロックを同一のグループとすることができる。
また、テストパターン生成装置１００は、対象のＦＦとフォワード方向にあるＦＦとの間のデータパス上のゲート段数とクロックパス上のゲート段数との差分値に基づいて、対象のＦＦのデータ入力に付された冗長ディレーを削除する。これにより、レーシングを回避しつつ、回路モデルの縮小化を図ることができる。
また、テストパターン生成装置１００は、対象のＦＦとバックワード方向にあるＦＦとの間のデータパス上のゲート段数と、バックワード方向にあるＦＦのクロックパス上のゲート段数との差分値に基づいて、対象のＦＦのデータ出力に付された冗長ディレーを削除する。これにより、レーシングを回避しつつ、回路モデルの縮小化を図ることができる。
また、テストパターン生成装置１００は、ドメイン間でデータを受け渡す場合、ある転送方向におけるドメイン間の故障の数と、反対の転送方向におけるドメイン間の故障の数と、に基づくクロックの入力順と逆順で検出可能な故障を一時的にＡＴＰＧの対象外とする。これにより、入力順において検出できない故障を対象外としておくことにより、入力順による故障検出と、同一クロックドメイン間での故障検出と、を同時に行うことができ、クロックの入力回数を減らすことができる。したがって、テストパターンの数を削減することができる。
なお、本実施の形態で説明したテストパターン生成方法は、予め用意されたテストパターン生成プログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本テストパターン生成プログラムは、磁気ディスク、光ディスク、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）フラッシュメモリなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、テストパターン生成プログラムは、インターネット等のネットワーク２０９を介して配布してもよい。
上述した実施の形態に関し、さらに以下の付記を開示する。
（付記１）コンピュータが、
テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
処理を実行することを特徴とするテストパターン生成方法。
（付記２）前記取得する処理では、前記ブロックの各々について、前記回路情報に基づく前記ブロックに含まれるフリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のパスに関する第３特徴量を取得し、
前記割り当てる処理では、前記グループの各々について、前記グループに含まれるブロックの各々を前記比率に応じた間隔と、前記複数の分割回路の各々に付された異なる順序と、によって前記複数の分割回路に割り当てた場合における前記複数の分割回路の各々についての前記第３特徴量の合計値が最小となるように、前記グループに含まれるブロックを割り当てる、
ことを特徴とする付記１に記載のテストパターン生成方法。
（付記３）前記割り当てる処理では、前記分割数を前記グループに含まれるブロックの数で割った時に余りがある場合、前記グループに含まれるブロックのうちの前記余りの数のブロックを前記複数の分割回路と異なる分割回路に割り当てる、
ことを特徴とする付記１または２に記載のテストパターン生成方法。
（付記４）前記第２特徴量は、前記ブロックに含まれるスキャン用のフリップフロップの数であることを特徴とする付記１〜３のいずれか一つに記載のテストパターン生成方法。
（付記５）前記コンピュータが、
前記ブロックに含まれるフリップフロップマクロであって、フリップフロップとデータパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートとを有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出する処理を実行し、
前記回路情報は、導出した前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示すことを特徴とする付記１〜４のいずれか一つに記載のテストパターン生成方法。
（付記６）前記コンピュータが、
前記ブロックに含まれるフリップフロップマクロであって、フリップフロップとデータパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートとを有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出する処理を実行し、
前記回路情報は、導出した前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示すことを特徴とする付記１〜５のいずれか一つに記載のテストパターン生成方法。
（付記７）前記コンピュータが、
前記対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ信号が受け渡される場合における前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップまでの間のデータパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ信号が受け渡される場合における前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップまでの間のデータパス上の故障の第２数と、を特定し、
前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
処理を実行することを特徴とする付記１〜６のいずれか一つに記載のテストパターン生成方法。
（付記８）コンピュータが、
テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行することを特徴とするテストパターン生成方法。
（付記９）コンピュータが、
テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行することを特徴とするテストパターン生成方法。
（付記１０）コンピュータが、
テストパターン生成の対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記対象回路に含まれるゲートの端子の各々についての故障のうち、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第２数と、を特定し、
前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
処理を実行することを特徴とするテストパターン生成方法。
（付記１１）コンピュータに、
テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
処理を実行させることを特徴とするテストパターン生成プログラム。
（付記１２）コンピュータに、
テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行させることを特徴とするテストパターン生成プログラム。
（付記１３）コンピュータに、
テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行させることを特徴とするテストパターン生成プログラム。
（付記１４）コンピュータに、
テストパターン生成の対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記対象回路に含まれるゲートの端子の各々についての故障のうち、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第２数と、を特定し、
前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
処理を実行させることを特徴とするテストパターン生成プログラム。
（付記１５）テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
処理を実行する制御部を有することを特徴とするテストパターン生成装置。
（付記１６）テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行する制御部を有することを特徴とするテストパターン生成装置。
（付記１７）テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理を実行する制御部を有することを特徴とするテストパターン生成装置。
（付記１８）テストパターン生成の対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記対象回路に含まれるゲートの端子の各々についての故障のうち、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第２数と、を特定し、
前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
処理を実行する制御部を有することを特徴とするテストパターン生成装置。
（付記１９）テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
処理をコンピュータに実行させるテストパターン生成プログラムを記録したことを特徴とする記録媒体。
（付記２０）テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理をコンピュータに実行させるテストパターン生成プログラムを記録したことを特徴とする記録媒体。
（付記２１）テストパターン生成の対象回路のゲートおよび前記ゲート間の接続関係を示す第１回路情報を取得し、
前記第１回路情報が示す前記対象回路内のブロックに含まれるフリップフロップマクロであって、フリップフロップと、データパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートと、を有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出し、
前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示す第２回路情報を生成する、
処理をコンピュータに実行させるテストパターン生成プログラムを記録したことを特徴とする記録媒体。
（付記２２）テストパターン生成の対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記対象回路に含まれるゲートの端子の各々についての故障のうち、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ受け渡される信号のパス上の故障の第２数と、を特定し、
前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
処理をコンピュータに実行させるテストパターン生成プログラムを記録したことを特徴とする記録媒体。
１００ テストパターン生成装置
１０１ 回路情報
１０２ 対象回路
１０３−１〜１０３−８，１４０１−１〜１４０１−３０，１７００−１〜１７００−１０ ブロック
１０４−１〜１０４−３，１５０１−１〜１５０１−４，１７０１−１〜１７０１−３ グループ
１０５−１〜１０５−４，１６００−１〜１６００−１６，１９００−１〜１９００−１７ 分割回路
３０１，３０４ 取得部
３０２ クロックパストレース部
３０３ データパストレース部
３０５ 分類部
３０６ 割当部
３０７ 故障カウント部
３０８ 印加順序決定部
３０９ 対象外化決定部

Claims (8)

  1. コンピュータが、
    テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
    取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
    分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
    処理を実行することを特徴とするテストパターン生成方法。
  2. 前記取得する処理では、前記ブロックの各々について、前記回路情報に基づく前記ブロックに含まれるフリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のパスに関する第３特徴量を取得し、
    前記割り当てる処理では、前記グループの各々について、前記グループに含まれるブロックの各々を前記比率に応じた間隔と、前記複数の分割回路の各々に付された異なる順序と、によって前記複数の分割回路に割り当てた場合における前記複数の分割回路の各々についての前記第３特徴量の合計値が最小となるように、前記グループに含まれるブロックを割り当てる、
    ことを特徴とする請求項１に記載のテストパターン生成方法。
  3. 前記割り当てる処理では、前記分割数を前記グループに含まれるブロックの数で割った時に余りがある場合、前記グループに含まれるブロックのうちの前記余りの数のブロックを前記複数の分割回路と異なる分割回路に割り当てる、
    ことを特徴とする請求項１または２に記載のテストパターン生成方法。
  4. 前記コンピュータが、
    前記ブロックに含まれるフリップフロップマクロであって、フリップフロップとデータパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートとを有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのフォワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出する処理を実行し、
    前記回路情報は、導出した前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示すことを特徴とする請求項１〜３のいずれか一つに記載のテストパターン生成方法。
  5. 前記コンピュータが、
    前記ブロックに含まれるフリップフロップマクロであって、フリップフロップとデータパスとなり得る前記フリップフロップのデータ入力側とデータ出力側との少なくともいずれかに挿入された複数の冗長なディレーゲートとを有するフリップフロップマクロに含まれる前記フリップフロップから、前記フリップフロップのバックワード方向にあるフリップフロップまでの間のデータパス上のゲートの数と、前記ブロックに含まれる前記フリップフロップにクロック信号を供給するクロック端子から前記フリップフロップまでの間にあるクロックパス上のゲートの数と、の差分値を導出する処理を実行し、
    前記回路情報は、導出した前記差分値に基づいて前記複数の冗長なディレーゲートのいずれかを削除した前記フリップフロップマクロを含む前記対象回路のゲートおよび前記ゲート間の接続関係を示すことを特徴とする請求項１〜４のいずれか一つに記載のテストパターン生成方法。
  6. 前記コンピュータが、
    前記対象回路には第１クロックドメインと、前記第１クロックドメインと異なる第２クロックドメインとがある場合、前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップへ信号が受け渡される場合における前記第１クロックドメインに属するフリップフロップから前記第２クロックドメインに属するフリップフロップまでの間のデータパス上の故障の第１数と、前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップへ信号が受け渡される場合における前記第２クロックドメインに属するフリップフロップから前記第１クロックドメインに属するフリップフロップまでの間のデータパス上の故障の第２数と、を特定し、
    前記第１数と前記第２数との比較に基づいて、前記第１クロックドメインの第１クロックと前記第２クロックドメインの第２クロックとの入力順を決定し、
    前記ゲートの端子の各々についての故障のうち、決定した前記入力順と逆の順序によって検出可能な故障を示す情報を生成する、
    処理を実行することを特徴とする請求項１〜５のいずれか一つに記載のテストパターン生成方法。
  7. コンピュータに、
    テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
    取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
    分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
    処理を実行させることを特徴とするテストパターン生成プログラム。
  8. テストパターン生成の対象回路に含まれる複数のブロックの各々について、前記対象回路のゲートおよび前記ゲート間の接続関係を示す回路情報に基づく前記ブロックのサイズに関する第１特徴量と、前記回路情報に基づく前記ブロックの機能に関する第２特徴量と、を取得し、
    取得した前記第１特徴量が第１所定範囲内であり、かつ取得した前記第２特徴量が第２所定範囲内であるブロックが同一のグループとなるように、前記複数のブロックを複数のグループに分類し、
    分類した前記複数のグループの各々について、前記グループに含まれるブロックの数と、前記複数のブロックを分割する分割数と、の比率に基づいて、前記グループに含まれるブロックの各々を、前記分割数の複数の分割回路のいずれかに割り当てる、
    処理を実行する制御部を有することを特徴とするテストパターン生成装置。
JP2014243552A 2014-12-01 2014-12-01 テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置 Active JP6365273B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2014243552A JP6365273B2 (ja) 2014-12-01 2014-12-01 テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置
US14/938,000 US9772377B2 (en) 2014-12-01 2015-11-11 Circuit division method for test pattern generation and circuit division device for test pattern generation

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2014243552A JP6365273B2 (ja) 2014-12-01 2014-12-01 テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置

Publications (2)

Publication Number Publication Date
JP2016109427A JP2016109427A (ja) 2016-06-20
JP6365273B2 true JP6365273B2 (ja) 2018-08-01

Family

ID=56079054

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2014243552A Active JP6365273B2 (ja) 2014-12-01 2014-12-01 テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置

Country Status (2)

Country Link
US (1) US9772377B2 (ja)
JP (1) JP6365273B2 (ja)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN116108783B (zh) * 2023-04-04 2023-07-18 上海思尔芯技术股份有限公司 分块逻辑时序分析建模及处理方法、系统、设备及介质

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998049576A1 (fr) * 1997-04-25 1998-11-05 Hitachi, Ltd. Circuit logique et son procede d'essai
JPH11134385A (ja) * 1997-08-26 1999-05-21 Sharp Corp 論理回路の機能検証方法および機能検証のための回路割付装置
JPH1183958A (ja) * 1997-09-02 1999-03-26 Sharp Corp テストパタン生成装置並びにテストパタン生成プログラムを記録した記録媒体
JP3157775B2 (ja) * 1998-04-14 2001-04-16 日本電気アイシーマイコンシステム株式会社 半導体集積回路装置及びその回路設計方法
JP3196931B2 (ja) * 1999-01-20 2001-08-06 日本電気株式会社 パーティショニング方法および装置、ならびにエミュレーション方法および装置
US6330429B1 (en) * 1999-04-14 2001-12-11 Lucent Technologies, Inc. Channel grouping system and method for a wireless communications system
JP2001060216A (ja) 1999-08-24 2001-03-06 Hitachi Ltd 論理等価性検証装置
JP5794027B2 (ja) * 2011-08-02 2015-10-14 富士通株式会社 テストパターン生成装置，テストパターン生成方法およびテストパターン生成プログラム

Also Published As

Publication number Publication date
US20160154056A1 (en) 2016-06-02
JP2016109427A (ja) 2016-06-20
US9772377B2 (en) 2017-09-26

Similar Documents

Publication Publication Date Title
US4263651A (en) Method for determining the characteristics of a logic block graph diagram to provide an indication of path delays between the blocks
CN110647901B (zh) 对电子电路内的扫描触发器进行分组和排序的系统和方法
CN105631087B (zh) 用于集成电路布局生成的方法、器件和计算机程序产品
US20160034631A1 (en) Method of generating techfile having reduced corner variation value
US8306803B2 (en) Method and apparatus for assisting integrated circuit designing with a substrate coupling
Chowdhary et al. How accurately can we model timing in a placement engine?
CN116227398B (zh) 一种自动化生成ip核测试激励的方法及系统
CN118940687A (zh) 芯片的安全设计方法、电子设备及存储介质
JP6365273B2 (ja) テストパターン生成方法、テストパターン生成プログラム、およびテストパターン生成装置
WO2010092825A1 (ja) 回路解析方法
JP4388965B2 (ja) クロックゲーティング解析プログラム、該プログラムを記録した記録媒体、クロックゲーティング解析装置、およびクロックゲーティング解析方法
US7409650B2 (en) Low power consumption designing method of semiconductor integrated circuit
KR100999016B1 (ko) 반도체 장치에 대한 동시 동작 신호 노이즈에 기초하여 지터를 견적하는 방법, 그 견적에 사용하는 동시 동작 신호노이즈량 대 지터량 상관 관계를 산출하는 방법, 이들을 실현하는 프로그램을 기록한 기록매체, 및 반도체 장치 및 그것이 탑재된 프린트 회로 기판의 설계 방법
US10891411B2 (en) Hierarchy-driven logical and physical synthesis co-optimization
Wold Design verification and performance analysis
US7036096B1 (en) Estimating capacitances using information including feature sizes extracted from a netlist
CN108536585B (zh) 数据变更影响域分析方法
Khatri et al. RASP-FIT: A Fast and Automatic Fault Injection Tool for Code-Modification of FPGA Designs
Kuo et al. Efficient trimmed-sample Monte Carlo methodology and yield-aware design flow for analog circuits
CN112115609A (zh) 功耗仿真评估方法及装置
Zhang et al. Path delay test generation toward activation of worst case coupling effects
CN117521586B (zh) 芯片设计的布局规划方法及相关设备
Deodhar et al. Color counting and its application to path delay fault coverage
JP2014186648A (ja) 設計支援装置、設計支援方法、および設計支援プログラム
US20220114321A1 (en) Systems And Methods For Generating Placements For Circuit Designs Using Pyramidal Flows

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20170804

TRDD Decision of grant or rejection written
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20180531

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20180605

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20180618

R150 Certificate of patent or registration of utility model

Ref document number: 6365273

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150