Pages

Friday, April 26, 2013

Serial vs Parallel, Sequential vs Concurrent

In a Turing machine, instructions are executed one after the other, so, by definition, its behaviour is always sequential. However, in a multitasking system we have many and concurrent processes. The operating system reduces the concurrent programs to a definite sequence of operations (but not pre-determined, it is an on-the-fly operation and depends to the contingency of the processes). A multitasking system operates also on single-core computers. Parallel execution means that the system divide the instructions to different core processors. This may occurs both in single-task and multitasking systems.

The use of the term parallel and concurrent is widespread in other domains as well, like programming, but it has determined some confusion with the somehow related terms sequential and concurrent. I will try to highlight the differences, using some practical example. My goal is to explain this picture:



The serial/parallel and sequential/concurrent characterizations are orthogonal. From a common-sense point of view, this orthogonality can be associated to the ontological separation between space and time, form and behaviour, objects and processes, being and doing. Adding the zero points to both axis - i.e. when there is no change (static), or when there is no topological decomposition (unity), we may map our system description on this picture.

In electronics, serial (or series) and parallel identify wo different configurations of some components. 

By the sake of an example, let us consider this representation:

> component X >

where the ">" symbol identifies the input and output direction. 

The serial configuration is a sort of chain, where the output of the first element is the input of the second:

INPUT > component A > component B > .. > component N > OUTPUT 

On the contrary, the parallel configuration is a sort of knitting, created by connecting to one spot all the inputs, and to another spot all the outputs. 

INPUT > component A > OUTPUT
      > component B > 
      > ..          > 
      > component N >

In electronics serial and parallel represent a type of static topology, determining the actual behaviour of the circuit. When there is no concurrency, parallelism is deterministic.

In order to describe dynamic, time-related phenomena, we use the term sequential and concurrent. For example, a certain outcome may be obtained via a certain sequence of tasks (eg. a recipe). When we are talking with someone, we are producing a sequence of words. However, in reality, many other processes occur in the same moment, and thus, concur to the actual result of a certain action. If a lot of people is talking at the same time, concurrent talks may interfere with our sequence, but the outcomes of this interference are not known in advance. Concurrency introduces indeterminacy.

We construct an example starting from digital communication, and then human communication. A decade ago, serial and parallel were commonly used to identify two kind of cables. In a serial adapter, a digital message is only temporally distributed along the same communication line (eg. one wire). In a parallel adapter, this is divided also on parallel communication lines (eg. many wires), and then reconstructed on the receiving end. 

Let us image a game, with 9 children. If we dispose them as a chain, give a message at the first and receive it at the end, we would have a serial communication. More words compose the message, consisting in a sequence of communication unities. For now, let us supposes a perfect communication between the children (similarly to digital communication with no failures).

I like ice-cream so much. > X > X > X > X > X > X > X > X > X > ....

This is a sequential process reproduced on a serial infrastructure.

Now, let us image to divide the children in groups of 3. We divide the phrase in three parts, give the first to the child of the line at our left, the second to the center line's child, etc.

I like ice-cream so much. > I like    > X > X > X > .... > ....
                          > ice-cream > X > X > X > ....
                          > so much   > X > X > X > ....

This is a sequential process reproduced on a parallel infrastructure (still partially serialized although). In both cases, because of the perfect transfer, the result is determined in advance.

However, if other people are talking to the first child at the same time as you, or, if we consider the actual individual interpretation performed by each child, then many interrelated concurrent processes will concur simultaneously to the final reconstruction. The outcome is non-determined in advance.