{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22732"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22732","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel algorithms for logic synthesis","abstract":"U of I Only","abstract_html":"U of I Only","abstract_has_math":false,"creators":["De, Kaushik"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:49:38Z","date_published":"2011-05-07T13:49:38Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1993 De, Kaushik"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411602","(UMI)AAI9411602"],"render_values":[{"text":"AAI9411602","href":null,"code":true},{"text":"(UMI)AAI9411602","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22732","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":["De, Kaushik"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:49:38Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer 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":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1993 De, Kaushik"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411602","(UMI)AAI9411602","http://hdl.handle.net/2142/22732"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["U of I Only","The size of the VLSI circuit is increasing at a very rapid pace, and soon the sequential algorithms running on a uniprocessor will be inadequate to handle such large circuits. Parallel processing can be used to reduce the computation time considerably with almost no degradation in the quality. Most of the parallel algorithms developed for VLSI CAD applications, however, are designed for one specific parallel architecture. As a result, considerable effort and expense are needed to port them to different parallel machines. The ongoing ProperCAD project at the University of Illinois offers a bright solution to that problem by allowing the user to develop parallel algorithms on the top of a portable framework such that the programs developed will run unchanged on a variety of parallel machines, both shared and distributed memory machines. In this thesis, parallel algorithms for combinational logic synthesis using two approaches are developed: (1) the Transduction method, which uses the concept of a set of permissible functions to perform various logic transformations to reduce the size of logic circuit, and (2) the MIS approach, which uses algebraic factoring and node simplification for the purpose of logic minimization. The parallel algorithms developed in this thesis offer three major contributions. First, the parallel algorithms use an asynchronous, message-driven computing model with no synchronizing barriers separating phases of parallel computation. Second, these algorithms are portable across a wide variety of parallel architectures, shared memory machines such as Encore Multimax and Sequent Symmetry, distributed memory machines such as Intel/860, and networks of workstations. Finally, these algorithms are built around well defined sequential algorithm interfaces, so that the parallel algorithms can benefit from the future improvements and expansions of the sequential algorithms. Very large circuits, however, can not he handled as a whole by any synthesis algorithm. Those circuits are partitioned, and then the partitions are synthesized independently in parallel. A parallel synthesis system based on the partitioning approach is also described in this thesis.","Made available in DSpace on 2011-05-07T13:49:38Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411602.pdf: 6355450 bytes, checksum: 3bb06b7f99bf9f4fe90ebb884be0854c (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:37Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:28:09-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission"]},{"key":"dc:title","label":"Title","values":["Parallel algorithms for logic synthesis"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["De, Kaushik"],"dc:date":["2011-05-07T13:49:38Z","10000-01-01","1993"],"dc:description":["U of I Only","The size of the VLSI circuit is increasing at a very rapid pace, and soon the sequential algorithms running on a uniprocessor will be inadequate to handle such large circuits. Parallel processing can be used to reduce the computation time considerably with almost no degradation in the quality. Most of the parallel algorithms developed for VLSI CAD applications, however, are designed for one specific parallel architecture. As a result, considerable effort and expense are needed to port them to different parallel machines. The ongoing ProperCAD project at the University of Illinois offers a bright solution to that problem by allowing the user to develop parallel algorithms on the top of a portable framework such that the programs developed will run unchanged on a variety of parallel machines, both shared and distributed memory machines. In this thesis, parallel algorithms for combinational logic synthesis using two approaches are developed: (1) the Transduction method, which uses the concept of a set of permissible functions to perform various logic transformations to reduce the size of logic circuit, and (2) the MIS approach, which uses algebraic factoring and node simplification for the purpose of logic minimization. The parallel algorithms developed in this thesis offer three major contributions. First, the parallel algorithms use an asynchronous, message-driven computing model with no synchronizing barriers separating phases of parallel computation. Second, these algorithms are portable across a wide variety of parallel architectures, shared memory machines such as Encore Multimax and Sequent Symmetry, distributed memory machines such as Intel/860, and networks of workstations. Finally, these algorithms are built around well defined sequential algorithm interfaces, so that the parallel algorithms can benefit from the future improvements and expansions of the sequential algorithms. Very large circuits, however, can not he handled as a whole by any synthesis algorithm. Those circuits are partitioned, and then the partitions are synthesized independently in parallel. A parallel synthesis system based on the partitioning approach is also described in this thesis.","Made available in DSpace on 2011-05-07T13:49:38Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411602.pdf: 6355450 bytes, checksum: 3bb06b7f99bf9f4fe90ebb884be0854c (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:37Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:28:09-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission"],"dc:identifier":["AAI9411602","(UMI)AAI9411602","http://hdl.handle.net/2142/22732"],"dc:language":["eng"],"dc:rights":["Copyright 1993 De, Kaushik"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Parallel algorithms for logic synthesis"],"dc:type":["text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}