| Presentation | 2008-11-19 Accuracy and Speed Improvement of Random Walk Simulation Using Walk Sharing and Return-to-Start Transient Analysis Technique Hitoshi MIWA, Goro SUZUKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Random walk is a statistical approach to solve electric circuits using Markov chain Monte Carlo method. Unlike conventional circuit simulation, random walk can compute voltages or currents of only a small portion of the large circuit in very simple computation process. However, required computational repetition number per node is large. It is difficult to judge whether the solution has sufficiently converged. To overcome these difficulties, we propose three techniques; random walk termination decision technique, walk sharing technique and return-to-initial-value technique. Without sacrificing accuracy, the walk sharing technique reduced the computational repetition number by about a half and the return-to-initial-value technique reduced the computational repetition number in a transient analysis of a circuit with capacitors by about 20 times in our experiments. In the transient analysis using conventional random walk, all the nodes in the circuit need to be analyzed even if only one node is to be analyzed. Only one node of interest needs to be analyzed using our return-to-initial-value technique. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Monte Carlo method / Markov chain / circuit analysis / power grid noise analysis / random walk / SPICE / KCL |
| Paper # | VLD2008-87,DC2008-55 |
| Date of Issue |
| Conference Information | |
| Committee | VLD |
|---|---|
| Conference Date | 2008/11/10(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 | VLSI Design Technologies (VLD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Accuracy and Speed Improvement of Random Walk Simulation Using Walk Sharing and Return-to-Start Transient Analysis Technique |
| Sub Title (in English) | |
| Keyword(1) | Monte Carlo method |
| Keyword(2) | Markov chain |
| Keyword(3) | circuit analysis |
| Keyword(4) | power grid noise analysis |
| Keyword(5) | random walk |
| Keyword(6) | SPICE |
| Keyword(7) | KCL |
| 1st Author's Name | Hitoshi MIWA |
| 1st Author's Affiliation | Department of Information Science, University of Kitakyushu() |
| 2nd Author's Name | Goro SUZUKI |
| 2nd Author's Affiliation | Department of Information Science, University of Kitakyushu |
| Date | 2008-11-19 |
| Paper # | VLD2008-87,DC2008-55 |
| Volume (vol) | vol.108 |
| Number (no) | 298 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |