Single-mode, Single-processor Giotto Scheduling

Benjamin Horowitz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1238
April 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1238.pdf

This report presents a new algorithm for scheduling single-mode Giotto programs for a single processor. We extend the classical scheduling problem 1 | rj; dj; prec; pmtn | - to an infinite, periodic variant. We present a polynomial time algorithm for this variant that finds a feasible schedule whenever one exists. We show how to embed the problem of scheduling a class of single-mode Giotto programs for a single processor into our more general problem. The embedding yields a pseudopolynomial-time algorithm that allows more programs to be scheduled than previous techniques. Finally, we present a technique to aggregate distinct activities into the same thread, and we show how to execute Giotto programs using a single stack.


BibTeX citation:

@techreport{Horowitz:CSD-03-1238,
    Author = {Horowitz, Benjamin},
    Title = {Single-mode, Single-processor Giotto Scheduling},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5329.html},
    Number = {UCB/CSD-03-1238},
    Abstract = {This report presents a new algorithm for scheduling single-mode Giotto programs for a single processor. We extend the classical scheduling problem 1 | rj; dj; prec; pmtn | - to an infinite, periodic variant. We present a polynomial time algorithm for this variant that finds a feasible schedule whenever one exists. We show how to embed the problem of scheduling a class of single-mode Giotto programs for a single processor into our more general problem. The embedding yields a pseudopolynomial-time algorithm that allows more programs to be scheduled than previous techniques. Finally, we present a technique to aggregate distinct activities into the same thread, and we show how to execute Giotto programs using a single stack.}
}

EndNote citation:

%0 Report
%A Horowitz, Benjamin
%T Single-mode, Single-processor Giotto Scheduling
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1238
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5329.html
%F Horowitz:CSD-03-1238