JP5066866B2

JP5066866B2 - 並列処理方法

Info

Publication number: JP5066866B2
Application number: JP2006222642A
Authority: JP
Inventors: 洋司柴田; 徹宮内
Original assignee: Fujitsu Semiconductor Ltd
Current assignee: Fujitsu Semiconductor Ltd
Priority date: 2006-08-17
Filing date: 2006-08-17
Publication date: 2012-11-07
Anticipated expiration: 2026-08-17
Also published as: JP2008047738A

Description

本発明は、複数の中央処理装置を用いた並列処理方法に関するものである。
近年、半導体装置（ＬＳＩ）は大規模化・高集積化が進められている。そのため、論理回路データに基づいて作成されたレイアウトデータを、半導体装置の製造に必要なマスク等を描画するための描画データに変換するための処理時間が長くなる傾向にあり、該処理時間を短くすることが望まれている。

一般に、半導体装置（ＬＳＩ）は、使用される用途に応じて仕様、すなわち搭載機能や動作速度が決定され、その仕様に基づいてＣＡＤ（Computer Aided Design ）装置等を用いて論理設計、回路設計が行われる。そして、回路設計された論理回路データに基づいて素子を配置等した半導体装置の図形データであるレイアウトデータが作成される。このレイアウトデータは、データ変換に係る計算機において、実際にマスク、レチクル、ウエハに描画する描画装置（例えばＥＢ描画露光装置：Electron Beam Exposure System ）に入力可能な描画データに変換される。この描画データが描画装置に入力されることでマスク等が描画され、半導体装置の製造に供される。

ところで、レイアウトデータから描画データへ変換するための処理時間は、半導体装置の大規模化・高集積化に伴い長くなる傾向にあり、複数の中央処理装置（ＣＰＵ）を用いた並列処理によって該処理時間を短縮することも提案されている。

図７は、このような計算機によるデータ変換態様を示すフローチャートである。同図に示すように、この計算機は、レイアウトデータとしてＧＤＳIIフォーマットファイルを入力して（ステップ９１）、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリアを複数の分割データ領域に分割し、更に該分割データ領域（ＪＯＢ）をその出現順に各中央処理装置に割り振る（ステップ９２）。具体的には、例えば変換後の出力がＭＥＢＥＳフォーマットの場合、データエリアを複数分割してなる縦ストライプを、該データエリアの正面から見て左面上側から順次、等間隔で横に区切って、複数の分割データ領域に分割する。同図では、このような分割のイメージ例として、３つの分割データ領域「１」〜「３」への分割例を図示している。

そして、当該計算機は、各中央処理装置による並列処理にて、分割された分割データ領域の図形処理、例えば論理積処理、論理和処理、リサイズ処理、矩形分割処理等の図形演算を実行する（ステップ９３）。

続いて、計算機は、各中央処理装置により個別に図形処理された分割データ領域を統合する登録処理を実行し（ステップ９４）、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする（ステップ９５）。

ところで、この計算機は、図形処理に際し、分割された分割データ領域をその出現順に各中央処理装置に割り振って、これら中央処理装置による並列処理を行っている。一方、各分割データ領域は、それに包含される線分密度やパターン密度等に応じて、計算量の比重が異なるデータ領域、即ち計算量の異なるデータ領域を形成する。従って、並列処理の終盤（例えば右面下側）に出現する分割データ領域に、計算量の比重が重くなるデータ領域が存在していた場合、特に重いデータ領域を割り振られた一の中央処理装置の処理時間が長くなり、他の全ての中央処理装置が図形処理を完了していたとしても、計算機としては、前記一の中央処理装置の完了待ち状態が発生する。これは、複数の中央処理装置による並列処理としては、非効率な状態である。

図８は、複数の中央処理装置による非効率な並列処理として、２つの中央処理装置による３つの分割データ領域「１」〜「３」の並列処理態様を説明する説明図である。なお、同図において、横軸は各中央処理装置の処理時間である。また、最初に現れる分割データ領域「１」は、計算量の比重が軽いデータ領域となっており、次に現れる分割データ領域「２」は、計算量の比重がやや重いデータ領域となっている。また、分割データ領域「３」は、計算量の比重が重いデータ領域となっている。

