Algorithms and Parallel Computing

1.3 ALGORITHMS

The IEEE Standard Dictionary of Electrical and Electronics Terms defines an algorithm as “A prescribed set of well-defined rules or processes for the solution of a problem in a finite number of steps” [4]. The tasks or processes of an algorithm are interdependent in general. Some tasks can run concurrently in parallel and some must run serially or sequentially one after the other. According to the above definition, any algorithm is composed of a serial part and a parallel part. In fact, it is very hard to say that one algorithm is serial while the other is parallel except in extreme trivial cases. Later, we will be able to be more quantitative about this. If the number of tasks of the algorithm is W, then we say that the work associated with the algorithm is W.

The basic components defining an algorithm are

1. the different tasks,

2. the dependencies among the tasks where a task output is used as another task’s input,

3. the set of primary inputs needed by the algorithm, and

4. the set of primary outputs produced by the algorithm.

1.3.1 Algorithm DG

Usually, an algorithm is graphically represented as a DG to illustrate the data dependencies among the algorithm tasks. We use the DG to describe our algorithm in preference to the term “dependence graph” to highlight the fact that the algorithm variables flow as data between the tasks as indicated by the arrows of the DG. On the other hand, a dependence graph is a graph that has no arrows at its edges, and it becomes ...