(57)【要約】【課題】Ｗ−ＣＳＰ構造の半導体装置に係る半導体チップのタワーポスト自動配置方法を提供する。【解決手段】タワーポスト配置領域を区分けし、配置区分けごとに最も近い外周辺を判定する工程と、割り付けられたタワーポストの個数がその外周辺のパッドの個数と一致するように各配置区分のタワーポストをなるべく近い外周辺に割り付けていく工程と、同じ外周辺に割り付けられたタワーポストをその外周辺と垂直な方向に並ぶタワーポストごとにグループ化するとともにこれらのグループのタワーポスト数に対応させてその外周辺に配列されたパッドを一端から順にグループ化する工程と、このグループ分けに基づいてタワーポストとパッドとの対応付けを行う工程と、タワーポストとパッドとを直線で接続し、これらの直線間で交差が存在するか否かを順にチェックし、交差が存在する場合は対応するパッドどうしを置換する処理を交差が無くなるまで繰り返す工程とを含む。【選択図】図４
2006332516.tif 000002
【特許請求の範囲】
【請求項１】
パッドが設けられた半導体チップの表面に形成される外部接続電極の配置を自動的に行う半導体装置の自動設計方法であって、
前記外部接続電極の配置位置を決定するとともに、当該外部接続電極の配置領域を複数の配置区分に区分けし、前記パッドが配列された外周辺と該配置区分との位置関係から当該配置区分に対して１つ以上の該外周辺を対応づける配置領域決定工程と、
前記対応づけられた外周辺に対して前記配置区分に配置された前記外部接続電極を割り付け、対応する前記外周辺が複数ある場合には前記配置区分に配置された前記外部接続電極を該外周辺のいずれかに割り付ける処理を、割り付けられた前記外部接続電極の個数が当該外周辺の前記パッドの個数と一致するまで行う割付辺決定工程と、
同じ前記外周辺に割り付けられた前記外部接続電極を当該外周辺と垂直な方向に並ぶ当該外部接続電極ごとにグループ化するとともに、これらのグループの外部接続電極数に対応させて当該外周辺に配列された当該パッドを一端から順にグループ化する配置カラム決定工程と、
対応する前記外部接続電極のグループおよび前記パッドのグループ間で、当該外部接続電極と当該パッドとの対応付けを行う配置ロウ決定工程と、
対応づけられた前記外部接続電極と前記パッドとを直線状の仮想配線で接続し、当該仮想配線の交差の有無を順にチェックし、交差が存在する場合には当該仮想配線どうしで前記外部接続電極と前記パッドとの対応関係を置換する処理を行う配置編集工程と、
を含むことを特徴とする半導体装置の自動設計方法。
【請求項２】
前記配置領域決定工程が、前記配置領域を、３行３列以上の矩形の前記配置区分に区分けすることを特徴とする請求項１に記載の半導体装置の自動設計方法。
【請求項３】
前記割付辺決定工程が、前記パッドの数が多い前記外周辺から順に、前記外部接続電極の割り付けを行うことを特徴とする請求項１または２に記載の半導体装置の自動設計方法。
【請求項４】
前記割付辺決定工程が、
最も近い外周辺が１つのみの配置区分に配置された前記外部接続電極についての割り付けを行う第１ステップと、
当該第１ステップ後に、最も近い外周辺が２個以上の配置区分に配置された前記外部接続電極について、当該外周辺に近い当該外部接続電極から順に、前記配置領域の対角線方向に沿って割り付けを行う第２ステップと、
を含むことを特徴とする請求項１〜３のいずれかに記載の半導体装置の自動設計方法。
【請求項５】
前記配置編集工程が、交差が存在する前記仮想配線どうしで前記外部接続電極と前記パッドとの対応関係を置換する処理を、該交差が無くなるまで繰り返す工程であることを特徴とする請求項１〜４のいずれかに記載の半導体装置の自動設計方法。
【請求項６】
パッドが設けられた半導体チップの表面に形成される外部接続電極の配置を自動的に行う半導体装置の自動設計装置であって、
前記外部接続電極の配置位置を決定するとともに、当該外部接続電極の配置領域を複数の配置区分に区分けし、前記パッドが配列された外周辺と該配置区分との位置関係から当該配置区分に対して１つ以上の該外周辺を対応づける配置領域決定手段と、
前記対応づけられた外周辺に対して前記配置区分に配置された前記外部接続電極を割り付け、対応する前記外周辺が複数ある場合には前記配置区分に配置された前記外部接続電極を該外周辺のいずれかに割り付ける処理を、割り付けられた前記外部接続電極の個数が当該外周辺の前記パッドの個数と一致するまで行う割付辺決定手段と、
同じ前記外周辺に割り付けられた前記外部接続電極を当該外周辺と垂直な方向に並ぶ当該外部接続電極ごとにグループ化するとともに、これらのグループの外部接続電極数に対応させて当該外周辺に配列された当該パッドを一端から順にグループ化する配置カラム決定手段と、
対応する前記外部接続電極のグループおよび前記パッドのグループ間で、当該外部接続電極と当該パッドとの対応付けを行う配置ロウ決定手段と、
対応づけられた前記外部接続電極と前記パッドとを直線状の仮想配線で接続し、当該仮想配線の交差の有無を順にチェックし、交差が存在する場合には当該仮想配線どうしで前記外部接続電極と前記パッドとの対応関係を置換する処理を行う配置編集手段と、
を含むことを特徴とする半導体装置の自動設計装置。
【請求項７】
前記配置領域決定手段が、前記配置領域を、３行３列以上の矩形の前記配置区分に区分けすることを特徴とする請求項６に記載の半導体装置の自動設計装置。
【請求項８】
前記割付辺決定手段が、前記パッドの数が多い前記外周辺から順に、前記外部接続電極の割り付けを行うことを特徴とする請求項６または７に記載の半導体装置の自動設計装置。
【請求項９】
前記割付辺決定手段が、
最も近い外周辺が１つのみの配置区分に配置された前記外部接続電極についての割り付けを行い、
さらに、最も近い外周辺が２個以上の配置区分に配置された前記外部接続電極について、当該外周辺に近い当該外部接続電極から順に、前記配置領域の対角線方向に沿って割り付けを行う、
ことを特徴とする請求項６〜８のいずれかに記載の半導体装置の自動設計装置。
【請求項１０】
前記配置編集手段が、交差が存在する前記仮想配線どうしで前記外部接続電極と前記パッドとの対応関係を置換する処理を、該交差が無くなるまで繰り返すことを特徴とする請求項６〜９のいずれかに記載の半導体装置の自動設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半導体集積回路の自動設計技術に関し、より詳細には、パッドが設けられた半導体チップの表面に形成される外部接続電極の配置を自動的に行う技術に関する。
【背景技術】
【０００２】
近年、半導体集積回路の高集積化・多機能化などに伴い、かかる半導体集積回路のパッド数および半導体パッケージの外部接続電極（すなわち電極ピン）の数が増大する傾向にある。このため、電極ピンの配置を決定してパッドと配線する設計作業も複雑化が進んでおり、かかる設計作業の自動化技術に対する要望も高まっている。
【０００３】
電極ピンの配置・配線を自動化する際には、配線長が短く且つ一層配線が可能であることが望まれる。
【０００４】
従来、パッド・電極ピン間の配線を自動化するための技術としては、例えば下記特許文献１、２で開示されたものが知られている。
【０００５】
特許文献１では、電極ピンの配置領域を４個の台形領域に区分けし、それぞれの区分領域の電極ピンと、この区分領域に対向する外周辺に配列されたパッドとを、予め定められた優先順位にしたがって配線している（特許文献１の段落０１１１〜０１２０、図６〜図９、図１２等参照）。
【０００６】
また、特許文献２では、複数のパッドと複数の電極ピンとを配線するための共通引き出しパターンを予め作成しておき、この共通引き出しパターンを適当に配置することによって、自動配置を実現している（特許文献２の段落００３９〜００４０等参照）。
【特許文献１】特開２０００−３５９８６号公報
【特許文献２】特開２０００−１００９５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１、２で開示された技術には、以下のような欠点があった。
【０００８】
特許文献１の技術では、各区分領域の電極ピンと、対向する外周辺のパッドとが、同数であることを前提としている。このため、例えばパッド数が外周辺ごとに異なるような場合に、適切な配線を行うことができなくなる。すなわち、特許文献１の技術には、半導体集積回路部分の設計に対する制約が大きいという欠点がある。
【０００９】
また、特許文献２の技術では、パッドや電極ピンの総数が、引き出しパターンの配線数の整数倍であることが必要となる。したがって、特許文献２の技術にも、半導体集積回路部分の設計に対する制約が大きいという欠点がある。
【００１０】
この発明の課題は、配線長が短く、一層配線が可能で、且つ、半導体集積回路部分に対する制約が小さい自動設計技術を提供することにある。
【課題を解決するための手段】
【００１１】
（１）第１の発明は、パッドが設けられた半導体チップの表面に形成される外部接続電極の配置を自動的に行う半導体装置の自動設計方法に関する。
【００１２】
そして、外部接続電極の配置位置を決定するとともに、外部接続電極の配置領域を複数の配置区分に区分けし、パッドが配列された外周辺と配置区分との位置関係から配置区分に対して１つ以上の外周辺を対応づける配置領域決定工程と、対応づけられた外周辺に対して配置区分に配置された外部接続電極を割り付け、対応する外周辺が複数ある場合には配置区分に配置された外部接続電極を外周辺のいずれかに割り付ける処理を、割り付けられた外部接続電極の個数が外周辺のパッドの個数と一致するまで行う割付辺決定工程と、同じ外周辺に割り付けられた外部接続電極を外周辺と垂直な方向に並ぶ外部接続電極ごとにグループ化するとともに、これらのグループの外部接続電極数に対応させて外周辺に配列されたパッドを一端から順にグループ化する配置カラム決定工程と、対応する外部接続電極のグループおよびパッドのグループ間で、外部接続電極とパッドとの対応付けを行う配置ロウ決定工程と、対応づけられた外部接続電極とパッドとを直線状の仮想配線で接続し、仮想配線の交差の有無を順にチェックし、交差が存在する場合には仮想配線どうしで外部接続電極とパッドとの対応関係を置換する処理を行う配置編集工程とを含む。
【００１３】
（２）第２の発明は、パッドが設けられた半導体チップの表面に形成される外部接続電極の配置を自動的に行う半導体装置の自動設計装置に関する。
【００１４】
そして、外部接続電極の配置位置を決定するとともに、外部接続電極の配置領域を複数の配置区分に区分けし、パッドが配列された外周辺と配置区分との位置関係から配置区分に対して１つ以上の外周辺を対応づける配置領域決定手段と、対応づけられた外周辺に対して配置区分に配置された外部接続電極を割り付け、対応する外周辺が複数ある場合には配置区分に配置された外部接続電極を外周辺のいずれかに割り付ける処理を、割り付けられた外部接続電極の個数が外周辺のパッドの個数と一致するまで行う割付辺決定手段と、同じ外周辺に割り付けられた外部接続電極を外周辺と垂直な方向に並ぶ外部接続電極ごとにグループ化するとともに、これらのグループの外部接続電極数に対応させて外周辺に配列されたパッドを一端から順にグループ化する配置カラム決定手段と、対応する外部接続電極のグループおよびパッドのグループ間で、外部接続電極とパッドとの対応付けを行う配置ロウ決定手段と、対応づけられた外部接続電極とパッドとを直線状の仮想配線で接続し、仮想配線の交差の有無を順にチェックし、交差が存在する場合には仮想配線どうしで外部接続電極とパッドとの対応関係を置換する処理を行う配置編集手段とを含む。
【発明の効果】
【００１５】
第１、第２の発明では、各外部接続電極を、最適な外周辺に配列されたパッドから順に接続することができるので、各配線の配線長を短くすることが可能である。
【００１６】
また、最も近い外周辺が２個以上の配置区分に配置された外部接続電極を、これらの外周辺のいずれかに適宜割り付けることができるので、各外周辺のパッド数やパッドの総数の制約がない。
【００１７】
さらに、外部接続電極とパッドとを直線状の仮想配線で接続し、仮想配線の交差が存在する場合にはこれらの仮想配線どうしで外部接続電極とパッドとの対応関係を置換するので、一層配線が可能である。
【発明を実施するための最良の形態】
【００１８】
以下、この発明の実施形態について、図面を用いて説明する。なお、図中、各構成成分の大きさ、形状および配置関係は、この発明が理解できる程度に概略的に示してあるにすぎず、また、以下に説明する数値的条件は単なる例示にすぎない。
【００１９】
この実施形態では、この発明を、Ｗ−ＣＳＰ(Wafer Level Chip Size Package) におけるタワーポストの配置に適用する場合を例に採って説明する。
【００２０】
図１は、この実施形態に係る自動設計装置の全体構成を概略的に示すブロック図である。図１に示したように、この実施形態の自動設計装置１００は、自動配置処理装置１１０と、外部記憶装置１２０と、入力装置１３０と、表示装置１４０とを備えている。
【００２１】
自動配置処理装置１１０は、タワーポストの配置を自動的に行う。このために、自動配置処理装置１１０は、演算処理部１１１と、配置状態記憶部１１２とを備える。演算処理部１１１は、後述のようなタワーポスト自動配置処理を実行する。配置状態記憶部１１２は、演算処理部１１１の処理中に、配置状態を示すデータを適宜保存する。
【００２２】
外部記憶装置１２０は、例えばハードディスク等で構成され、接続データ格納領域１２１、セル格納領域１２２およびレイアウトデータ格納領域１２３を有している。接続データ格納領域１２１には、各パッドの識別番号と各タワーポストの識別番号とを示すデータや、これらパッドおよびタワーポストの接続関係を示すデータが格納される。セル格納領域１２２には、タワーポスト用のセルが格納される。レイアウトデータ格納領域１２３には、演算処理部１１１がタワーポスト自動配置処理を完成することによって生成されたレイアウトデータを、配置状態記憶部１１２から読み出して、保存する。
【００２３】
入力装置１３０は、キーボードやコンピュータマウス等で構成され、設計者がタワーポスト自動配置処理の制約や条件等を入力する際などに使用する。
【００２４】
表示装置１４０は、例えばＣＲＴ(Cathode Ray Tube)等で構成され、入力装置１３０による入力結果の確認や、タワーポスト自動配置処理の結果（すなわち、配置状態記憶部１１２の最終的なレイアウトデータ）などを、設計者が確認するために使用される。
【００２５】
図２は、この実施形態に係るタワーポスト自動配置処理の全体構成を示す概略フローチャートである。
【００２６】
図２に示したように、この実施形態に係るタワーポスト自動配置処理は、配置領域決定工程Ｓ２０１と、割付辺決定工程Ｓ２０２と、配置カラム決定工程Ｓ２０３と、配置ロウ決定工程Ｓ２０４と、タワーポスト配置編集工程Ｓ２０５と、タワーポスト配置工程Ｓ２０６とを含む。
【００２７】
以下、これらの各工程Ｓ２０１〜Ｓ２０６の詳細について説明する。
【００２８】
配置領域決定工程
配置領域決定工程Ｓ２０１について、図３および図４を用いて説明する。ここで、図３は本工程Ｓ２０１を示す詳細フローチャートであり、図４は本工程Ｓ２０１終了時のレイアウトデータを示す概念図である。以下に説明するように、配置領域決定工程Ｓ２０１では、タワーポストの配置位置を決定し、タワーポストの配置領域を複数の配置区分に区分けし、さらに、パッドが配列された外周辺のうち最も近いものを配置区分ごとに判定する。
【００２９】
まず、演算処理部１１１（図１参照）は、外部記憶装置１２０の接続データ格納領域１２１から上述のような接続データ（各パッドの識別番号、各タワーポストの識別番号、各パッドおよび各タワーポストの接続関係を示すデータ）を読み出すとともに、外部から上述のような設計条件（Ｗ−ＣＳＰの外形状データ、タワーポストの配置間隔、タワーポストのロウ数およびカラム数など）を読み込む（図３のステップＳ４０１参照）。この実施形態では、タワーポストのロウ数およびカラム数をそれぞれ「６」（したがって総数は３６）とした場合を例に採って説明するが、これに限られるものでないことは言うまでもない。
【００３０】
次に、演算処理部１１１は、Ｗ−ＣＳＰ構造の半導体装置を作製するための半導体チップについて、表面（タワーポスト配置面）４１０の中心点４２０を求める。そして、演算処理部１１１は、上述の接続データおよび設計条件を用いて、この半導体チップ上に、タワーポストＴ(1,1) 〜Ｔ(6,6) を仮配置する（ステップＳ４０２参照）。このとき、演算処理部１１１は、この半導体チップ表面の中心点４２０と、タワーポスト配列の中心点とを、一致させる。これにより、タワーポストの配置領域４３０が決定される。演算処理部１１１は、各タワーポストＴ(1,1) 〜Ｔ(6,6) の配置位置などから、この配置領域４３０を判定する（ステップＳ４０３参照）。
【００３１】
なお、図４に示したように、半導体チップ４１０の、外周辺Ｗの近傍にはパッドＰＷ１〜ＰＷ７が配置され、外周辺Ｓの近傍にはパッドＰＳ１〜ＰＳ１０が配置され、外周辺Ｅの近傍にはパッドＰＥ１〜ＰＥ９が配列され且つ外周辺Ｎの近傍にはパッドＰＮ１〜ＰＮ７が配列されている。これらのパッドＰＷ１〜ＰＷ７，ＰＳ１〜ＰＳ１０，ＰＥ１〜ＰＥ９，ＰＮ１〜ＰＮ７の配置は、この実施形態に係るタワーポスト自動配置処理よりも前の処理工程で行われる。
【００３２】
続いて、演算処理部１１１は、この配置領域４３０を、９個の配置区分ＡＷＳ，ＡＳ，ＡＳＥ，ＡＥ，ＡＥＮ，ＡＮ，ＡＮＷ，ＡＷ，ＡＣに区分けする（ステップＳ４０４参照）。この実施形態では、各配置区分の面積（したがって、各配置区分に含まれるタワーポストの個数）を同一にしたが、必ずしも同一である必要はない。
【００３３】
さらに、演算処理部１１１は、外周辺Ｗ，Ｓ，Ｅ，Ｎのうち最も近いものを、配置区分ごとに判定する（ステップＳ４０５参照）。この実施形態では、配置区分ＡＷ，ＡＳ，ＡＥ，ＡＮは、対向する１個の外周辺Ｗ，Ｓ，Ｅ，Ｎに最も近く、また、配置区分ＡＷＳ，ＡＳＥ，ＡＥＮ，ＡＮＷは、２個の外周辺に最も近い（例えば、配置区分ＡＷＳの場合は外周辺Ｗ，Ｓ）。さらに、中央の配置区分ＡＣは、すべての外周辺Ｗ，Ｓ，Ｅ，Ｎに最も近いと判定される。
【００３４】
以上により、配置領域決定工程Ｓ２０１が終了する。
【００３５】
割付辺決定工程
割付辺決定工程Ｓ２０２（図２参照）について、図５および図６を用いて説明する。ここで、図５は本工程Ｓ２０２を示す詳細フローチャートであり、図６は本工程Ｓ２０２終了時のレイアウトデータを示す概念図である。以下に説明するように、割付辺決定工程Ｓ２０２では、最も近い外周辺が１つのみの配置区分に配置されたタワーポストについては、最も近い外周辺を割り付ける。また、最も近い外周辺が２個以上の配置区分に配置されたタワーポストについては、最も近い外周辺のいずれかに割り付ける。この処理は、割り付けられたタワーポストの個数が外周辺のパッドの個数と一致するまで行われる。この割付辺決定工程Ｓ２０２では、各タワーポストを外周辺に対応づける処理のみを行い、各パッドへの割り付けは行わない。
【００３６】
配線距離を短くするためには、パッド数が多い外周辺から順に、タワーポストの割り付け処理を行うことが望ましい。また、各外周辺に対してタワーポストの割り付け処理を行う際には、「最も近い外周辺」の数が少ない配置区分に設けられたタワーポストから割り付けていくことが望ましい。
【００３７】
まず、演算処理部１１１は、割り付け処理の対象となる外周辺を選択する（図５のステップＳ５０１参照）。ここでは、パッド数が最も多い外周辺である、外周辺Ｓが選択される。
【００３８】
次に、演算処理部１１１は、割り付け処理の対象となる配置区分として、「最も近い外周辺」の数が最も少ない配置区分を選択する（ステップＳ５０２参照）。ここでは、外周辺Ｓに対応する４個の配置区分ＡＷＳ，ＡＳ，ＡＳＥ，ＡＣから、配置区分ＡＳが選択される。
【００３９】
演算処理部１１１は、配置区分ＡＳに配置されたタワーポストを、外周辺Ｓに近いものから順に、外周辺Ｓに割り付ける（ステップＳ５０３参照）。ここでは、タワーポストＴ(6,3) ，Ｔ(6,4) ，Ｔ(5,3) ，Ｔ(5,4) の順に、選択されるものとする。演算処理部１１１は、割り付けたタワーポストが配置区分ＡＳ内の最後のタワーポストＴ(5,4) を割り付けると、配置区分ＡＳに対する割り付け処理を終了する（ステップＳ５０４参照）。また、この割り付け処理は、割り付け処理が施されたタワーポストの個数が、その外周辺に配列されたパッド数に達するまで行われ、かかるパッド数に達したときは当該外周辺への割り付け処理を終了する（ステップＳ５０５参照）。ここでは、外周辺Ｓのパッド数は１０個であり且つ配置区分ＡＳのタワーポスト数は４個なので、配置区分ＡＳ内のタワーポストＴ(6,3) ，Ｔ(6,4) ，Ｔ(5,3) ，Ｔ(5,4) はすべて外周辺Ｓに割り付けられる。
【００４０】
続いて、演算処理部１１１は、割り付け処理の対象となる配置区分として、先に選択された配置区分の両側に位置している配置区分を選択する（ステップＳ５０６参照）。ここでは、配置区分ＡＳの両側の配置区分ＡＷＳ，ＡＳＥが選択される。
【００４１】
演算処理部１１１は、配置区分ＡＷＳ，ＡＳＥに配置されたタワーポストを、順次選択し、外周辺Ｓに割り付ける（ステップＳ５０７参照）。このときの割り付けは、外周辺Ｓに近く且つ配置区分ＡＳに近いタワーポストから順に、配置領域４３０の対角線方向に沿って行われる。この実施形態では、まずタワーポストＴ(6,2) が割り付けられ、次にタワーポストＴ(6,5) が割り付けられ、さらにタワーポストＴ(6,1) ，Ｔ(5,2) ，Ｔ(6,6) ，Ｔ(5,5) の順で割り付けられる。上述の配置区分ＡＳに対する処理と同様、演算処理部１１１は、配置区分ＡＷＳ，ＡＳＥ内の最後のタワーポストを割り付けると配置区分ＡＷＳ，ＡＳＥに対する割り付け処理を終了し（ステップＳ５０８参照）、また、割り付け処理されたタワーポストの個数が当該外周辺に配列されたパッド数に達したときは当該外周辺への割り付け処理を終了する（ステップＳ５０９参照）。ここでは、タワーポストＴ(5,5) が割り付けられた時点で、割り付けられたタワーポストの個数が１０個となるので、外周辺Ｓに対する割り付け処理は終了する。このため、演算処理部１１１は、ステップＳ５１０〜Ｓ５１２を実行せずに、ステップＳ５１３にジャンプする。
【００４２】
次に、演算処理部１１１は、すべての外周辺に対する処理が終了したか否かをチェックする（ステップＳ５１４参照）。ここでは、外周辺Ｅ，Ｎ，Ｗに対する処理が終了していないので、演算処理部１１１は、ステップＳ５０１に戻る。
【００４３】
ステップＳ５０１で、演算処理部１１１は、再び、割り付け処理の対象となる外周辺を選択する。ここでは、パッド数が二番目に多い外周辺である、外周辺Ｅが選択される。
【００４４】
さらに、演算処理部１１１は、割り付け処理の対象となる配置区分として、外周辺Ｅに対応する４個の配置区分ＡＳＥ，ＡＥ，ＡＥＮ，ＡＣから配置区分ＡＥを選択する（ステップＳ５０２参照）。
【００４５】
ステップＳ５０３〜Ｓ５０５では、上述の場合と同様にして、タワーポストＴ(4,6) ，Ｔ(3,6) ，Ｔ(4,5) ，Ｔ(3,5) に対して、外周辺Ｅに割り付けられる。
【００４６】
続いて、ステップＳ５０６では、割り付け処理の対象となる配置区分として、先に選択された配置区分ＡＥの両側の配置区分ＡＳＥ，ＡＥＮが選択される。
【００４７】
ステップＳ５０７で、演算処理部１１１は、上述の場合と同様、配置区分ＡＳＥ，ＡＥＮに配置されたタワーポストを順次選択し、外周辺Ｓに割り付ける。このとき、上述の処理で外周辺Ｓに割り付けられたタワーポストＴ(5,5) ，Ｔ(6,5) ，Ｔ(6,6) は、選択されない。この実施形態では、まずタワーポストＴ(5,6) が割り付けられ、次にタワーポストＴ(2,6) が割り付けられ、さらにタワーポストＴ(1,6) ，Ｔ(2,5) ，Ｔ(1,5) の順で割り付けられる。
【００４８】
タワーポストＴ(1,5) が割り付けられた時点で、割り付けられたタワーポストの個数が外周辺Ｅのパッド数（すなわち９個）に達するので、外周辺Ｅに対する割り付け処理は終了する（ステップＳ５０９参照）。
【００４９】
次に、演算処理部１１１は、すべての外周辺に対する処理が終了したか否かをチェックする（ステップＳ５１４参照）。ここでは、外周辺Ｎ，Ｗに対する処理が終了していないので、演算処理部１１１は、ステップＳ５０１に戻る。
【００５０】
ステップＳ５０１で、演算処理部１１１は、再び、割り付け処理の対象となる外周辺を選択する。外周辺Ｎ，Ｗのパッド数はともに７個であるので、どちらの外周辺の割り付け処理を先に行ってもよいが、ここでは、外周辺Ｗが選択されるものとする。
【００５１】
演算処理部１１１は、上述の外周辺Ｅに対する処理と同様にして、配置区分ＡＷに対する割り付け処理を行い、さらに、配置区分ＡＷＳ，ＡＮＷに対する割り付け処理を行う。そして、タワーポストＴ(1,1) が割り付けられた時点で、割り付けられたタワーポストの個数が外周辺Ｅのパッド数（すなわち７個）に達するので、外周辺Ｅに対する割り付け処理は終了する（ステップＳ５０９参照）。
【００５２】
続いて、演算処理部１１１は、すべての外周辺に対する処理が終了したか否かをチェックし（ステップＳ５１４参照）、外周辺Ｎに対する処理が終了していないと判断してステップＳ５０１に戻る。
【００５３】
ステップＳ５０１で、演算処理部１１１は、割り付け処理の対象となる外周辺Ｎを選択する。そして、演算処理部１１１は、上述と同様にして、配置区分ＡＮに対する割り付け処理を行い、さらに、配置区分ＡＥＮ，ＡＮＷに対する割り付け処理を行う。ここでは、割り付け処理されたタワーポスト数が外周辺Ｎのパッド数（すなわち、７個）に達する前に、配置区分ＡＥＮ，ＡＮＷの全タワーポストに対する割り付け処理が終了する（ステップＳ５０８，Ｓ５０９参照）。
【００５４】
次は、演算処理部１１１は、ステップＳ５１０で、配置区分ＡＣを選択する。そして、演算処理部１１１は、タワーポストＴ(3,4) を、外周辺Ｎに割り付ける（ステップＳ５１１参照）。続いて、演算処理部１１１は、配置区分ＡＣ内の全タワーポストに対する処理が終了したか否かをチェックする（Ｓ５１２参照）。ここでは、全タワーポストに対する処理が終了したので、演算処理部１１１は、ステップＳ５１３にジャンプする。ここでは、最後の外周辺Ｎに対する処理が終了したので、割付辺決定工程Ｓ２０２を終了する。
【００５５】
なお、図６において、タワーポスト内の符号は、当該タワーポストが割り付けられた外周辺を示している。
【００５６】
配置カラム決定工程
配置カラム決定工程Ｓ２０３（図２参照）について、図７および図８を用いて説明する。ここで、図７は本工程Ｓ２０３を示す詳細フローチャートであり、図８は本工程Ｓ２０３終了時のレイアウトデータを示す概念図である。以下に説明するように、配置カラム決定工程Ｓ２０３では、同じ外周辺に割り付けられたタワーポストを当該外周辺と垂直な方向に並ぶタワーポストごとにグループ化するとともに、これらのグループのタワーポスト数に対応させて、当該外周辺に配列されたパッドを一端から順にグループ化する。
【００５７】
まず、演算処理部１１１は、対象となる外周辺を選択する（ステップＳ７０１参照）。本工程Ｓ２０３においては、外周辺の選択順序は任意であるが、ここでは外周辺Ｓが最初に選択されるものとする。
【００５８】
次に、演算処理部１１１は、上述の割付辺決定工程Ｓ２０２で外周辺Ｓに割り付けられた各タワーポストを、外周辺Ｓと垂直な方向（すなわち、カラム方向）に並ぶタワーポストごとにグループ化する（ステップＳ７０２参照）。これにより、タワーポストのグループＴＳＧ１〜ＴＳＧ６が設定される。
【００５９】
続いて、演算処理部１１１は、外周辺ＳのパッドＰＳ１〜ＰＳ１０を、外周辺の一端側（ここでは、図８の左側とする）から順にグループ化する（ステップＳ７０３参照）。各パッド・グループに含まれるパッド数は、対応するタワーポスト・グループＴＳＧ１〜ＴＳＧ６のタワーポスト数と同じ数に設定される。例えば、最も左側のタワーポスト・グループＴＳＧ１には１個のタワーポストＴ(6,1) が属しているので、これに対応させて、最も左側の１個のパッドＰＳ１が属するグループＰＳＧ１が設定される。次いで、左側から二番目のタワーポスト・グループＴＳＧ２には２個のタワーポストＴ(5,2) ，Ｔ(6,2) が属しているので、これに対応させて、次の２個のパッドＰＳ２，ＰＳ３が属するグループＰＳＧ２が設定される。このようにして、図８に示したような、パッド・グループＰＳＧ１〜ＰＳＧ６が設定される。
【００６０】
この実施形態では、タワーポスト・グループＴＳＧ１〜ＴＳＧ６を特定する番号「１」〜「６」を、各タワーポストのカラム番号と称する。
【００６１】
その後、演算処理部１１１は、すべての外周辺に対する処理が終了したか否かをチェックする（ステップＳ７０４参照）。そして、演算処理部１１１は、全外周辺に対する処理が終了するまで、ステップＳ７０１〜Ｓ７０４の処理を繰り返す。
【００６２】
以上のような処理により、各タワーポストのカラム番号が決定される。
【００６３】
配置ロウ決定工程
配置ロウ決定工程Ｓ２０４（図２参照）について、図９および図１０を用いて説明する。ここで、図９は本工程Ｓ２０４を示す詳細フローチャートであり、図１０は本工程Ｓ２０４のレイアウトデータを示す概念図である。以下に説明するように、配置ロウ決定工程Ｓ２０４では、対応するタワーポストのグループおよびパッドのグループ間で、外部接続電極とパッドとの対応付けを行う。
【００６４】
まず、演算処理部１１１は、対象となるカラムを選択する（ステップＳ９０１参照）。本工程Ｓ２０４においては、カラムの選択順序は任意であるが、ここではカラム１，２，・・・の順に選択されるものとする。
【００６５】
演算処理部１１１は、選択されたカラムについて、タワーポストの個数をチェックする（ステップＳ９０２参照）。そして、タワーポストの個数が「１」の場合、演算処理部１１１は、そのタワーポストのロウ番号として、そのまま「１」を割り当てる（ステップＳ９０３参照）。例えば、図１０において、タワーポストＴ(6,1) のロウ番号としては、そのまま「１」が割り当てられる。次に、演算処理部１１１は、このカラムが最後のカラムであるか否かをチェックする（ステップＳ９０６参照）。最後のカラムでない場合、演算処理部１１１は、ステップＳ９０１に戻る。
【００６６】
一方、ステップＳ９０２においてタワーポストが２個以上の場合、演算処理部１１１は、これらタワーポストの中心座標と、対応する各パッドの中心座標とをチェックする（ステップＳ９０４参照）。なお、ここでは、対応する外周辺の方向に沿った座標をｘ座標とし、当該外周辺に直角な座標をｙ座標とする（図１０参照）。
【００６７】
そして、タワーポストよりもｘ座標が小さいパッド（外周辺Ｓにおいては、該当する各タワーポストよりも左側に配置されたパッド）については、ｘ座標が小さいパッドから順に、ｙ座標が大きいタワーポスト（外周辺から遠いタワーポスト）に割り当てる。そして、ｘ座標が小さいパッドに割り当てられたタワーポストから順に、ロウ番号１，２，・・・を割り当てる。図１０の例では、タワーポストＴ(6,2) にはロウ番号「１」が割り当てられ、タワーポストＴ(5,2) にはロウ番号「２」が割り当てられる。
【００６８】
一方、ステップＳ９０４で、タワーポストよりもｘ座標が大きいパッド（外周辺Ｓにおいては、該当する各タワーポストよりも右側に配置されたパッド）については、ｘ座標が大きいパッドから順に、ｙ座標が大きいタワーポストに割り当てる（ステップＳ９０５参照）。そして、ｘ座標が小さいパッドに割り当てられたタワーポストから順に、ロウ番号１，２，・・・を割り当てる。図１０の例では、タワーポストＴ(6,5) にはロウ番号「１」が割り当てられ、タワーポストＴ(5,5) にはロウ番号「２」が割り当てられる。
【００６９】
ステップＳ９０６で最後のカラムであると判断されたとき、配置ロウ決定工程Ｓ２０４が終了する。
【００７０】
タワーポスト配置編集工程
タワーポスト配置編集工程Ｓ２０５（図２参照）について、図１１および図１２を用いて説明する。ここで、図１１は本工程Ｓ２０５を示す詳細フローチャートであり、図１２は本工程Ｓ２０５のレイアウトデータを示す概念図である。以下に説明するように、このタワーポスト配置編集工程Ｓ２０５では、上述の配置ロウ決定工程で対応づけられたタワーポストとパッドとを直線状の仮想配線で接続して、各仮想配線における交差の有無を順にチェックし、交差が存在する仮想配線どうしでタワーポストとパッドとの対応関係を置換する。
【００７１】
まず、演算処理部１１１は、各タワーポストに割り当てられたロウ番号、カラム番号に基づいて、各タワーポストと各パッドとを、直線状の仮想配線で結ぶ（ステップＳ１１０１参照）。
【００７２】
続いて、演算処理部１１１は、置換処理数を示す変数ｎに「０」を代入し（ステップＳ１１０２参照）、チェック対象となる仮想配線を選択する（ステップＳ１１０３参照）。交差のチェックを行う順序は任意であるが、例えば所定のタワーポストに対応する仮想配線から時計回り或いは反時計回りにチェックしていけばよい。
【００７３】
演算処理部１１１は、選択された仮想配線に対して、他の仮想配線と交差しているか否かをチェックする（ステップＳ１１０４参照）。
【００７４】
交差が確認された場合、演算処理部１１１は、交差している仮想配線どうしで、各タワーポストに対応するパッドを置換する（ステップＳ１１０５参照）。例えば、図１０において、タワーポストＴ(1,5) とパッドＰＥ９とを結ぶ仮想配線１２０１は、タワーポストＴ(3,4) とパッドＰＮ１とを結ぶ仮想配線１２０２と交差している。この場合、演算処理部１１１は、対応するパッドＰＥ９，ＰＮ１を置換する。これにより、タワーポストＴ(1,5) とパッドＰＮ１とが新たな仮想配線１２１１で結ばれ且つタワーポストＴ(3,4) とパッドＰＥ９とが新たな仮想配線１２１２で結ばれることになって、かかる交差は無くなる。なお、この処理によって、新たな仮想配線１２１２と仮想配線１２０３，１２０４との間にそれぞれ新たな交差が発生するが、これらの交差については、その後の仮想配線１２０３，１２０４に対する置換処理によって対処される。置換処理が終了すると、演算処理部１１１は、置換処理数ｎに「１」を加える（ステップＳ１１０６参照）。
【００７５】
一方、ステップＳ１１０４で交差が確認されなかった場合、演算処理部１１１は、ステップＳ１１０５の処理をスキップする。
【００７６】
次に、演算処理部１１１は、選択された仮想配線が最後の仮想配線か否かを判断し（ステップＳ１１０７参照）、最後でない場合はステップＳ１１０３に戻る。
【００７７】
一方、ステップＳ１１０７で最後の仮想配線であると判断した場合、演算処理部１１１は、置換処理数ｎの値をチェックする（ステップＳ１１０８参照）。そして、置換処理数ｎが「０」でない場合、演算処理部１１１は、ｎに再び「０」を代入した後（ステップＳ１１０２参照）、最初の仮想配線から交差の有無のチェックをやり直す（ステップＳ１１０３〜Ｓ１１０７参照）。一方、ｎが「０」の場合、演算処理部１１１は、タワーポスト配置編集工程Ｓ２０５を終了する。
【００７８】
上述のように、交差を解消するためにパッドの置換を行うと、新たな交差が発生する場合がある。このため、このタワーポスト配置編集工程Ｓ２０５では、最後の仮想配線の確認が終了した時点の置換処理数ｎが「０」になるまで、ステップＳ１１０２〜Ｓ１１０７の処理が繰り返される。
【００７９】
タワーポスト配置工程
最後に、タワーポスト配置工程Ｓ２０６（図２参照）について、図１３および図１４を用いて説明する。ここで、図１４は本工程Ｓ２０６を示す詳細フローチャートであり、図１４は本工程Ｓ２０６のレイアウトデータを示す概念図である。
【００８０】
演算処理部１１１は、対象となるパッドを選択する（ステップＳ１３０１参照）。本工程Ｓ２０６においては、パッドの選択順序は任意であるが、例えば外周辺Ｓの最小座標のパッドから反時計回りに選択していけばよい。
【００８１】
次に、演算処理部１１１は、選択されたパッドに対応するタワーポストのロウ番号およびカラム番号を特定する（ステップＳ１３０２参照）。この特定は、例えば配置状態記憶部１１２（図１参照）に一時保存された情報などを用いて行えばよい。
【００８２】
続いて、演算処理部１１１は、このロウ番号およびカラム番号に対応するタワーポストセルを、外部記憶装置１２０のセル格納領域１２２（図１参照）から読み出し、当該レイアウトに配置する（ステップＳ１３０３参照）。
【００８３】
そして、演算処理部１１１は、選択されたパッドが最後のパッドであるか否かをチェックし（ステップＳ１３０４参照）、最後のパッドであると判断されるまでステップＳ１３０１〜Ｓ１３０３を繰り返す。
【００８４】
一方、ステップＳ１３０４で最後のパッドであると判断された場合、演算処理部１１１は、完成したレイアウトデータを、レイアウトデータ格納領域１２３に格納し（ステップＳ１３０５参照）、タワーポストの自動配置処理を終了する。
【００８５】
なお、レイアウトデータ格納領域１２３に格納されたレイアウトデータは、他の自動設計装置に読み出されて、次の自動設計工程に使用される。
【００８６】
以上説明したように、この実施形態では、各タワーポストを、最も近い外周辺のパッドに接続されるように、自動配置することができる。したがって、タワーポストとパッドとを結ぶ配線の配線長を短くすることが可能である。
【００８７】
また、この実施形態では、最も近い外周辺が２個以上存在する配置区分のタワーポストを、これらの外周辺のいずれかに適宜割り付けることができる。したがって、各外周辺のパッド数やパッドの総数の制約がない。
【００８８】
さらに、この実施形態では、タワーポストとパッドとを直線状の仮想配線で接続し、仮想配線の交差が存在する場合にはこれらの仮想配線どうしでパッドを置換する。したがって、一層配線のみで自動配線を実現することが可能である。
【図面の簡単な説明】
【００８９】
【図１】実施形態に係る自動設計装置の全体構成を概略的に示すブロック図である。
【図２】実施形態に係るタワーポスト自動配置処理の全体構成を示す概略フローチャートである。
【図３】実施形態に係る配置領域決定工程を示すフローチャートである。
【図４】実施形態に係る配置領域決定工程のレイアウトデータを示す概念図である。
【図５】実施形態に係る割付辺決定工程を示すフローチャートである。
【図６】実施形態に係る割付辺決定工程のレイアウトデータを示す概念図である。
【図７】実施形態に係る配置カラム決定工程を示すフローチャートである。
【図８】実施形態に係る配置カラム決定工程のレイアウトデータを示す概念図である。
【図９】実施形態に係る配置ロウ決定工程を示すフローチャートである。
【図１０】実施形態に係る配置ロウ決定工程のレイアウトデータを示す概念図である。
【図１１】実施形態に係るタワーポスト配置編集工程を示すフローチャートである。
【図１２】実施形態に係るタワーポスト配置編集工程のレイアウトデータを示す概念図である。
【図１３】実施形態に係るタワーポスト配置工程を示すフローチャートである。
【図１４】実施形態に係るタワーポスト配置工程のレイアウトデータを示す概念図である。
【符号の説明】
【００９０】
１００  自動設計装置
１１０  自動配置処理装置
１１１  演算処理部
１１２  配置状態記憶部
１２０  外部記憶装置
１２１  接続データ格納領域
１２２  セル格納領域
１２３  レイアウトデータ格納領域
１３０  入力装置
１４０  表示装置
【図１】
2006332516.tif 000003
【図２】
2006332516.tif 000004
【図３】
2006332516.tif 000005
【図４】
2006332516.tif 000006
【図５】
2006332516.tif 000007
【図６】
2006332516.tif 000008
【図７】
2006332516.tif 000009
【図８】
2006332516.tif 000010
【図９】
2006332516.tif 000011
【図１０】
2006332516.tif 000012
【図１１】
2006332516.tif 000013
【図１２】
2006332516.tif 000014
【図１３】
2006332516.tif 000015
【図１４】
2006332516.tif 000016