ここで、２つの中央処理装置による処理が開始されると、一の中央処理装置（以下、「ＣＰＵ１」という）に分割データ領域「１」が割り振られるとともに、他の中央処理装置（以下、「ＣＰＵ２」という）に分割データ領域「２」が割り振られる。そして、時刻ｔ１１において分割データ領域「１」の図形処理を完了したＣＰＵ１には、最後の分割データ領域「３」が割り振られる。従って、ＣＰＵ２は、時刻ｔ１２において分割データ領域「２」の図形処理を完了するものの、計算量の比重が重いデータ領域の分割データ領域「３」を割り振られたＣＰＵ１は、時刻ｔ１３においてその図形処理を完了する。これにより、ＣＰＵ２に時刻ｔ１２〜ｔ１３の時間Ｔ１１の待ち時間が発生することになり、並列処理が非効率な状態であることが確認される。

例えば、並行処理全体の処理時間が２〜３時間クラスのレイアウトデータの場合、ＣＰＵ間の動作完了時刻に最大で２０〜３０分の時間差が発生するものがある。従って、このような時間差を埋めることができれば、１つのレイアウトデータあたり５〜１５％の処理時間の短縮が期待される。

本発明の目的は、半導体装置のレイアウトデータに基づくデータエリアが複数分割されてなる分割データ領域を、複数の中央処理装置による並列処理にて効率的に図形処理して描画データに変換することができる並列処理方法を提供することにある。

上記問題点を解決するために、請求項１及び請求項２に記載の発明は、半導体装置のレイアウトデータに基づくデータエリアを、複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、前記算出された各分割データ領域の計算量の比重に基づいて、前記複数の中央処理装置に割り振る処理順位決定段階とを備える。

上記各構成によれば、前記複数の中央処理装置による並列処理に際し、各中央処理装置には、分割データ領域がその計算量の比重に基づいて割り振られ、図形処理される。従って、各中央処理装置が最終段階で処理する分割データ領域は、その計算量の比重が小さくなることで、一の中央処理装置の図形処理中に他の中央処理装置の図形処理が完了し新たに割り振られる分割データ領域がなかったとしても、該他の中央処理装置に発生する待ち時間は低減される。従って、前記分割された複数の分割データ領域を、複数の中央処理装置による並列処理にて効率的に図形処理して描画データに変換することができる。

特に、請求項１に記載の発明は、前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階を備え、前記処理順位決定段階は、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域のみを、該計算量の比重の大きい順番で、前記複数の中央処理装置に割り振ることを要旨とする。

同構成によれば、前記複数の中央処理装置による並列処理に際し、各中央処理装置には、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域のみ、計算量の比重の大きい順番で割り振られる。従って、前記所定の判定閾値よりも小さい計算量の比重を有する分割データ領域、即ち他の中央処理装置に発生する待ち時間への影響が小さい分割データ領域については、計算量の比重の大きい順番での各中央処理装置への割り振りが割愛される。このため、各中央処理装置に割り振るために、例えば全ての分割データ領域を計算量の比重の大きい順番に並び替える必要はなく、演算負荷の徒な増加を回避することができる。

特に、請求項２に記載の発明は、前記算出段階は、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することを要旨とする。

同構成によれば、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することで、当該算出処理を追加しても、全体としての処理時間の増加を抑制することができる。
請求項３に記載の発明は、請求項１に記載の並列処理方法において、前記算出段階は、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することを要旨とする。
同構成によれば、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することで、当該算出処理を追加しても、全体としての処理時間の増加を抑制することができる。

請求項４に記載の発明は、請求項１〜請求項３のいずれか一項に記載の並列処理方法において、前記図形情報は、線分密度及びパターン密度の少なくとも一つであることを要旨とする。
請求項５に記載の発明は、半導体装置のレイアウトデータに基づくデータエリアを、格子状に複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階と、前記所定の判定閾値よりも大きい計算量の比重を
有する分割データ領域が前記データエリアの中心から所定の半径以内に収まっている場合に、前記データエリアの中心から一側回転方向に渦巻き状に並ぶ前記分割データ領域の順番で、前記複数の中央処理装置に割り振る処理順位決定段階とを備えたことを要旨とする。

