Single-mode, Single-processor Giotto Scheduling

Benjamin Horowitz

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1238

2003

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/Archive/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},
    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