| Presentation | 2010-12-01 Adjacent Insertion and Its Effectiveness in Code-Based 3-D Placement Shin UESUGI, Mineo KANEKO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Three Dimensional (3D) cuboid placement can be considered as a mathematical background of several practical problems such as task scheduling problem for dynamically reconfigurable VLSIs. One typical approach to this 3D placement is the combination of a coding method of placement and a stochastic search method such as Simulated Annealing (SA). Being inspired by the success of Sequence Pair (SP) or Ordered-Tree (O-Tree) in two-dimensional rectangular placement, Sequence Quintuple code, which uses five sequences of cuboid names, and Double-Tree and Seqence (DTS), which uses two trees and one sequence, have been proposed. However, when those methods are combined with SA search, their convergence to solutions of good quality is not so fine as SP and O-tree in 2D placement. In this report, we focus on a kind of redundancy that SQ coding has, which may generate worthless neighbor solutions with a high probability. So we try to improve the convergence to a good solution by suppressing those worthless neighbor solutions. To this end, we will introduce a novel move operation named "adjacent insertion" into SQ framework, which is based on the concept that, in any proper placement, every cuboid is expected to share its border with other cuboid. Finally, our proposed method is evaluated through computer experiments. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | 3-D placement / simulated annealing (SA) algorithm / adjacent insertion / computer experiment |
| Paper # | VLD2010-77,DC2010-44 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2010/11/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Dependable Computing (DC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Adjacent Insertion and Its Effectiveness in Code-Based 3-D Placement |
| Sub Title (in English) | |
| Keyword(1) | 3-D placement |
| Keyword(2) | simulated annealing (SA) algorithm |
| Keyword(3) | adjacent insertion |
| Keyword(4) | computer experiment |
| 1st Author's Name | Shin UESUGI |
| 1st Author's Affiliation | School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)() |
| 2nd Author's Name | Mineo KANEKO |
| 2nd Author's Affiliation | School of Information Science, Japan Advanced Institute of Science and Technology (JAIST) |
| Date | 2010-12-01 |
| Paper # | VLD2010-77,DC2010-44 |
| Volume (vol) | vol.110 |
| Number (no) | 317 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |