from the city of Vienna: Notes on SPMD architecture A I

Notes on SPMD architecture A I

1-D and 2-D processing implementation.

If the art of ship-building were in the wood, ships would exist by Nature

Aristotle

The object of this post is to summarize some background information in 1-D and 2-D processing implementation.

--------------------

Both signal and image processing involves 1-D and 2-D mathematical computing (1-D and 2-D processing). 1-D processing is performed over 1-D data objects (vectors), and 2-D processing over 2-D data objects (matrices).

As is well known, a vector A consisting of n elements is said to have a size (or length) of n, and its elements are denoted by Ai (i=1,.,n). A matrix A consisting of m rows and n columns is said to have a size of mxn (abbreviated: a mxn matrix) and its elements are denoted by Aij (i=1,.,m; j=1,.,n), being i the row number and j the column number. Moreover, the matrix transposition is an operation that consists in exchanging rows by columns. So, being AT the matrix resultant of transposing the matrix A, then Aij = ATji.

On the other hand, in the C programming language (among others), an array consists of a set of elements stored in consecutive memory locations. A vector is implemented as an array of elements, a matrix as an array of rows and a row as an array of elements. This is the vectors and matrices implementation model that will be used within this work.

According to the above, and being p a pointer to the first element of the array, the aforementioned elements Ai, Aij, and ATij can be addressed as p+(i-1), p+(j-1)+(i-1)*n and p+(i-1)+(j-1)*m, respectively.

2-D processing consists of two 1-D processings, one horizontal and the other vertical (over the rows and the columns of the matrix, respectively). Due to the fact that consecutive accesses to consecutive memory locations are faster than consecutive accesses to non-consecutive memory locations, processing rows are faster than processing columns. For that reason, 2-D processing is implemented as a sequence consisting of horizontal processing + a matrix transposition + horizontal processing.

In the writing of this article, Roxette (I remember you) have collaborated in an involuntary but decisive way.