基準ハイトセルと、前記基準ハイトセルよりも第1方向における高さが高いマルチハイトセルと、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給し、且つ、前記第1方向に垂直な第2方向に延伸する第1電源配線と、前記正電源電圧及び前記負電源電圧のうちの他方である第2電源電圧を供給し、且つ、前記第2方向に延伸する第2電源配線とを具備し、前記マルチハイトセルは、セル内回路と、前記セル内回路に電気的に接続され、前記第1方向に延伸する第1及び第2電源供給配線とを備え、前記基準ハイトセルの前記第1方向における高さをa、前記マルチハイトセルの前記第1方向における高さをb、前記第1及び第2電源配線の前記第1方向における幅をwとしたときに、前記第1電源供給配線は、少なくとも、前記マルチハイトセルの下端からw/2だけ前記第1方向に離れた第1位置と前記マルチハイトセルの下端からb-a-w/2だけ前記第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられ、前記第2電源供給配線は、少なくとも、前記マルチハイトセルの下端からaw/2だけ前記第1方向に離れた第3位置と前記マルチハイトセルの下端からb-w/2だけ前記第1方向に離れた第4位置との間の第2高さ範囲をカバーするように設けられ、前記第1電源配線は、前記第1電源供給配線に接続されるように設けられ、前記第2電源配線は、前記第2電源供給配線に接続されるように設けられている半導体集積回路。請求項1に記載の半導体集積回路であって、前記第1電源配線は、前記基準ハイトセルの下端を通過するように設けられ、前記第2電源配線は、前記基準ハイトセルの上端を通過するように設けられる半導体集積回路。セル配置手段により、少なくとも一の基準ハイトセルと、前記基準ハイトセルよりも第1方向における高さが高い少なくとも一のマルチハイトセルとを含む複数のセルを配置する配置工程と、配線手段により、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給する第1電源配線と、前記正電源電圧及び前記負電源電圧のうちの他方である第2電源電圧を供給する第2電源配線とを、前記第1方向に垂直な第2方向に延伸するように設ける工程とを具備し、前記マルチハイトセルは、セル内回路と、前記セル内回路に電気的に接続され、前記第1方向に延伸する第1及び第2電源供給配線とを備えており、前記基準ハイトセルの前記第1方向における高さをa、前記マルチハイトセルの前記第1方向における高さをb、前記第1及び第2電源配線の前記第1方向における幅をwとしたときに、前記第1電源供給配線は、少なくとも、前記マルチハイトセルの下端からw/2だけ前記第1方向に離れた第1位置と前記マルチハイトセルの下端からb-a-w/2だけ前記第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられ、前記第2電源供給配線は、少なくとも、前記マルチハイトセルの下端からaw/2だけ前記第1方向に離れた第3位置と前記マルチハイトセルの下端からb-w/2だけ前記第1方向に離れた第4位置との間の第2高さ範囲をカバーするように設けられ、前記第1電源配線は、前記第1電源供給配線に接続されるように設けられ、前記第2電源配線は、前記第2電源供給配線に接続されるように設けられる半導体集積回路の設計方法。請求項3に記載の半導体集積回路の設計方法であって、前記第1電源配線は、前記基準ハイトセルの下端を通過するように設けられ、前記第2電源配線は、前記基準ハイトセルの上端を通過するように設けられる半導体集積回路の設計方法。請求項3又は4に記載の半導体集積回路の設計方法であって、前記配置工程は、前記基準ハイトセルと同じ高さを有し且つ前記第1方向に並ぶように規定された複数のセル行に、前記複数のセル行のそれぞれにおいて前記複数のセルが前記第2方向に並ぶように、前記複数のセルを初期的に配置する工程と、前記複数のセル行のうちの第1セル行及び前記第1セル行に隣接する第2セル行にかけて前記少なくとも一のマルチハイトセルのうちの第1マルチハイトセルが配置され、これにより、前記第2セル行に前記基準ハイトセルよりも低い高さを有し、前記複数のセルのいずれもが配置されていない空き領域であるデッドスペースが形成された場合に、前記少なくとも一のマルチハイトセルのうち前記第2セル行に隣接する第3セル行に配置された第2マルチハイトセルを前記デッドスペースの少なくとも一部を埋めるように再配置する工程とを含む半導体集積回路の設計方法。請求項5に記載の半導体集積回路の設計方法であって、前記配置工程が、更に、前記第2マルチハイトセル以上の幅を有する前記デッドスペースが前記第2セル行に存在せず、且つ、前記第2セル行に存在する前記基準ハイトセルの高さを有し、前記複数のセルのいずれもが配置されていない空き領域である一又は複数の空きサイトの幅と前記デッドスペースの幅の合計が、前記第2マルチハイトセルの幅以上である場合、前記一又は複数の空きサイトと前記デッドスペースとで形成される領域の少なくとも一部を埋めるように前記第2マルチハイトセルを再配置する工程を含む半導体集積回路の設計方法。請求項6に記載の半導体集積回路の設計方法であって、前記第2マルチハイトセル以上の幅を有する前記デッドスペースが前記第2セル行に存在せず、前記第2セル行に位置し、前記基準ハイトセルの高さを有すると共に前記複数のセルのいずれもが配置されていない空き領域である空きサイトの幅と、前記デッドスペースの幅の合計が前記第2マルチハイトセルの幅より小さく、前記第2セル行に配置された前記基準ハイトセルを再配置することで形成された前記基準ハイトセルの高さを有する空き領域である再配置空きサイトの幅が前記第2マルチハイトセルの幅以上である場合に、前記再配置空きサイトの少なくとも一部を埋めるように前記第2マルチハイトセルを再配置する工程を含む半導体集積回路の設計方法。請求項3又は4に記載の半導体集積回路の設計方法であって、前記配置工程は、前記基準ハイトセルと同じ高さを有し且つ前記第1方向に並ぶように規定された複数のセル行に、前記複数のセル行のそれぞれにおいて前記複数のセルが前記第2方向に並ぶように、前記複数のセルを配置する工程と、前記複数のセル行のうちの第1セル行及び前記第1セル行に隣接する第2セル行にかけて前記少なくとも一のマルチハイトセルのうちの第1マルチハイトセルが配置され、これにより、前記第2セル行に前記基準ハイトセルよりも低い高さを有し、前記複数のセルのいずれもが配置されていない空き領域であるデッドスペースが形成された場合に、前記第2セル行の前記デッドスペースの幅と、前記第2セル行に位置し、前記基準ハイトセルの高さを有すると共に前記複数のセルのいずれもが配置されていない空き領域である空きサイトの幅と、前記少なくとも一のマルチハイトセルのうち前記第2セル行に隣接する第3セル行に配置された複数の第2マルチハイトセルの幅をそれぞれに認識する工程と、前記デッドスペース及び前記空きサイトの少なくとも一部を埋めるように前記第2マルチハイトセルを再配置する工程とを具備し、前記デッドスペース及び前記空きサイトを埋める前記第2マルチハイトセルの組み合わせが、認識された前記第2セル行の前記デッドスペースの幅と、前記第2セル行の前記空きサイトの幅と、前記第3セル行に配置された前記第2マルチハイトセルの幅とに基づいて決定される半導体集積回路の設計方法。基準ハイトセルと、前記基準ハイトセルよりも第1方向における高さが高いマルチハイトセルとを定義したセルライブラリを記憶する記憶装置と、前記セルライブラリに定義された前記基準ハイトセルと前記マルチハイトセルとを含む複数のセルを配置するセル配置手段と、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給する第1電源配線と、前記正電源電圧及び前記負電源電圧のうちの他方である第2電源電圧を供給する第2電源配線とを、前記第1方向に垂直な第2方向に延伸するように設ける配線手段とを具備し、前記セルライブラリにおいて、前記マルチハイトセルは、セル内回路と、前記セル内回路に電気的に接続され、且つ、前記第1方向に延伸する第1及び第2電源供給配線とを備えているように定義され、前記基準ハイトセルの前記第1方向における高さをa、前記マルチハイトセルの前記第1方向における高さをb、前記第1及び第2電源配線の前記第1方向における幅をwとしたときに、前記第1電源供給配線は、前記ライブラリにおいて、少なくとも、前記マルチハイトセルの下端からw/2だけ前記第1方向に離れた第1位置と前記マルチハイトセルの下端からb-a-w/2だけ前記第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられているように定義されており、前記ライブラリにおいて、前記第2電源供給配線は、少なくとも、前記マルチハイトセルの下端からaw/2だけ前記第1方向に離れた第3位置と前記マルチハイトセルの下端からb-w/2だけ前記第1方向に離れた第4位置との間の第2高さ範囲をカバーするように定義されており、前記配線手段は、前記第1電源配線を前記第1電源供給配線に接続されるように配置すると共に、前記第2電源配線は、前記第2電源供給配線に接続されるように配置する半導体集積回路の設計装置。基準ハイトセルと、前記基準ハイトセルよりも第1方向における高さが高いマルチハイトセルとを定義したセルライブラリを記憶する記憶装置を備えたコンピュータを、前記セルライブラリに定義された前記基準ハイトセルと前記マルチハイトセルとを含む複数のセルを配置するセル配置手段と、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給する第1電源配線と、前記正電源電圧及び前記負電源電圧のうちの他方である第2電源電圧を供給する第2電源配線とを、前記第1方向に垂直な第2方向に延伸するように設ける配線手段として機能させるプログラムであって、前記セルライブラリにおいて、前記マルチハイトセルは、セル内回路と、前記セル内回路に電気的に接続され、且つ、前記第1方向に延伸する第1及び第2電源供給配線とを備えているように定義され、前記基準ハイトセルの前記第1方向における高さをa、前記マルチハイトセルの前記第1方向における高さをb、前記第1及び第2電源配線の前記第1方向における幅をwとしたときに、前記第1電源供給配線は、前記ライブラリにおいて、少なくとも、前記マルチハイトセルの下端からw/2だけ前記第1方向に離れた第1位置と前記マルチハイトセルの下端からb-a-w/2だけ前記第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられているように定義されており、前記ライブラリにおいて、前記第2電源供給配線は、少なくとも、前記マルチハイトセルの下端からaw/2だけ前記第1方向に離れた第3位置と前記マルチハイトセルの下端からb-w/2だけ前記第1方向に離れた第4位置との間の第2高さ範囲をカバーするように定義されており、前記配線手段は、前記第1電源配線を前記第1電源供給配線に接続されるように配置すると共に、前記第2電源配線は、前記第2電源供給配線に接続されるように配置するプログラム。したがって、本発明の目的は、セルベースの半導体集積回路において、異なるセル高さを有するセルを効率良く配置するための技術を提供することにある。本発明の一の観点では、半導体集積回路が、基準ハイトセルと、基準ハイトセルよりも第1方向における高さが高いマルチハイトセルと、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給し、且つ、第1方向に垂直な第2方向に延伸する第1電源配線と、正電源電圧及び負電源電圧のうちの他方である第2電源電圧を供給し、且つ、第2方向に延伸する第2電源配線とを具備する。マルチハイトセルは、セル内回路と、セル内回路に電気的に接続され、第1方向に延伸する第1及び第2電源供給配線とを備えている。基準ハイトセルの第1方向における高さをa、マルチハイトセルの第1方向における高さをb、電源配線の第1方向における幅をwとしたときに、第1電源供給配線は、少なくとも、マルチハイトセルの下端からw/2だけ第1方向に離れた第1位置とマルチハイトセルの下端からb-a-w/2だけ第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられている。第2電源供給配線は、少なくとも、マルチハイトセルの下端からaw/2だけ第1方向に離れた第3位置とマルチハイトセルの下端からb-w/2だけ第1方向に離れた第4位置との間の第2高さ範囲をカバーするように設けられている。第1電源配線は、第1電源供給配線に接続されるように配置され、第2電源配線は、第2電源供給配線に接続されるように配置されている。本発明の他の観点では、半導体集積回路の設計方法が、セル配置手段により、基準ハイトセルと、基準ハイトセルよりも第1方向における高さが高いマルチハイトセルとを配置する工程と、配線手段により、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給する第1電源配線と、正電源電圧及び負電源電圧のうちの他方である第2電源電圧を供給する第2電源配線とを、第1方向に垂直な第2方向に延伸するように配置する工程とを具備している。マルチハイトセルは、セル内回路と、セル内回路に電気的に接続され、第1方向に延伸する第1及び第2電源供給配線とを備えている。基準ハイトセルの第1方向における高さをa、マルチハイトセルの第1方向における高さをb、電源配線の第1方向における幅をwとしたときに、第1電源供給配線は、少なくとも、マルチハイトセルの下端からw/2だけ第1方向に離れた第1位置とマルチハイトセルの下端からb-a-w/2だけ第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられる。また、第2電源供給配線は、少なくとも、マルチハイトセルの下端からaw/2だけ第1方向に離れた第3位置とマルチハイトセルの下端からb-w/2だけ第1方向に離れた第4位置との間の第2高さ範囲をカバーするように設けられる。第1電源配線は、第1電源供給配線に接続されるように配置され、第2電源配線は、第2電源供給配線に接続されるように配置される。本発明の更に他の観点では、半導体集積回路の設計装置が、基準ハイトセルと、基準ハイトセルよりも第1方向における高さが高いマルチハイトセルとを定義したライブラリを記憶する記憶装置と、基準ハイトセルと、基準ハイトセルよりも第1方向における高さが高いマルチハイトセルとを配置するセル配置手段と、正電源電圧及び負電源電圧のうちの一方である第1電源電圧を供給する第1電源配線と、正電源電圧及び負電源電圧のうちの他方である第2電源電圧を供給する第2電源配線とを、第1方向に垂直な第2方向に延伸するように配置する配線手段とを具備する。セルライブラリにおいて、マルチハイトセルは、セル内回路と、セル内回路に電気的に接続され、第1方向に延伸する第1及び第2電源供給配線とを備えているように定義される。基準ハイトセルの第1方向における高さをa、マルチハイトセルの第1方向における高さをb、電源配線の第1方向における幅をwとしたときに、第1電源供給配線は、セルライブラリにおいて、少なくとも、マルチハイトセルの下端からw/2だけ第1方向に離れた第1位置とマルチハイトセルの下端からb-a-w/2だけ第1方向に離れた第2位置との間の第1高さ範囲をカバーするように設けられているように定義されている。更に、セルライブラリにおいて、第2電源供給配線は、少なくとも、マルチハイトセルの下端からaw/2だけ第1方向に離れた第3位置とマルチハイトセルの下端からb-w/2だけ第1方向に離れた第4位置との間の第2高さ範囲をカバーするように定義されている。配線手段は、第1電源配線を第1電源供給配線に接続されるように設けると共に、第2電源配線は、第2電源供給配線に接続されるように設ける。本発明によれば、セルベースの半導体集積回路において、異なるセル高さを有するセルを効率良く配置するための技術が提供される。以下、添付図面を参照しながら本発明の実施形態について説明する。第1の実施形態:図3Aは、本発明の第1の実施形態における基本ハイトセル30の平面レイアウトを示す平面図であり、図3Bは、マルチハイトセル40の平面レイアウトを示す平面図である。以下では、横方向にX軸が上下方向にY軸が取られた直交座標系を用いて説明を行う。図3Aの基本ハイトセル30と図3Bのマルチハイトセル40の、それぞれのセル枠1A、1Bの下端のY座標が0と定義される。また、図3A、図3Bは、いずれも、セルベース設計において使用されるセルライブラリに登録されているセルレイアウトを示していることに留意されたい。後述のように、マルチハイトセル40には、配線工程において電源メッシュを構成する電源配線が追加される。図3A、図3Bにおいて、符号1A、1Bはセル枠を示しており、符号2はNウェル、符号3はPウェルを示している。Nウェル2にはP型不純物が高濃度にドープされた拡散領域2aが形成され、Pウェル3にはN型不純物が高濃度にドープされた拡散領域3aが形成される。拡散領域2a、3aを縦断するようにポリシリコン配線4が設けられ、拡散領域2aとポリシリコン配線4とでPMOSトランジスタが形成され、拡散領域3aとポリシリコン配線4とでNMOSトランジスタが形成される。これらのPMOSトランジスタ及びNMOSトランジスタにより、セル内回路が形成される。図3A、図3Bでは、Nウェル2がPウェル3の上方に位置しているように図示されているが、実際のセルレイアウトでは、Pウェル3がNウェル2の上方に位置している配置も可能であることに留意されたい。図3Aに図示されているように、基本ハイトセル30の上端にはVDD電源配線8Aが配置され、下端にはVSS電源配線7Aが配置される。VSS電源配線7A及びVDD電源配線8Aは、電源メッシュを構成する電源配線であり、X軸方向に延伸するように設けられている。VDD電源配線8AにはVDD側電源供給配線5Aが接続されており、正電源電圧VDDは、VDD側電源供給配線5Aを介して基本ハイトセル30のセル内回路を構成する素子に供給される。同様に、VSS電源配線7AにはVSS側電源供給配線6Aが接続されており、負電源電圧VSSは、VSS側電源供給配線6Aを介して基本ハイトセル30のセル内回路を構成する素子に供給される。VDD側電源供給配線5A、及び、VSS側電源供給配線6Aは、いずれも、Y軸方向に延伸するように設けられている。基本ハイトセル30内のセル内回路の素子の間の電気的接続は、セル内配線9によって行われる。基本ハイトセル30のY軸方向におけるセル高さはaである。基本ハイトセル30に対応して設けられるNウェル2及びPウェル3は、セル枠1AからX軸方向VSS電源配線7A及びVDD電源配線8Aが延伸する方向に距離cだけはみ出して設けられる。Nウェル2及びPウェル3のセル枠1Aからはみ出した部分は、オーバーラップ領域11Aと呼ばれる。一方、図3Bに図示されているように、マルチハイトセル40についても、VDD側電源供給配線5BとVSS側電源供給配線6Bが設けられ、正電源電圧VDD及び負電源電圧VSSは、それぞれ、VDD側電源供給配線5BとVSS側電源供給配線6Bを介してマルチハイトセル40のセル内回路を構成する素子に供給される。マルチハイトセル40のセル高さはbただし、b>aである。マルチハイトセル40のセル高さbは、基本ハイトセル30のセル高さaの整数倍に限定されず、任意に選択可能である。ここで、セルライブラリに登録されているセルレイアウトでは、マルチハイトセル40に電源メッシュを構成する電源配線が設けられていないことに留意されたい。本実施形態では、マルチハイトセル40のVDD側電源供給配線5BとVSS側電源供給配線6Bの配置に特色がある。VSS側電源供給配線6Bは、少なくとも、マルチハイトセル40の下端からw/2だけY軸方向に離れた高さ位置とマルチハイトセル40の下端からb-a-w/2だけY軸方向に離れた高さ位置との間の高さ範囲をカバーするように設けられる。ここで、wは、電源メッシュを構成する電源配線の幅即ち、図3AのVDD電源配線8A、VSS電源配線7Aの幅である。図3Bでは、VSS側電源供給配線6Bがマルチハイトセル40の下端からw/2だけY軸方向に離れた高さ位置からb-a-w/2だけY軸方向に離れた高さ位置まで延伸する構造が図示されているが、VSS側電源供給配線6Bは当該高さ範囲を少なくともカバーすることが要求されるのであり、当該高さ範囲を超えて延伸してもよい。同様に、VDD側電源供給配線5Bは、少なくとも、マルチハイトセル40の下端からaw/2だけY軸方向に離れた高さ位置とマルチハイトセル40の下端からb-w/2だけY軸方向に離れた高さ位置との間の高さ範囲をカバーするように設けられる。VSS側電源供給配線6Bと同様に、VDD側電源供給配線5Bは、当該高さ範囲を少なくともカバーすることが要求されるのであり、当該高さ範囲を超えて延伸してもよい。後述されるように、図3Bに図示されているようなVDD側電源供給配線5BとVSS側電源供給配線6Bの配置は、基本ハイトセル30と隣接してマルチハイトセル40が配置された場合における電源配線の位置の整合性を確保するためのものである。加えて、基本ハイトセル30と隣接して配置された場合のウェル境界の不整合を回避する目的で、マルチハイトセル40の左右端には、基本ハイトセル30のセル枠1AからNウェル2、Pウェル3のオーバーラップ幅cと同じ幅のオーバーラップ領域11Bが、マルチハイトセル40のセル枠1BからNウェル2、Pウェル3の内側方向に取られている。このオーバーラップ領域11Bには、Nウェル2及びPウェル3は規定されていない。図4A~図4Cは、基本ハイトセル30とマルチハイトセル40とが隣接して配置される場合のレイアウトを示す平面図である。半導体集積回路の設計においては、セル配置工程において基本ハイトセル30とマルチハイトセル40とが配置された後、基本ハイトセル30のVSS電源配線7AとVDD電源配線8Aとそれぞれに接続するVSS電源配線7BとVDD電源配線8Bがマルチハイトセル40を横切るように配線される。このとき、VSS電源配線7AとVSS電源配線7Bとが一直線上に配置され、VDD電源配線8AとVDD電源配線8Bとが一直線上に配置される。ここで、本実施形態では、図4A~図4Cに図示されているように、Y軸方向における基本ハイトセル30とマルチハイトセル40の位置関係が、基本ハイトセル30の高さ範囲の全体がマルチハイトセル40の高さ範囲に収まるという条件の下で可変であることに留意されたい。例えば、図4Aに図示されているように、基本ハイトセル30とマルチハイトセル40とが、それらの下端が位置整合するように配置されてもよく、図4Bに図示されているように、それらの上端が位置整合するように配置されてもよい。更に、図4Cに図示されているように、基本ハイトセル30とマルチハイトセル40とが、基本ハイトセル30の下端がマルチハイトセル40の下端から上方にずれ、且つ、基本ハイトセル30の上端がマルチハイトセル40の下端から下方にずれているように配置されてもよい。ここで、本実施形態では、VDD側電源供給配線5B及びVSS側電源供給配線6Bのレイアウトに起因して、基本ハイトセル30とマルチハイトセル40の位置関係が可変であっても電源配線の位置が整合することに留意されたい。まず、VSS側電源供給配線6Bが、マルチハイトセル40の下端からw/2だけY軸方向に離れた高さ位置とマルチハイトセル40の下端からb-a-w/2だけY軸方向に離れた高さ位置との間の高さ範囲をカバーするように設けられていることにより、基本ハイトセル30とマルチハイトセル40の位置関係に関わらずVSS電源配線7AとVSS電源配線7Bとの位置が整合する。同様に、VDD側電源供給配線5Bが、マルチハイトセル40の下端からaw/2だけY軸方向に離れた高さ位置とマルチハイトセル40の下端からb-w/2だけY軸方向に離れた高さ位置との間の高さ範囲をカバーするように設けられていることにより、基本ハイトセル30とマルチハイトセル40の位置関係に関わらずVDD電源配線8AとVDD電源配線8Bとの位置が整合する。このように、本実施形態では、VDD側電源供給配線5B及びVSS側電源供給配線6Bの配置が最適化図3B参照されていることによって、基本ハイトセル30とマルチハイトセル40との高さ方向Y軸方向における相対位置が自在に調節可能である。これにより、例えばスペーサーセルなどを用いることなく異なるセル高さを有するセルを効率良く配置することが可能になる。ここで、基本ハイトセル30のオーバーラップ領域11Aとマルチハイトセル40のオーバーラップ領域11Bとが、基本ハイトセル30とマルチハイトセル40とが隣接して配置されたときにNウェル2及びPウェル3の位置を整合させる役割を果たしていることに留意されたい。基本ハイトセル30とマルチハイトセル40とが隣接して配置されると、それらの相対位置に関わらず、Nウェル2及びPウェル3は、基本ハイトセル30とマルチハイトセル40の間で接続される。本実施形態において、異なるセル高さa、bを有する基本ハイトセル30とマルチハイトセル40とを効率よく配置するためには、基本ハイトセル30とマルチハイトセル40との間でY軸方向の位置関係が可変であることを最大限に利用することが好ましい。ここで、一つの問題は、マルチハイトセル40を配置すると、基本ハイトセル30の高さに満たない高さの空き領域以下、デッドスペースという。ができることである。デッドスペースには、基本ハイトセル30を配置することができないので、セル配置において、デッドスペースを可能な限り排除することが基本ハイトセル30とマルチハイトセル40とを効率よく配置する場合に重要になる。以下では、デッドスペースを可能な限り排除するための設計方法、及び、それを実現する設計装置について説明する。図5は、本発明の一実施形態における半導体集積回路の設計方法において使用される半導体集積回路設計装置の構成を示すブロック図である。当該半導体集積回路設計装置は、コンピュータとして構成されており、CPU51と、メモリ52と、入力装置53と、出力装置54と、外部記憶装置55とを備えている。外部記憶装置55には論理合成ツール61と自動配置ツール62と配線ツール63とがインストールされている。論理合成ツール61がCPU51、メモリ52、入力装置53と、出力装置54とを用いて実行されることで論理合成が行われ、自動配置ツール62が実行されることでセルの配置が行われ、配線ツール63が実行されることで配線が行われる。外部記憶装置55には、更に、セルライブラリ64が格納されている。このセルライブラリ64とは、レイアウトパターン、LEFLibraryExchangeFormatデータ、DEFDesignExchangeFormatデータ等を含むデータの総称である。セルライブラリ64は、図3Aに図示されている基本ハイトセル30のデータを格納する基本ハイトセルライブラリ64aと、図3Bに図示されているマルチハイトセル40のデータを格納するマルチハイトセルライブラリ64bとを含んでいる。マルチハイトセルライブラリ64bには、複数の異なる高さのマルチハイトセル40のデータが格納されていてもよい。また、後述されるように、セル配置の工程においてマルチハイトセル40の位置が上下方向に変更されることがあるが、このような処理に対応するマルチハイトセルライブラリ64bのライブラリ形態としては、セルの原点位置を複数持つ1種類のレイアウト構造をマルチハイトセルライブラリ64bに格納してもよく、原点位置が異なる複数のレイアウト構造をマルチハイトセルライブラリ64bに格納してもよい。図6は、本発明の一実施形態における半導体集積回路の設計手順を示すフローチャートである。論理合成ステップS01が行われてネットリストが作成され、そのネットリストに応じて、セル配置ステップS02及び配線ステップS03が行われる。セル配置では、上記の基本ハイトセル30及びマルチハイトセル40が配置され、配線では、配置されたセル間の配線が行われる。上述されているように、セル高さが異なる基本ハイトセル30とマルチハイトセル40を効率よく配置し、半導体集積回路のチップ面積を低減することが重要であり、本実施形態では、そのような要求に応じたセル配置処理が行われる。以下では、基本ハイトセル30とマルチハイトセル40を効率よく配置するためのセル配置処理について説明する。図7A、図7Bは、本発明の一実施形態でのセル配置処理を示すフローチャートであり、図8A乃至図8Fは、セル配置処理の具体例を示すレイアウト図である。以下では、マルチハイトセルライブラリ64bが、セルの原点位置を複数持つレイアウト構造のマルチハイトセル40のデータを格納しているとして、セル配置処理を説明する。図7A、図7Bのセル配置処理は、概略的には、基本ハイトセル30及びマルチハイトセル40の自動配置を行った後、マルチハイトセル40を、それより下方に位置する空き領域を埋めるように移動可能な場合に移動して再配置するというものである。空き領域とは、基本ハイトセル30及びマルチハイトセル40の何れも配置されていない領域のことである。ここで、マルチハイトセル40が基本ハイトセル30の整数倍の高さに限定されないことに起因して、自動配置では、2種類の空き領域が生じ得る。まず、基本ハイトセル30の高さに満たない高さの空き領域が生じ得る。上述のように、このような空き領域を、以下では、デッドスペースという。更に、基本ハイトセル30と同じ高さの空き領域が生じ得る。このような空き領域を、以下では、空きサイトという。そして、図7A、図7Bのセル配置処理の一つの特徴は、デッドスペースと空きサイトのうち、デッドスペースを優先して埋めるようにマルチハイトセル40の再配置を行い、その後、空きサイトを埋めるように基本ハイトセル30の再配置が行われることである。詳細には、まず、本実施形態のセル配置処理では、デッドスペースの幅とマルチハイトセル40の幅を比較することで当該デッドスペースにマルチハイトセル40が移動可能かを調べる。移動可能な場合、そのデッドスペースの少なくとも一部を埋めるようにマルチハイトセル40が移動される。次に、デッドスペースの幅と空きサイトの幅の合計とマルチハイトセル40の幅を比較し、当該デッドスペースと空きサイトとを合わせた領域にマルチハイトセルが移動可能かが調べられる。移動可能な場合、当該デッドスペースと空きサイトとを合わせた領域の少なくとも一部を埋めるようにマルチハイトセル40が移動される。最後に、基本ハイトセル30の再配置によって形成した空きサイトにマルチハイトセル40を移動可能かが調べられる。移動可能な場合、形成した当該空きサイトにマルチハイトセル40が移動される。基本ハイトセル30の高さに満たない高さを有するデッドスペースは、マルチハイトセル40の配置にしか活用できないから、デッドスペースを優先して埋めるようにマルチハイトセル40の再配置を行うことにより、セルを効率よく配置することができる。以下、図7A、図7Bのセル配置処理について詳細に説明する。まず、ステップS101では、基本ハイトセルライブラリ64aとマルチハイトセルライブラリ64bの読み込みが行われる。更に、ステップS102では、自動配置ツール62により、高さの異なるセルがチップ上のサイトセル配置の格子に初期的に配置される。ステップS102では、基本ハイトセル30とマルチハイトセル40が混ざって配置される。ステップS103では、基本ハイトセル30とマルチハイトセル40が混ざって配置された初期状態に対し、セルの再配置に向けたチェックを開始するセル行X軸方向に並んで配置された、各種セルを配置する最小単位であるサイトの集合のことが選択される。以下では、選択されたセル行をチェック対象セル行と呼ぶ。図8A~図8Fの例では、最下端のセル行20aが最初のチェック対象セル行に設定され、下から上の順序でセル行20a~20dがチェック対象セル行に順次に選択される。ここで、チェックを開始するセル行は任意に選択可能であり、また、セルの再配置を行なう対象のセル行の範囲を指定しても良いことに留意されたい。ステップS104では、チェック対象セル行のマルチハイトセルを除く領域がチェック対象領域として抽出される。例えば、図8Aの例では、チェック対象セル行として最下端のセル行20aが選択され、マルチハイトセル40aを除く領域がチェック対象領域21aとして抽出されている。また、図8Bの例では、チェック対象セル行として2番目のセル行20bが選択され、マルチハイトセル40aを除く領域がチェック対象領域21bとして抽出される。ステップS105では、ステップS104で抽出を行ったチェック対象領域に上方向で隣接するセル行にマルチハイトセルが配置されているかが判断される。チェック対象領域に上方向で隣接するセル行にマルチハイトセルが配置されている場合は、当該マルチハイトセルの検出を行った上で処理がステップS106に進み、マルチハイトセルが配置されていない場合は、処理がステップS113に進む。例えば、図8Bの例では、チェック対象領域21bに上方向で隣接するセル行にマルチハイトセル40b、40cが配置されていると判断される。ステップS106では、ステップS105にて検出したマルチハイトセルの下方向に隣接してデッドスペースがあるかが判断される。上述のように、デッドスペースとは、基本ハイトセルの高さaに満たない高さを持つ空き領域のことである。例えば、図8Cの例では、マルチハイトセル40bの下方向に隣接してデッドスペース23aが存在すると判断される。デッドスペースがあった場合はステップS107へ処理が進み、デッドスペースが無い場合はステップS108へ処理が進む。例えば、チェック対象セル行が2番目のセル行20bに選択されている図8Cの例では、デッドスペース23a、23bが抽出される。ステップS107では、ステップS106で抽出した個々のデッドスペースの横方向のサイズと、ステップS105にて検出したマルチハイトセルのセル幅がそれぞれ認識され、デッドスペースの横方向の幅とマルチハイトセルのセル幅とが比較される。例えば、図8Cの例では、マルチハイトセル40bのセル幅Xaとデッドスペース23aの幅Xbが比較される。ステップS107の結果、デッドスペース23aの幅Xbがマルチハイトセルのセルサイズ以上であればステップS112に進み、デッドスペースの幅Xbがマルチハイトセルのセルサイズ以下であれば、ステップS108に進む。ステップS106でマルチハイトセルの下方向にデッドスペースが無いと判断された場合、またはステップS107でデッドスペースの幅がマルチハイトセルのセル幅よりも小さいと判断された場合、ステップS108は、マルチハイトセルの下方向に空きサイトがあるかを判断する。例えば、図8Cの例では、マルチハイトセル40bの下方向に隣接して空きサイト22aが存在すると判断される。空きサイトが存在した場合はステップS109に進み、空きサイトが存在しない場合はステップS113に進む。ステップS109では、マルチハイトセルの下方向に隣接するチェック対象領域の空きサイトとデッドスペースの幅の合計が算出され、合計の幅と、マルチハイトセルのセル幅とが比較される。例えば、図8Cの例では、デッドスペース23aの幅Xbと空きサイト22aの幅Xcの合計と、マルチハイトセル40bのセル幅Xaとが比較される。空きサイトとデッドスペースの合計幅がマルチハイトセルのセルサイズ以上であればステップS112に進み、空きサイトとデッドスペースの合計幅が、マルチハイトセルのセルサイズ以下であればステップS110に進む。ステップS110では、チェック対象領域内にある全ての空きサイトの幅の合計が算出され、空きサイトの幅の合計とマルチハイトセルのセル幅とが比較される。チェック対象領域内の全ての空きサイトの幅の合計がマルチハイトセルのセル幅より大きい場合は処理がステップS111に進み、そうでない場合は処理がステップS113に進む。ステップS111では、チェック対象セル行の基本ハイトセルを再配置することで、空きサイトの位置を最適化して上方向のセル行のマルチハイトセルを下方向に移動させるための空きサイトを作り出す。ステップS112では、チェック対象領域のデッドスペース又は空きサイトの領域がもっとも小さくなるよう、マルチハイトセルライブラリ64bに登録されている原点位置が異なる複数のマルチハイトセルのうちから最適なものを選択して、マルチハイトセルを再配置する。ステップS113では、チェック対象セル行が最上端のセル行かを判断し、最上端のセル行の場合にはステップS115に進み、最上端のセル行ではない場合はステップS114に進む。ステップS114では、チェック対象セル行の設定を1つ上方向のセル行に設定してステップS104に戻り処理を繰り返す。ステップS115では、ステップS105~S114の繰り返しで生じた空きサイトを使用して基本ハイトセルが最適に再配置される。ステップS116では、演算により、残存しているデッドスペースにウェルが配置される。以上で、セル配置処理が完了する。セル配置処理が完了した後、配線工程が行われ、セル間の配線のレイアウトが決定される。この配線工程において、マルチハイトセルを横切るようにVDD電源配線、VSS電源配線が配置される。これにより、例えば、図4A乃至図4Cに図示されているようなマルチハイトセル40のレイアウトが実現される。図8A乃至図8Fは、図7A、図7Bに図示されているセル配置処理の具体例を示すセル配置図であり、図8Aに図示されている初期配置から、図7A、図7Bのセル配置処理によって基本ハイトセルとマルチハイトセルとが再配置される処理の例を示している。図8Aに図示されているように、初期配置では、マルチハイトセルライブラリ64bに登録されている原点位置が異なる複数のマルチハイトセル40のうち、左下を原点として持つマルチハイトセル40を用いて、自動配置ツール62によって自由にセル配置が実行されるステップS102。このため、図8Aに図示されているように、初期配置の段階では、基本ハイトセル30及びマルチハイトセル40が配置されない空き領域50が発生することになる。続いて、図8Aの最下端のセル行20aが最初のチェック対象セル行に選択されステップS103。更に、最下端のセル行20aにおいてマルチハイトセル40aが配置されていない領域が、チェック対象領域21aとして選択されるステップS104。図8Aでは、チェック対象領域21aに上方向に隣接するセル行20bにマルチハイトセルが存在せず、最上端のセル行でもないためステップS113、ステップS114において、チェック対象セル行が上方向に隣接するセル行20bに設定される。図8B、図8Cは、2番目のセル行20bがチェック対象セル行に設定された後のセル配置処理の手順を示している。図8Bに図示されているように、2番目のセル行20bにチェック対象領域21bが設定されステップS104、チェック対象領域21bに上方向で隣接する3番目のセル行20cにマルチハイトセル40b、40cが配置されていると判断されるステップS105。引き続いて行われるステップS106の処理においては、チェック対象領域21bの中から、図8Cに図示されているデッドスペース23a、23bが抽出される。図8Cに図示されているように、本実施形態では、最小の基本ハイトセルの配置ができない空き領域がデッドスペース23a、23bとして定義され、基本ハイトセルが配置可能な空き領域が空きサイト22a~22cと定義される。引き続いて行われるステップS107~S109、S112の一連の処理について、図8C、図8Dを例として説明を行う。図8Cに図示されているように、マルチハイトセル40bの下方向に隣接してデッドスペース23aが存在しており、ステップS107の処理では、このデッドスペース23aの幅Xbとマルチハイトセル40bのセル幅Xaが比較される。図8Cの例では、幅Xbは、セル幅Xaより小さいため、ステップS108が行われ、図8Cのマルチハイトセル40bの下方向に隣接する空きサイト22aが検出される。尚、幅Xbの方がセル幅Xaより大きい場合は、マルチハイトセル40bとデッドスペース23aの位置がずれていると、マルチハイトセル40bの再配置が行えない下方向に移動できないので、ステップS107の処理では、セル幅だけではなく、再配置の対象のマルチハイトセル40bの座標も認識される。次に、ステップS109では、ステップS106で抽出したデッドスペース23aとステップS108で抽出した空きサイト22aの幅の合計XbXcと、マルチハイトセル40bのセル幅Xaとが比較される。図8Cの場合、マルチハイトセル40bのセル幅Xaよりデッドスペース23aと空きサイト22aの幅の合計XbXcが大きいため、ステップS112へ進み、マルチハイトセルライブラリ64bに登録された原点位置が異なる複数のマルチハイトセルの中から、図8Dに示すようにデッドスペースが小さくなる最適な原点を持つマルチハイトセルが選択され、マルチハイトセル40bの位置に再配置される。これにより、実質的に、マルチハイトセル40bが下方向に移動されたことになる。なお、図8Cのマルチハイトセル40bのセル幅Xaより空きサイト22aとデッドスペース23aの幅の合計XbXcが小さかった場合は、ステップS110へ処理が進む。一方、マルチハイトセル40cについては、マルチハイトセル40cの下方向に隣接してデッドスペースは無く、空きサイト22bが存在するが、マルチハイトセル40cのセル幅Xdより、空きサイト22bのセル幅Xeの方が小さい。この場合、ステップS110~S112の一連の処理が行われる。図8D、図8Eを例にして、ステップS110~S112の処理を説明する。図8Dを参照して、ステップS110では、チェック対象領域21b内図8B参照にある全ての空きサイト22b、22cの幅の合計XeXfと、マルチハイトセル40cのセル幅Xdとが比較される。全ての空きサイトの幅の合計XeXfがマルチハイトセル40cのセル幅Xd以上となる場合は、ステップS111において基本セルの再配置が行われる。具体的には、ステップS111の再配置では、図8D及び図8Eに図示されているように、基本ハイトセル30aが移動され、その後に、ステップS112の処理において、図8Dで示すように配置されていたマルチハイトセル40cを、空きサイトを使用して、図8Eに図示されているように、マルチハイトセル40cそのまま1セル行分だけ下方向に移動させる処理が行われる。つまり、ステップS110では、ステップS109にてマルチハイトセル直下に空きサイトやデッドスペースを見つけられなかったとしても、チェック対象セル行の基本ハイトセルの配置換えをすることで、対象のマルチハイトセルの直下に空きサイトを集める処理が行われる。結果として、初期配置時には、配置配線ツールにより、マルチハイトセルが、その左下隅を原点として図8Aのように配置されるが、図8B~図8Eのように、配置の最適化がセル行ごとに行われ、最終的には図8Fに示すような、高集積化されたセル配置が実現される。以上に説明されているように、本実施形態では、上述のようなマルチハイトセルの構造とセル配置処理を使用することで、半導体集積回路の設計時に、基本ハイトセルとマルチハイトセルとを効率よく集積化し、チップ面積の削減が可能となる。また、本実施形態では、マルチハイトセルのセル高さが基本ハイトセルの整数倍に限定されないため、柔軟なセル配置が可能になる。ここで、本実施形態では、図3Bに図示されているようなマルチハイトセル40のVDD側電源供給配線5BとVSS側電源供給配線6Bのレイアウトにより、隣接する基本ハイトセル30との相対位置に関わらず、電源メッシュを構成する電源配線の位置を整合させることができる。基本ハイトセル30とマルチハイトセル40の相対位置に関わらず、電源メッシュのVDD電源配線8A、8BとVSS電源配線7A、7Bとを、それぞれに直線状に配置しても、マルチハイトセル40のVDD側電源供給配線5B及びVSS側電源供給配線6Bと接することになる。このため、チップ上の電源メッシュ構造を変えること無く、マルチハイトセル40を上下方向に移動させながら再配置し、高集積化を達成することができる。例えば、図4Aは、基本ハイトセル30とマルチハイトセル40をセル下端を位置整合させて隣接して配置したレイアウトの例であり、図4Bはセル上端で位置整合させて隣接した配置したレイアウトの例であり、図4Cはセルの高さ方向の中心付近で隣接して配置したレイアウトの例である。どのレイアウトであっても、電源メッシュのVSS電源配線7A、7Bと、電源メッシュのVDD電源配線8A、8Bを曲げることなく、マルチハイトセル40のセル内回路に電源電圧の供給を行なうことができる。第2の実施形態:図9A、図9Bは、本発明の第2の実施形態におけるセル配置処理の手順を示すフローチャートであり、図10A乃至図10Dは、セル配置処理の具体例を示すレイアウト図である。第1の実施形態では、マルチハイトセル40b、40cが、それに下方向に隣接するデッドスペース又は空きサイトに移動されているが、第2の実施形態では、チェック対象セル行のチェック対象領域の空きサイト及びデッドスペースの幅、及び、チェック対象セル行に上方向で隣接するマルチハイトセルのそれぞれのセル幅が認識され、これらの情報を用いて、複数のマルチハイトセルの中からチェック対象セル行の空きサイトやデッドスペースが少なくなる組み合わせを選択することで、高集積化が実現される。詳細には、第2の実施形態のセル配置処理では、図7A、図7Bに示されているセル配置処理に対してステップS106a~S112aの処理が異なる。以下では、ステップS106a~S112aの処理について詳細に説明する。図9Aを参照して、ステップS106aでは、ステップS105で検出した、チェック対象領域の上方向に隣接するセル行の全てのマルチハイトセル個々のセル幅が記憶される。例えば、図10Aの例では、2番目のセル行20bがチェック対象セル行として設定され、セル行20bのマルチハイトセル40a以外の領域がチェック対象領域として選択されている場合に、マルチハイトセル40b、40c、40dのセル幅Xa、Xd、Xhが記憶される。ステップS106bでは、チェック対象セル行にデッドスペースがあるかの判断が行われる。例えば、2番目のセル行20bがチェック対象セル行として設定される図10Aの例では、更に、チェック対象セル行にデッドスペース23a、23bがあると判断される。デッドスペースがない場合は、ステップS107aに処理が進み、デッドスペースがある場合は、ステップS107cに処理が進む。ステップS107aでは、チェック対象セル行に空きサイトがあるかの判断が行われる。空きサイトがあれば、処理はステップS107bに進み、空きサイトがない場合は、ステップS113へ進む。ステップS107bでは、チェック対象セル行の空きサイトの横方向の幅の合計が計算され、ステップS106aでセル幅が記憶されたマルチハイトセルのうち、セル幅が最小のセルのマルチハイトセルのセル幅と、空きサイトの幅の合計とが比較される。比較の結果、選択された最小のマルチハイトセルのセル幅より、空きサイトの横方向の幅の合計が小さい場合は、ステップS113に進み、マルチハイトセルのセル幅より、空きサイトの横方向のサイズの合計幅が大きい場合は、ステップS108aに進む。ステップS108aでは、ステップS106aで記憶したマルチハイトセルのセル幅に基づいて、再配置するマルチハイトセルの組み合わせが選択される。このとき、マルチハイトセルの組み合わせは、空きサイトの幅の合計と再配置されるマルチハイトセルのセルサイズの合計の差分が最小になるように選択される。次に、ステップS107cでは、ステップS106bで抽出した個々のデッドスペースの幅を記憶する。さらに、ステップS108bは、ステップS106aで記憶した、マルチハイトセルのセルサイズと、ステップS107cで記憶したデッドスペースの幅を元に、個々のデッドスペースの幅に最も近い値のセルサイズとなるマルチハイトセルを、再配置するマルチハイトセルとして選抜する。次に、ステップS109aでは、チェック対象セル行及びチェック対象セル行に上方向で隣接するセル行に、再配置するマルチハイトセルの再配置予定領域が設定される。例えば、2番目のセル行20bがチェック対象セル行として設定される図10Bの例では、セル行20b、20cに再配置予定領域R1、R2が設定される。再配置予定領域の設定では、チェック対象セル行にデッドスペースがある際は、デッドスペースを優先して、再配置するマルチハイトセルのセル幅分の再配置予定領域が設定される。更に、ステップS109aでは、再配置するマルチハイトセルのセル幅分の領域が確保できない場合に、チェック対象セル行の空きサイトを使用してチェック対象セル行内の基本ハイトセルを再配置することで、マルチハイトセルの再配置領域を確保する処理も実施される。ステップS110aでは、ステップS109aで抽出した、マルチハイトセルの再配置予定領域内に基本ハイトセルがあるかの判断を行い、基本ハイトセルがある場合には、ステップS111aに処理が進み、基本ハイトセルがない場合は、ステップS112aに処理が進む。例えば、図10Bの例では、再配置予定領域R1、R2に、基本ハイトセル30a、30bがあると判断される。ステップS111aでは、チェック対象セル行と、チェック対象セル行に上方向に隣接するセル行の、再配置するマルチハイトセルの再配置予定領域と、再配置されないマルチハイトセルを除く領域が配置替え対象領域として設定され、配置替え対象領域内の空きサイトを使用して、基本ハイトセルが再配置される。例えば、図10Bの例では、セル行20b、20cの再配置予定領域R1、R2及びマルチハイトセル40dを除く領域が、配置替え対象領域Fとして設定され、配置替え対象領域Fの中で基本ハイトセルが再配置される。ステップS112aでは、ステップS109aで抽出した再配置予定領域R1、R2に、ステップS108a又はステップS108bで選択されたマルチハイトセルが再配置される。図10A~図10Dは、図9A、図9Bに図示されているセル配置処理のうち、第1の実施形態とは異なるステップS106a~S112aまでの処理の具体例を示す一連のセル配置図である。図10Aは、ステップS102にて初期配置されたセル配置図であり、ステップS114により、チェック対象セル行が2番目のセル行20bに設定されているとする。このとき、チェック対象領域即ち、チェック対象セル行であるセル行20bのうちマルチハイトセル40a以外の領域に上方向に隣接してマルチハイトセル40b、40c、40dが存在するため、ステップS106aでは、マルチハイトセル40bのセル幅Xaとマルチハイトセル40cのセル幅Xdとマルチハイトセル40dのセル幅Xhが記憶される。ステップS106bでは、チェック対象セル行であるセル行20bのデッドスペースの有無が判断される。図10Aの例では、デッドスペース23a、23bが抽出される。ステップS107cでは、チェック対象セル行であるセル行20bの、デッドスペース23a、23bの幅Xb、Xgが記憶される。ステップS108bでは、ステップS106aで記憶されたマルチハイトセル40b、40c、40dのセル幅Xa、Xd、Xhに基づいて、再配置するマルチハイトセルの組み合わせが選択される。再配置するマルチハイトセルの組み合わせとしては、デッドスペース23a、23bの幅Xb、Xgの値に最も近いセル幅のマルチハイトセルの組み合わせが選択される。ここで、デッドスペースの幅と最も近いセル幅のマルチハイトセルを選抜する理由は、チェック対象セル行に可能な限り空きサイトを確保することで、後述するステップS111aの処理で、チェック対象セル行の上のセル行から基本セルをより多く、下方向へ再配置できるようにする為である。図10Aの場合は、マルチハイトセル40b、40cが再配置の対象となる。一方、図10Aについて、仮に、チェック対象セル行として選択された2番目のセル行20bにデッドスペース23aと23bが無いとした場合には、ステップS106bの判断により、ステップS107a1に処理が進み、チェック対象セル行であるセル行20bの空きサイトの有無が判断される。その後、ステップS107bでは、チェック対象セル行であるセル行20bの空きサイト22a、22b、22cのセルサイズの合計XcXeXfと、マルチハイトセル40b、40c、40dのうち、最もセル幅の小さいマルチハイトセルのセル幅Xdとが比較される。尚、最もセルサイズの大きいマルチハイトセル40dを比較対象にしてしまうと、最もセルサイズの小さいXdのセルサイズを持つ40cのマルチハイトセルの最適配置の可能性を消してしまうため、ステップS107bでは、最小のセル幅のマルチハイトセルが比較対象として設定される。この例では、最もセル幅の小さいマルチハイトセル40cのセル幅Xdより空きサイト22a、22b、22cの幅の合計XcXeXfが大きいので、ステップS108aでは、マルチハイトセル40b、40c、40dのセル幅Xa、Xd、Xhに基づいて、空きサイトの幅の合計XcXeXfとの差分が小さいセル幅を有するマルチハイトセルを、再配置するマルチハイトセルの組み合わせとして選抜する。以上の処理により、チェック対象セル行にデッドスペース又は空きサイトが存在する場合には、それらのデッドスペースや空きサイトの幅を有効に使用して、再配置するマルチハイトセルの組み合わせを選択することができる。次に、選択されたマルチハイトセルの再配置方法を説明する。ステップS109aでは、デッドスペース23a、23bを優先して、マルチハイトセル40bのセル幅Xaとマルチハイトセル40cのセル幅Xdに対応した幅の再配置予定領域R1、R2が設定される。この際、再配置するマルチハイトセルのセル幅がデッドスペースの幅より大きく、且つ、チェック対象セル行セル行20bに空きサイトはあるが、デッドスペースに隣接していない場合には、チェック対象セル行であるセル行20b内の基本ハイトセルが空きサイトを使用して再配置され、デッドスペースに隣接する空きサイトを作り出すことで、チェック対象セル行であるセル行20bに再配置するマルチハイトセル40b、40cのセル幅Xa、Xdに対応する幅の再配置予定領域R1、R2が確保される。また、チェック対象セル行セル行20bにデッドスペースがない場合も、チェック対象セル行内の基本ハイトセルを空きサイトを使用して再配置することで、再配置対象のマルチハイトセルのセル幅分の再配置予定領域が確保される。図10Bに図示されている例では、デッドスペース23a、23bに隣接した空きサイトを使用して、再配置予定領域R1、R2が、マルチハイトセル40b、40cを再配置すべき領域として設定される。更に、再配置予定領域R1、R2に重なっている基本ハイトセル30a、30bが存在するためステップS110a、ステップS111aでは、チェック対象セル行セル行20bと、チェック対象セル行の上方向に隣接するセル行20cの2つのセル行の、再配置予定領域R1、R2と、再配置されないマルチハイトセル40dを除く領域が、配置替え対象領域Fとして定義される。ステップS111aでは、更に、配置替え対象領域F内にある基本ハイトセルと空きサイトとが検出され、再配置となる基本ハイトセル30a、30bを再配置予定領域R1、R2から排除するよう、配置替え対象領域F内にある基本ハイトセルを含めて基本ハイトセルの再配置を実施する。その際、チェック対象セル行のセル行20bの空きサイトを優先して埋めるように基本ハイトセルが再配置される。尚、配置替え対象領域Fは、マルチハイトセルの高さに応じて、3つ以上のセル行にオーバーラップするように設定されてもよい。再配置予定領域R1、R2内に位置していた基本ハイトセル30a、30bの再配置が完了後、ステップS112aにて、ステップS109aにて選択された再配置するマルチハイトセルが再配置予定領域R1、R2に移動される。図10Cは、マルチハイトセルを再配置した結果を示しており、図10Cでは、基本ハイトセル30a、30b、マルチハイトセル40b、40cがチェック対象セル行として設定された2番目のセル行20bに再配置されている。その後、第1の実施形態と同様に、ステップS113~S114が行われる。これにより、最終的には、前述したステップS106a~S112aの処理が最上端のセル行まで繰り返して行われる。その後、第1の実施形態と同様に、ステップS115において全セル行のサイトを可能な限り埋めるように、上方向から下方向の順序でまたはその逆の順序基本ハイトセルの再配置が実施される。これにより、図10Dのセル配置が得られる。第2実施形態のセル配置処理では、マルチハイトセルの再配置を1セルずつ下方向へ移動を行うのではなく、チェック対象セル行の空きサイト及びデッドスペースの幅、及び、各マルチハイトセルのセル幅が認識され、認識されたこれらの情報に基づいて、チェック対象セル行の上方向に隣接するセル行に位置する複数のマルチハイトセルの中からチェック対象セル行の空きサイトやデッドスペースが少なくなるマルチハイトセルの組み合わせが選択される。これにより、高い集積度でセルを再配置することが可能となる。