16.3 Parallelism 545
If we want our program to be pipelined efficiently, there are a few dos and don’ts
which should be kept in mind.
- Avoid conditional statements (‘if-statements’) within loops. Also avoid
subroutine or function calls within loops.
- In the case of nested loops whose order can be interchanged, the longest loop
should always be the interior loop.
- Use standard, preferably machine-optimised software to perform standard tasks.
- If possible, use indexed loops (‘do-loops’) rather than conditional loops
(‘while-loops’).
A few remarks are in order. In the third item, use of standard software for standard
tasks is recommended. There exists a standard definition, called LAPACK, of lin-
ear algebra routines. Often, vendors provide machine-optimised versions of these
libraries; these should always be used if possible.
If a function call or IF-statement cannot be avoided, consider splitting the loop
into two loops: one in which the function calls or if-statements occur, and another in
which the vectorisable work is done. Some computers contain amask-registerwhich
contains some of the bits which are relevant to a certain condition (e.g. the sign
bit for the conditiona[i]>0). This mask register can be used by the processor to
include the condition in the pipeline process. Finally, compiling with the appropiate
optimisation options will, for some or perhaps most of the above recommendations,
automatically implement the necessary improvements in the executable code.
16.3 Parallelism
16.3.1 Parallel architectures
Parallel computers achieve increase in performance by using multiple processors,
which are connected together in some kind of network. There is a large variety of
possible arrangements of processors and of memory segments over the computer
system. Several architecture classifications exist. The most famous classification is
that of Flynn who distinguishes the following four types of architectures [ 1 , 2 ]:
- SISD: Single Instruction Single Data stream computers;
- MISD: Multiple Instruction Single Data stream computers;
- SIMD: Single Instruction Multiple Data stream computers;
- MIMD:Multiple Instruction Multiple Data stream computers.
The single/multiple instruction refers to the number of instructions that can be per-
formed concurrently on the machine, and the single/multiple data refers to whether
the machine can process one or more data streams at the same time.