同構成によれば、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域が前記データエリアの中心から所定の半径以内に収まっている場合に、各中央処理装置には、前記データエリアの中心から一側回転方向に渦巻き状に並ぶ前記分割データ領域の順番で割り振られ、図形処理される。一般に、演算処理機能ブロックを備える半導体装置の場合、該演算処理機能ブロックはレイアウト規模及びパターン密度が高く、一方、外部入出力機能ブロックはレイアウト規模及びパターン密度が低くなることが実績として得られている。従って、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域が前記データエリアの中心から所定の半径以内に収まっている場合に、該データエリアの中心部に前記演算処理機能ブロックが配置されたレイアウトであることが推定される。このとき、各中央処理装置には、前記データエリアの中心から一側回転方向に渦巻き状に並ぶ前記分割データ領域の順番で割り振られることで、概ね計算量の比重の大きい前記分割データ領域の順番で割り振られ、図形処理される。従って、各中央処理装置が最終段階で処理する分割データ領域は、その計算量の比重が小さくなることで、一の中央処理装置の図形処理中に他の中央処理装置の図形処理が完了し新たに割り振られる分割データ領域がなかったとしても、該他の中央処理装置に発生する待ち時間は低減される。従って、前記分割された複数の分割データ領域を、複数の中央処理装置による並列処理にて効率的に図形処理して描画データに変換することができる。

本発明では、半導体装置のレイアウトデータに基づくデータエリアが複数分割されてなる分割データ領域を、複数の中央処理装置による並列処理にて効率的に図形処理して描画データに変換することができる並列処理方法を提供することができる。

（第１の実施形態）
以下、本発明を具体化した第１の実施形態について図面に従って説明する。
図１は、本実施形態に係る並列処理方法を概略的に示す説明図である。同図に示すように、この並列処理に係るシステムは、複数（例えば４つ）の中央処理装置としてのプロセッサ１〜４と、これらプロセッサ１〜４を統括制御する並列処理計算機１１とを備えて構成される。なお、このシステムは、１台の計算機にこれらプロセッサ１〜４及び並列処理計算機１１を搭載した、いわゆるマルチＣＰＵマシンであってもよいし、例えばＬＡＮ環境下の複数台（４台）の計算機からなるマシンであってもよい。なお、図１では図示しないが、いずれの構成であっても、これらプロセッサ１〜４及び並列処理計算機１１の処理に係るプログラムを格納するための記憶領域（ＲＯＭ領域）及び処理結果を一時的に格納するためのワーキングエリア（メモリ）等が存在する。

そして、並列処理計算機１１は、レイアウトデータとしてのＧＤＳIIフォーマットファイルを入力して、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリア１２を複数の分割データ領域に分割する。ここでは、これら複数の分割データ領域は、データエリア１２を複数分割してなる縦ストライプＬ１〜Ｌ８となっている。これら縦ストライプＬ１〜Ｌ８は、その符号の昇順に図１の左から右に順番に配置されている。

次に、並列処理計算機１１は、各縦ストライプＬ１〜Ｌ８ごとにその図形情報を抽出するための図形検査を行う。具体的には、並列処理計算機１１は、情報抽出の負担が極力少なくなるよう、各縦ストライプＬ１〜Ｌ８の図形処理の中間データ（スリット法やラスタスキャン法により得られた線分情報）を、当該縦ストライプＬ１〜Ｌ８の図形情報として抽出する。

続いて、並列処理計算機１１は、各縦ストライプＬ１〜Ｌ８の図形情報に基づいて、該各縦ストライプＬ１〜Ｌ８の計算量の比重を算出する（算出段階）。
そして、並列処理計算機１１は、各縦ストライプＬ１〜Ｌ８の計算量の比重と所定の判定閾値とを大小比較する（比較段階）。そして、並列処理計算機１１は、上記所定の判定閾値よりも大きい計算量の比重を有する縦ストライプＬ１〜Ｌ８のみを該計算量の比重の大きい縦ストライプＬ１〜Ｌ８の順番で、前記複数のプロセッサ１〜４に割り振る（処理順位決定段階）。つまり、並列処理計算機１１は、各縦ストライプＬ１〜Ｌ８単位での優先順位を決定しており、プロセッサ１〜４は、各縦ストライプＬ１〜Ｌ８を１処理単位とする。

図１では、前記所定の判定閾値よりも大きい計算量の比重を有する２つの縦ストライプＬ４，Ｌ７について、該計算量の比重の大きい縦ストライプＬ７，Ｌ４からＬ１、Ｌ２の順番（丸付き数字の昇順）で、プロセッサ１〜４に割り振られる例を示している。なお、前記所定の判定閾値よりも小さい計算量の比重を有する残りの４つの縦ストライプＬ３、Ｌ５，Ｌ６，Ｌ８については、該計算量の比重の大きい順番での並び替えが行われることはなく、例えばその符号の昇順でプロセッサ１〜４にそのまま割り振られる。これは、例えば全ての縦ストライプＬ１〜Ｌ８を計算量の比重の大きい順番に並び替えることによる、演算負荷の徒な増加を回避するためである。

