(57)【要約】【課題】半導体装置上のレイアウトにおける配線の交差を判定する配線交差判定プログラムおよび配線交差判定方法において、効率的な交差判定を行うこと。【解決手段】中央近傍から周辺方向へ向かう第１、第２の配線間の交差判定ため、第１の配線の始点を原点として該第１の配線の終点の横座標、縦座標、および第２の配線の始点および終点の横座標、縦座標を取得し、第１の配線の終点の横座標、縦座標を用いて第１の配線に対応するダイバージェンスとセグメントとからなる第１のマンハッタン線を得、第２の配線の始点および終点の横座標、縦座標を用いて同様に第２の配線に対応する第２のマンハッタン線を得、第１のマンハッタン線と第２のマンハッタン線とが交差しない場合を、第１の配線と第２の配線とは交差しない配置であると判定し、交差する場合を、第１の配線と第２の配線とは交差する配置である可能性があると判定する。【選択図】図１
2006260172.tif 000002
【特許請求の範囲】
【請求項１】
半導体装置のレイアウト面の中央近傍から周辺方向へ向かう第１、第２の配線間の交差判定を行う配線交差判定プログラムであって、
前記第１の配線の始点を原点として、該第１の配線の終点の横座標、縦座標を取得する第１のステップと、
前記第１の配線の始点を原点として、前記第２の配線の始点および終点の横座標、縦座標を取得する第２のステップと、
前記取得された第１の配線の終点の前記横座標、縦座標を用いて、前記第１の配線に対応する第１のダイバージェンスと第１のセグメントとからなる第１のマンハッタン線を得る第３のステップと、
前記取得された第２の配線の始点および終点の前記横座標、縦座標を用いて、前記第２の配線に対応する第２のダイバージェンスと第２のセグメントとからなる第２のマンハッタン線を得る第４のステップと、
前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差しない場合を、前記第１の配線と前記第２の配線とは交差しない配置であると判定する第５のステップと、
前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差する場合を、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定する第６のステップと
をコンピュータに実行させる配線交差判定プログラム。
【請求項２】
前記半導体装置の前記レイアウト面の中央近傍の点を仮想原点にとった第２の座標系における、前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値より大きいとき、前記第１、第２のダイバージェンスは前記始点に発する横方向、前記第１、第２のセグメントは前記終点に終端する縦方向のそれぞれ線であり、前記第２の座標系における前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値より小さいとき、前記第１、第２のダイバージェンスは前記始点に発する縦方向、前記第１、第２のセグメントは前記終点に終端する横方向のそれぞれ線であるとすることを特徴とする請求項１記載の配線交差判定プログラム。
【請求項３】
前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定がされたとき、前記第１、第２のダイバージェンスが横方向である条件の下で、
前記第１の配線の終点の前記縦座標と前記第２の配線の終点の前記縦座標とが同一符号でありかつ前記第２の配線の始点の前記縦座標が正でありかつ前記第２の配線の終点の前記縦座標が前記第１の配線の終点の前記縦座標以上のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップと、
前記第１の配線の終点の前記縦座標と前記第２の配線の終点の前記縦座標とが同一符号でありかつ前記第２の配線の始点の前記縦座標が負でありかつ前記第２の配線の終点の前記縦座標が前記第１の配線の終点の前記縦座標以下のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップとをさらにコンピュータに実行させ、
前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定がされたとき、前記第１、第２のダイバージェンスが縦方向である条件の下で、
前記第１の配線の終点の前記横座標と前記第２の配線の終点の前記横座標とが同一符号でありかつ前記第２の配線の始点の前記横座標が正でありかつ前記第２の配線の終点の前記横座標が前記第１の配線の終点の前記横座標以上のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップと、
前記第１の配線の終点の前記横座標と前記第２の配線の終点の前記横座標とが同一符号でありかつ前記第２の配線の始点の前記横座標が負でありかつ前記第２の配線の終点の前記横座標が前記第１の配線の終点の前記横座標以下のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップとをさらにコンピュータに実行させる
請求項２記載の配線交差判定プログラム。
【請求項４】
複数の配線それぞれに番号を与え該番号の最も若いものを前記第１の配線と設定し、前記番号の次に若いものを前記第２の配線として設定するステップをコンピュータに実行させてから、前記第１のステップ以下をステップｉとしてコンピュータに実行させ、次に、前記番号のさらに次に若いものを前記第２の配線として設定するステップをコンピュータに実行させてから、前記第１のステップ以下をステップｉｉとしてコンピュータに実行させ、以下、同様に前記第２の配線として最後の番号のものについてまで前記第１のステップ以下をステップｉｉｉとしてコンピュータに実行させ、
さらに、前記番号の最も若いもの、前記番号の次に若いものを、それぞれ、番号がひとつ増加したものに置き換えて、前記ステップｉ、ｉｉ、ｉｉｉをステップａとしてコンピュータに実行させ、
さらに、前記番号の最も若いもの、前記番号の次に若いものを、それぞれ、番号がさらにひとつ増加したものに置き換えて、前記ステップａをコンピュータに実行させ、以下、同様に前記第１の配線として最後の番号のものについてまで前記ステップａをコンピュータに実行させる
請求項１記載の配線交差判定プログラム。
【請求項５】
半導体装置のレイアウト面の中央近傍から周辺方向へ向かう第１、第２の配線間の交差判定を行う配線交差判定方法であって、
前記第１の配線の始点を原点として、該第１の配線の終点の横座標、縦座標を取得する第１のステップと、
前記第１の配線の始点を原点として、前記第２の配線の始点および終点の横座標、縦座標を取得する第２のステップと、
前記取得された第１の配線の終点の前記横座標、縦座標を用いて、前記第１の配線に対応する第１のダイバージェンスと第１のセグメントとからなる第１のマンハッタン線を得る第３のステップと、
前記取得された第２の配線の始点および終点の前記横座標、縦座標を用いて、前記第２の配線に対応する第２のダイバージェンスと第２のセグメントとからなる第２のマンハッタン線を得る第４のステップと、
前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差しない場合を、前記第１の配線と前記第２の配線とは交差しない配置であると判定する第５のステップと、
前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差する場合を、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定する第６のステップと
を具備することを特徴とする配線交差判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体装置上のレイアウトにおける配線の交差を判定する配線交差判定プログラムおよび配線交差判定方法に係り、特に、交差判定の効率化に好適な配線交差判定プログラムおよび配線交差判定方法に関する。
【背景技術】
【０００２】
半導体装置上のレイアウトにおいて、配線が交差するか否かを判定することは、限られた配線層数の半導体装置では重要な課題である。一般に、レイアウト面の中央近傍から周辺方向に向かう配線は、半導体装置の外部接続端子に接続される配線である。近年、半導体装置の外部接続端子数が増加しており、このような配線の交差を簡便に判定できないとタイムリーな半導体装置の開発が妨げられる。すなわち、外部接続端子数が比較的少ないうちは、実際の配線配置を行い配線の可否を判断することで間に合ったが、外部接続端子数が増加するに従いこのような方法は通用しなくなりつつある。
【０００３】
より具体的には、交差を避けるには配線が異常な形状や引き回しにならざるを得ない場合を実際の配線を行う前に簡便により分けられると、このような好ましくない配線設計を避ける意味で好都合である。なお、本願のような配線の交差判定とは異なるが、配線ルートの決定を自動化する技術には下記特許文献１記載のものがある。同文献には、配線が異常な形状や引き回しになるなどのような好ましくない配線設計になるのを避けることについての言及はない。
【特許文献１】特開２００１−３５０８１３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、半導体装置上のレイアウトにおける配線の交差を判定する配線交差判定プログラムおよび配線交差判定方法において、効率的な交差判定が可能な配線交差判定プログラムおよび配線交差判定方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一態様に係る配線交差判定プログラムは、半導体装置のレイアウト面の中央近傍から周辺方向へ向かう第１、第２の配線間の交差判定を行う配線交差判定プログラムであって、前記第１の配線の始点を原点として、該第１の配線の終点の横座標、縦座標を取得する第１のステップと、前記第１の配線の始点を原点として、前記第２の配線の始点および終点の横座標、縦座標を取得する第２のステップと、前記取得された第１の配線の終点の前記横座標、縦座標を用いて、前記第１の配線に対応する第１のダイバージェンスと第１のセグメントとからなる第１のマンハッタン線を得る第３のステップと、前記取得された第２の配線の始点および終点の前記横座標、縦座標を用いて、前記第２の配線に対応する第２のダイバージェンスと第２のセグメントとからなる第２のマンハッタン線を得る第４のステップと、前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差しない場合を、前記第１の配線と前記第２の配線とは交差しない配置であると判定する第５のステップと、前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差する場合を、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定する第６のステップとをコンピュータに実行させる。
【０００６】
また、本発明の一態様に係る配線交差判定方法は、半導体装置のレイアウト面の中央近傍から周辺方向へ向かう第１、第２の配線間の交差判定を行う配線交差判定方法であって、前記第１の配線の始点を原点として、該第１の配線の終点の横座標、縦座標を取得する第１のステップと、前記第１の配線の始点を原点として、前記第２の配線の始点および終点の横座標、縦座標を取得する第２のステップと、前記取得された第１の配線の終点の前記横座標、縦座標を用いて、前記第１の配線に対応する第１のダイバージェンスと第１のセグメントとからなる第１のマンハッタン線を得る第３のステップと、前記取得された第２の配線の始点および終点の前記横座標、縦座標を用いて、前記第２の配線に対応する第２のダイバージェンスと第２のセグメントとからなる第２のマンハッタン線を得る第４のステップと、前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差しない場合を、前記第１の配線と前記第２の配線とは交差しない配置であると判定する第５のステップと、前記得られた第１のマンハッタン線と前記得られた第２のマンハッタン線とが交差する場合を、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定する第６のステップとを具備することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、半導体装置上のレイアウトにおける配線の交差を判定する配線交差判定プログラムおよび配線交差判定方法において効率的な交差判定が可能になる。
【発明を実施するための最良の形態】
【０００８】
本発明の一態様に係る配線交差判定プログラムまたは配線交差判定方法では、交差判定がされる第１、第２の配線に対応して、ダイバージェンスとセグメントとからなるマンハッタン線をそれぞれ得る。そして、これらのマンハッタン線同士が交差しない場合を、第１、第２の配線は交差しない配置であると判定し、交差する場合を、第１、第２の配線は交差する配置である可能性があると判定する。マンハッタン線の交差／非交差は、後述するが、第１、第２の配線の始点、終点の座標が特定できれば簡単な場合分けにより容易に判定ができる。したがって、効率的な交差判定が可能になる。なお、「第１、第２の配線が交差する」とは、その状態において同一配線層上で第１、第２の配線をレイアウト設計すると、第１、第２の配線の少なくとも一方が異常な引き回しになることと等価である。異常な引き回しとは、半導体装置のレイアウト面の中央近傍から周辺方向へ単調に向かうだけではなく、戻り（回り込み）が発生することをいう。
【０００９】
本発明の実施態様として、前記半導体装置の前記レイアウト面の中央近傍の点を仮想原点にとった第２の座標系における、前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値より大きいとき、前記第１、第２のダイバージェンスは前記始点に発する横方向、前記第１、第２のセグメントは前記終点に終端する縦方向のそれぞれ線であり、前記第２の座標系における前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値より小さいとき、前記第１、第２のダイバージェンスは前記始点に発する縦方向、前記第１、第２のセグメントは前記終点に終端する横方向のそれぞれ線である、とすることができる。第２の座標系における第１、第２の配線の終点の座標によらず、一律な判定を可能とするものである。
【００１０】
ここで、前記半導体装置の前記レイアウト面の中央近傍の点を仮想原点にとった前記第２の座標系における、前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値と等しいとき、前記第１、第２のダイバージェンスは前記始点に発する横方向、前記第１、第２のセグメントは前記終点に終端する縦方向のそれぞれ線である、とすることができる。「第１、第２の配線の終点の座標が、その横座標の絶対値がその縦座標の絶対値と等しい」ときにおけるダイバージェンスおよびセグメントの方向設定を上記の前者に含めるやり方である。逆に、「前記第１、第２の配線の前記終点の座標が、その横座標の絶対値がその縦座標の絶対値と等しい」とき、前記第１、第２のダイバージェンスは前記始点に発する縦方向、前記第１、第２のセグメントは前記終点に終端する横方向のそれぞれ線である、と設定してもよい。
【００１１】
また、実施態様として、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定がされたとき、前記第１、第２のダイバージェンスが横方向である条件の下で、前記第１の配線の終点の前記縦座標と前記第２の配線の終点の前記縦座標とが同一符号でありかつ前記第２の配線の始点の前記縦座標が正でありかつ前記第２の配線の終点の前記縦座標が前記第１の配線の終点の前記縦座標以上のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップと、前記第１の配線の終点の前記縦座標と前記第２の配線の終点の前記縦座標とが同一符号でありかつ前記第２の配線の始点の前記縦座標が負でありかつ前記第２の配線の終点の前記縦座標が前記第１の配線の終点の前記縦座標以下のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップとをさらにコンピュータに実行させ、前記第１の配線と前記第２の配線とは交差する配置である可能性があると判定がされたとき、前記第１、第２のダイバージェンスが縦方向である条件の下で、前記第１の配線の終点の前記横座標と前記第２の配線の終点の前記横座標とが同一符号でありかつ前記第２の配線の始点の前記横座標が正でありかつ前記第２の配線の終点の前記横座標が前記第１の配線の終点の前記横座標以上のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップと、前記第１の配線の終点の前記横座標と前記第２の配線の終点の前記横座標とが同一符号でありかつ前記第２の配線の始点の前記横座標が負でありかつ前記第２の配線の終点の前記横座標が前記第１の配線の終点の前記横座標以下のとき、前記第１の配線と前記第２の配線とは交差しない配置であると判定するステップとをさらにコンピュータに実行させる、としてもよい。
【００１２】
この実施態様は、「第１の配線と第２の配線とは交差する配置である可能性がある」場合をさらに詳細に場合分けして判定するものである。すなわち、後述するように、可能性がある場合であっても交差しない場合があるので所定の条件に照らし合わせこれを判定する。
【００１３】
ここで、前記第１の配線と前記第２の配線とは交差しない配置であるとの判定が得られないとき、前記第１の配線と前記第２の配線とは交差する配置であるとの結果を出力するステップをさらにコンピュータに実行させるようにしてもよい。交差の可能性より踏み込んで交差することを判定として出力するものである。
【００１４】
また、実施態様として、複数の配線それぞれに番号を与え該番号の最も若いものを前記第１の配線と設定し、前記番号の次に若いものを前記第２の配線として設定するステップをコンピュータに実行させてから、前記第１のステップ以下をステップｉとしてコンピュータに実行させ、次に、前記番号のさらに次に若いものを前記第２の配線として設定するステップをコンピュータに実行させてから、前記第１のステップ以下をステップｉｉとしてコンピュータに実行させ、以下、同様に前記第２の配線として最後の番号のものについてまで前記第１のステップ以下をステップｉｉｉとしてコンピュータに実行させ、さらに、前記番号の最も若いもの、前記番号の次に若いものを、それぞれ、番号がひとつ増加したものに置き換えて、前記ステップｉ、ｉｉ、ｉｉｉをステップａとしてコンピュータに実行させ、さらに、前記番号の最も若いもの、前記番号の次に若いものを、それぞれ、番号がさらにひとつ増加したものに置き換えて、前記ステップａをコンピュータに実行させ、以下、同様に前記第１の配線として最後の番号のものについてまで前記ステップａをコンピュータに実行させる、としてもよい。これにより、複数の配線のすべての組み合わせについて、交差判定を行うことができる。
【００１５】
以上を踏まえ、以下では本発明の実施形態を図面を参照しながら説明する。図１は、本発明の一実施形態に係る配線交差判定プログラムの概略フローチャートである。以下、図１に示す流れに沿ってこのプログラムの内容を説明する。説明中で適宜、図２ないし図７を参照する。
【００１６】
まず、交差判定を行うふたつの配線それぞれの半導体装置のレイアウト面における象限をそれらの終点の座標から判断する（ステップ１１）。半導体装置のレイアウト面は、例えば図２に示されるようになっている。図２は、半導体装置のレイアウト面における配線の象限を説明するための図である。すなわち、レイアウト面２０には、そのほぼ中央を原点とするＵＶ座標系（後述するＸＹ座標系と区別のため第２の座標系ともいう）が設定されており、直線Ｕ＝Ｖおよび直線Ｕ＝−Ｖにより領域が４つ象限に区切られる。便宜上、これらの直線の上側９０°扇状領域を第１象限とし、第１象限から右回りに、第２象限、第３象限、第４象限と定義する。以下、交差判定を行うふたつの配線は同一の象限にあるものとする。
【００１７】
交差判定する各配線は、レイアウト面２０の中央近傍から周辺方向に向かって配置されている。例えば図２中に示す配線ａ〜ｅである。実際の配線は図示するような直線だけでなく、中央近傍（始点）から周辺方向（終点）への経路が、ＵＶ座標系の各成分で見た場合にその絶対値が単調な増加となる場合（すなわち戻り（回り込み）が発生しない場合）を含む。各配線の象限は、その終点がどの象限に位置するかで判断する。直線Ｕ＝Ｖ上または直線Ｕ＝−Ｖ上に位置する場合は、その直線に面するいずれかの領域と判断してよいが、ここでは便宜上、第２象限または第４象限であるとして扱う。
【００１８】
ふたつの配線についてその領域が判断できると、それらの配線に対応するマンハッタン線のダイバージェンスおよびセグメントの向きが特定できる（同ステップ）。例えば図２中に示した配線ａ〜ｅは、図３に示すようなダイバージェンスＤおよびセグメントＳの向きとなる。図３は、図２中に示す各配線ａ〜ｅのマンハッタン線（ダイバージェンスとセグメントとからなる）を示す図である。すなわち、第１、第３象限では、ダイバージェンスは縦方向、セグメントは横方向、第２、第４象限では、反対に、ダイバージェンスは横方向、セグメントは縦方向である。なお、ダイバージェンスは、配線の始点に発し、セグメントは配線の終点に終端する、それぞれＵ軸またはＶ軸に平行な線分である。
【００１９】
次に、交差判定する配線の一方（第１の配線）の始点を原点として、その終点のｘ座標（横座標）、ｙ座標（縦座標）を取得する（ステップ１２）。ＸＹ座標系の座標（ｘ，ｙ）は、ＵＶ座標系による座標を平行移動したものとして得られる。これにより、例えば第１の配線が第４象限にあるとすると、第１の配線は、図４中に示す実線のようなダイバージェンスＤとセグメントＳとからなるマンハッタン線として認知される。図４は、交差判定するふたつの配線間の座標定義を示す図である。ここで、始点座標＝（ＤＡ１，ＳＡ１）＝（０，０）であり、終点座標＝（ＤＡ２，ＳＡ２）である。以下、第１の配線のダイバージェンスＤとセグメントＳとからなるマンハッタン線（第１のマンハッタン線：以下実線で示す）を親マンハッタン線ともいう。また、第１のマンハッタン線のダイバージェンス、セグメントは、それぞれ第１のダイバージェンス、第１のセグメントである。
【００２０】
同様に、上記第１の配線の始点を原点として、交差判定する他方の配線（第２の配線）の始点および終点のｘ座標、ｙ座標を取得する（ステップ１３）。この座標（ｘ，ｙ）も、それぞれ、ＵＶ座標系による座標を平行移動したものとして得られる。これにより、例えば第２の配線が第４象限にあるとすると、第２の配線は、図４中に示す破線のようなダイバージェンスＤとセグメントＳとからなるマンハッタン線として認知される。ここで、始点座標＝（ＤＢ１，ＳＢ１）であり、終点座標＝（ＤＢ２，ＳＢ２）である。以下、第２の配線のダイバージェンスＤとセグメントＳとからなるマンハッタン線（第２のマンハッタン線：以下破線で示す）を子マンハッタン線ともいう。また、第２のマンハッタン線のダイバージェンス、セグメントは、それぞれ第２のダイバージェンス、第２のセグメントである。
【００２１】
次に、第１のマンハッタン線と第２のマンハッタン線との交差を、上記取得された各ｘ座標、ｙ座標から判定する（ステップ１４）。具体的には、各ｘ座標、ｙ座標の条件を吟味すると、図５に示すように、交差が発生しない場合（＃９）、交差する場合（＃３、＃４、＃７、＃８）、交差の可能性がある場合（＃１、＃２、＃５、＃６）に分類され得るので、この判定表に従う。図５は、ふたつの配線の座標関係によるマンハッタン線の状態および配線交差の判定結果を示す図である（ただし、簡単のためここではＤＢ１＝０として結果を得ている。）。図５は、交差判定する配線が第４象限にある場合を図示しているが、同様に、他の象限についても判定表をあらかじめ作成しておくことができる。
【００２２】
ステップ１４における判定結果として、第１、第２のマンハッタン線が交差しない場合は（ステップ１５のＹ）、第１の配線と第２の配線とは交差しないと判定する（ステップ１９）。これは、少なくともマンハッタン線で交差しなければ、マンハッタン線に対応する、レイアウト面の中央近傍から周辺方向に向かう配線間でも交差は発生しない、と作図で容易に結論づけられるからである。
【００２３】
ステップ１４における判定結果として、第１、第２のマンハッタン線が交差しないと確定的には言えない場合は（ステップ１５のＮ）、上記取得された各ｘ座標、ｙ座標の条件をさらに吟味し、交差判定を行う（ステップ１６）。ここで、図５に示す判定表で＃３、＃４、＃７、＃８に分類された場合は、配線として交差は確定している（図７（ｃ）で補足する）ので、交差の可能性がある＃１、＃２、＃５、＃６の場合が詳細判定の対象である。
【００２４】
図６は、図５における「交差の可能性あり」の場合（＃１、＃２、＃５、＃６）をさらに座標関係で場合分けしたマンハッタン線および配線交差の判定結果を示す図である（ただし、簡単のためここではＤＢ１＝０として結果を得ている。）。図６に示すように、上記の＃１、＃２、＃５、＃６の場合は、図示する条件２の違いで、配線交差の判定結果は変化する。これを図７を参照して説明する。図７は、図６中に示す＃１−１、＃１−２、および図５中に示す＃３の条件における配線の状態の説明図である。
【００２５】
＃１−１の場合は、図７（ａ）に示すように、第１の配線（実線）と第２の配線（破線）とは交差する。交差を避けようとすると、第２の配線に戻り（回り込み）が発生する。ここで「戻り（回り込み）」についてはすでに定義した通りである。＃１−１の場合に対して、＃１−２の場合は、図７（ｂ）に示す作図で明らかなように、マンハッタン線では交差するが、配線としては交わらない配置が可能である。＃２−１、＃２−２、＃５−１、＃５−２、＃６−１、＃６−２の場合も同様である。なお、図６は、交差判定する配線が第４象限にある場合を図示しているが、同様に、他の象限についても判定表をあらかじめ作成しておくことができる。
【００２６】
図７（ｃ）は、図５の＃３の場合を参考として示したものである。この場合は、図示するように、常に（＝他の条件によらず）第１の配線（実線）と第２の配線（破線）とは交差する。交差を避けようとすると、第２の配線に戻り（回り込み）が発生する。図５の＃４、＃７、＃８の場合も同様である。
【００２７】
図６における＃１−２、＃２−２＃、＃５−２、＃６−２の場合（配線が交差しないと判定される場合）を一般化すると、第１、第２のダイバージェンスが横方向である条件の下（第２、第４象限）では、１）第１の配線の終点のｙ座標と第２の配線の終点のｙ座標とが同一符号でありかつ第２の配線の始点のｙ座標が正でありかつ第２の配線の終点のｙ座標が第１の配線の終点のｙ座標以上の（場合によっては「以上の」を「超える」と考えてもよい）ときと、２）第１の配線の終点のｙ座標と第２の配線の終点のｙ座標とが同一符号でありかつ第２の配線の始点のｙ座標が負でありかつ第２の配線の終点のｙ座標が第１の配線の終点のｙ座標以下（場合によっては「以下」を「未満」と考えてもよい）のときとである。
【００２８】
また、第１、第２のダイバージェンスが縦方向である条件の下（第１、第３象限）では、１）第１の配線の終点のｘ座標と第２の配線の終点のｘ座標とが同一符号でありかつ第２の配線の始点のｘ座標が正でありかつ第２の配線の終点のｘ座標が第１の配線の終点のｘ座標以上の（場合によっては「以上の」を「超える」と考えてもよい）ときと、２）第１の配線の終点のｘ座標と第２の配線の終点のｘ座標とが同一符号でありかつ第２の配線の始点のｘ座標が負でありかつ第２の配線の終点のｘ座標が第１の配線の終点のｘ座標以下（場合によっては「以下」を「未満」と考えてもよい）のときとである。
【００２９】
ステップ１６における判定として、第１、第２の配線が交差しないとの結果が得られた場合は（ステップ１７のＹ）、第１の配線と第２の配線とは交差しないと判定を出力する（ステップ１９）。また、ステップ１６における判定を含めて第１、第２の配線が交差するとの結果が得られた場合には（ステップ１７のＮ）、第１の配線と第２の配線とは交差するとの判定を出力する（ステップ１８）。
【００３０】
以上説明のように、この実施形態の配線交差判定プログラムによれば、マンハッタン線の交差判定を利用して同一象限にある任意の配線の交差判定を容易に行うことができる。この結果を用いて、半導体装置の設計者は、各配線の始点、終点の配置を修正し、場合によっては上記プログラムにより配線交差判定を再び行うことができる。
【００３１】
なお、以上では、図５、図６に示した配線交差の判定表を各象限であらかじめ作成しておくとして説明したが、ソフトウエアとしては、例えば第４象限でのみ作成しておいて、図２に示したレイアウト面２０を９０°づつ回転させて４回に分けて処理すれば同様の処理が可能である。また、簡易的には、ステップ１６、ステップ１７を設けず、ステップ１５でＮ側に抜けた場合には「交差の可能性がある」との結果を出力する、とすることもできる。その場合、図５の＃１、＃２、＃５、＃６の場合に「交差の可能性がある」の出力を行い、＃３、＃４、＃７、＃８の場合に「交差する」の出力を行って、幾分か詳しく結果を出力するようにしてもよい。
【００３２】
次に、本発明の別の実施形態たる複数の配線間の交差判定プログラムについて、図８を参照して説明する。図８は、複数の配線についての配線交差判定プログラム（＝本発明の別の実施形態）の概略フローチャートである。このプログラムは、複数の配線における２つの配線のすべての組について配線交差判定を行うものである。
【００３３】
まず、交差判定する複数（番号１〜ｎ）の配線（ただし同一象限）のＵＶ座標位置を取得する（ステップ８１）。配線の番号はあらかじめ与えられていても、与えられていない場合には仮想的にプログラムが与えるようにしてもよい。そして、その番号の１（配線１）を第１の配線と設定し、その番号の２（配線２）を第２の配線と設定する（ステップ８２）。この設定条件で、図１に示した配線交差判定（ステップ１０）を実行する。これによりそのふたつ（＝配線１と配線２）の配線間の交差判定結果が得られる。
【００３４】
次に、第２の配線が最後の番号ｎになっているか否かにより、なっていなければ（ステップ８３のＮ）第２の配線として番号を１加えたものに置き換え（ステップ８４）ステップ１０を実行する。これにより配線１と配線３の交差判定結果が得られる。以下、同様に、第２の配線がｎになるまで、ステップ８４、ステップ１０、ステップ８３のループを繰り返す。以上により、配線１と配線２〜ｎとの間の交差判定がそれぞれなされる。
【００３５】
ステップ８３で第２の配線が配線ｎになっていれば、次に、第１の配線として番号を１加えたもの（＝２）に置き換え（ステップ８５）、第２の配線としては番号が第１の配線の番号より１大きいもの（＝３）に置き換える（ステップ８６）。そして、第１の配線が最後の番号ｎになっているか否かにより、なっていなければ（ステップ８７のＮ）ステップ１０を実行する。これにより配線２と配線３との交差判定結果が得られる。以下は上記と同様にステップ８３を経て、ステップ８４、ステップ１０、ステップ８３のループを繰り返す。以上により、配線２と配線３〜ｎとの間の交差判定がそれぞれなされる。
【００３６】
さらに、ステップ８３で第２の配線が配線ｎになっていれば、次に、第１の配線として番号を１加えたもの（＝３）に置き換え（ステップ８３）、第２の配線としては番号が第１の配線の番号より１大きいもの（＝４）に置き換える（ステップ８６）。そして、上記と同様に、ステップ８７からステップ１０の交差判定を行いステップ８３を経て、ステップ８４、ステップ１０、ステップ８３のループの繰り返しと、そのループの終了後のステップ８５、８６、８７、１０の各処理とを交互に行う。最後にステップ８７で第１の配線が最後の番号ｎになっていれば終了する。以上により、すべての配線間の交差判定結果が得られる。
【００３７】
図８に示した複数の配線間の交差判定処理は、端的に言うと、配線１と配線２〜ｎそれぞれとの交差判定、配線２と配線３〜ｎそれぞれとの交差判定、配線３と配線４〜ｎそれぞれとの交差判定、…、配線ｎ−１と配線ｎとの交差判定、という手順による配線全組み合わせの交差判定である。このようのプログラムによれば、半導体装置として外部接続端子が非常に多い場合（例えば現状では３００端子以上のものがある）に配線レイアウト設計を円滑化する手助けになる。
【図面の簡単な説明】
【００３８】
【図１】本発明の一実施形態に係る配線交差判定プログラムの概略フローチャート。
【図２】半導体装置のレイアウト面における配線の象限を説明するための図。
【図３】図２中に示す各配線ａ〜ｅのマンハッタン線（ダイバージェンスとセグメント）を示す図。
【図４】交差判定するふたつの配線間の座標定義を示す図。
【図５】ふたつの配線の座標関係によるマンハッタン線の状態および配線交差の判定結果を示す図。
【図６】図５における「交差の可能性あり」の場合をさらに座標関係で場合分けしたマンハッタン線および配線交差の判定結果を示す図。
【図７】図６中に示す＃１−１、＃１−２、および図５中に示す＃３の条件における配線の状態の説明図。
【図８】複数の配線についての配線交差判定プログラム（本発明の別の実施形態）の概略フローチャート。
【符号の説明】
【００３９】
２０…半導体装置のレイアウト面、Ｄ…ダイバージェンス、Ｓ…セグメント。
【図１】
2006260172.tif 000003
【図２】
2006260172.tif 000004
【図３】
2006260172.tif 000005
【図４】
2006260172.tif 000006
【図５】
2006260172.tif 000007
【図６】
2006260172.tif 000008
【図７】
2006260172.tif 000009
【図８】
2006260172.tif 000010