| Presentation | 2006-11-28 Computational Complexity of Simultaneous Optimization of Control Schedule and Skew in Datapath Synthesis Takayuki OBATA, Mineo KANEKO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | As well as the schedule affects system performance, the control skew, i.e., the arrival time difference of control signals between registers, can be utilized to improve the system performance. In this paper, we discuss the simultaneous optimization of the control step assignment and the control skew assignment, and we prove that, even if the execution sequence of operations assigned to the same resource is fixed and only the control step assignment remains unfixed, the simultaneous optimization problem under a fixed clock period is NP-hard. The proof is based on the reduction from 3SAT problem. The result of this paper would become an important base for various types of the intentional-skew-aware system optimization problems. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | High-Level Synthesis / Skew Scheduling / Control Scheduling / NP-hard |
| Paper # | VLD2006-65,DC2006-52 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2006/11/21(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computational Complexity of Simultaneous Optimization of Control Schedule and Skew in Datapath Synthesis |
| Sub Title (in English) | |
| Keyword(1) | High-Level Synthesis |
| Keyword(2) | Skew Scheduling |
| Keyword(3) | Control Scheduling |
| Keyword(4) | NP-hard |
| 1st Author's Name | Takayuki OBATA |
| 1st Author's Affiliation | School of Information Science, Japan Advanced Institute of Science and Technology() |
| 2nd Author's Name | Mineo KANEKO |
| 2nd Author's Affiliation | School of Information Science, Japan Advanced Institute of Science and Technology |
| Date | 2006-11-28 |
| Paper # | VLD2006-65,DC2006-52 |
| Volume (vol) | vol.106 |
| Number (no) | 390 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |