1. Oberoende trådar

Den enklaste typen av problem i trådad programmering är där trådarna är oberoende. För att få reda på om två trådar är oberoende, tänk på detta sätt:

• Tänk dig att läsmängden representerar mängden variabler som tråden läser från men inte skriver till.
• Tänk dig att skrivmängden representerar mängden variabler som tråden skriver till (och kanske läser men det spelar ingen roll).
• Två trådar är oberoende om deras respektive skrivmängd inte innehåller något element i den andra trådens skrivmängd eller läsmängd.

Tråd 1 och Tråd 2 är oberoende om och endast om:



Varför är det så lätt att programmera trådade program bestående av oberoende trådar? Jo för att varje tråd beter sig som ett eget program, det spelar ingen roll i vilken ordning de atomära handlingarna utförs. Oberoende trådar kommunicerar inte med varandra och trådarna är inte beroende av resultatet av varandras arbete. De ignorerar helt enkelt varandra.

2. Matrismultiplikation

Itreativ och rekursiv parallellism är problem som ofta kan delas upp i oberoende trådar. Ett exempel på iterativ parallellism är matrismultiplikation. Vi tänker oss att vi vill räkna ut C=AxB. Alla matriserna är av dimensionen n. Ett element i C, t.ex. C(row,col) räknar man fram på detta sätt:

C(row,col)=A(row,1)*B(1,col)+A(row,2)*B(2,col)+..+A(row,n)*B(n,col)

För att inte starta för många trådar räcker det med om varje rad i matrisen C beräknas i en egen tråd.

• Hur kan vi veta att trådarna i programmet är oberoende? Vi börjar med att fundera på matriserna A och B. Eftersom ingen tråd kommer att skriva till dessa matriser kan man ignorera dem, de ingår ju inte i någon tråds skrivmängd. Nu funderar vi över matrisen C, den matrisen skriver vi till, men ingen av trådarna läser från den. Eftersom vi har delat upp arbetet så att varje tråd skriver till varsin rad av C är trådarna oberoende per definition.

public class MatrixMultiplication{
  public static void main(String[] args){
    int DIMENSION=3;
    int a[][]={{1,2,3},
	       {4,5,6},
	       {7,8,9}};
	       
    int b[][]={{1,-1,1},
	       {1,-2,2},
	       {3,-2,-7}};
	       
    int c[][]={{0,0,0},
	       {0,0,0},
	       {0,0,0}};
	       
    // Create the threads
    RowCalculator rc[]=new RowCalculator[3];
    for(int i=0; i<DIMENSION; i++){
       rc[i]=new RowCalculator(a,b,c,i);
       rc[i].start();
    }
    // Wait for the threads to die
    for(int i=0; i<DIMENSION; i++){
      try{
        rc[i].join();
      }catch(Exception e){System.out.println(e);}
    }
    // Display result
    for(int i=0; i<DIMENSION; i++){
      System.out.println(c[i][0]+","+c[i][1]+","+c[i][2]);
   
    }
  }
}
// RowCalculator
// Calculates one row in the matrix
class RowCalculator extends Thread{
  int DIMENSION=3;
  int a[][];
  int b[][];
  int c[][];
  int row;
  public RowCalculator(int a[][],int b[][], int c[][], int row){
    this.a=a;
    this.b=b;
    this.c=c;
    this.row=row;
  }
  public void run(){
    for(int col=0; col<DIMENSION; col++){
      for(int x=0; x<DIMENSION; x++){
        c[row][col]=c[row][col]+a[row][x]*b[x][col];
	// c[0][0]=1*1+2*1+3*3=12;
	// c[0][1]=1*(-1)+2*(-2)+3*(-2)=-11 osv..
      }
    }
  }
}

[olle@dev1]$ java MatrixMultiplication
12,-11,-16
27,-26,-28
42,-41,-40