{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20390"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20390","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Modulo Scheduling with isomorphic control transformations","abstract":"This dissertation addresses the complexities involved with scheduling in the presence of conditional branches. This is a particularly important problem for processors that execute multiple operations per cycle and are not fully utilized by local scheduling techniques. Since conditional branches introduce multiple execution paths, it is difficult for a global scheduler to keep track of the various paths and to select the appropriate operations to schedule. A new approach to global instruction scheduling is presented that uses Isomorphic Control Transformations (ICTs). If-conversion is used to convert an acyclic control flow graph into a large basic block or hyper-block. Local scheduling techniques which are well-known and widely supported can then be applied to schedule operations. After scheduling, the control flow graph is regenerated using Reverse If-Conversion.","abstract_html":"This dissertation addresses the complexities involved with scheduling in the presence of conditional branches. This is a particularly important problem for processors that execute multiple operations per cycle and are not fully utilized by local scheduling techniques. Since conditional branches introduce multiple execution paths, it is difficult for a global scheduler to keep track of the various paths and to select the appropriate operations to schedule. A new approach to global instruction scheduling is presented that uses Isomorphic Control Transformations (ICTs). If-conversion is used to convert an acyclic control flow graph into a large basic block or hyper-block. Local scheduling techniques which are well-known and widely supported can then be applied to schedule operations. After scheduling, the control flow graph is regenerated using Reverse If-Conversion.","abstract_has_math":false,"creators":["Warter, Nancy Jeanne"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Hwu, Wen-Mei W."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:37:50Z","date_published":"2011-05-07T12:37:50Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1993 Warter, Nancy Jeanne"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411817","(UMI)AAI9411817"],"render_values":[{"text":"AAI9411817","href":null,"code":true},{"text":"(UMI)AAI9411817","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20390","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hwu, Wen-Mei W."]},{"key":"dc:creator","label":"Author","values":["Warter, Nancy Jeanne"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:37:50Z","10000-01-01","1993"]},{"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":["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 Warter, Nancy Jeanne"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411817","(UMI)AAI9411817","http://hdl.handle.net/2142/20390"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This dissertation addresses the complexities involved with scheduling in the presence of conditional branches. This is a particularly important problem for processors that execute multiple operations per cycle and are not fully utilized by local scheduling techniques. Since conditional branches introduce multiple execution paths, it is difficult for a global scheduler to keep track of the various paths and to select the appropriate operations to schedule. A new approach to global instruction scheduling is presented that uses Isomorphic Control Transformations (ICTs). If-conversion is used to convert an acyclic control flow graph into a large basic block or hyper-block. Local scheduling techniques which are well-known and widely supported can then be applied to schedule operations. After scheduling, the control flow graph is regenerated using Reverse If-Conversion.","One well-known local scheduling based technique is Modulo Scheduling. Modulo Scheduling is a software pipelining technique that effectively schedules loops for high-performance processors. This dissertation highlights the benefits of Modulo Scheduling over other software pipelining techniques based on global scheduling. The ICTs are applied to Modulo Scheduling to schedule loops with conditional branches. Experimental results show that this approach allows more flexible scheduling and thus better performance than Modulo Scheduling with Hierarchical Reduction. Modulo Scheduling with ICTs targets processors with no or limited support for conditional execution such as superscalar processors. However, in processors that do not require instruction set compatibility, support for Predicated Execution can be used. This dissertation shows that Modulo Scheduling with Predicated Execution has better performance and lower code expansion than Modulo Scheduling with ICTs on processors without special hardware support.","Made available in DSpace on 2011-05-07T12:37:50Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411817.pdf: 5897497 bytes, checksum: f45566b339b981797d17f81063cbc49f (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:43:34Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:04-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":["Modulo Scheduling with isomorphic control transformations"]}]}],"canonical_facts":{"dc:contributor":["Hwu, Wen-Mei W."],"dc:creator":["Warter, Nancy Jeanne"],"dc:date":["2011-05-07T12:37:50Z","10000-01-01","1993"],"dc:description":["This dissertation addresses the complexities involved with scheduling in the presence of conditional branches. This is a particularly important problem for processors that execute multiple operations per cycle and are not fully utilized by local scheduling techniques. Since conditional branches introduce multiple execution paths, it is difficult for a global scheduler to keep track of the various paths and to select the appropriate operations to schedule. A new approach to global instruction scheduling is presented that uses Isomorphic Control Transformations (ICTs). If-conversion is used to convert an acyclic control flow graph into a large basic block or hyper-block. Local scheduling techniques which are well-known and widely supported can then be applied to schedule operations. After scheduling, the control flow graph is regenerated using Reverse If-Conversion.","One well-known local scheduling based technique is Modulo Scheduling. Modulo Scheduling is a software pipelining technique that effectively schedules loops for high-performance processors. This dissertation highlights the benefits of Modulo Scheduling over other software pipelining techniques based on global scheduling. The ICTs are applied to Modulo Scheduling to schedule loops with conditional branches. Experimental results show that this approach allows more flexible scheduling and thus better performance than Modulo Scheduling with Hierarchical Reduction. Modulo Scheduling with ICTs targets processors with no or limited support for conditional execution such as superscalar processors. However, in processors that do not require instruction set compatibility, support for Predicated Execution can be used. This dissertation shows that Modulo Scheduling with Predicated Execution has better performance and lower code expansion than Modulo Scheduling with ICTs on processors without special hardware support.","Made available in DSpace on 2011-05-07T12:37:50Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411817.pdf: 5897497 bytes, checksum: f45566b339b981797d17f81063cbc49f (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:43:34Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:04-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":["AAI9411817","(UMI)AAI9411817","http://hdl.handle.net/2142/20390"],"dc:language":["eng"],"dc:rights":["Copyright 1993 Warter, Nancy Jeanne"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Modulo Scheduling with isomorphic control transformations"],"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:25:15Z"}