{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81274"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81274","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits","abstract":"In the first part of the work, we propose an algorithm to decompose a given finite state machine (FSM) into smaller interacting FSMs such that by themselves they have plenty of self-loops, although the original FSM may not have any self-loops. We power down these decomposed FSM during the transitions corresponding to the self-loops to save power consumption. Second, we extend the above work to resynthesize sequential machines. We propose a symbolic simulation-based algorithm to extract the self-loops of the underlying FSM. We partition the sequential machine and apply the above clockgating technique. Third, we propose a synthesis methodology that uses algebraic techniques like kernel extraction, cube extraction, and collapsing to minimize power consumption of a logic function. A unique power cost function based on a fast mapping of a Boolean expression to a generic library is used to steer the above algebraic transformations to reduce its power consumption. Fourth, in order to guide the proposed synthesis tool, we developed a probability-based power estimation algorithm, by specifically solving the problem of identifying a desirable intermediate support-set. We proposed an exact polynomial time algorithm and also developed a heuristic solution for solving the above problem. Our heuristic solution is canonical and of constant complexity, a very desirable quality for a power metric guiding synthesis tool. Finally, we present a technology mapping algorithm which minimizing power consumption under strict timing constraint derived from industrial delay models. We introduced a novel concept of a delay-cost curve to store only important design trade-offs on the delay versus cost spectrum at each node of the circuit. We prove that our approach requires exponentially lesser storage compared to previous approaches and that it has bounded error. We report experimental results on each of our algorithm on a variety of combinational and sequential benchmark circuits.","abstract_html":"In the first part of the work, we propose an algorithm to decompose a given finite state machine (FSM) into smaller interacting FSMs such that by themselves they have plenty of self-loops, although the original FSM may not have any self-loops. We power down these decomposed FSM during the transitions corresponding to the self-loops to save power consumption. Second, we extend the above work to resynthesize sequential machines. We propose a symbolic simulation-based algorithm to extract the self-loops of the underlying FSM. We partition the sequential machine and apply the above clockgating technique. Third, we propose a synthesis methodology that uses algebraic techniques like kernel extraction, cube extraction, and collapsing to minimize power consumption of a logic function. A unique power cost function based on a fast mapping of a Boolean expression to a generic library is used to steer the above algebraic transformations to reduce its power consumption. Fourth, in order to guide the proposed synthesis tool, we developed a probability-based power estimation algorithm, by specifically solving the problem of identifying a desirable intermediate support-set. We proposed an exact polynomial time algorithm and also developed a heuristic solution for solving the above problem. Our heuristic solution is canonical and of constant complexity, a very desirable quality for a power metric guiding synthesis tool. Finally, we present a technology mapping algorithm which minimizing power consumption under strict timing constraint derived from industrial delay models. We introduced a novel concept of a delay-cost curve to store only important design trade-offs on the delay versus cost spectrum at each node of the circuit. We prove that our approach requires exponentially lesser storage compared to previous approaches and that it has bounded error. We report experimental results on each of our algorithm on a variety of combinational and sequential benchmark circuits.","abstract_has_math":false,"creators":["Roy, Sumit"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:10:21Z","date_published":"2015-09-25T20:10:21Z","updated_at":"2026-07-22T22:26:15Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI9912360"],"render_values":[{"text":"(MiAaPQ)AAI9912360","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81274","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Banerjee, Prithviraj"]},{"key":"dc:creator","label":"Author","values":["Roy, Sumit"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:10:21Z","10000-01-01","1998"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81274","(MiAaPQ)AAI9912360"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In the first part of the work, we propose an algorithm to decompose a given finite state machine (FSM) into smaller interacting FSMs such that by themselves they have plenty of self-loops, although the original FSM may not have any self-loops. We power down these decomposed FSM during the transitions corresponding to the self-loops to save power consumption. Second, we extend the above work to resynthesize sequential machines. We propose a symbolic simulation-based algorithm to extract the self-loops of the underlying FSM. We partition the sequential machine and apply the above clockgating technique. Third, we propose a synthesis methodology that uses algebraic techniques like kernel extraction, cube extraction, and collapsing to minimize power consumption of a logic function. A unique power cost function based on a fast mapping of a Boolean expression to a generic library is used to steer the above algebraic transformations to reduce its power consumption. Fourth, in order to guide the proposed synthesis tool, we developed a probability-based power estimation algorithm, by specifically solving the problem of identifying a desirable intermediate support-set. We proposed an exact polynomial time algorithm and also developed a heuristic solution for solving the above problem. Our heuristic solution is canonical and of constant complexity, a very desirable quality for a power metric guiding synthesis tool. Finally, we present a technology mapping algorithm which minimizing power consumption under strict timing constraint derived from industrial delay models. We introduced a novel concept of a delay-cost curve to store only important design trade-offs on the delay versus cost spectrum at each node of the circuit. We prove that our approach requires exponentially lesser storage compared to previous approaches and that it has bounded error. We report experimental results on each of our algorithm on a variety of combinational and sequential benchmark circuits.","Made available in DSpace on 2015-09-25T20:10:21Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9912360.pdf: 6783847 bytes, checksum: 6d0adc365b3d1ceae584f9a0198686e0 (MD5) Previous issue date: 1998","Embargo set by: Seth Robbins for item 82555 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","135 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998."]},{"key":"dc:title","label":"Title","values":["Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Roy, Sumit"],"dc:date":["2015-09-25T20:10:21Z","10000-01-01","1998"],"dc:description":["In the first part of the work, we propose an algorithm to decompose a given finite state machine (FSM) into smaller interacting FSMs such that by themselves they have plenty of self-loops, although the original FSM may not have any self-loops. We power down these decomposed FSM during the transitions corresponding to the self-loops to save power consumption. Second, we extend the above work to resynthesize sequential machines. We propose a symbolic simulation-based algorithm to extract the self-loops of the underlying FSM. We partition the sequential machine and apply the above clockgating technique. Third, we propose a synthesis methodology that uses algebraic techniques like kernel extraction, cube extraction, and collapsing to minimize power consumption of a logic function. A unique power cost function based on a fast mapping of a Boolean expression to a generic library is used to steer the above algebraic transformations to reduce its power consumption. Fourth, in order to guide the proposed synthesis tool, we developed a probability-based power estimation algorithm, by specifically solving the problem of identifying a desirable intermediate support-set. We proposed an exact polynomial time algorithm and also developed a heuristic solution for solving the above problem. Our heuristic solution is canonical and of constant complexity, a very desirable quality for a power metric guiding synthesis tool. Finally, we present a technology mapping algorithm which minimizing power consumption under strict timing constraint derived from industrial delay models. We introduced a novel concept of a delay-cost curve to store only important design trade-offs on the delay versus cost spectrum at each node of the circuit. We prove that our approach requires exponentially lesser storage compared to previous approaches and that it has bounded error. We report experimental results on each of our algorithm on a variety of combinational and sequential benchmark circuits.","Made available in DSpace on 2015-09-25T20:10:21Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9912360.pdf: 6783847 bytes, checksum: 6d0adc365b3d1ceae584f9a0198686e0 (MD5) Previous issue date: 1998","Embargo set by: Seth Robbins for item 82555 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","135 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998."],"dc:identifier":["http://hdl.handle.net/2142/81274","(MiAaPQ)AAI9912360"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:15Z"}