Parallel Systems Project

Objectives

For a frequently occurring computational problem you should:

For the performance study, you should use:

The roofline model will be briefly discussed during the last exercise session using this visual studio solution .

Organization

Here are the rules for the project:

We expect the following deliverables:

Topics 2016-2017 (click here)

For each topic we will give some pointers to problem descriptions together with a number of possible implementations.
We will also try to give an estimation of the difficulty level and feasibility.

Topics 2014-2015

For each topic we will give some pointers to problem descriptions together with a number of possible implementations.
We will also try to give an estimation of the difficulty level and feasibility.

a) Pattern recognition in signals

Consider the following large, historical 1D signal consisting of 2 variables that fluctuate in time:

Let's index the two arrays as follows:

Now we want to find matches of a given, limited signal - the query - in the historical data.
Example:

Indexed as follows:



To find a match we slide the query over the historical data and for each offset calculate the distance between both:
  => 
Here the sum of absolute differences is taken as distance metric.

b) OpenCL-OpenGL integration for processing and viewing 3D images

c) Algorithms on matrices

for (i=n;i>=1;i--) {
    if (i < n) {
        if (g) {
            for (j=l;j<=n;j++) Double division to avoid possible underflow.
                v[j][i]=(a[i][j]/a[i][l])/g; // (*) calculating column
            for (j=l;j<=n;j++) {
                for (s=0.0,k=l;k<=n;k++) s += a[i][k]*v[k][j]; // (*) row x column (reduction)
                for (k=l;k<=n;k++) v[k][j] += s*v[k][i];  //(*) factor x column
            }
        }
        for (j=l;j<=n;j++) v[i][j]=v[j][i]=0.0;  // (*) setting column and row
    }
    v[i][i]=1.0;
    g=rv1[i];
    l=i;
}

d) Solving linear equations

e) Tree Construction and Tree Traversal (can be split into 2 separate topics)