Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Two Fundamental Limits on Dataflow Multiprocessing

David E. Culler, Klaus Erik Schauser and Thorsten von Eicken

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-716
December 1992

http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-716.pdf

This paper examines the argument for dataflow architectures in "Two Fundamental Issues in Multiprocessing." We observe two key problems. First, the justification of extensive multithreading is based on an overly simplistic view of the storage hierarchy. Second the local greedy scheduling policy embodied in dataflow is inadequate in many circumstances. A more realistic model of the storage hierarchy imposes significant constraints on the scheduling of computation and requires a degree of parsimony in the scheduling policy. In particular, it is important to establish a scheduling hierarchy that reflects the underlying storage hierarchy. However, even with this improvement, simple local scheduling policies are unlikely to be adequate.

Keywords: dataflow, multiprocessing, multithreading, latency tolerance, storage hierarchy, scheduling hierarchy


BibTeX citation:

@techreport{Culler:CSD-92-716,
    Author = {Culler, David E. and Schauser, Klaus Erik and von Eicken, Thorsten},
    Title = {Two Fundamental Limits on Dataflow Multiprocessing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6259.html},
    Number = {UCB/CSD-92-716},
    Abstract = {This paper examines the argument for dataflow architectures in "Two Fundamental Issues in Multiprocessing." We observe two key problems. First, the justification of extensive multithreading is based on an overly simplistic view of the storage hierarchy. Second the local greedy scheduling policy embodied in dataflow is inadequate in many circumstances. A more realistic model of the storage hierarchy imposes significant constraints on the scheduling of computation and requires a degree of parsimony in the scheduling policy. In particular, it is important to establish a scheduling hierarchy that reflects the underlying storage hierarchy. However, even with this improvement, simple local scheduling policies are unlikely to be adequate.  <p>Keywords: dataflow, multiprocessing, multithreading, latency tolerance, storage hierarchy, scheduling hierarchy}
}

EndNote citation:

%0 Report
%A Culler, David E.
%A Schauser, Klaus Erik
%A von Eicken, Thorsten
%T Two Fundamental Limits on Dataflow Multiprocessing
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-716
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6259.html
%F Culler:CSD-92-716