MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
スポンサーリンク
概要
- 論文の詳細を見る
The optimization techniques for VLSI/PCB placement with larger solution space and more objectives are facing big challenges to get a better solution with less runtime. In this paper, a new stochastic algorithm, named MSA, is proposed to improve the best case and the worst case of multi-objective placement. MSA is mixed by simulated annealing (SA), genetic algorithm (GA) and relay-race algorithm (RRA). It is based on a two-stage SA in which the temperature scheduling and a set of moving methods are designed differently for different stages, i.e. one type of relay. During the first stage, to explore huge solution space more effectively, the moving methods with big changes, such as the crossover operator from GA, are used in higher temperature. During the second stage, to get a better final convergence, the moving methods with small changes are used in lower temperature. Furthermore, the guide from RRA, i.e. another type of relay, which adjusts the selection probability among moving methods according to the improving speed, is integrated to improve the exploration efficiency. Based on the experiment comparing with the published data, MSA improves the multiple objectives of placement. MSA obtains >13% Pareto improvement for power with a constraint of delay, comparing with SA. Under a tight delay constraint, MSA outperforms RRA in a part of Pareto frontiers. Besides, a near log-linear trend of average improvement rates from SA to MSA is gotten. That means MSA is more suitable for the placement with larger solution space.
- 2011-09-19
著者
-
Takahashi Atsushi
Division of Electrical, Electronic and Information Engineering, Osaka University
-
UENO Shuichi
Department of Communication and Integrated Systems, Tokyo Institute of Technology
-
TAKAHASHI Atsushi
Graduate School of Science and Technology, Tokyo Institute of Technology
-
Takahashi Atsushi
Division Of Electrical Electronic And Information Engineering Osaka University
-
Ueno Shuichi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
-
Ueno Shuichi
Department Of Biological Science Faculty Of Science Yamaguchi University
-
Sheng Yiqiang
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
-
Takahashi Atsushi
Division Of Electrical Electronic And Information Engineering Graduate School Of Engineering Osaka University
関連論文
- A-3-10 Top Layer Plating Lead Maximization for BGA Packages
- 2層BGAパッケージのための詳細ビア配置手法の評価(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- 入力べクトルと回路の内部状態を考慮したピーク電力高速見積もり手法(低電力設計と回路設計技術,システムオンシリコンを支える設計技術)
- PCB配線設計のための一層複線指定長自動配線手法(システム設計と高位・論理設計,物理設計及び一般)
- On Two Problems of Nano-PLA Design
- 最小総変位配置実現問題のための高速位相変更手法(物理設計,物理設計及び一般)
- 単層プリント基板配線のための効率的な高混雑度領域特定および45度線による混雑度緩和法(回路最適化技術,システム設計及び一般)
- エラー検出回復方式における加算器の性能評価(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 一般同期方式における消費電力を抑えたクロック木構成のためのクラスタ分割法(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- A Clustering Based Fast Clock Schedule Algorithm for Light Clock-Trees(Special Section on VLSI Design and CAD Algorithms)
- A Note on Two Problems of Nano-PLA Design
- A Note on Two Problems of Nano-PLA Design
- A Note on Two Problems of Nano-PLA Design
- A-3-1 一般同期方式におけるクラスタ分割に基づくクロック木の性能評価(A-3.VLSI設計技術,一般セッション)
- Gene expression profiling of human myocardium with atrial fibrillation by DNA microarray analysis
- Cardioprotective effects of angiotensin II receptor blockade on the molecular responses induced by mechanical stress in cardiac myocytes
- DNA microarray analysis of the in vivo progression mechanism for heart failure in Dahl salt-sensitive rats
- A RELATIONSHIP BETWEEN ELECTROCHEMICAL REDUCTION POTENTIAL AND THE ENZYMATIC REDUCTION OF NITRATED NAPHTHALENES BY MICROSOMES OR CYTOSOL FROM RAT LIVER
- A-3-4 単層プリント基板配線のための高混雑度領域特定手法(A-3.VLSI設計技術,一般セッション)
- On the Complexity of Fault Testing for Reversible Circuits
- A-1-26 On the Complexity of Fault Testing for Reversible Circuits
- Analytical Device Model of SOI MOSFETs Including Self-Heating Effect
- MILP-Based Efficient Routing Method with Restricted Route Structure for 2-Layer Ball Grid Array Packages
- VLSI設計自動化の現状と将来展望(プロセス・デバイス・回路シミュレーション及び一般)
- Effect of Chaetochromin A, Chaetochromin D and Ustilaginoidin A,Bis (naphtho-γ-pyrone) Derivatives, on the Mouse Embryo Limb Bud and Midbrain Cells in Culture
- Doppler ultrasound measurements of knee joint synovitis in rheumatoid arthritis patients treated with infliximab
- Power Doppler and spectral Doppler measurements of knee-joint synovitis in rheumatoid arthritis patients with superficial pattern signals and in those with deep pattern signals
- Achilles tendonitis in a patient with Behcet's disease
- Two localization patterns of vascularity demonstrated by power Doppler sonography at the suprapatellar recess in knee joints of patients with rheumatoid arthritis : intracapsular and supracortical
- Power Doppler sonography for detection of intraarticular vascularization in knee joints of patients with rheumatoid arthritis
- On Dynamic Fault Tolerance for WSI Networks
- On Two-Directional Orthogonal Ray Graphs
- Orthogonal ray graphs and nano-PLA design (コンカレント工学)
- Orthogonal ray graphs and nano-PLA design (回路とシステム)
- On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
- On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
- On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
- On the permutation routing in all-optical caterpillar networks (回路とシステム)
- On the permutation routing in all-optical caterpillar networks (コンカレント工学)
- "B-2 Metabolic Study of Tris(2-Chloroethyl) Phosphate (TCEP) in vivo and in vitro.
- ORIGIN AND CHARACTERISTICS OF FRESHLY ISOLATED RENAL CELLS OBTAINED BY PERFUSION OF COLLAGENASE IN VITRO
- COMPARISONS OF THE TOXICOKINETIC PARAMETERS IN RATS DETERMINED FOR LOW AND HIGH DOSE OF γ-CHLORDANE
- COMPARATIVE STUDY ON METABOLISM OF N-NITROSODIMETHYLAMINE AND N-NITROSOMETHYLBENZYLAMINE IN RAT LIVER
- A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
- On the Three-Dimensional Orthogonal Drawing of Series-Parallel Graphs
- A-1-27 On the Three-Dimensional Layout of Butterfly Networks
- A-1-31 A Note on Sparse Networks Tolerating Random Faults for Cycles(A-1. 回路とシステム, 基礎・境界)
- On the Proper-Path-Decomposition of Trees
- Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Midblastula transition (MBT) of the cell cycles in the yolk and pigment granule-free translucent blastomeres obtained from centrifuged Xenopus embryos
- ESTABLISHMENT A METHOD TO ANALYZE CELL CYCLE AND CELL DIFFERENTIATION UPON EARLY XENOPUS DEVELOPMENT USING TRANSPARENT BLASTOMERES(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
- CHANGES IN INTRACELLULAR CA^ CONCENTRATION DURING EARLY EMBRYONIC CELL CYCLES IN XENOPUS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
- THE REGULATING MECHANISM OF CENTROSOME SEPARATION AFTER MID-BLASTULA TRANSITION (MBT) IN XENOPUS EMBRYOS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
- FREQUENCY AND ELECTROPHYSIOLOGICAL CHARACTERISTICS OF PATIENTS WITH MULTIPLE AND MULTIPLE CONPONENTS OF ACCESSORY ATRIOVENTRICULAR PATHWAYS IN CATHETER ABLATION
- On-Line Multicasting in All-Optical Networks
- A-1-25 On Efficient Universal Quantum Circuits
- Universal test sets for reversible circuits (コンカレント工学)
- Universal test sets for reversible circuits (回路とシステム)
- A-1-14 Fault Testing for Linear Reversible Circuits
- On Fault Testing for Reversible Circuits
- Sacral Arachnoid Cyst Associated with Marfan Syndrome
- Multidetector-row CT Imaging of Aneurysm Rupture of the Aortic Arch
- Expression of Matrix Metalloproteinases in Patients With Acute Myocardial Infarction
- A Note on the Circuit-switched Fixed Routing in Networks (特集 並列処理)
- Fault-Tolerant Meshes with Efficient Layouts
- FPGA上に実現した可変レイテンシ回路の動作検証(論理設計2,システムオンシリコンを支える設計技術)
- 最小総変位配置実現問題に対し効率的な位相変更手法CRP手法の提案(物理設計,システムオンシリコンを支える設計技術)
- ゲートレベルシミュレーションによるエラー検出・回復方式回路の評価(論理設計2,システムオンシリコンを支える設計技術)
- A-3-20 準ニュートン法を用いた自由角度配線のための逐次改善手法(A-3.VLSI設計技術,一般セッション)
- エラー検出回復方式における様々な加算器の性能評価(システムと信号処理及び一般)
- 集合対間配線問題に関する一考察(配置配線,物理設計及び一般)
- MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations (ディペンダブルコンピューティング)
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム(実装技術と低消費電力化,デザインガイア2011-VLSI設計の新しい大地-)
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム(実装技術と低消費電力化,デザインガイア2011-VLSI設計の新しい大地-)
- A-3-3 単層プリント基板配線のための各ネットの配線長達成性を考慮した等長配線手法(A-3.VLSI設計技術,一般セッション)
- 一般同期方式における最適2クラスタ分割手法
- 遅延ばらつき適応回路 : 遅延ばらつき状況下の高性能回路
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム
- FPGA上に実現した可変レイテンシ回路の性能評価(再構成回路,システムオンシリコンを支える設計技術)
- FOREWORD
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム
- A New Variation of Adaptive Simulated Annealing for 2D/3D Packing Optimization
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- A New Variation of Adaptive Simulated Annealing for 2D/3D Packing Optimization
- エラー検出回復方式を用いた可変レイテンシ回路のための高速な性能見積もり手法(低電力化・高信頼化,組込み技術とネットワークに関するワークショップETNET2013)
- 単層プリント基板のための各ネットの目標配線長達成性を考慮した配線手法(配線設計,システムオンシリコンを支える設計技術)
- A-3-6 指定長幹配線間題において配線長を調整する領域に関する一考察(A-3.VLSI設計技術)
- 半正定値緩和法を用いた LELECUT トリプルパターニングのためのレイアウト分割手法
- 側壁ダブルパターニングのための修正2色グリッド配線法 (VLSI設計技術)
- ダブルパターニングにおけるリソグラフィECOのためのパターン局所修正法 (VLSI設計技術)
- エラー検出回復方式を用いた可変レイテンシ回路のための高速な性能見積もり手法(低電力化・高信頼化,組込み技術とネットワークに関するワークショップETNET2013)
- 集合対間配線に対する配線長差削減アルゴリズムの改良 (VLSI設計技術)
- FPGA上に実現した可変レイテンシ回路の性能評価