そして、上述の態様で縦ストライプＬ１〜Ｌ８の割り振られた各プロセッサ１〜４は、互いに並行して該当の縦ストライプＬ１〜Ｌ８を図形処理、例えば論理積処理、論理和処理、リサイズ処理、矩形分割処理等の図形演算を実行する。

以上により、全ての縦ストライプＬ１〜Ｌ８の図形処理が完了すると、並列処理計算機１１は、各プロセッサ１〜４により個別に図形処理された縦ストライプＬ１〜Ｌ８を統合して、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする。

図２は、このような並列処理方法を総括して示すフローチャートである。同図に示すように、このシステムは、レイアウトデータとしてＧＤＳIIフォーマットファイルを入力して（ステップ１１）、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリア１２を複数の縦ストライプＬ１〜Ｌ８に分割する（ステップ１２）。

続いて、このシステムは、縦ストライプＬ１〜Ｌ８ごとにその図形情報を抽出するための図形検査を行い（ステップ１３）、各縦ストライプＬ１〜Ｌ８の図形情報に基づいて、該各縦ストライプＬ１〜Ｌ８の計算量の比重を算出し、更に計算量の比重の大きい縦ストライプＬ１〜Ｌ８の順番で、前記複数のプロセッサ１〜４に割り振る（ステップ１４）。このとき、必要に応じステップ１２とステップ１３のフロー順が入れ替わって処理が行われてもよい。

そして、このシステムは、各プロセッサ１〜４による並列処理にて、縦ストライプＬ１〜Ｌ８の図形処理を実行する（ステップ１５）。
続いて、このシステムは、各プロセッサ１〜４により個別に図形処理された分割データ領域を統合する登録処理を実行し（ステップ１６）、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする（ステップ１７）。

次に、本実施形態の動作について、便宜的に構成を一部簡略化して説明する。
図３は、複数のプロセッサとしての２つのＣＰＵ１、ＣＰＵ２により、複数の縦ストライプとしての３つの分割データ領域「１」〜「３」を並列処理する態様を説明する説明図である。なお、同図において、横軸は各プロセッサの処理時間である。また、分割データ領域「１」は、計算量の比重がやや重いデータ領域となっており、分割データ領域「２」は、計算量の比重が軽いデータ領域となっている。また、分割データ領域「３」は、計算量の比重が重いデータ領域となっている。

ここで、このシステムによる処理が開始されると、ＣＰＵ１に計算量の比重が重い（一番重い）分割データ領域「３」が割り振られるとともに、ＣＰＵ２に計算量の比重がやや重い（次に重い）分割データ領域「１」が割り振られる。そして、時刻ｔ１において分割データ領域「１」の図形処理を完了したＣＰＵ２には、計算量の比重が軽い（一番軽い）分割データ領域「３」が割り振られる。そして、ＣＰＵ１、ＣＰＵ２は、概ね同時刻にそれぞれの図形処理を完了する。これにより、ＣＰＵ１、ＣＰＵ２それぞれに発生する待ち時間が抑制される。

以上詳述したように、本実施形態によれば、以下に示す効果が得られるようになる。
（１）本実施形態では、複数のプロセッサ１〜４による並列処理に際し、各プロセッサ１〜４には、計算量の比重の大きい縦ストライプ（分割データ領域）の順番で割り振られ、図形処理される。つまり、各縦ストライプは、予めその計算量の比重の大きさで順番付けされており、各プロセッサ１〜４は、計算量の比重の大きい縦ストライプから先行して図形処理することで、該処理の最終段階に計算量の比重の小さい縦ストライプを集中して図形処理することができる。そして、各プロセッサ１〜４が最終段階で処理する縦ストライプの計算量の比重が小さくなることで、一のプロセッサ１〜４の図形処理中に他のプロセッサ１〜４の図形処理が完了し新たに割り振られる縦ストライプがなかったとしても、該他のプロセッサ１〜４に発生する待ち時間は低減され、これらプロセッサ１〜４の図形処理を概ね同時に完了することができる。従って、前記分割された複数の縦ストライプを、複数のプロセッサ１〜４による並列処理にて効率的に図形処理して描画データに変換することができる。

（２）また、レイアウトデータを描画データに変換するための処理時間を短縮できることで、例えばファンドリービジネス（ＣＯＴビジネス）で必須となってきている描画前データのユーザ検図など、対象となる海外ユーザに対し処理時間短縮によるタイムリーな供給を実現することができる。さらに、処理時間短縮とスピーディな検図結果の確認をもって、レクチル製作の納期短縮にも貢献することができる。

（３）本実施形態では、複数のプロセッサ１〜４による並列処理に際し、各プロセッサ１〜４には、所定の判定閾値よりも大きい計算量の比重を有する縦ストライプのみ、計算量の比重の大きい順番で割り振られる。従って、前記所定の判定閾値よりも小さい計算量の比重を有する縦ストライプ、即ち他のプロセッサ１〜４に発生する待ち時間への影響が小さい縦ストライプについては、計算量の比重の大きい順番での各プロセッサ１〜４への割り振りが割愛される。このため、各プロセッサ１〜４に割り振るために、例えば全ての縦ストライプを計算量の比重の大きい順番に並び替える必要はなく、演算負荷の徒な増加を回避することができる。

（４）本実施形態では、各プロセッサ１〜４への割り振り単位（処理単位）である分割データ領域を、極めて簡易な形状である縦ストライプにすることができる。
（第２の実施形態）
以下、本発明を具体化した第２の実施形態について図面に従って説明する。なお、第２の実施形態は、各プロセッサ１〜４による並列処理と並行して、並列処理計算機１１による図形検査を行うように変更した構成であるため、第１の実施形態と同様の部分についてはその詳細な説明は省略する。

図４は、本実施形態に係る並列処理方法を概略的に示す説明図である。同図に示すように、並列処理計算機１１は、レイアウトデータとしてのＧＤＳIIフォーマットファイルを入力して、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリア１２を複数の分割データ領域に分割する。ここでは、これら複数の分割データ領域は、データエリア１２を複数分割してなる縦ストライプＬ１〜Ｌ８を順次、等間隔で横に区切って分割してなる格子状の領域１３となっている。

次に、並列処理計算機１１は、図４の左上の領域１３−１から下側に向かう順番でプロセッサ１〜４にそのまま割り振るとともに、図４の右下の領域１３―２から上側に向かう順番で該領域１３ごとにその図形情報を抽出するための図形検査を行う。具体的には、並列処理計算機１１は、情報抽出の精度が高くなるよう、各領域１３の図形処理の中間データ（スリット法やラスタスキャン法により得られた線分密度（線分数等）情報やその領域におけるパターン密度（パターン数、パターン占有率））を、当該領域１３の図形情報として抽出する。そして、並列処理計算機１１は、各領域１３の図形情報に基づいて、該各領域１３の計算量の比重を算出する（算出段階）。そして、並列処理計算機１１は、計算量の比重の大きい領域１３の順番で、前記複数のプロセッサ１〜４に割り振る（処理順位決定段階）。このとき、各領域１３の情報抽出の精度が高いことで、より細かな処理順位の調整が可能である。

一方、上述の態様で領域１３の割り振られた各プロセッサ１〜４は、互いに並行して該当の領域１３を図形処理する。つまり、並列処理計算機１１は、各プロセッサ１〜４による並列処理と並行して、図形検査及び処理順位決定等を行う。なお、図４では、処理の最初の段階で各プロセッサ１〜４にそのまま割り振られ、該各プロセッサ１〜４による処理が完了した領域１３に網目状のパターンを付して明示している。これら領域１３の処理時間を利用して、前記並列処理計算機１１による図形検査及び処理順位決定等が行われる。

なお、各プロセッサ１〜４には、当初、データエリア１２の配置順にそのまま領域１３が割り振られるため、各プロセッサ１〜４に対する計算量の比重の大きい順番での領域１３の割り振りは、該各プロセッサ１〜４が一方向から処理する領域１３に、前記並列処理計算機１１が逆方向から処理する領域１３が追いついた時点で開始してもよいし、該並列処理計算機１１が逆方向から処理する領域１３が一定数に達した時点で開始してもよい。

図４では、各プロセッサ１〜４の処理の中盤で、計算量の比重の大きい領域１３ａ，１３ｂ，１３ｃ，１３ｄがその順番（丸付き数字の昇順）で、プロセッサ１〜４に割り振られる例を示している。

以上により、全ての領域１３の図形処理が完了すると、並列処理計算機１１は、各プロセッサ１〜４により個別に図形処理された領域１３を統合して、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする。

以上詳述したように、本実施形態によれば、前記第１の実施形態における（１）（２）の効果に加えて以下に示す効果が得られるようになる。
（１）本実施形態では、各プロセッサ１〜４による各領域１３の一方向からの図形処理に並行して、他方向から該各領域１３に含まれる図形情報を抽出して、該各領域１３の計算量の比重を算出することで、当該算出処理を追加しても、全体としての処理時間の増加を抑制することができる。特に、図形情報の抽出段階で作成される各種データが処理順位決定のみでしか活用できない場合に有効である。

