Overview of EECS 290N (Edward A. Lee)

EECS 290N, Section 002
Concurrent Models of Computation
Edward A. Lee
Fridays, 9-12AM, 540AB Cory

This course will study models of computation (MoCs) that emphasize composition of software components that execute concurrently. Applications include building programs with controlled timing, for example embedded software systems, and programs that exploit parallel or distributed hardware such as multicore machines. We study established concurrent MoCs, including threads, message passing, and distributed object-oriented technologies, but the focus will be on actor models. These include process networks (PN), dataflow (SDF, DDF, BDF), synchronous/reactive (SR) models, and timed models of computation, including discrete-event (DE) systems and time-triggered models. We will also cover continuous-time (CT) models of computation, including a light discussion of simulation techniques. Finally, we will discuss heterogeneous models, including the combination of CT models with models of software and networks to model cyber-physical systems (CPS), hybrid systems (which combine CT models with state machines), and Statecharts (which combine SR with state machines).

For all models of computation, we will consider questions of semantics and efficient implementation. Techniques will be developed to understand determinacy, to analyze behaviors of programs, to ensure bounded memory usage, to study termination properties such as deadlock, and to exploit parallel hardware. We will study ongoing research questions, including efficient mechanisms for sharing data structures across actors in an actor model, verifying schedulability of distributed real-time systems, joint modeling of computation, networking, and physical dynamics, and model-engineering techniques for building and managing large, complex, concurrent programs.

The course will combine an experimental approach with a study of semantics. The objective will be to develop a deep understanding of the wealth of alternative approaches to managing concurrency and time in software. The experimental portion of the course will use Ptolemy II as the software laboratory, and students will be guided to create simple extensions in Java and models of systems using Ptolemy II. A term project will be required.

The semantics portion of the course will build on the mathematics of partially ordered sets, particularly as applied to prefix orders and Scott orders. It will develop a framework for models of computation for concurrent systems that uses partially ordered tags associated with events. Discrete-event models, synchronous/reactive languages, dataflow models, and process networks will be studied in this context. Basic issues of computability, boundedness, determinacy, liveness, and the modeling of time will be studied. Classes of functions over partial orders, including continuous, monotonic, stable, and sequential functions will be considered, as will semantics based on fixed-point theorems.

Projects will be presented at the end of the semester in a forum that will be as close as possible in organization to a professional workshop. Project papers will follow a standard four-page, two-column conference format, and presentations will be 20 minute oral presentations. Students in the course will form the "program committee" for the conference, and will review papers submitted to the conference. Although no paper will be rejected, authors will be expect to respond to issues raised by reviewers, and the quality of the reviews will be taken into account in the grade assigned to the reviewers.

Grading will be based on homework exercises, reviews of project papers, and the project paper and presentation. This course is designed as a three unit class.

Class web page: http://embedded.eecs.berkeley.edu/concurrency.