Theory and practice

 [ MIT ]

Arvind Mithal—almost always referred to as Arvind—is now the head of the faculty of computer science at a Boston trade school. The school, also known as MIT, is of course one of the top places for all things computer science. From education to service to startups to research, MIT is perhaps the best in the world.

Today I thought we might discuss one of Arvind’s main research themes.

Although this work started in the 1980’s I believe that it underscores an important point. This insight might apply to current research topics like quantum computers.

But first I cannot resist saying something personal about him. Arvind is a long time friend of mine, and someone who gets the stuck in elevator measure of many hours. This measure is one I made up, but I hope you get the idea.

Arvind is the only name I have ever known for Arvind. I was a bit surprised to see that the Wikipedia reference for him states his “full” name. He told me that he found having one name—not two—was a challenge. For example, he sometimes had to explain when arriving at a check-in desk at a conference that he only had one name. His name tag often became:

because the conference software could not handle people with one name.

## Dataflow—The prehistory

About forty years ago one of the major open problem in CS was how to make computers go faster. It is still an issue, but in the 1980’s this problem was one of all-hands-on-deck. It was worked on by software engineers, by electrical engineers, by researchers of all kinds including complexity theorists. Conferences like FOCS and STOC—hardcore theory conferences—often contained papers on how to speed up computations.

Two examples come to mind:

${\bullet }$ The idea of systolic arrays led by Hsiang-Tsung Kung then at CMU. Also his students, especially Charles Leiserson, made important contributions.

${\bullet }$ The idea of the Ultracomputer led by Jacob Schwartz at NYU. An ultracomputer has N processors, N memories and an N log N message-passing switch connecting them. Note, the use of “N” so you can tell that it came from a theorist.

Arvind tried to make computers faster by inventing a new type of computer architecture. Computers then were based on the classic von Neumann architecture or control flow architecture. He and his colleagues worked for many years trying to replace this architecture by dataflow.

A bottleneck in von Neumann style machines is caused by the program counter fetch cycle. Each cycle the program counter decides which instruction to get, and thus which data to get. These use the same hardware channel, which causes the famous von Neumann bottleneck. We have modified Wikipedia’s graphic to make the bottleneck aspect clearer:

## Dataflow—The promise

Arvind is usually identified with the invention of dataflow computer architecture. The key idea of this architecture is to avoid the above bottleneck by eliminating the program counter. If there are no instructions to fetch, then it would seem that we can beat the bottleneck. Great idea.

Dataflow architectures do not have a program counter, and so data is king. Roughly data objects move around in such a machine, and they eventually appear at computational units. Roughly these machines operate, at a high level, like a directed graph from complexity theory. Data moves along edges to nodes that compute values. Moreover, nodes compute as soon as all the input data is present. After the node computes the value, the new data is sent to the next node; and so on.

The hope was that this would yield a way to increase the performance of computers. No program counter, no instruction fetching, could make dataflow machines faster.

## Dataflow—The actual

The dataflow idea is clever. The difficulty is while dataflow can work, classic von Neumann machines have been augmented in various ways. The competition rarely stays put. These updates did not eliminate the von Neumann bottleneck, but they reduce the cost of it, and let von Neumann machines continue to get faster. Caches are one example of how they avoid the bottleneck, thus making the dataflow machines less attractive. Thus, a cache for program instructions makes it likely that the program fetch step does not actually happen. This is an attack on the main advantage of dataflow machines.

The paper by David Culler, Klaus Schauser, and Thorsten von Eicken titled Two Fundamental Limits on Dataflow Multiprocessing? discusses these issues in detail. They start by saying:

The advantages of dataflow architectures were argued persuasively in a seminal 1983 paper by Arvind and Iannucci and in a 1987 revision entitled “Two Fundamental Issues in Multiprocessing”. However, reality has proved less favorable to this approach than their arguments would suggest. This motivates us to examine the line of reasoning that has driven dataflow architectures and fine-grain multithreading to understand where the argument went awry.

## Dataflow—Lessons

What are the lessons? Is there one?

I claim there are lessons. The work of Arvind on dataflow was and is important. It did not lead to the demise of von Neumann machines. I am using one right now to write this.

Dataflow did lead to insights on programming that have many applications. The dataflow idea may yet impact special computational situations: there is interest in using them for data intensive applications.

Ken adds that dataflow has been realized in other ways. Caches and pipes and subsequent architecture innovations profit from designs that enhance locality. The MapReduce programming model gives a general framework that fits this well. The paradigm of streaming is even a better fit. Note that Wikipedia says both that it is “equivalent to dataflow programming” and “was explored within dataflow programming”—so perhaps the parent lost out to the wider adaptability of her children.

I think there are lessons: Practical goals like making hardware go faster, are complex and many faceted. A pure theory approach such as systolic arrays or ultra computers or dataflow machines is unlikely to suffice. Also the existing technology like von Neumann machines will continue to evolve.

A question is: Could quantum computers be subject to the same lesson? Will non-quantum machines continue to evolve in a way to make the quantum advantage less than we think? Or is this type of new architecture different? Could non-quantum machines incorporate tricks from quantum and ${\dots}$

## Open Problems

Speaking about theory and practice: Noga Alon, Phillip Gibbons, Yossi Matias, and Mario Szegedy are the winners of the 2019 ACM Paris Kanellakis Theory and Practice Award.

We applaud them on receiving this award. Sadly the Paris award reminds us that Paris Kanellakis died in the terrible plane crash of American Airlines Flight 965 on December 20, 1995. Also on that flight were his wife, Maria Otoya, and their two children, Alexandra and Stephanos.

The citation for the award says:

They pioneered a framework for algorithmic treatment of streaming massive datasets, and today their sketching and streaming algorithms remain the core approach for streaming big data and constitute an entire subarea of the field of algorithms.

In short they invented streaming.

1. May 29, 2020 9:31 pm

Can you do what theory can say about computer vision and cognition?

May 29, 2020 11:52 pm

Hi Dick

When I think of the origins of “Dataflow” I think of Bert Sutherland’s 1965 MIT thesis, which predated “pretty much everything else”. What do you think?

Cheers

Alan