（２）本実施形態では、各プロセッサ１〜４への割り振り単位（処理単位）である分割データ領域を、極めて簡易な形状である格子状の領域１３にすることができる。
（第３の実施形態）
以下、本発明を具体化した第３の実施形態について図面に従って説明する。なお、第３の実施形態は、計算量の比重が大きい領域１３がデータエリア１２の中心部に集中する度合いを判断して、各プロセッサ１〜４に割り振る領域１３の順番を決定するように変更した構成であるため、第１及び第２の実施形態と同様の部分についてはその詳細な説明は省略する。

図５は、本実施形態に係る並列処理方法を概略的に示す説明図である。同図に示すように、並列処理計算機１１は、レイアウトデータとしてのＧＤＳIIフォーマットファイルを入力して、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリア１２を複数の分割データ領域に分割する。ここでは、これら複数の分割データ領域は、データエリア１２を複数分割してなる縦ストライプＬ１〜Ｌ８を順次、等間隔で横に区切って分割してなる格子状の領域１３となっている。

次に、並列処理計算機１１は、領域１３ごとにその図形情報を抽出するための図形検査を行う。なお、この図形情報の抽出段階で作成される各種データは、メモリに蓄えられ、その後の図形処理で活用可能であることで、該図形情報の抽出処理を追加しても、これに伴う全体としての演算負荷の増加、即ち全体としての処理時間の増加が抑制される。

続いて、並列処理計算機１１は、各領域１３の図形情報に基づいて、該各領域１３の計算量の比重を算出する（算出段階）。そして、並列処理計算機１１は、各領域１３の計算量の比重と所定の判定閾値とを大小比較し（比較段階）、該所定の判定閾値よりも大きい計算量の比重を有する領域１３を抽出する。

次に、並列処理計算機１１は、前記抽出された計算量の比重の大きい領域１３が、前記データエリア１２の中心から、例えば半径６０％の面積以内に収まっているかを判断する。そして、並列処理計算機１１は、抽出された計算量の比重の大きい領域１３が、データエリア１２の中心から半径６０％の面積以内に収まっている場合に、該データエリア１２の中心から一側回転方向（図５において破線で示した反時計回転方向）に渦巻き状に並ぶ領域１３の順番（丸付き数字の昇順）で、前記複数のプロセッサ１〜４に割り振る（処理順位決定段階）。これは、システムＬＳＩの場合、その演算処理機能ブロック（ＣＰＵ部）はレイアウト規模及びパターン密度が高く、一方、外部入出力機能ブロック（Ｉ／Ｏ部）はレイアウト規模及びパターン密度が低くなることが実績として得られていることによる。つまり、計算量の比重の大きい領域１３が、データエリア１２の中心から半径６０％の面積以内に収まっている場合には、並列処理計算機１１は、演算処理機能ブロックがデータエリア１２の中心部に配置されたレイアウトであると判断して、前記データエリア１２の中心を基準に上述の態様で各領域１３の優先順位を決定している。

そして、上述の態様で領域１３の割り振られた各プロセッサ１〜４は、互いに並行して該当の領域１３を図形処理する。
以上により、全ての領域１３の図形処理が完了すると、並列処理計算機１１は、各プロセッサ１〜４により個別に図形処理された領域１３を統合して、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする。

図６は、このような並列処理方法を総括して示すフローチャートである。同図に示すように、このシステムは、レイアウトデータとしてＧＤＳIIフォーマットファイルを入力して（ステップ２１）、該ファイルを内部フォーマットに変換するとともに、該変換に合わせて処理対象となるデータエリア１２を複数の領域１３に分割する（ステップ２２）。

続いて、このシステムは、領域１３ごとにその図形情報を抽出するための図形検査を行い（ステップ２３）、各領域１３の図形情報に基づいて、該各領域１３の計算量の比重を算出し、更に計算量の比重の大きい領域１３が、前記データエリア１２の中心から、例えば半径６０％の面積以内に収まっているかを判断する（ステップ２４）。

そして、このシステムは、計算量の比重の大きい領域１３が、前記データエリア１２の中心から半径６０％の面積以内に収まっていると判断されると、該データエリア１２の中心から一側回転方向に渦巻き状に並ぶ領域１３の順番で、各プロセッサ１〜４に割り振り（ステップ２５）、一方、前記データエリア１２の中心から半径６０％の面積以内に収まっていないと判断されると、予め設定されているデータエリア１２の配置順、例えば図４の左上の領域１３−１から下側に向かう順番のまま、各プロセッサ１〜４に割り振る。

