Files in this item



application/pdf9411817.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Modulo Scheduling with isomorphic control transformations
Author(s):Warter, Nancy Jeanne
Doctoral Committee Chair(s):Hwu, Wen-Mei W.
Department / Program:Electrical and Computer Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
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.
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.
Issue Date:1993
Rights Information:Copyright 1993 Warter, Nancy Jeanne
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9411817
OCLC Identifier:(UMI)AAI9411817

This item appears in the following Collection(s)

Item Statistics