Serial Programming Models

We can now describe the two most common serial programming models in terms of these patterns.

A. Imperative Programming
In the imperative model of computation, the programmer directly tells the computer what to do and the order in which to do it. Serial imperative programming models, in order to be universal, need at a minimum to support the sequence, selection, and iteration control-flow patterns and typically the random-read and random-write patterns.

In addition, recursion and functions are usually supported, although they are technically not needed. FORTRAN, in particular, only relatively recently added support for recursion.

Imperative programming is the dominant serial programming model today. Its chief disadvantage from the point of view of parallelization is its over-specification of the ordering of operations. It is difficult to determine automatically, given an imperative program, which ordering constraints are essential for the correct operation of the program and which are an accidental result of the way the programmer expressed the computation. In particular, since pointers can refer anywhere in the global array, the global memory array is a potential source and destination for all operations, making it a universal data dependency.

B. Functional Programming
The functional model of computation is based on rewriting nested trees or graphs. Pure functional languages typically only support selection and recursion for control flow, and random read for data access. Data structures can be created (using dynamic memory allocation) but not modified. Despite their simplicity, pure functional languages are universal. Some algorithms that depend on incremental modification of data in-place are however difficult to express in purely functional languages.

The chief advantage of functional languages from a parallelization point of view is that only the essential data dependencies are expressed and only these data dependencies constrain the order of operations.