そして、このシステムは、各プロセッサ１〜４による並列処理にて、領域１３の図形処理を実行する（ステップ２６）。
続いて、このシステムは、各プロセッサ１〜４により個別に図形処理された分割データ領域を統合する登録処理を実行し（ステップ２７）、所要の描画データ（例えばＭＥＢＥＳフォーマットファイル）へとフォーマッティングする（ステップ２８）。

以上詳述したように、本実施形態によれば、前記第１の実施形態における（２）の効果に加えて以下に示す効果が得られるようになる。
（１）本実施形態では、前記所定の判定閾値よりも大きい計算量の比重を有する領域１３がデータエリア１２の中心から半径６０％の面積以内に収まっている場合、即ち演算処理機能ブロックがデータエリア１２の中心部に配置されたレイアウトであると判断された場合に、各プロセッサ１〜４には、データエリア１２の中心から一側回転方向に渦巻き状に並ぶ領域１３の順番で割り振られる。これにより、各プロセッサ１〜４には、概ね計算量の比重の大きい領域１３の順番で割り振られ、図形処理される。従って、各プロセッサ１〜４が最終段階で処理する領域１３は、その計算量の比重が小さくなることで、一のプロセッサ１〜４の図形処理中に他のプロセッサ１〜４の図形処理が完了し新たに割り振られる領域１３がなかったとしても、該他のプロセッサ１〜４に発生する待ち時間は低減され、これらプロセッサ１〜４の図形処理を概ね同時に完了することができる。従って、前記分割された複数の領域１３を、複数のプロセッサ１〜４による並列処理にて効率的に図形処理して描画データに変換することができる。

（２）本実施形態では、各領域１３の計算量の比重の大きさに基づいて厳密に該各領域１３を並べ替えることなく、各プロセッサ１〜４に概ね計算量の比重の大きい順番で割り振ることができる。このため、並べ替えのための演算負荷を軽減することができる。

なお、上記実施形態は以下のように変更してもよい。
・前記第１の実施形態において、各プロセッサ１〜４への割り振り単位（処理単位）である分割データ領域は、領域１３であってもよい。この場合、並列処理計算機１１は、各領域１３の図形情報に基づいて、該各領域１３の計算量の比重を算出する。そして、並列処理計算機１１は、計算量の比重の大きい領域１３の順番で、前記複数のプロセッサ１〜４に割り振る。なお、領域１３の図形情報の抽出段階で作成される各種データをメモリに蓄え、その後の図形処理で活用させるようにすれば、該図形情報の抽出処理を追加しても、これに伴う全体としての演算負荷の増加、即ち全体としての処理時間の増加が抑制される。

・前記第２の実施形態において、領域１３の図形情報の抽出段階で作成される各種データをメモリに蓄え、その後の図形処理で活用させるようにすれば、該図形情報の抽出処理を追加しても、これに伴う全体としての演算負荷の増加、即ち全体としての処理時間の増加が抑制される。

・前記第２の実施形態において、各領域１３の計算量の比重と所定の判定閾値とを大小比較し、該所定の判定閾値よりも大きい計算量の比重を有する領域１３のみを、該計算量の比重の大きい順番で、複数のプロセッサ１〜４に割り振るようにしてもよい。

・前記第３の実施形態において、抽出された計算量の比重の大きい領域１３が、データエリア１２の中心から半径６０％の面積以内に収まっている場合に、該データエリア１２の中心から他側回転方向（図５において時計回転方向）に渦巻き状に並ぶ領域１３の順番で、前記複数のプロセッサ１〜４に割り振ってもよい。

・前記第３の実施形態において、計算量の比重が大きい領域１３がデータエリア１２の中心部に集中する度合いの判断に係る半径は、６０％に限定されるものではない。
・前記第３の実施形態において、設計レイアウト段階において何らかの手段により事前にＣＰＵ部がチップの６０％に収まっている情報を入手できる場合には、計算能力の比重判断を行うことなく、該データエリア１２の中心から一側回転方向に渦巻き状に並ぶ領域１３の順番で並列による図形処理を開始してもよい。

・前記各実施形態において、各分割データ領域の計算量の比重の算出に際し、図形情報として特徴的なパラメータを抽出してもよい。具体的には、同一図形の繰り返し配置数、補正禁止枠の占有率、プログラム固有に所有する最適化された配置情報などである。

