JPH04362785A - 組合せ最適化装置 - Google Patents
組合せ最適化装置Info
- Publication number
- JPH04362785A JPH04362785A JP3181505A JP18150591A JPH04362785A JP H04362785 A JPH04362785 A JP H04362785A JP 3181505 A JP3181505 A JP 3181505A JP 18150591 A JP18150591 A JP 18150591A JP H04362785 A JPH04362785 A JP H04362785A
- Authority
- JP
- Japan
- Prior art keywords
- cost
- data
- conversion
- arrangement
- placement
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【0001】
【産業上の利用分野】本発明は、設計分野、特に論理回
路設計における組合せ最適化問題を高速実行する装置に
関するものである。
路設計における組合せ最適化問題を高速実行する装置に
関するものである。
【0002】
【従来の技術】最近、組合せ最適化装置は論理回路設計
などの分野で盛んに利用されるようになってきた。この
組合せ最適化装置としては、例えば、S.Kirkpa
trick, C.D.Gelatt, M.P.Ve
cchi ”Optimization by Sim
ulated Annealing”(Science
,Vol.220,No.4598,pp671−68
0,1983)などに記載されているシミュレーティッ
ド・アニーリングという構成が知られている。
などの分野で盛んに利用されるようになってきた。この
組合せ最適化装置としては、例えば、S.Kirkpa
trick, C.D.Gelatt, M.P.Ve
cchi ”Optimization by Sim
ulated Annealing”(Science
,Vol.220,No.4598,pp671−68
0,1983)などに記載されているシミュレーティッ
ド・アニーリングという構成が知られている。
【0003】以下、図3を参照しながら従来の組合せ最
適化装置について説明する。図3において、細線は制御
信号を、2重線は主にデータの参照関係を、太線は制御
信号及びデータの流れを主に示す。図3において、31
は配置データを生成する配置変換手段を複数記憶したデ
ータベース、32はデータベース31から配置変換手段
を無作為に選択し、配置変換手段により生成された新し
い配置データのコストを計算する変換適用手段、33は
従来の配置データのコストと新しい配置データのコスト
を比較して、従来の配置データと新しい配置データのい
ずれを採用するかを決定するコスト評価手段、34は温
度と呼ばれるパラメータを管理・変更する温度管理手段
、35は配置データの変動を観察し、変動がなくなった
ら処理を終了する処理終了判定手段、36は初期値を設
定、及び生成する初期化する手段である。
適化装置について説明する。図3において、細線は制御
信号を、2重線は主にデータの参照関係を、太線は制御
信号及びデータの流れを主に示す。図3において、31
は配置データを生成する配置変換手段を複数記憶したデ
ータベース、32はデータベース31から配置変換手段
を無作為に選択し、配置変換手段により生成された新し
い配置データのコストを計算する変換適用手段、33は
従来の配置データのコストと新しい配置データのコスト
を比較して、従来の配置データと新しい配置データのい
ずれを採用するかを決定するコスト評価手段、34は温
度と呼ばれるパラメータを管理・変更する温度管理手段
、35は配置データの変動を観察し、変動がなくなった
ら処理を終了する処理終了判定手段、36は初期値を設
定、及び生成する初期化する手段である。
【0004】以上のような図3の構成において、以下、
その動作について図4に示したフローチャートとともに
説明する。
その動作について図4に示したフローチャートとともに
説明する。
【0005】まず、401では初期化手段により初期値
の組合せを生成し、初期値の組合せのコストを計算し、
温度管理手段34で管理されている温度というパラメー
タを初期化する。
の組合せを生成し、初期値の組合せのコストを計算し、
温度管理手段34で管理されている温度というパラメー
タを初期化する。
【0006】次に、402では、変換適用手段32を用
いてデータベース31に記憶されている配置変換手段を
無作為に選択し、選択した配置変換手段を適用して新配
置データを生成する。403では、コスト評価手段33
により402で生成した配置データのコストを計算する
。
いてデータベース31に記憶されている配置変換手段を
無作為に選択し、選択した配置変換手段を適用して新配
置データを生成する。403では、コスト評価手段33
により402で生成した配置データのコストを計算する
。
【0007】404では、403で計算した新配置デー
タのコストと従来配置データのコストと温度管理手段3
4で管理している温度に基づいて、新配置データを採用
するかをコスト評価手段33により決定する。以下にそ
の方法を示す。
タのコストと従来配置データのコストと温度管理手段3
4で管理している温度に基づいて、新配置データを採用
するかをコスト評価手段33により決定する。以下にそ
の方法を示す。
【0008】新配置データのコストが従来配置データの
コストより減少した場合は、新配置データを採用する。 逆に、新配置データのコストが従来配置データのコスト
より増加した場合は、0以上1未満の乱数を発生させ、
その乱数が exp(−△C/T) より大きい時に新配置データを採用する。ここで、△C
は新配置データのコストと従来配置データのコストの差
、Tは温度管理手段34で管理している温度である。
コストより減少した場合は、新配置データを採用する。 逆に、新配置データのコストが従来配置データのコスト
より増加した場合は、0以上1未満の乱数を発生させ、
その乱数が exp(−△C/T) より大きい時に新配置データを採用する。ここで、△C
は新配置データのコストと従来配置データのコストの差
、Tは温度管理手段34で管理している温度である。
【0009】新配置データを採用する場合は405で配
置データを更新し、採用しない場合は従来の配置データ
のまま406へ飛ぶ。
置データを更新し、採用しない場合は従来の配置データ
のまま406へ飛ぶ。
【0010】406では、コスト評価手段33により配
置データを生成した回数を管理し、その回数が設定した
値を越えたら温度管理手段34で管理している温度を下
げる。逆に、その回数が設定値以内の場合は402へ戻
る。
置データを生成した回数を管理し、その回数が設定した
値を越えたら温度管理手段34で管理している温度を下
げる。逆に、その回数が設定値以内の場合は402へ戻
る。
【0011】407では、処理終了判定手段35を用い
て、各温度における最終コストが3回続けて同じ場合に
処理を終了する。そうでない場合は402に戻る。
て、各温度における最終コストが3回続けて同じ場合に
処理を終了する。そうでない場合は402に戻る。
【0012】
【発明が解決しようとする課題】しかし、以上の方法で
は、配置変換手段を無作為に適用するため、無駄な配置
変換手段を適用する可能性が大きくなり、処理時間がか
かる。本発明は上記課題に鑑み、配置変換手段を効率的
に適用して処理時間を短縮することを目的とする。
は、配置変換手段を無作為に適用するため、無駄な配置
変換手段を適用する可能性が大きくなり、処理時間がか
かる。本発明は上記課題に鑑み、配置変換手段を効率的
に適用して処理時間を短縮することを目的とする。
【0013】
【課題を解決するための手段】この目的を達成するため
、本発明は、配置変換手段の有効性を判定する変換有効
性判定手段と、複数の配置変換手段の適用比率を上記変
換有効性判定手段の判定結果に基づいて調整する適用比
率調整手段とを有している。
、本発明は、配置変換手段の有効性を判定する変換有効
性判定手段と、複数の配置変換手段の適用比率を上記変
換有効性判定手段の判定結果に基づいて調整する適用比
率調整手段とを有している。
【0014】
【作用】本発明において、配置転換手段の適用比率を管
理する適用比率調整手段は配置変換手段の有効性を温度
毎に判定する変換有効性判定手段のデータに基づき、次
の温度における適用比率を決定する。この比率に基づき
次の温度に対し、有効性の高い配置変換手段を優先的に
適用することにより、無駄な配置変換手段を適用する回
数を減少させるようにしたものである。
理する適用比率調整手段は配置変換手段の有効性を温度
毎に判定する変換有効性判定手段のデータに基づき、次
の温度における適用比率を決定する。この比率に基づき
次の温度に対し、有効性の高い配置変換手段を優先的に
適用することにより、無駄な配置変換手段を適用する回
数を減少させるようにしたものである。
【0015】
【実施例】以下、図1を参照しながら本発明の一実施例
について説明する。
について説明する。
【0016】図1において、細線は制御信号を、2重線
は主にデータの参照関係を、太線は制御信号及びデータ
の流れを主に示す。図1において、1は配置データを生
成する配置変換手段を複数記憶したデータベース、6は
配置変換手段の有効性を判定する変換有効性判定手段、
5は複数の配置変換手段の適用比率を変換有効性判定手
段6の判定結果に基づいて調整する適用比率調整手段、
2は適用比率調整手段5によって決定された適用比率に
基づいてデータベース1から選択した配置変換手段を適
用し、適用された配置変換手段により生成された新しい
配置データのコストを計算する変換適用手段、3は従来
の配置データのコストと新しい配置データのコストを比
較して、従来の配置データと新配置データのいずれを採
用するかを決定するコスト評価手段、4は温度と呼ばれ
るパラメータを管理・変更する温度管理手段、7は配置
データの変動を観察し、変動がなくなったら処理を終了
する処理終了判定手段、8は初期値を設定、及び生成す
る初期化手段である。
は主にデータの参照関係を、太線は制御信号及びデータ
の流れを主に示す。図1において、1は配置データを生
成する配置変換手段を複数記憶したデータベース、6は
配置変換手段の有効性を判定する変換有効性判定手段、
5は複数の配置変換手段の適用比率を変換有効性判定手
段6の判定結果に基づいて調整する適用比率調整手段、
2は適用比率調整手段5によって決定された適用比率に
基づいてデータベース1から選択した配置変換手段を適
用し、適用された配置変換手段により生成された新しい
配置データのコストを計算する変換適用手段、3は従来
の配置データのコストと新しい配置データのコストを比
較して、従来の配置データと新配置データのいずれを採
用するかを決定するコスト評価手段、4は温度と呼ばれ
るパラメータを管理・変更する温度管理手段、7は配置
データの変動を観察し、変動がなくなったら処理を終了
する処理終了判定手段、8は初期値を設定、及び生成す
る初期化手段である。
【0017】以上のような図1の構成において、以下、
その動作について図2に示したフローチャートとともに
説明する。
その動作について図2に示したフローチャートとともに
説明する。
【0018】まず、201では初期化手段8により初期
値の組合せを生成し、初期値の組合せコストを計算し、
温度管理手段4で管理している温度というパラメータと
、適用比率調整手段5で管理している適用比率というパ
ラメータを初期化する。
値の組合せを生成し、初期値の組合せコストを計算し、
温度管理手段4で管理している温度というパラメータと
、適用比率調整手段5で管理している適用比率というパ
ラメータを初期化する。
【0019】次に、202では、変換適用手段2により
適用比率調整手段5で管理している適用比率の大小に基
づいてデータベース1に記憶されている配置変換手段を
1つ選択する。適用比率が大きい配置変換手段ほど優先
的に選択される。
適用比率調整手段5で管理している適用比率の大小に基
づいてデータベース1に記憶されている配置変換手段を
1つ選択する。適用比率が大きい配置変換手段ほど優先
的に選択される。
【0020】203では、同じく変換適用手段2により
202で選択した配置変換手段を適用して新配置データ
を生成する。204では、コスト評価手段3により20
3で生成した配置データのコストを計算する。
202で選択した配置変換手段を適用して新配置データ
を生成する。204では、コスト評価手段3により20
3で生成した配置データのコストを計算する。
【0021】205では、204で計算した新配置デー
タのコストと従来配置データのコストと温度管理手段4
で管理している温度に基づいて、新配置データを採用す
るかをコスト評価手段3により決定する。以下にその方
法を示す。
タのコストと従来配置データのコストと温度管理手段4
で管理している温度に基づいて、新配置データを採用す
るかをコスト評価手段3により決定する。以下にその方
法を示す。
【0022】新配置データのコストが従来配置データの
コストより減少した場合は、新配置データを採用する。 逆に、新配置データのコストが従来配置データのコスト
より増加した場合は、0以上1未満の乱数を発生させ、
その乱数が exp(−△C/T) より大きい時に新配置データを採用する。ここで、△C
は新配置データのコストと従来配置データのコストの差
、Tは温度管理手段4で管理している温度である。
コストより減少した場合は、新配置データを採用する。 逆に、新配置データのコストが従来配置データのコスト
より増加した場合は、0以上1未満の乱数を発生させ、
その乱数が exp(−△C/T) より大きい時に新配置データを採用する。ここで、△C
は新配置データのコストと従来配置データのコストの差
、Tは温度管理手段4で管理している温度である。
【0023】新配置データを採用する場合は206で配
置データを更新し、採用しない場合は従来の配置データ
のまま207へ飛ぶ。
置データを更新し、採用しない場合は従来の配置データ
のまま207へ飛ぶ。
【0024】コスト評価手段3により207では、配置
データを生成した回数を管理し、その回数が設定した値
を越えたら温度管理手段4で管理している温度を下げる
。逆に、その回数が設定値以内の場合は202へ飛ぶ。
データを生成した回数を管理し、その回数が設定した値
を越えたら温度管理手段4で管理している温度を下げる
。逆に、その回数が設定値以内の場合は202へ飛ぶ。
【0025】208では、適用比率調整手段5と変換有
効性判定手段6を用いて温度毎の適用比率を更新する。
効性判定手段6を用いて温度毎の適用比率を更新する。
【0026】変換有効性判定手段6では、データベース
1に記憶されている各配置変換手段の有効性を温度毎に
判定する。本実施例では、各配置変換手段の適用回数と
その配置変換手段を適用しコストが減少した回数の比率
が大きい程、有効性が高いと判定している。
1に記憶されている各配置変換手段の有効性を温度毎に
判定する。本実施例では、各配置変換手段の適用回数と
その配置変換手段を適用しコストが減少した回数の比率
が大きい程、有効性が高いと判定している。
【0027】適用比率調整手段5では、まず、変換有効
性判定手段6の結果に基づいて、複数の配置変換手段を
有効性の高い順に順位付けする。次に順位の高い配置変
換手段と順位の低い配置変換手段に分ける。順位の高い
配置変換手段に対しては適用比率を増加させ、順位の低
い配置変換手段に対しては適用比率を減少させる。さら
に、増加率は順位が高い程大きくし、減少率は順位が低
い程大きくする。これらの増減率に基づいて、次の温度
における適用比率を決定する。
性判定手段6の結果に基づいて、複数の配置変換手段を
有効性の高い順に順位付けする。次に順位の高い配置変
換手段と順位の低い配置変換手段に分ける。順位の高い
配置変換手段に対しては適用比率を増加させ、順位の低
い配置変換手段に対しては適用比率を減少させる。さら
に、増加率は順位が高い程大きくし、減少率は順位が低
い程大きくする。これらの増減率に基づいて、次の温度
における適用比率を決定する。
【0028】つまり、変換有効性判定手段によって判定
された有効性が高い配置変換手段ほど適用比率を大きく
し、有効性が低い配置変換手段ほど適用比率を小さくす
る。
された有効性が高い配置変換手段ほど適用比率を大きく
し、有効性が低い配置変換手段ほど適用比率を小さくす
る。
【0029】本実施例では、配置変換手段数をN、最大
増減率幅をW、配置変換手段の優先順位をi、(N−1
)/2 の商を分割数nとし、各配置変換手段の適用比
率の増減率r(i)を以下のように定めている。Nが奇
数(N=2n+1)の場合は、 r(i) = +(W/n)×((n+1) − i)
i ≦ nr(i) = 0
i = n+1r(i)
= −(W/n)×(i − (n+1))
i > n+1Nが偶数(N=2(n+1))の場合は
、r(i) = +(W/n)×((n+1) − i
) i ≦ nr(i) = 0
i = n+1,n+
2r(i) = −(W/n)×(i − (n+2)
) i > n+2としている。
増減率幅をW、配置変換手段の優先順位をi、(N−1
)/2 の商を分割数nとし、各配置変換手段の適用比
率の増減率r(i)を以下のように定めている。Nが奇
数(N=2n+1)の場合は、 r(i) = +(W/n)×((n+1) − i)
i ≦ nr(i) = 0
i = n+1r(i)
= −(W/n)×(i − (n+1))
i > n+1Nが偶数(N=2(n+1))の場合は
、r(i) = +(W/n)×((n+1) − i
) i ≦ nr(i) = 0
i = n+1,n+
2r(i) = −(W/n)×(i − (n+2)
) i > n+2としている。
【0030】209では、処理終了判定手段7を用いて
、各温度における最終コストが3回続けて同じ場合に処
理を終了する。そうでない場合は202に戻る。
、各温度における最終コストが3回続けて同じ場合に処
理を終了する。そうでない場合は202に戻る。
【0031】以上のように、適用比率調整手段5と変換
有効性判定手段6を設けて、各温度毎に適用比率を調整
することにより、配置変換手段の効果的な適用が可能に
なる。
有効性判定手段6を設けて、各温度毎に適用比率を調整
することにより、配置変換手段の効果的な適用が可能に
なる。
【0032】
【発明の効果】以上のように本発明は配置変換手段の有
効性を温度毎に判定する変換有効性判定手段と前記変換
有効性判定手段のデータに基づき、次の温度における配
置転換手段の適用比率を決定する適用比率調整手段を設
けることにより、無駄な配置変換手段を適用する回数を
減少させるので、その結果、高速処理が可能となる。
効性を温度毎に判定する変換有効性判定手段と前記変換
有効性判定手段のデータに基づき、次の温度における配
置転換手段の適用比率を決定する適用比率調整手段を設
けることにより、無駄な配置変換手段を適用する回数を
減少させるので、その結果、高速処理が可能となる。
【図1】本発明の実施例における構成図
【図2】実施例
におけるフローチャート
におけるフローチャート
【図3】従来の組合せ最適化装
置における構成図
置における構成図
【図4】従来の組合せ最適化装置にお
けるフローチャート
けるフローチャート
1 データベース
2 変換適用手段
3 コスト評価手段
4 温度管理手段
5 適用比率調整手段
6 変換有効性判定手段
7 処理終了判定手段
8 初期化手段
Claims (1)
- 【請求項1】 新しい配置データを生成する複数の配
置変換手段と、各配置変換手段の有効性を判定する変換
有効性判定手段と、複数の配置変換手段を適用する比率
を上記変換有効性判定手段の判定結果に基づいて調整す
る適用比率調整手段と、上記適用比率調整手段で決定し
た適用比率に基づいて複数の配置変換手段のいずれかを
適用して生成される新しい配置データのコストを計算す
る変換適用手段と、従来の配置データのコストと新しい
配置データのコストを比較して従来の配置データと新し
い配置データのいずれを採用するかを決定するコスト評
価手段と、温度と呼ばれるパラメータを管理する温度管
理手段と、配置データのコストの変動がなくなったとき
処理を終了する処理終了判定手段を具備することを特徴
とする組合せ最適化装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3181505A JP2893144B2 (ja) | 1991-06-10 | 1991-06-10 | 組合せ最適化装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3181505A JP2893144B2 (ja) | 1991-06-10 | 1991-06-10 | 組合せ最適化装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04362785A true JPH04362785A (ja) | 1992-12-15 |
| JP2893144B2 JP2893144B2 (ja) | 1999-05-17 |
Family
ID=16101938
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3181505A Expired - Lifetime JP2893144B2 (ja) | 1991-06-10 | 1991-06-10 | 組合せ最適化装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2893144B2 (ja) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02242474A (ja) * | 1989-03-16 | 1990-09-26 | Hitachi Ltd | 素子配置最適化方法及び装置並びに最適配置判定方法及び装置 |
-
1991
- 1991-06-10 JP JP3181505A patent/JP2893144B2/ja not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02242474A (ja) * | 1989-03-16 | 1990-09-26 | Hitachi Ltd | 素子配置最適化方法及び装置並びに最適配置判定方法及び装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2893144B2 (ja) | 1999-05-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CA2115731C (en) | Dynamically programmable bus arbiter with provisions for historical feedback and error detection and correction | |
| KR100586351B1 (ko) | 상변화 물질 메모리 소자에 기록 동작을 실행하는 기술 및장치 | |
| US7499960B2 (en) | Adaptive memory allocation | |
| CN102081964B (zh) | 动态随机访问存储器刷新的方法和系统 | |
| CN107272876A (zh) | 用于管理多核片上系统上的全局芯片功率的方法和装置 | |
| Gotlieb et al. | Performance of movable-head disk storage devices | |
| CN111245732B (zh) | 一种流量控制方法、装置及设备 | |
| CN113325998B (zh) | 读写速度控制方法、装置 | |
| US10908675B2 (en) | Electronic device for signal processing with embedded optimization of electrical energy consumption and a corresponding method | |
| WO2021042245A1 (zh) | 一种用于控制散热装置的方法及其设备 | |
| KR20180085605A (ko) | 핸드쉐이크를 이용하여 메모리의 전력을 조절하는 시스템 온 칩 및 이의 동작 방법 | |
| JP7110278B2 (ja) | 負荷を均衡化するための方法、装置、機器、コンピュータ読み取り可能な記憶媒体及びコンピュータプログラム | |
| CN109981732A (zh) | 海量文件传输控制方法及装置 | |
| JPH04362785A (ja) | 組合せ最適化装置 | |
| US11797410B2 (en) | Chiplet-level performance information for configuring chiplets in a processor | |
| CN105528303B (zh) | 用于管理存储系统的方法和装置 | |
| US7302457B2 (en) | Method and apparatus for providing random bits | |
| CN114065121A (zh) | 一种求解伊辛模型的计算方法及设备 | |
| CN115660055B (zh) | 降低存储器带宽的方法 | |
| CN115134300A (zh) | 面向软件定义网络的交换设备规则缓存管理方法 | |
| JP5678923B2 (ja) | ストレージシステム、入出力制御装置、入出力制御方法、および、コンピュータ・プログラム | |
| JP2729987B2 (ja) | ネットワーク構成データ処理装置の重み保持方式 | |
| KR20210125729A (ko) | 인공 신경망의 웨이트 갱신 시스템 및 방법 | |
| JP7783969B2 (ja) | ニューラルネットワークプロセッサによるニューラルネットワークの特徴マップの処理方法、装置及び機器 | |
| CN119127877B (zh) | 针对数据库的数据处理系统、方法、装置、存储介质和计算机程序产品 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |