Benjamin Horowitz

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1238

, 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},
    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