(57)【要約】【目的】複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置最適化処理の対象を適切に絞ることにより少ない処理時間で適切な配置を行う。【構成】アレイブロックを分割数に応じて分割して得られる分割要素の配列を変えて、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定するブロック候補選定処理部１０６と、全てのアレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満たすように決定する配置処理部１１０とを備え、ブロック候補は幅及び長さによって規定される矩形形状を有し、ブロック候補選定処理部１０６は各ブロック候補の幅及び長さに基づいて各ブロック候補の形状がばらつくように各ブロック候補を選定する。【選択図】図１
2017027333.tif 000002
【特許請求の範囲】
【請求項１】
所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理装置において、
複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定するブロック候補選定処理部と、
全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定する配置処理部とを備えて成り、
前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、
前記ブロック候補選定処理部は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴とする配置処理装置。
【請求項２】
前記ブロック候補選定処理部は、前記各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、前記スコアに基づいて前記各ブロック候補の形状がばらつくように前記ブロック候補を選定することを特徴とする請求項1記載の配置処理装置。
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅である。
【請求項３】
前記ブロック候補選定処理部は、
複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割するブロック分割部と、
前記分割要素の配列を変えることによって、前記アレイブロックについて、相互に形状が異なる複数のブロック候補を生成するブロック候補生成部と、
前記ブロック候補生成部が生成した各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、ｍ個のブロック候補を選定する場合、最小のスコアｔ１と最大のスコアｔｍが付けられたブロック候補を選定すると共に、（ｍ−２）個のブロック候補については、下記Ｄが最小となるスコアが付けられたブロック候補を選定するブロック候補選択部とを備えて成ることを特徴とする請求項１又は２記載の配置処理装置。
Ｄ＝Σ（ｔｋ＋１−ｔｋ）２
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅、ｍ、ｎ（≧ｍ）は正の整数、ｋは１から（ｍ−１）まで変わる正の整数であり、ｔ１，・・・，ｔｍは各ブロック候補のスコアを小さい順に並べたものである。
【請求項４】
前記分割要素は回路素子であると共に前記ブロックはフロアプランを構成するブロックであり、
前記配置処理部は、前記ブロック候補選定処理部が選定したブロック候補を用いて、前記所定条件を満たすように全ブロックの配置を決定することによってフロアプランを生成することを特徴とする請求項１乃至３のいずれか一に記載の配置処理装置。
【請求項５】
所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理方法において、
ブロック候補選定処理部が、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定し、
配置処理部が、全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定して成り、
前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、
前記ブロック候補選定処理部は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴とする配置処理方法。
【請求項６】
前記ブロック候補選定処理部は、前記各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、前記スコアに基づいて前記各ブロック候補の形状がばらつくように前記ブロック候補を選定することを特徴とする請求項５記載の配置処理方法。
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅である。
【請求項７】
前記ブロック候補選定処理部は、
複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割するブロック分割部と、
前記分割要素の配列を変えることによって、前記アレイブロックについて、相互に形状が異なる複数のブロック候補を生成するブロック候補生成部と、
前記ブロック候補生成部が生成した各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、ｍ個のブロック候補を選定する場合、最小のスコアｔ１と最大のスコアｔｍが付けられたブロック候補を選定すると共に、（ｍ−２）個のブロック候補については、下記Ｄが最小となるスコアが付けられたブロック候補を選定するブロック候補選択部とを備えて成ることを特徴とする請求項５又は６記載の配置処理方法。
Ｄ＝Σ（ｔｋ＋１−ｔｋ）２
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅、ｍ、ｎ（≧ｍ）は正の整数、ｋは１から（ｍ−１）まで変わる正の整数であり、ｔ１，・・・，ｔｍは各ブロック候補のスコアを小さい順に並べたものである。
【請求項８】
前記分割要素は回路素子であると共に前記ブロックはフロアプランを構成するブロックであり、
前記配置処理部は、前記ブロック候補選定処理部が選定したブロック候補を用いて、前記所定条件を満たすように全ブロックの配置を決定することによってフロアプランを生成することを特徴とする請求項５乃至７のいずれか一に記載の配置処理方法。
【請求項９】
コンピュータに請求項５乃至８のいずれか一に記載の配置処理方法を実行させることを特徴とする配置処理用プログラム。
【請求項１０】
請求項９記載の配置処理用プログラムを記録して成ることを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定の形状を有する複数のブロックを所定条件を満たすように配置する配置処理装置、配置処理方法、配置処理用プログラム及び配置処理用プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来から、ＬＳＩ（Large Scale Integration circuit）やＦＰＤ（Flat Panel Display）等の分野において、所定の形状を有する複数のブロックを所定条件を満たすように配置する配置処理装置が開発されている。
例えば、特許文献１に記載された発明では、回路素子を１個又は複数個用いてブロックを構成し、総面積最小化等の所定条件を満足するように複数のブロックを配置することにより、最適なフロアプランを得るように構成されている。
【０００３】
近年ＬＳＩの微細化に伴いますますアナログレイアウト設計の効率化が求められている。従来の製造プロセスに適合する設計のＬＳＩレイアウトがあるとき、前記レイアウトを新しい製造プロセスでも再利用する方法が考えられる。しかしながら、製造プロセス等が変わることによって回路素子の大きさが変わるとデッドスペースができる場合があり、その場合、ＬＳＩ面積を小型化するために、デッドスペースが生じないよう回路素子を分割してブロックの形状を変更しながら再配置する等の必要性が生じる。
【０００４】
配置処理装置としてフロアプラン設計装置の例を説明すると、図１３に旧プロセスに適合するよう作成されたＬＳＩのフロアプラン（旧フロアプラン）の一例を示すように、旧フロアプランは複数のブロックＡ〜Ｇをデッドスペース等が生じないように最適化した配置となっている。図１３の旧フロアプランを新プロセスに適合するように変更する場合、単に新プロセスに適合するようにブロックＡ〜Ｇの回路素子を変更すると、図１４に示すようにブロックＡ〜Ｇの大きさが変わるため、デッドスペースが生じてしまう恐れがある。
【０００５】
尚、各ブロックＡ〜Ｇは、ＬＳＩを構成する１個又は複数のＭＯＳトランジスタ、１個又は複数個の抵抗、１個又は複数個のキャパシタ等の回路素子をグループ分け（例えば回路素子の種類別にグループ分け）して配置するように構成されたものである。
【０００６】
また、近年のプロセスでは、回路素子を分割してアレイ素子によって構成する場合、アレイ素子特性の均一化のために、分割数が多くなる傾向にある。配置最適化の手法としてシミュレーテッド・アニーリング等種々の方法が有るが、デッドスペースが生じないように、ブロックの分割数を変えながらブロックを再配置する必要性があるため、分割数が多くなるに従って、配置を最適化するための処理対象が増加し、多くの処理時間が必要になるという問題がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１３−０４５３１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、前記問題点に鑑み成されたもので、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行えるようにすることを課題としている。
【課題を解決するための手段】
【０００９】
本発明の第１の視点によれば、所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理装置において、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定するブロック候補選定処理部と、全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定する配置処理部とを備えて成り、前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、前記ブロック候補選定処理部は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴とする配置処理装置
が提供される。
【００１０】
また本発明の第２の視点によれば、所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理方法において、ブロック候補選定処理部が、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定し、配置処理部が、全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定して成り、前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、前記ブロック候補選定処理部は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴とする配置処理方法が提供される。
【００１１】
また、本発明の第３の視点によれば、コンピュータに前記配置処理方法を実行させることを特徴とする配置処理用プログラムが提供される。
また、本発明の第４の視点によれば、前記配置処理用プログラムを記録して成ることを特徴とするコンピュータ読み取り可能な記録媒体が提供される。
【発明の効果】
【００１２】
本発明の配置処理装置によれば、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
また、本発明のフロアプラン設計方法によれば、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
【００１３】
また、コンピュータが本発明の配置処理用プログラムを実行することにより、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
また、本発明の記録媒体に記録した配置処理用プログラムをコンピュータに実行させることにより、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態に係るフロアプラン設計装置のブロック図である。
【図２】本発明の実施の形態に係るフロアプラン設計装置のフローチャートである。
【図３】本発明の実施の形態に係るフロアプラン設計装置の部分詳細フローチャートである。
【図４】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図５】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図６】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図７】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図８】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図９】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図１０】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図１１】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図１２】本発明の実施の形態に係るフロアプラン表示を示す図である。
【図１３】本発明の実施の形態に係るフロアプラン設計装置の説明図である。
【図１４】従来のフロアプラン表示を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態に係る配置処理装置、配置処理方法、配置処理方法をコンピュータに実行させるための配置処理用プログラム及び配置処理用プログラムを記録したコンピュータ読み取り可能な記録媒体について、図面を用いて説明する。
尚、本発明の実施の形態では配置処理装置の例として、フロアプラン設計装置を挙げている。また、各図において同一部分には同一符号を付している。
【００１６】
本発明の実施の形態に係る配置処理装置としてのフロアプラン設計装置は、ＬＳＩを構成する回路要素の詳細なレイアウト設計を行う前の段階として、前記回路要素の概略配置を表すフロアプランを設計し表示する機能を有している。
図１は、本発明の実施の形態に係るフロアプラン設計装置のブロック図である。
【００１７】
図１において、フロアプラン設計装置１００は、フロアプラン生成処理部１０１、記憶部１０２、入力部１０３、表示部１０４を備えている。フロアプラン設計装置１００は、キーボードやマウスなどの入力部、表示部、中央処理装置（ＣＰＵ）及び記憶部を備えたコンピュータによって構成することができる。前記コンピュータに、コンピュータ読み取り可能な記録媒体（例えば、記憶部１０２、あるいは図示しない半導体メモリやＣＤ−ＲＯＭ等）に記録された配置処理用プログラムをインストールして実行させることにより、フロアプラン設計装置１００として機能させることができる。
【００１８】
入力部１０３は、データや命令を入力するためのもので、マウス、キーボードあるいは、ＵＳＢ（Universal Serial Bus）端子等の入力インタフェースによって構成される。
フロアプラン生成処理部１０１は、ＬＳＩの製造プロセスの変更や半導体の物理的仕様の変更等に伴い、既存のフロアプラン（旧フロアプラン）を基にして、新製造プロセス等に適した新フロアプランを生成する機能を有している。
【００１９】
記憶部１０２は、旧フロアプランのデータが含まれるフロアプランデータ１１１、新プロセスに適した基本回路素子の形状や大きさに関するデータが含まれる新基本回路素子データ１１２を記憶している。また、新たに生成したフロアプランもフロアプランデータ１１１内に記憶される。
【００２０】
回路素子の種類としてＭＯＳトランジスタ、抵抗、キャパシタ等がある。基本回路素子は回路素子の最小の大きさの回路素子であり、回路素子の種類毎に定められている。例えば、基本回路素子がＭＯＳトランジスタの場合、ゲート長及びゲート幅が所定長さに定められている。
【００２１】
フロアプランデータ１１１には、旧フロアプランに関するデータとして、アレイ状に配設された回路素子によって構成されるブロックの形状や大きさのデータ、各ブロックの配置位置のデータ、各ブロックを構成する回路素子のデータが含まれる。
【００２２】
詳細は後述するが、各ブロックは予め定めた数（分割数）に分割可能である。新フロアプラン生成の際に、ブロックを分割数に応じた複数の要素（分割要素）に分割し、前記分割要素の配列を変えることによってブロックを複数種類の形状に変更して使用される。ブロックには、複数の分割要素に分割可能なブロック（アレイブロック）と、分割要素には分割されないブロックの２種類がある。アレイブロックは１種類又は複数種類の分割数の分割要素に分割される。分割要素は単一の回路素子のみによって構成され、前記分割要素の最小のものが基本回路素子に等しくなる。
【００２３】
記憶部１０２には、フロアプラン設計処理に必要なその他のデータやプログラムも記憶される。
フロアプラン生成処理部１０１は、旧フロアプランデータ１１１を記憶部１０２から取り込むフロアプランデータ取込部１０５、ブロック候補を選定するブロック候補選定処理部１０６、選定したブロック候補を用いて全ブロックの最適配置を決定しフロアプランを生成するフロアプラン生成部１１０を備えている。
【００２４】
ブロック候補選定処理部１０６は、複数の分割要素に分割可能なブロック（アレイブロック）を所定の分割数の分割要素に分割するブロック分割部１０７、各アレイブロックについて前記得られた分割要素の配置位置を変えて全てのブロック候補を生成するブロック候補生成部１０８、前記生成した全てのブロック候補から所定条件を満たすブロック候補を選定するブロック候補選択部１０９を備えている。
【００２５】
ブロック分割部１０７は、旧フロアプランに含まれる各ブロックの中の分割可能なブロックを新フロアプラン用のブロック（アレイブロック）に変換し、入力部１０３によって設定した所定の分割数の分割要素に分割する機能を有している。また、ブロック分割部１０７は、分割数に応じて分割することによって得られる分割要素が新基本回路素子よりも小さくなる場合には分割処理は行わない。この場合、ブロック分割部１０７が表示部１０４に分割不能である旨表示させるようにフロアプラン生成処理部１０１を構成してもよい。
基本回路素子、分割要素、ブロック候補は、幅及び前記幅に直交する長さによって規定される矩形形状を有している。
【００２６】
ブロック候補選択部１０９は、ブロック候補生成部１０８が生成した各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように各ブロック候補を選定する機能を有している。即ち、ブロック候補選択部１０９は、各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状の相違の程度が均等化するように各ブロック候補を選定する機能を有している。換言すれば、ブロック候補選択部１０９は、各ブロック候補のアスペクト比に基づいて、前記各ブロック候補の形状の相違の程度が均等化するように各ブロック候補を選定する機能を有している。
表示部１０４は、フロアプラン生成処理部１０１によってフロアプラン生成処理途中で得られる情報や、最終的に得られるフロアプランを表示する機能を有している。
尚、フロアプラン生成部１１０は配置処理部を構成している。
【００２７】
図２は、フロアプラン設計装置１００のフローチャートであり、主としてフロアプラン生成処理部１０１が行う処理を示している。
図３は、フロアプラン設計装置１００の部分詳細フローチャートであり、主としてブロック候補選択部１０９が行う処理を示している。
図４〜図１１、図１３は本発明の実施の形態に係るフロアプラン設計装置の説明図で、図１２は表示部１０４における新フロアプラン表示を示す図である。
【００２８】
以下、図１〜図１４を用いて本発明の実施の形態の動作を詳細に説明する。
尚、予め入力部１０３によって旧フロアプランデータ１１１及び新プロセスに適した基本回路素子のデータ（新基本回路素子データ）１１２が入力され、記憶部１０２に記憶されているものとする。
先ず、フロアプラン生成処理部１０１のフロアプランデータ取込部１０５は、記憶部１０２からフロアプランデータ１１１に含まれる旧フロアプランデータ（図１３参照）を読み出し、単に新プロセスに適合するフロアプランに変換し出力する（図１４参照）。尚、処理対象のフロアプランが予め新プロセス用に変換済みのものの場合には、フロアプランデータ取込部１０５はデータ変換を行う必要はないため当該処理対象のフロアプランの取込処理のみを行う。
【００２９】
次に、ブロック候補選定処理部１０６のブロック分割部１０７は、フロアプランデータ取込部１０５から出力されたフロアプランのブロックＡ〜Ｇを、入力部１０３によって設定された分割数にブロックを均等に分割する（図２のステップＳ２０１）。分割要素は１個の回路素子によって構成される。このときブロック分割部１０７は、ブロックを分割して得られる分割要素の大きさが新基本回路素子データ１１２に含まれる基本回路素子の大きさ以上の場合には分割処理を行うが、分割要素が基本回路素子よりも小さい場合には分割処理を行わず、表示部１０４に分割処理のエラー表示を行う。
【００３０】
尚、ブロックには、フロアプランに用いる候補が一種類しか存在しないブロック（ハードブロック）と、フロアプランに用いる候補が複数種類存在するブロック（ソフトブロック）があるが、ハードブロックについては分割する必要はない。処理ステップＳ２０１においてブロック分割部１０７は、ブロックＡ〜Ｇの中のソフトブロックに対して分割数に応じた数に分割する。
【００３１】
次に、ブロック候補生成部１０８は、分割数が複数種類ある場合、先ず最初の分割数でブロックを分割することにより得られる複数の分割要素を、幅（Ｙ軸）方向に一列に並べたブロック候補から順に、幅方向を小さくすると共に長さ（Ｘ軸）方向を大きくしたブロック候補を生成し、最後に長さ方向に一列に並べたブロック候補まで分割要素の配列を変えて生成する（ステップＳ２０２）。これにより、当該分割数における全てのブロック候補が生成されたことになる。
【００３２】
図４（ａ）は分割数Ｍが２０のときのブロック候補を示す図である。分割要素の幅Ｗが６．０単位長で、ブロック候補の最大幅ＴｏｔａｌＷが１２０単位長である。また、分割要素の長さＬが４．５単位長で、ブロック候補の最大長さＴｏｔａｌＬが９０単位長である。
ブロック候補生成部１０８は、形状の相違程度が大きいブロック候補の数を増やすために、分割数に近似する数に分割したブロック候補も生成するように構成している。
従って図４（ａ）の例では、正規の分割要素と同じ形状及び大きさのダミーの分割要素４０１を１つ加えて、長さ方向に分割要素７個、幅方向に分割要素３個配列して計２１個に分割したブロック候補も生成している。
【００３３】
次に、ブロック候補生成部１０８は、全ての分割数についてブロック候補を生成したか否かを判定し（ステップＳ２０３）、未だ全ての分割数についてブロック候補を生成していない場合には分割数を他の分割数に変更して処理ステップＳ２０１に戻る（ステップＳ２０４）。
【００３４】
ブロック候補生成部１０８は、処理ステップＳ２０１〜Ｓ２０４を繰り返すことにより、１つのブロックに関して全ての分割数についてのブロック候補を生成する。
図４（ｂ）、（ｃ）、図５（ｄ）〜（ｈ）は、各々、分割数Ｍが１６、１２、１０、８、６、４、２の場合のブロック候補の例を示している。
【００３５】
次にブロック候補選択部１０９は、各ブロック候補の幅及び長さに基づいて、各ブロック候補の形状の相違の程度が均等化するように各ブロック候補を選定する（ステップＳ２０５）。即ち、ブロック候補選択部１０９は、各ブロック候補のアスペクト比に基づいて、各ブロック候補の形状の相違の程度が均等化するように各ブロック候補を選定する。
【００３６】
図３は、処理ステップＳ２０５のブロック候補選定処理の詳細を示すフローチャートである。
図３において、ブロック候補選択部１０９は、各ブロック候補のうち、大きさが所定条件を満たさないブロック候補を除外する（ステップＳ３０１）。ここで除外するブロック候補の例としては、ブロック候補がＬＳＩチップ面積内に収まらないものや、長さ及び幅の両方が他のブロック候補よりも大きいブロック候補がある。
次にブロック候補選択部１０９は、各ブロック候補の幅及び長さに基づいて各ブロック候補にスコアＳを付与する（ステップＳ３０２）。
【００３７】
ブロック候補選択部１０９が各ブロック候補にスコアＳを付与する処理について説明すると、先ず、前記例のように、複数の分割要素をアレイ状（同一方向に一列又は複数列に並ぶよう）に並べるとき、空き領域にダミーを入れると、例えば分割数Ｍ＝２０のとき、（列数（幅方向の分割要素数），行数（長さ方向の分割要素数））は次の関係が整列する。
（列数，行数）＝（１，２０），（２，１０），（３，７），（４，５），（５，４），（７，３），（１０，２），（２０，１）となる。
【００３８】
分割数がＭのとき、列数が√Ｍ（即ちブロックの長さがＬ√Ｍ）以下では列数の差が１（即ち、長さＬが等間隔）で、列数が√Ｍ（即ちブロックの長さＬ√Ｍ）以上では行数の差が１（即ち幅Ｗが等間隔）になる。
列数＝行数＝√Ｍに相当するブロック候補の長さＬ及び幅Ｗを中心として、それより縦長のブロック候補は幅に比例してスコアＳが決まるようにすると共にそれより横長のブロック候補は長さに比例してスコアＳが決まるように、各ブロック候補にスコアＳを付与する。
【００３９】
図６は、各ブロック候補に付与するスコア付けの詳細な説明図である。
図６において、分割数が複数種類ある場合の最大の分割数（最大分割数）をＭとし、Ｍ分割した矩形の分割要素の幅をＷ、長さをＬとすると、横１列に並べたブロック候補は幅Ｗ、長さＬＭの矩形となり、又、縦１列に並べたブロック候補は幅ＷＭ、長さＬの矩形となる。ブロック候補に付けるスコアＳの中心（長さ等間隔と幅等間隔の境界）となるブロック候補は、幅Ｗ√Ｍ、長さＬ√Ｍとなる。
【００４０】
幅Ｗ、長さＬの矩形を拡大・縮小して面積１に変形した矩形の幅をＹ０（Ｌ，Ｗ）、長さをＸ０（Ｌ，Ｗ）として次のように定義する。
（ｘｖ，ｙｖ）＝（Ｘ０（Ｌ，ＷＭ），Ｙ０（Ｌ，ＷＭ））
（ｘｃ，ｙｃ）＝（Ｘ０（Ｌ√Ｍ，Ｗ√Ｍ），Ｙ０（Ｌ√Ｍ，Ｗ√Ｍ））
（ｘＬ，ｙＬ）＝（Ｘ０（ＬＭ，Ｗ），Ｙ０（ＬＭ，Ｗ））
ｘｙ＝１となる（ｘ，ｙ）に対して２つの次式（１）が成立する。
Ｓ（ｘ，ｙ）＝−（ｘｃ−ｘ）／ｘｃ  （但し、ｘ≦ｘｃ（ｉ．ｅ．  ｙ≧ｙｃ））
＝（ｙｃ−ｙ）／ｙｃ  （但し、ｘ＞ｘｃ（ｉ．ｅ．  ｙ＜ｙｃ））
・・・（１）
【００４１】
図６において、点（ｘｃ，ｙｃ）は分割数最大のときの境界であり、その点はスコアＳ（ｘｃ，ｙｃ）が０となる点である。点（ｘＶ，ｙＶ）は分割数最大で縦１列に並べたときのブロック候補の右上角の点であり、そのブロック候補のスコアＳ（ｘＶ，ｙＶ）は−ａである。また、点（ｘＬ，ｙＬ）は分割数最大で横１列に並べたときのブロック候補の右上角の点であり、そのブロック候補のスコアＳ（ｘＬ，ｙＬ）はａである。
【００４２】
以上のようにして、最大分割数で分割したブロック候補のスコアを基にして、数式（１）を用いて、当該ブロックの他の分割数の各ブロック候補にスコアを付与する。即ち、最大分割数に対してスコア付けの中心（ｘｃ，ｙｃ）を決定した後、最大分割数のみならず他の分割数に対しても、当該中心（ｘｃ，ｙｃ）を用いた数式（１）により、各ブロック候補のスコアを算出する。
【００４３】
前記他の分割数のブロック候補のスコアを数式（１）により算出する場合、各ブロック候補の幅Ｗと長さＬに対し、（ｘ，ｙ）＝（Ｘ０（Ｌ，Ｗ），Ｙ０（Ｌ，Ｗ）をスコアＳ（ｘ，ｙ）に入れて算出する。即ち、各ブロック候補の面積を１に変形してからスコアＳ（ｘ，ｙ）を算出するこれにより、各ブロック候補には、（ｘｃ，ｙｃ）を中心とするスコアが付与される。
因みに、図４(a)に示した分割数２０の例の場合、スコアＳ＝０、−ａ、ａのブロック候補は図示した通りになる。
【００４４】
次にブロック候補選択部１０９は、全て（ｎ個）のブロック候補に付与したスコアのうち、下記数式（２）が最小になるようなｍ個のブロック候補を選定する（ステップＳ３０３）。即ち、ブロック候補選択部１０９は、選定したｍ個のブロック候補のスコアを小さい順に並べたときの隣接するスコアの差の二乗の和が最小になるようにブロック候補を選定する。
ここで、スコアｔ１、ｔ２、・・・、ｔｍは、図7に示すようにスコアＳを小さい順に並べたものであり、又、ブロック候補選択部１０９はｎ個のスコアのうち、最大のスコアが付与されたブロック候補（スコア＝ｔｍ）と最小のスコアが付与されたブロック候補（スコア＝ｔ１）は必ず選択するものとしている。前記所定数ｍは入力部１０３によって予め設定された正の整数、ｋは１から（ｍ−１）まで変わる正の整数、ｎ（≧ｍ）は正の整数である。尚、図７は、ｎが１３、ｍが６の例である。
【００４５】
Ｄ＝Σ（ｔｋ＋１−ｔｋ）２    ・・・・・（２）
前記値Ｄが最小になるとき、隣り合うブロック候補の各スコアｔｋ間の差異が最も均等になり、形状がばらつくようにブロック候補が選定される。これにより、１つのブロックについて、形状の相違が最も均等化した所定数のブロック候補が得られることになる。
【００４６】
ここで、前記スコアに基づいて選択したブロック候補の例と、前記スコアに基づかない方法で選択したブロック候補の例を比較して示す。
図８は長さ方向（Ｘ軸方向）の相違の程度が均等になるようにブロック候補を選択した例である。この例では、長さの長いブロック候補を多く選択し、幅広い（Ｙ軸方向に長い）ブロック候補は少なく選択する傾向がある。
【００４７】
図９は幅方向（Ｙ軸方向）の相違の程度が均等になるようにブロック候補を選択した例である。この例では、幅広のブロック候補を多く選択し、長さの長い（Ｘ軸方向に長い）ブロック候補は少なく選択する傾向がある。
図１０はＸ軸に対するブロック候補（矩形）の対角線の角度の相違の程度が均等になるようにブロック候補を選択した例である。この例では、正方形に近いブロック候補を多く選択し、幅広のブロック候補や長さの長いブロック候補は少なく選択する傾向がある。
【００４８】
図８〜図１０に示した例は、いずれも偏った形状のブロック候補が選択される傾向がある。
これに対して、本発明の実施の形態のように幅及び長さの両方に基づいて付与したスコアＳが均等化するようブロック候補を選択することにより、図１１に示すように分割数が１００の場合でも、形状の相違が最も均等化されたブロック候補が選定される。
【００４９】
ブロック候補選定処理部１０６は、全てのブロックについて処理ステップＳ２０１〜Ｓ２０５の処理を終了したか否か判定し（ステップＳ２０６）、処理が終了していない場合には処理を終了していない次のブロックに変更して（ステップＳ２０７）、前記処理を繰り返す。
以上のようにして、全ブロックの最適配置を求める前に、各ブロックＡ〜Ｇ毎に、スコアＳの相違の程度が最も均等化するように所定数ｍのブロック候補に絞り込む。
【００５０】
全てのブロックについて処理ステップＳ２０１〜Ｓ２０７の処理が終了すると、フロアプラン生成部１１０は、各ブロックについて選定されたブロック候補を用いて、これらのブロック候補の組み合わせを変えながら、シミュレーテッド・アニーリングや遺伝的アルゴリズム等の公知の最適化手法により、面積最小化等の所定条件を満たす新たなフロアプランを生成する（ステップＳ２０８）。
【００５１】
フロアプラン生成処理部１０１はフロアプラン生成部１１０が生成した新フロアプランを表示部１０４に表示し（ステップＳ２０９）、又、記憶部１０２のフロアプランデータ１１１に新フロアプランデータを記憶する（ステップＳ２１０）。表示部１０４には図１２に示す新フロアプランが表示される。
このように、相互の形状の相違の程度が最も均等化されたブロック候補を用いてフロアプランを生成することにより、処理対象のブロック候補数を少なく且つ偏ることなく絞ることが可能になり、少ない処理時間で適切にブロックを配置処理することが可能になる。
【００５２】
以上述べたように本発明の実施の形態は、所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理装置１００において、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定するブロック候補選定処理部１０６と、全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定する配置処理部１１０とを備えて成り、前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、ブロック候補選定処理部１０６は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴としている。
【００５３】
ここで、ブロック候補選定処理部１０６は、前記各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、前記スコアに基づいて前記各ブロック候補の形状がばらつくように前記ブロック候補を選定するように構成することができる。
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅である。
【００５４】
また、ブロック候補選定処理部１０６は、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割するブロック分割部１０７と、前記分割要素の配列を変えることによって、前記アレイブロックについて、相互に形状が異なる複数のブロック候補を生成するブロック候補生成部１０８と、  前記ブロック候補生成部が生成した各ブロック候補について、長さがＬ√Ｍで幅がＷ√Ｍのブロック候補を中心として、最も長いブロック候補のスコアを最大又は最小、最も幅広のブロック候補のスコアを最小又は最大となるように決定し、前記中心のブロック候補よりも長いブロック候補は幅に比例するスコアを付けると共に、前記中心のブロック候補よりも幅広のブロック候補は長さに比例するスコアを付け、ｍ個のブロック候補を選定する場合、最小のスコアｔ１と最大のスコアｔｍが付けられたブロック候補を選定すると共に、（ｍ−２）個のブロック候補については、下記Ｄが最小となるスコアが付けられたブロック候補を選定するブロック候補選択部１０９とを備えて成ることを特徴としている。
Ｄ＝Σ（ｔｋ＋１−ｔｋ）２
但し、Ｍはアレイブロックの分割数、ＬはアレイブロックをＭ分割することによって得られる分割要素の長さ、Ｗは前記分割要素の幅、ｍ、ｎ（≧ｍ）は正の整数、ｋは１から（ｍ−１）まで変わる正の整数であり、ｔ１，・・・，ｔｍは各ブロック候補のスコアを小さい順に並べたものである。
【００５５】
また、前記分割要素は回路素子であると共に前記ブロックはフロアプランを構成するブロックであり、配置処理部１１０は、ブロック候補選定処理部１０６が選定したブロック候補を用いて、前記所定条件を満たすように全ブロックの配置を決定することによってフロアプランを生成することを特徴としている。
係る構成により、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になるという効果を奏する。
【００５６】
また、本発明の実施の形態は、所定形状を有する複数のブロックを所定条件を満たすように配置する配置処理方法において、ブロック候補選定処理部１０６が、複数のブロック中に含まれ複数の分割要素に分割可能なブロックであるアレイブロックを所定の分割数に応じた分割要素に分割し、前記分割要素の配列を変えることによって、当該アレイブロックについて、相互に形状が異なる複数のブロック候補を生成すると共に前記複数のブロック候補の中から所定条件を満たすブロック候補を選定し、配置処理部１１０が、全ての前記アレイブロックを当該アレイブロックの各ブロック候補に置き換えながら全ブロックの配置を変更することによって、全ブロックの配置が所定条件を満足するように決定して成り、前記ブロック候補は幅及び前記幅に直交する長さによって規定される矩形形状を有し、前記ブロック候補選定処理部１０６は、前記各ブロック候補の幅及び長さに基づいて、前記各ブロック候補の形状がばらつくように前記各ブロック候補を選定することを特徴としている。
係る構成により、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
【００５７】
また、コンピュータが本発明の実施の形態に係る配置処理用プログラムを実行することにより、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
【００５８】
また、本発明の実施の形態に係る記録媒体に記録した配置処理用プログラムをコンピュータに実行させることにより、複数の分割要素に分割可能なアレイブロックを含む複数のブロックを配置処理する際、配置を最適化するための処理対象を適切に絞ることにより、少ない処理時間で適切な配置を行うことが可能になる。
尚、前記実施の形態では、配置処理装置としてフロアプラン設計装置の例を挙げたが、ＬＳＩやＦＰＤのレイアウト設計等他の用途にも適用可能である。
【産業上の利用可能性】
【００５９】
アナログ集積回路やデジタル集積回路のフロアプラン、ＦＰＤをはじめとして、所定の形状を有する複数のブロックを所定条件を満たすように配置する装置や方法に適用することが可能である。
【符号の説明】
【００６０】
１００・・・フロアプラン設計装置
１０１・・・フロアプラン生成処理部
１０２・・・記憶部
１０３・・・入力部
１０４・・・表示部
１０５・・・フロアプランデータ取込部
１０６・・・ブロック候補選定処理部
１０７・・・ブロック分割部
１０８・・・ブロック候補生成部
１０９・・・ブロック候補選択部
１１０・・・フロアプラン生成部
１１１・・・フロアプランデータ
１１２・・・新基本回路素子データ
Ａ〜Ｇ・・・ブロック
【図１】
2017027333.tif 000003
【図２】
2017027333.tif 000004
【図３】
2017027333.tif 000005
【図４】
2017027333.tif 000006
【図５】
2017027333.tif 000007
【図６】
2017027333.tif 000008
【図７】
2017027333.tif 000009
【図８】
2017027333.tif 000010
【図９】
2017027333.tif 000011
【図１０】
2017027333.tif 000012
【図１１】
2017027333.tif 000013
【図１２】
2017027333.tif 000014
【図１３】
2017027333.tif 000015
【図１４】
2017027333.tif 000016