{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23634"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23634","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization by simulated evolution and its application to cell placement","abstract":"We introduce the new optimization method of Simulated Evolution (SE), which is designed to find near optimal solutions to problems which are hard to solve by standard methods. The new algorithm is discussed in detail and a variety of measurements are taken to evaluate its performance under various conditions. In addition, a theoretical framework is introduced to formally describe the algorithm. A Markov analysis is performed using this mathematical model to analyze convergence properties.","abstract_html":"We introduce the new optimization method of Simulated Evolution (SE), which is designed to find near optimal solutions to problems which are hard to solve by standard methods. The new algorithm is discussed in detail and a variety of measurements are taken to evaluate its performance under various conditions. In addition, a theoretical framework is introduced to formally describe the algorithm. A Markov analysis is performed using this mathematical model to analyze convergence properties.","abstract_has_math":false,"creators":["Kling, Ralph Michael"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Engineering, Electronics and Electrical","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:21:23Z","date_published":"2011-05-07T14:21:23Z","updated_at":"2026-07-22T22:25:22Z","subjects":["Engineering, Electronics and Electrical"],"languages":["eng"],"rights":["Copyright 1990 Kling, Ralph Michael"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114300","(UMI)AAI9114300"],"render_values":[{"text":"AAI9114300","href":null,"code":true},{"text":"(UMI)AAI9114300","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23634","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":["Kling, Ralph Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:21:23Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering, Electronics and Electrical"]},{"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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1990 Kling, Ralph Michael"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114300","(UMI)AAI9114300","http://hdl.handle.net/2142/23634"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We introduce the new optimization method of Simulated Evolution (SE), which is designed to find near optimal solutions to problems which are hard to solve by standard methods. The new algorithm is discussed in detail and a variety of measurements are taken to evaluate its performance under various conditions. In addition, a theoretical framework is introduced to formally describe the algorithm. A Markov analysis is performed using this mathematical model to analyze convergence properties.","The Standard Cell placement problem in the VLSI design area was chosen as a representative problem for applying SE techniques. A new hierarchical placement technique using windowing methods is introduced. A complete placement program has been developed and thoroughly tested on a variety of industrial benchmark circuits. A comparative performance analysis with the most successful Simulated Annealing-based placement program is presented.","The SE algorithm has been implemented on several different sequential and parallel computing platforms. An evaluation of the achievable parallelism has been performed in each case. Furthermore, a special purpose coprocessor which speeds up wire length calculations as needed by placement programs has been designed, fabricated and tested.","Made available in DSpace on 2011-05-07T14:21:23Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114300.pdf: 5210862 bytes, checksum: b09177b5eab5227dbab34f1b770e3d71 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:05:48Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:33-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","U of I Only"]},{"key":"dc:title","label":"Title","values":["Optimization by simulated evolution and its application to cell placement"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Kling, Ralph Michael"],"dc:date":["2011-05-07T14:21:23Z","10000-01-01","1990"],"dc:description":["We introduce the new optimization method of Simulated Evolution (SE), which is designed to find near optimal solutions to problems which are hard to solve by standard methods. The new algorithm is discussed in detail and a variety of measurements are taken to evaluate its performance under various conditions. In addition, a theoretical framework is introduced to formally describe the algorithm. A Markov analysis is performed using this mathematical model to analyze convergence properties.","The Standard Cell placement problem in the VLSI design area was chosen as a representative problem for applying SE techniques. A new hierarchical placement technique using windowing methods is introduced. A complete placement program has been developed and thoroughly tested on a variety of industrial benchmark circuits. A comparative performance analysis with the most successful Simulated Annealing-based placement program is presented.","The SE algorithm has been implemented on several different sequential and parallel computing platforms. An evaluation of the achievable parallelism has been performed in each case. Furthermore, a special purpose coprocessor which speeds up wire length calculations as needed by placement programs has been designed, fabricated and tested.","Made available in DSpace on 2011-05-07T14:21:23Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114300.pdf: 5210862 bytes, checksum: b09177b5eab5227dbab34f1b770e3d71 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:05:48Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:33-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","U of I Only"],"dc:identifier":["AAI9114300","(UMI)AAI9114300","http://hdl.handle.net/2142/23634"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Kling, Ralph Michael"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Optimization by simulated evolution and its application to cell placement"],"dc:type":["text"],"thesis:degree_discipline":["Engineering, Electronics and Electrical"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:22Z"}