・前記各実施形態において、並列処理に係るプロセッサは、２〜３つであってもよいし、５つ以上であってもよい。
次に、上記実施形態及び別例から把握できる技術的思想について以下に追記する。
（付記１）
半導体装置のレイアウトデータに基づくデータエリアを、複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、
前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、
前記算出された各分割データ領域の計算量の比重に基づいて、前記複数の中央処理装置に割り振る処理順位決定段階とを備えたことを特徴とする並列処理方法。
（付記２）
付記１に記載の並列処理方法において、
前記図形情報は、線分数及びパターン密度の少なくとも一つであることを特徴とする並列処理方法。
（付記３）
付記１又は２に記載の並列処理方法において、
前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階を備え、
前記処理順位決定段階は、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域のみを、該計算量の比重の大きい順番で、前記複数の中央処理装置に割り振ることを特徴とする並列処理方法。
（付記４）
付記１〜３のいずれか一項に記載の並列処理方法において、
前記複数の分割データ領域は、前記データエリアを複数分割してなる縦ストライプであることを特徴とする並列処理方法。
（付記５）
付記１〜３のいずれか一項に記載の並列処理方法において、
前記複数の分割データ領域は、前記データエリアを複数分割してなる縦ストライプを等間隔で横に区切ったデータ領域であることを特徴とする並列処理方法。
（付記６）
付記１〜３のいずれか一項に記載の並列処理方法において、
前記抽出された各分割データ領域に含まれる図形情報を、該分割データ領域の割り振られた各中央処理装置の図形処理で活用することを特徴とする並列処理方法。
（付記７）
付記１〜３のいずれか一項に記載の並列処理方法において、
前記算出段階は、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することを特徴とする並列処理方法。
（付記８）
半導体装置のレイアウトデータに基づくデータエリアを、格子状に複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、
前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、
前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階と、
前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域が前記データエリアの中心から所定の半径以内に収まっている場合に、前記データエリアの中心から一側回転方向に渦巻き状に並ぶ前記分割データ領域の順番で、前記複数の中央処理装置に割り振る処理順位決定段階とを備えたことを特徴とする並列処理方法。

本発明に係る第１の実施形態を示す説明図。第１の実施形態の処理態様を示すフローチャート。第１の実施形態の動作を示す説明図。本発明に係る第２の実施形態を示す説明図。本発明に係る第３の実施形態を示す説明図。第３の実施形態の処理態様を示すフローチャート。従来形態の処理態様を示すフローチャート。従来形態の動作を示す説明図。

符号の説明

１〜４…プロセッサ
１１並列処理計算機
１２データエリア
１３…領域
Ｌ１〜Ｌ８縦ストライプ

Claims

半導体装置のレイアウトデータに基づくデータエリアを、複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、
前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、
前記算出された各分割データ領域の計算量の比重に基づいて、前記複数の中央処理装置に割り振る処理順位決定段階と、
前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階とを備え、
前記処理順位決定段階は、前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域のみを、該計算量の比重の大きい順番で、前記複数の中央処理装置に割り振ることを特徴とする並列処理方法。
半導体装置のレイアウトデータに基づくデータエリアを、複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、
前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、
前記算出された各分割データ領域の計算量の比重に基づいて、前記複数の中央処理装置に割り振る処理順位決定段階とを備え、
前記算出段階は、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することを特徴とする並列処理方法。
請求項１に記載の並列処理方法において、
前記算出段階は、前記各中央処理装置による前記各分割データ領域の一方向からの図形処理に並行して、他方向から前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出することを特徴とする並列処理方法。
請求項１〜請求項３のいずれか一項に記載の並列処理方法において、
前記図形情報は、線分密度及びパターン密度の少なくとも一つであることを特徴とする並列処理方法。
半導体装置のレイアウトデータに基づくデータエリアを、格子状に複数の分割データ領域に分割し、複数の中央処理装置による並列処理にて前記分割された複数の分割データ領域を図形処理して、描画データに変換する並列処理方法において、
前記各分割データ領域に含まれる図形情報を抽出して、該各分割データ領域の計算量の比重を算出する算出段階と、
前記算出された各分割データ領域の計算量の比重と所定の判定閾値とを大小比較する比較段階と、
前記所定の判定閾値よりも大きい計算量の比重を有する分割データ領域が前記データエリアの中心から所定の半径以内に収まっている場合に、前記データエリアの中心から一側回転方向に渦巻き状に並ぶ前記分割データ領域の順番で、前記複数の中央処理装置に割り振る処理順位決定段階とを備えたことを特徴とする並列処理方法。