| Presentation | 2005-12-02 Effective Contraction of Timed STGs for Decomposition Based Timed Circuit Synthesis Tomohiro YONEDA, Chris MYERS, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In the decomposition based synthesis method, for each output signal, an input signal set sufficient to synthesize a circuit for the output is first obtained, and the signal transition graph (STG) used as a specification is contracted to include only transitions on this input signal set and the output, from which the circuit for the output is synthesized efficiently. In order to extend this approach for the timed circuit synthesis, the contraction algorithm needs to handle timed STGs. A simple extension of the untimed contraction algorithm, however, loses several timing information, causing it to synthesize non-optimal circuits. On the other hand, an exact contraction algorithm that preserves the timing information precisely can be applied to only a small class of transitions, which degrades the performance of the decomposition based method. This paper proposes a way to contract timed STGs effectively without losing the optimality of the synthesized circuits. According to the experimental results, the proposed method can handle a wide variety of benchmark circuits successfully, and for large specifications, a significant reduction in the size of STGs is obtained by the proposed contraction method with almost no redundant gates. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Contraction / timed signal transition graphs / timed circuits / decomposition based logic synthesis |
| Paper # | VLD2005-86,ICD2005-181,DC2005-63 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2005/11/25(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) | Effective Contraction of Timed STGs for Decomposition Based Timed Circuit Synthesis |
| Sub Title (in English) | |
| Keyword(1) | Contraction |
| Keyword(2) | timed signal transition graphs |
| Keyword(3) | timed circuits |
| Keyword(4) | decomposition based logic synthesis |
| 1st Author's Name | Tomohiro YONEDA |
| 1st Author's Affiliation | National Institute of Informatics() |
| 2nd Author's Name | Chris MYERS |
| 2nd Author's Affiliation | University of Utah |
| Date | 2005-12-02 |
| Paper # | VLD2005-86,ICD2005-181,DC2005-63 |
| Volume (vol) | vol.105 |
| Number (no) | 449 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |