(57)【要約】【課題】始点、中継点、終点の点群パターンに対し効率的に配線パターンを発生すること。【解決手段】中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、配線パターンで接続されるべき始点と終点との対応組を発生し、使用不可の中継点を記憶し、中継点間に通せる配線パターンの数を中継点間配線可能数として記憶し、縦方向列の中継点のうち使用不可のものを除いた各中継点について、該縦方向列の端のものから、始点と終点との対応組にさらに中継点を対応づけた対応組を発生し、中継点を含む対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点の間の領域に仮に設けた場合に、該配線パターンが中継点間配線可能数を超える配線パターンとなるか否か判断し、判断の結果中継点間配線可能数を超えない配線パターンである場合に該配線パターンを必要な配線パターンとして発生する。【選択図】図４
2007310490.tif 000002
【特許請求の範囲】
【請求項１】
縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、ある始点からある中継点を経てある終点に至る配線パターンを発生させるプログラムであって、
配線パターンで接続されるべき前記始点群の中の始点と前記終点群の中の終点とを対応づけて、始点と終点との対応組を発生するステップと、
前記中継点群の中にある使用不可の中継点を記憶するステップと、
前記中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶するステップと、
前記中継点群の中のある縦方向列の中継点のうち前記使用不可の中継点を除外した各中継点について、該縦方向列の端のものから、始点と終点との前記対応組にさらに対応づけて、始点と中継点と終点との対応組を発生するステップと、
始点と中継点と終点との前記対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に仮に設けた場合に、該配線パターンが前記中継点間配線可能数を超える配線パターンとなるか否か判断するステップと、
始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超えない配線パターンである場合に該配線パターンを必要な配線パターンとして発生するステップと
をコンピュータに実行させるための配線パターン発生用プログラム。
【請求項２】
始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超える配線パターンである場合に、該配線パターンに対応する、始点と中継点と終点との前記対応組について該中継点の対応づけを外し、残る始点と終点との対応組に新たな中継点を対応づけて始点と中継点と終点との新たな対応組を発生するステップをさらにコンピュータに実行させる請求項１記載の配線パターン発生用プログラム。
【請求項３】
判断する前記ステップが、経由する中継点が最も始点寄りとなっている配線パターンから順に判断を行い、
始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超える配線パターンである場合に、始点と中継点と終点との該対応組およびこれに応じた該配線パターンを、前記必要な配線パターンが設けられる配線層とは異なる配線層に設けると判定するステップ
をさらにコンピュータに実行させる請求項１記載の配線パターン発生用プログラム。
【請求項４】
対応組を発生する前記ステップと判断する前記ステップと配線パターンを発生する前記ステップとが、前記ある縦方向列として、前記中継点群の横方向なかほどに設定された縦方向列を始めは対象になされ、その後順に横方向端部に向かって対象になる縦方向列を換えてなされ、
対応組を発生する前記ステップが、前記対象になる縦方向列を換える方向によって、対応づける該縦方向列の端からの方向が反対である
請求項１記載の配線パターン発生用プログラム。
【請求項５】
縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、ある始点からある中継点を経てある終点に至る配線パターンを発生する方法であって、
配線パターンで接続されるべき前記始点群の中の始点と前記終点群の中の終点とを対応づけて、始点と終点との対応組を発生するステップと、
前記中継点群の中にある使用不可の中継点を記憶するステップと、
前記中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶するステップと、
前記中継点群の中のある縦方向列の中継点のうち前記使用不可の中継点を除外した各中継点について、該縦方向列の端のものから、始点と終点との前記対応組にさらに対応づけて、始点と中継点と終点との対応組を発生するステップと、
始点と中継点と終点との前記対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に仮に設けた場合に、該配線パターンが前記中継点間配線可能数を超える配線パターンとなるか否か判断するステップと、
始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超えない配線パターンである場合に該配線パターンを必要な配線パターンとして発生するステップと
を具備することを特徴とする配線パターン発生方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、始点、中継点、終点を有する点群パターンに対して配線パターンを発生させる配線パターン発生用プログラムおよび配線パターン発生方法に係り、特に、同一配線層でできるだけ交わらないように配線パターンを発生させる配線パターン発生用プログラムおよび配線パターン発生方法に関する。
【背景技術】
【０００２】
始点、中継点、終点を有する点群パターンに対して配線パターンを発生させる作業は、例えば、多ピンの半導体チップを実装する基板において必要となる。始点は、半導体チップの各端子に対応する基板上のパッドの位置、中継点は、基板に取り付けられる半田ボールの位置にそれぞれ対応する。終点は、この場合パッド（始点）上にめっき層を形成するためのめっき給電パッドである。
【０００３】
上記の基板における、始点、中継点、終点を有する点群パターンは、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置されたものを想定することができる。このような点群パターンに対して効率的に配線パターンを発生することができるツールは今のところない。関連する技術分野の文献として下記特許文献１、２があるが、両者とも課題が本願とは異なる。
【特許文献１】特開２００５−２５９０３６号公報
【特許文献２】特開２００２−２６９１６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、始点、中継点、終点を有する点群パターンに対して配線パターンを発生させる配線パターン発生用プログラムおよび配線パターン発生方法において、効率的な配線パターン発生が可能な配線パターン発生用プログラムおよび配線パターン発生方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一態様に係る配線パターン発生用プログラムは、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、ある始点からある中継点を経てある終点に至る配線パターンを発生させるプログラムであって、配線パターンで接続されるべき前記始点群の中の始点と前記終点群の中の終点とを対応づけて、始点と終点との対応組を発生するステップと、前記中継点群の中にある使用不可の中継点を記憶するステップと、前記中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶するステップと、前記中継点群の中のある縦方向列の中継点のうち前記使用不可の中継点を除外した各中継点について、該縦方向列の端のものから、始点と終点との前記対応組にさらに対応づけて、始点と中継点と終点との対応組を発生するステップと、始点と中継点と終点との前記対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に仮に設けた場合に、該配線パターンが前記中継点間配線可能数を超える配線パターンとなるか否か判断するステップと、始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超えない配線パターンである場合に該配線パターンを必要な配線パターンとして発生するステップとをコンピュータに実行させる。
【０００６】
また、本発明の一態様に係る配線パターン発生方法は、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、ある始点からある中継点を経てある終点に至る配線パターンを発生する方法であって、配線パターンで接続されるべき前記始点群の中の始点と前記終点群の中の終点とを対応づけて、始点と終点との対応組を発生するステップと、前記中継点群の中にある使用不可の中継点を記憶するステップと、前記中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶するステップと、前記中継点群の中のある縦方向列の中継点のうち前記使用不可の中継点を除外した各中継点について、該縦方向列の端のものから、始点と終点との前記対応組にさらに対応づけて、始点と中継点と終点との対応組を発生するステップと、始点と中継点と終点との前記対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に仮に設けた場合に、該配線パターンが前記中継点間配線可能数を超える配線パターンとなるか否か判断するステップと、始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超えない配線パターンである場合に該配線パターンを必要な配線パターンとして発生するステップとを具備する。
【発明の効果】
【０００７】
本発明によれば、始点、中継点、終点を有する点群パターンに対して配線パターンを発生させる配線パターン発生用プログラムおよび配線パターン発生方法において、効率的な配線パターンの発生が可能になる。
【発明を実施するための最良の形態】
【０００８】
本発明の一態様に係る配線パターン発生用プログラムによれば、第１に、中継点群の中にある使用不可の中継点を記憶するようにコンピュータを機能させる。したがって、使用不可の中継点を自動的に避けて配線パターンが発生される。また、第２に、中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶するようにコンピュータを機能させる。この中継点間配線可能数は、始点と中継点と終点との対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に仮に設けた場合に、配線可能かどうか判断するときに参照される。すなわち、第３に、該配線パターンが中継点間配線可能数を超えない配線パターンである場合に必要な配線パターンとして発生するようにコンピュータを機能させる。したがって、中継点間配線可能数を踏まえて適切な配線パターンが発生される。
【０００９】
本発明の実施態様として、始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超える配線パターンである場合に、該配線パターンに対応する、始点と中継点と終点との前記対応組について該中継点の対応づけを外し、残る始点と終点との対応組に新たな中継点を対応づけて始点と中継点と終点との新たな対応組を発生するステップをさらにコンピュータに実行させる、としてもよい。中継点を換えれば条件を満たす配線パターンとなる場合があるからである。
【００１０】
また、実施態様として、判断する前記ステップが、経由する中継点が最も始点寄りとなっている配線パターンから順に判断を行い、始点と中継点と終点との前記対応組に応じた前記配線パターンが前記中継点間配線可能数を超える配線パターンである場合に、始点と中継点と終点との該対応組およびこれに応じた該配線パターンを、前記必要な配線パターンが設けられる配線層とは異なる配線層に設けると判定するステップをさらにコンピュータに実行させる、としてもよい。始点と中継点と終点との対応組およびこれに応じた配線パターンを別の配線層に設けることができる場合の取り得る対応の一つである。
【００１１】
また、実施態様として、前記中継点間配線可能数がｎ−１以上である場合に、始点と中継点と終点との前記対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に設けて、前記必要な配線パターンとして発生するステップをさらにコンピュータに実行させる、としてもよい。中継点間配線可能数がｎ−１以上である場合は、始点と中継点と終点との対応組に応じた配線パターンを、該中継点の横方向に隣接する両中継点がそれぞれ属する縦方向列の間の領域に設けることが容易にできる。そこで、中継点間配線可能数がｎ−１以上である場合を選んで簡単化した処理をコンピュータに実行させる。
【００１２】
また、実施態様として、対応組を発生する前記ステップと判断する前記ステップと配線パターンを発生する前記ステップとが、前記ある縦方向列として、前記中継点群の横方向なかほどに設定された縦方向列を始めは対象になされ、その後順に横方向端部に向かって対象になる縦方向列を換えてなされ、対応組を発生する前記ステップが、前記対象になる縦方向列を換える方向によって、対応づける該縦方向列の端からの方向が反対である、とすることができる。中継点群において最初の縦方向列を中継点群の横方向なかほどに設ける場合の態様である。「対応組を発生する前記ステップが、前記対象になる縦方向列を換える方向によって、対応づける該縦方向列の端からの方向が反対」となるのは、始点の並ぶ順に中継点を対応づけるためである。
【００１３】
以上を踏まえ、以下では本発明の実施形態を図面を参照しながら説明する。図１は、本発明の一実施形態が対象とする、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンの一例を示す図である。この点群パターンを有する対象は配線基板１０であり、配線基板１０の中心から上側９０度範囲、下側９０度範囲、左側９０度範囲、右側９０度範囲にそれぞれ配線パターンで接続されるべき始点群、中継点群、終点群がある。上側９０度範囲、下側９０度範囲、左側９０度範囲、右側９０度範囲をそれぞれ、上象限、下象限、左象限、右象限と呼ぶ。
【００１４】
始点群を構成する始点１１Ｔ、１１Ｂ、１１Ｌ、１１Ｒは、半導体チップ実装用パッドの位置に相当する。中継点群を構成する中継点１２Ｔ、１２Ｂ、１２Ｌ、１２Ｒは、半田ボール取り付け用パッドの位置に相当する。終点群を構成する終点１３Ｔ、１３Ｂ、１３Ｌ、１３Ｒは、めっき給電パッドの位置に相当する。代表して上側の中継点１２Ｔからなる中継点群は、グリッド状（縦ｎ、横ｍとする）に配置され、この中継点群の上側に終点１３Ｔからなる終点群が横方向に列状に配置され、下側に始点１１Ｔからなる始点群が横方向に列状に配置されている。配線基板１０の下側、左側、右側も向きが異なるが相対的に同じ配置に始点群、中継点群、終点群が設けられている。以下の説明では、主に、代表して上側の始点群、中継点群、終点群について説明を行う。
【００１５】
図１に示すような配置の始点群、中継点群、始点群の配置が与えられたときに、始点から中継点を経て終点に至る配線パターンを効率的に発生するのが本実施形態の機能である。発生された配線パターンによれば、各終点１３Ｔ、１３Ｂ、１３Ｌ、１３Ｒをめっき給電パッドとしてパッド（始点）上にめっき層を形成することができる。
【００１６】
図２は、図１に示した点群パターンに配線パターンを設ける場合の諸元を示す説明図である。図２に示すように、配線パターン２０が、ある始点１１Ｔからある中継点１２Ｔを経てある終点１３Ｔに至るように発生されたとする。ここで発生させる配線パターン２０は、図示するように、中継点群の領域内では、中継して用いるその中継点の横方向隣接の
両中継点がそれぞれ属する縦方向列の間の領域に設けられるものとする。できるだけ交わらない配線パターンを発生させるためである。
【００１７】
配線パターン２０のデザインルールとして、ライン／スペースが、始点、中継点間ではＬｓ／Ｓｓ、中継点、終点間ではＬｍ／Ｓｍとする。また、中継点の横方向最大径はＬｐ、中継点間の横方向配置ピッチはＢｐとする。これらにより、横方向隣接の中継点間に通せる配線パターンの数（中継点間配線可能数Ｎｍｍａｘ）は、以下の式で表せる。すなわち、Ｌｓ＋Ｓｓ≧Ｌｍ＋Ｓｍのとき、Ｎｍｍａｘ＝［（Ｂｐ−Ｌｐ−Ｓｓ）／（Ｌｓ＋Ｓｓ）］、Ｌｍ＋Ｓｍ≧Ｌｓ＋Ｓｓのとき、Ｎｍｍａｘ＝［（Ｂｐ−Ｌｐ−Ｓｍ）／（Ｌｍ＋Ｓｍ）］である。ここで［・］はガウス記号（・を超えない最大の整数）を表す。分母で−Ｓｓまたは−Ｓｍを行っているのは、ライン／スペースのペアが中継点間に存在できるためには必ずラインの両側にスペースがなければならないからである。
【００１８】
図３は、始点と終点との対応組に中継点を対応づける（縫い付ける）諸態様を示す説明図である。後述するが、始点１１Ｔそれぞれと終点１３Ｔそれぞれとはあらかじめ対応づけがなされている。図３（ａ）に示すように、この対応はそれらの並び順である。この始点１１Ｔと終点１３Ｔとの対応づけに対してさらに中継点１２Ｔの対応づけ（以下ではこれを「縫い付ける」ともいう）を行っていく。
【００１９】
縫い付けは、中継点群の特定の列（対象列）を対象としてその端のものから行っていく。図３（ａ）に示すように、縫い付けが図で左方向に進む場合（すなわち、対象列の右側の縦方向列には縫い付けが済み、対象列の左側の縦方向列には縫い付けがされていない場合）には、中継点を効率的に活用するため、対象列の上側端の中継点から縫い付けられる。後述するが、縫い付けが図で右方向に進む場合には、同様の理由で対象列の下側端の中継点から縫い付けられる。なお、縫い付けが図で左方向に進む場合に対象列の下側端から縫い付け、縫い付けが図で右方向に進む場合に対象列の上側端から縫い付ける、とすることもできる（図で、配線パターンが対象列の左下から進入し右上に出る場合はこのようになる）。
【００２０】
図３（ａ）、（ｂ）、（ｃ）は、中継点間配線可能数Ｎｍｍａｘ＝３で、中継点の縦の並び数ｎが４の場合を示している。図３（ｂ）、（ｃ）において、中継点のうち黒丸で表されているものは使用不可の中継点としてあらかじめ設定されているものである。使用不可の中継点の数はＮｘとして図で示されている。
【００２１】
図３（ａ）、（ｂ）、（ｃ）で楕円で示されたところは、図示の対象列に縫い付けが行われるときの配線数のチェックポイントである。図３（ａ）、（ｂ）、（ｃ）の場合は、いずれの場合も、すべてのチェックポイントにおいて配線数は中継点間配線可能数Ｎｍｍａｘ＝３以下に収まっている。したがって、図示するように対象列の中継点について縫い付けが可能である。一般に、中継点の縦の並び数がｎのとき、中継点間配線可能数Ｎｍｍａｘがｎ−１以上である場合は、図３（ａ）、（ｂ）、（ｃ）に示すように中継点の縫い付けは容易である。この場合必要な中継点間の配線数はｎ−１だからである。Ｎｘが増えるにつれさらに余裕が出る。
【００２２】
図３（ｄ）、（ｅ）、（ｆ）は、中継点間配線可能数Ｎｍｍａｘ＝２で、中継点の縦の並び数ｎが４の場合を示している。使用不可の中継点（黒丸）、およびその数Ｎｘについては上記と同様である。図３（ｄ）、（ｅ）、（ｆ）の場合、中継点の○の中に×が表示されたものは縫い付けができなかったものである。試しに図示の対象列の中継点○のどれでもよいが代わりに×のあるものを中継点として使用すると、楕円で示されるチェックポイントはいずれかで配線数が３になる。図３（ｄ）、（ｅ）、（ｆ）に示す場合は、×が表示された中継点は使用しないものとしてそのままにする。配線層として別の配線層がない場合の態様例である。
【００２３】
図３（ｇ）、（ｈ）、（ｉ）は、上記と同様に、中継点間配線可能数Ｎｍｍａｘ＝２で、中継点の縦の並び数ｎが４の場合を示している。ただし、配線層として別の配線層があるとした場合の態様例となっている。
【００２４】
この場合は、対象列の使える中継点に対して、チェックポイントでの配線数を考慮せずに一度順に対応づけを行う。そのあとで、すべてのチェックポイントで配線数が中継点間配線可能数Ｎｍｍａｘ以下になっているかチェックし、なっていればそのままでよい。このチェックで中継点間配線可能数Ｎｍｍａｘを超えるチェックポイントがある場合は、最も始点１１Ｔ寄りの中継点を対象にこれを通る配線を除いたときに、すべてのチェックポイントで配線数が中継点間配線可能数Ｎｍｍａｘ以下になっているかチェックする。
【００２５】
Ｎｍｍａｘ以下になっていれば、その中継点およびこれを通る配線パターンに接続される始点１１Ｔ、終点１３Ｔはまとめて別の配線層による接続のものとして扱いそれで終わる。このチェックで中継点間配線可能数Ｎｍｍａｘを超えるチェックポイントがまだある場合は、同様に、次に始点１１Ｔ寄りの中継点を対象に同様の手順を行う。このようにして、すべてのチェックポイントで配線数が中継点間配線可能数Ｎｍｍａｘ以下になるようになるまでチェックおよび別配線層移行を行う。
【００２６】
以上の手順を行うと、図３（ｇ）の場合は、対象列の中継点１２Ｔのうち始点１１Ｔよりの２つの配線パターンおよびそれにつながる始点および終点（図で一点鎖線の表示）が別の配線層のものとして扱われる。また、図３（ｈ）の場合は、別の配線層のものとして扱われる組は発生せず、図３（ｉ）の場合は、対象列の中継点１２Ｔのうち始点１１Ｔよりの１つの配線パターンおよびそれにつながる始点および終点（図で一点鎖線の表示）が別の配線層のものとして扱われる。
【００２７】
なお、この例で、対象列の中継点１２Ｔのうち始点１１Ｔ寄りのものから優先して他の配線層のものとしているのは、この配線層でできるだけ始点群の周囲に配線スペースの余裕を発生させたいためである。始点群の周囲に優先的に配線スペースの余裕を発生させる必要がなければ、例えば、対象列の中継点１２Ｔのうち終点１３Ｔ寄りのものから優先して他の配線層のものとするように処理してもよい。
【００２８】
次に、図４は、本発明の一実施形態に係る配線パターン発生用プログラムのフローを示す流れ図である。以下、図４を参照してこの配線パターン発生用プログラムのフローを説明する。
【００２９】
まず、始点、終点、中継点の配置を設定する（ステップ４１）。これはすでに述べた図１に示したような始点１１Ｔ、１１Ｂ、１１Ｌ、１１Ｒ、終点１３Ｔ、１３Ｂ、１３Ｌ、１３Ｒ、中継点１２Ｔ、１２Ｂ、１２Ｌ、１２Ｒの配置である。次に、始点と終点とを対応づける（ステップ４２）。これは、始点１１Ｔ、１１Ｂ、１１Ｌ、１１Ｒの並びに従って、それぞれ順に終点１３Ｔ、１３Ｂ、１３Ｌ、１３Ｒの並びに対応づければよい。典型的には、始点１１Ｔの数と終点１３Ｔの数とは同じである。始点１１Ｂと終点１３Ｂ、始点１１Ｌと終点１３Ｌ、始点１１Ｒと終点１３Ｒも同様である。各象限においてその中での始点と終点の数が異なる場合は、当然ながら、配線パターンの発生結果として配線パターンの接続されない始点または終点が発生する。なお、中継点の縦方向（始点と終点に挟まれる方向）の数はｎである。
【００３０】
次に、縫い付け対象外（使用不可）の中継点を設定し（ステップ４３）これを記憶する。このような中継点には結果として配線パターンが接続されない。続いて配線層を設定する（ステップ４４）。初めはまったく配線パターンを発生させていない配線層が設定される。続いてデザインルールを設定する（ステップ４５）。これにより、中継点間配線可能数Ｎｍｍａｘを［（Ｂｐ−Ｌｐ−Ｓｓ）／（Ｌｓ＋Ｓｓ）］または［（Ｂｐ−Ｌｐ−Ｓｍ）／（Ｌｍ＋Ｓｍ）］として求めることができるので（同ステップ：図２参照）、これを記憶する。
【００３１】
次に、象限を設定する（ステップ４６）。中継点の縫い付けは象限ごとに行う。続いて、中継点の中の適当な縦方向列を開始列として設定しこれを最初の対象列とする（ステップ４７）。また始点の中で縫い付け処理を行う最初のもの（開始点）を設定する（同ステップ）。開始列と開始点は、図２の図示で言えばそれぞれ横方向のなかほどのものを選ぶ。そこから左方向（または右方向）に中継点の縫い付けを行った場合に中継点の不足が生じないように開始列および開始点を選ぶ。
【００３２】
次に、対象列の中継点への縫い付けを行う（ステップ４８）。例えば、すでに述べたように、中継点間配線可能数Ｎｍｍａｘがｎ−１以上である場合は、図３（ａ）、（ｂ）、（ｃ）に示すように、容易に縫い付けがなされる。また、中継点間配線可能数Ｎｍｍａｘがｎ−１未満である場合は、例えば、図３（ｄ）、（ｅ）、（ｆ）に示すようになる。この場合、対象列の最も終点１３Ｔ寄りの中継点から仮に縫い付けを行い、各チェックポイントで配線数が中継点間配線可能数Ｎｍｍａｘ内に収まっているかチェックする。収まっていれば、その仮縫い付けをそのまま縫い付け結果とし、収まっていなければその中継点の対応づけを解除して同一の始点、終点に次の新たな中継点を仮に縫い付ける。これで同様にチェックを行う。以下同様に、対象列の最も始点１１Ｔ寄りの中継点までを処理する。
【００３３】
中継点間配線可能数Ｎｍｍａｘがｎ−１未満である場合であって、配線層が別にもある場合は、例えば、図３（ｇ）、（ｈ）、（ｉ）に示すようになる。この手順はすでに説明したので省略するが、縫い付けられた始点、中継点、終点の組の一部が別の層に移されることになる（同ステップ４８）。
【００３４】
一つの対象列について縫い付けが終わったら次の対象列に移り同様に処理を行う（ステップ、４９、５０のＮからステップ４８）。なお、対象列を例えば左方向に換えながら処理し縫い付けが終了したら開始列の右隣を対象列にして今度は右方向に対象列を換えながら同様に処理する（図５（ａ）、（ｂ）を参照）。図５は、始点と終点との対応組に中継点を対応づける（縫い付ける）順序の例を示す説明図である。このようにして一つの象限の処理が終了したら（ステップ５０のＹ）、象限を更新し（ステップ５１、５２のＮからステップ４７以下）、同様の処理を行う。
【００３５】
全象限で処理が終了したら（ステップ５２のＹ）、別の配線層がある場合は（ステップ５３のＹ）、別の配線層の処理に移行する。別の配線層での処理は、図３（ｇ）（ｈ）（ｉ）を参照した説明と基本的に同様である。すなわち、ある配線層で別の層のものとされた始点、中継点、終点の組について、その新しい配線層において、再びすべてのチェックポイントで配線数が中継点間配線可能数Ｎｍｍａｘ以下になっているかチェックし、そうでなければさらに一部を第３の配線層のものとする処理である。場合により、さらに配線層の数によってステップ５３でループする場合がある。以上により配線の発生処理が終わる。
【００３６】
以上説明したように、本実施形態によれば、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンに対して、ある始点からある中継点を経てある終点に至る配線パターンを発生させるに当たり、効率化が図れる。具体的には、使用不可の中継点を自動的に避けて配線パターンが発生される。また、中継点群の横方向隣接の中継点間に通せる配線パターンの数を中継点間配線可能数として記憶し、これにより、始点と中継点と終点との対応組に応じた配線パターンを、該中継点の横方向に隣接する縦方向列の間の領域に仮に設けた場合に、配線可能かどうか判断する。そしてこの配線パターンが中継点間配線可能数を超えないものである場合に、中継点間配線可能数を踏まえた適切な配線パターンとして発生がなされる。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施形態が対象とする、縦ｎ、横ｍの中継点群の縦方向上下にそれぞれ終点群、始点群が横方向に列状に配置された点群パターンの一例を示す図。
【図２】図１に示した点群パターンに配線パターンを設ける場合の諸元を示す説明図。
【図３】始点と終点との対応組に中継点を対応づける（縫い付ける）諸態様を示す説明図。
【図４】本発明の一実施形態に係る配線パターン発生用プログラムのフローを示す流れ図。
【図５】始点と終点との対応組に中継点を対応づける（縫い付ける）順序の例を示す説明図。
【符号の説明】
【００３８】
１０…配線基板、１１Ｔ，１１Ｂ，１１Ｌ，１１Ｒ…始点（半導体チップ実装用パッド）、１２Ｔ，１２Ｂ，１２Ｌ，１２Ｒ…中継点（半田ボール取り付け用パッド）、１３Ｔ，１３Ｂ，１３Ｌ，１３Ｒ…終点（めっき給電パッド）、２０…配線パターン。
【図１】
2007310490.tif 000003
【図２】
2007310490.tif 000004
【図３】
2007310490.tif 000005
【図４】
2007310490.tif 000006
【図５】
2007310490.tif 000007