Information

Author(s) Erik-Jan Lingen, Matthias Möller
Deadline No deadline
Submission limit No limitation

Sign in

[Threads] Exercise 8 : Gram-Schmidt Algorithm

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.


Task

Implement a parallel program that executes the Gram-Schmidt algorithm to make the columns of an \(N \times N\) matrix \(\mathbf{A}\) orthonormal through a series of dot products and vector subtractions.

The pseudo-code of the Gram-Schmidt algorithm reads as follows:

\begin{align*} &\text{do }j=1,\dots,N\\ &\quad \text{do }k=1,\dots,j-1\\ &\quad\quad c_k := \mathbf{A}_j^\top \cdot \mathbf{A}_k\\ &\quad \text{end do}\\ &\quad \mathbf{A}_j := \mathbf{A}_j - \sum_{k=1}^{j-1} c_k \cdot \mathbf{A}_k\\ &\quad \mathbf{A}_j := \frac{\mathbf{A}_j}{\| \mathbf{A}_j \|}\\ &\text{end do} \end{align*}

Note that \(\mathbf{A}_{j}\) denotes the \(j\)-th column of the matrix \(\mathbf{A}\) and superscript \(\top\) stands for taking the transpose.

The code below show a serial implementation of the Gram-Schmidt algorithm.

In the parallel implementation of the Gram-Schmidt algorithm, the matrix \(\mathbf{A}\) is distributed row-wise over the processors:

08-gram-schmidt-threads/row-wise-distribution-1.svg

This means that each thread handles \(\frac{N}{p}\) rows, with \(p\) the number of threads.

Hints

Use the functions matrix_alloc and matrix_free to create and destroy a matrix with arbitrary dimensions.

Define a struct data_t that is to be passed to each thread. It should contain at least the matrix size, a pointer to the matrix, a pointer to a shared reduction variable, and the first and last row indices to be processed by a thread.

You must define a data_t instance for each thread!

What performance do you get? How could you improve the performance?


Question 1: Gram-Schmidt Algorithm
Question 2: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.