Concurrency, Synchronization, and Speculation-The Dataflow Way

Krishna Kavi*; Charles Shelor*; Domenico Pace┼    * Department of Computer Science and Engineering, University of North Texas Denton, Texas, USA
┼ Information Technology and Services Accenture, Turin, Italy

Abstract

This chapter provides a brief overview of dataflow, including concepts, languages, historical architectures, and recent architectures. It is to serve as an introduction to and summary of the development of the dataflow paradigm during the past 45 years. Dataflow has inherent advantages in concurrency, synchronization, and speculation over control flow or imperative implementations. However, dataflow has its own set of challenges to efficient implementations. This chapter addresses the advantages and challenges of dataflow to set a context for the remainder of this issue.

Keywords

Dataflow

Architecture

Survey

Abbreviations

ABI address buffer identifier

AQ acknowledgment queue of D2NOW

CU computing unit in Codelet

D2NOW data-driven network of workstations

DDM data-driven multithreading model

DFE dataflow engine in Maxeler

D-TSU distributed thread scheduling unit in Teraflux

DU data cache unit in TRIPS

EDGE explicit data graph execution in TRIPS

EP execution pipeline of SDF

EPN epoch number of SDF

ETS explicit token store

EU execution unit in TRIPS

EXC execution continuation of SDF

FP frame pointer

GM graph memory of D2NOW

GU global control unit in TRIPS

IP instruction pointer

IU instruction cache unit in TRIPS

L-TSU local thread scheduling unit in Teraflux

NIU network interface unit of D2NOW

PE processing element of WaveScalar

PLC preload continuation of SDF

PSC poststore continuation of SDF

RIP retry instruction pointer of SDF

RQ ready queue of D2NOW

RS register set identifier

RU register unit in TRIPS

SC synchronization count in SDF

SDF scheduled dataflow

SISAL streams and Iteration in a Single Assignment Language

SM synchronization memory of D2NOW

SP synchronization pipeline of SDF

SU scheduling unit in Codelet

SU scheduling unit of SDF

TLS thread-level speculation

TP threaded procedure in Codelet

TRIPS Tera-op Reliable Intelligently adaptive Processing System

TSU thread synchronization unit of D2NOW

VAL value-based programming language

WTC waiting continuation of SDF

1 Introduction

Achieving high performance is possible when multiple activities (or multiple instructions) can be executed concurrently. The concurrency must not incur large overheads if it is to be effective. A second issue that must be addressed while executing concurrent activities is synchronization and/or coordination of the activities. These actions often lead to sequentialization of parallel activities, thus defeating the potential performance gains of concurrent execution. Thus, effective use of synchronization and coordination are essential to achieving high performance. One way to achieve this goal is through speculative execution, whereby it is speculated that concurrent activities do not need synchronization or coordination or predict the nature of the coordination. Successful speculation will reduce sequential portions of parallel programs; but misprediction may add to execution times and power consumption since the speculatively executed activities must be undone and the activity must be restarted with correct synchronization.

The dataflow model of computation presents a natural choice for achieving concurrency, synchronization, and speculations. In the basic form, activities in a dataflow model are enabled when they receive all the necessary inputs; no other triggers are needed. Thus, all enabled activities can be executed concurrently if functional units are available. And the only synchronization among computations is the flow of data. In a broader sense, coordination or predicate results can be viewed as data that enable or coordinate dataflow activities. The functional nature of dataflow (eliminating side effects that plague imperative programming models) makes it easier to use speculation or greedy execution; unnecessary or unwanted computations can be simply discarded without any need for complex recovery on mis-speculations.

In this chapter, we introduce well-understood dataflow models of computation in Section 2. We review programming languages that adhere to dataflow principles in Section 3. We present historical attempts at developing architectures implementing the dataflow models along with a discussion of the limitations of dataflow encountered by these architectures in Section 4. We present some recent variations of the dataflow paradigm that could potentially lead to efficient architectures in Section 5. As a case study in Section 6, we provide how one such architecture, scheduled dataflow (SDF), implements concurrency, synchronization, and speculation. Finally, we include our conclusions and prognosis on the future of the model as a viable alternative to control-flow systems in Section 7.

2 Dataflow Concepts

2.1 Dataflow Formalism

The dataflow model of computation is based on the use of graphs to represent computations and flow of information among the computations. The signal processing community uses a visual dataflow model to specify computations. Some examples of environments used by this community include Signal [1, 2], Lustre [3], and Ptolemy [4]. In this chapter, our focus is on general-purpose programming and general-purpose computer architectures. Hence, we will not review programming models, languages, or environments for specific or restricted domains; however, Lee [5] provides a good survey on such languages and models.

One of the earliest dataflow models is called Kahn [6] process networks. A program in this model consists of channels, processes, and links connecting these processes. Figure 1 shows an example program and the corresponding graphical representation of the process network. In principle, channels can be viewed as arrays or lists (sequence of values). It is also possible to associate firing semantics with a process to define necessary input sequences and nondeterminism. We again refer the reader to the survey by Lee [5]. A process takes the required sequences of inputs from its input channels and creates sequences on output channels. To facilitate continuous execution and concurrency, one can view the sequences of data on channels as partially ordered. A set of inputs may contain multiple, partially ordered inputs, where the lack of ordering among subsequences allows for concurrency.

There have been several formalisms that have extended Kahn process networks. We use specific notations to describe a process network, which resemble the most common view of dataflow graphs to graphically represent computations. We use the notations from Ref. [7] in the rest of this section.

A dataflow graph is a directed graph in which the elements are called links and actors [8]. In this model, actors (nodes) describe operations, while links receive data from a single actor and transmit values to one or more actors by way of arcs; arcs can be considered as channels of communication, while links can be viewed as placeholders or buffers

=<A?L,E>,

where A = {a1, a2, ., an} is the set of actors; L = {l1, l2, ., lm} is the set of links and ?(AXL)?(LxA) is the set of edges connecting links and actors.

In its basic form, activities (or nodes) are enabled for execution when all input arcs contain tokens and no output arcs contain tokens. However, if we consider arcs as (potentially...