An FSM Re-Engineering Approach to Sequential Circuit Synthesis by State Splitting

dc.contributor.authorLin, Yuan
dc.contributor.authorQu, Gang
dc.contributor.authorVilla, Tiziano
dc.contributor.authorSangiovanni-Vincentelli, Alberto
dc.date.accessioned2008-04-28T13:11:06Z
dc.date.available2008-04-28T13:11:06Z
dc.date.issued2008
dc.description.abstractWe propose Finite State Machine (FSM) re-engineering, a performance enhancement framework for FSM synthesis and optimization. It starts with the traditional FSM synthesis procedure, then proceeds to re-construct a functionally equivalent but topologically different FSM based on the optimization objective, and concludes with another round of FSM synthesis on the re-constructed FSM. This approach explores a larger solution space that consists of a set of FSMs functionally equivalent to the original one, making it possible to obtain better solutions than in the original FSM. Guided by the result from the rst round of synthesis, the solution space exploration process can be rapid and cost-ef cient. We apply this framework to FSM state encoding for power minimization and area minimization. The FSM is rst minimized and encoded using existing state encoding algorithms. Then we develop both a heuristic algorithm and a genetic algorithm to re-construct the FSM. Finally, the FSM is reencoded by the same encoding algorithms. To demonstrate the effectiveness of this framework, we conduct experiments on MCNC91 sequential circuit benchmarks. The circuits are read in and synthesized in SIS environment. After FSM re-engineering are performed, we measure the power, area and delay in the newly synthesized circuits. In the powerdriven synthesis, we observe an average 5.5% of total power reduction with 1.3% area increase and 1.3% delay increase. This results are in general better than other low power state encoding techniques on comparable cases. In the area-driven synthesis, we observe an average 2.7% area reduction, 1.8% delay reduction, and 0.4% power increase. Finally, we use integer linear programming to obtain the optimal low power state encoding for benchmarks of small size. We nd that the optimal solutions in the re- engineered FSMs are 1% to 8% better than the optimal solutions in the original FSMs in terms of power minimization.en
dc.format.extent334511 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/7872
dc.language.isoen
dc.relation.isAvailableAtA. James Clark School of Engineeringen_us
dc.relation.isAvailableAtElectrical & Computer Engineeringen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us
dc.subjectfinite state machineen
dc.subjectsequential circuit synthesisen
dc.subjectpower minimizationen
dc.subjectarea minimizationen
dc.titleAn FSM Re-Engineering Approach to Sequential Circuit Synthesis by State Splittingen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR_FSM.pdf
Size:
326.67 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.8 KB
Format:
Item-specific license agreed upon to submission
Description: