Donald Bren School of Information and Computer Sciences

Our goal is to devise a computer comprising large numbers of cooperating processors (LSI). In doing so we reject the sequential and memory cell semantics of the von Neumann model, and instead adopt the asynchronous and functional semantics of dataflow. We describe a dataflow base machine language and unfolding interpreter that generates large numbers of asynchronous tasks for execution. Also presented is the high-level dataflow programming language Id, as well as an initial design for a dataflow machine and the results of detailed, deterministic simulation experiments on a part of that machine. For example, we show that a dataflow machine can automatically unfold the nested loops of n-by-n matrix multiply to reduce its time complexity from O(n^3) to O(n) so long as sufficient processors and communication capacity is available. Similarly, quicksort executes with average O(n) time demanding O(n) processors. Also discussed are the use of processor and communication time complexity analysis, and "flow analysis", as aids in understanding the behavior of the machine.