Algorithms and Parallel Computing

7.2 DEFINING ALGORITHM VARIABLES

We define three types of variables in an algorithm:

• Input variables
• Output variables
• Intermediate or input/output (I/O) variables

An input variable is one that has its instances appearing only on the right-hand side (RHS) of the equations of the algorithm. a(j), b(j), and x(i − j) in Eq. 7.1 are examples of input variables. An output variable is one that has its instances appearing only on the left-hand side (LHS) of the algorithm. The IIR algorithm does not have output variables as such. An intermediate variable is one that has its instances appearing both on the LHS and on the RHS of the equations of the algorithm. Variable y(i) in Eq. 7.2 is an example of an intermediate I/O variable. We consider an intermediate variable as being both an input or output variable with different index dependencies for each side of the iteration statement. This will be discussed in more detail in the next two sections. We will see in Chapter 12 how we are able to extract a parallel execution for any algorithm using the formal techniques we present in the following chapters.