Programmazione.it :: Una soluzione parallela per la moltiplicazione di matrici in Java (2/3)

Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!

Una soluzione parallela per la moltiplicazione di matrici in Java (2/3)

Scritto da Francesco Carotenuto il 10-03-2010 ore 11:11

Nel precedente articolo abbiamo indicato l'utilizzo dei thread pool come una buona scelta per implementare la moltiplicazioni di matrici in parallelo. L'idea che è alla base di questo programma è quello di affidare a ogni thread del pool pezzi di matrici, esattamente di dimensioni (n/2)x(n/2), su cui effettueremo le operazioni di moltiplicazione e addizione, inoltre assumiamo per semplicità che n sia una potenza di due.

Ad esempio, se dobbiamo effettuare un prodotto tra due matrici A e B e la relativa matrice prodotto P di dimensioni 16x16, avremo quattro sottomatrici 4x4 sia per A che per B; nel caso di A esse saranno A00, A01, A10, A11, e in maniera analoga indicheremo in questo modo le sottomatrici di B e P. Il prodotto P00, che equivale alle prime quattro righe e colonne della matrice P, sarà:

P00=A00*B00+A01*B10

Analogo ragionamento si può fare per le altre tre parti di P. Quindi abbiamo bisogno di realizzare una struttura dati Matrix, che oltre a inglobare la matrice vera e propria, includa i vari metodi get e set per poter lavorare sui singoli elementi e un metodo split, che scompone la nostra matrice nxn in quattro sottomatrici (n/2)x(n/2), con un'implementazione analoga al listato seguente:

public class Matrix{
 
  private int dim;
  private double[][]data;
  private int rowDisplace,colDisplace;
 
  public Matrix(int d){
    dim=d;
    rowDisplace=colDisplace=0;
    data= newdouble[d][d];
  }
 
  private Matrix(double[][]matrix, int x, int y, int d){
    data=matrix;
    rowDisplace=x;
    colDisplace=y;
    dim=d;
  }
 
  public double get(int row, int col){
    return data[row+rowDisplace][col+colDisplace];
  }
 
  public void set(int row, int col, double value){
   data[row+rowDisplace][col+colDisplace]=value;
  }
 
  public int getDim(){
   return dim;
  }
 
  public Matrix[][]split(){
    Matrix[][]result= new Matrix[2][2];
    int newDim=dim/2;
    result[0][0]=
     new Matrix(data,rowDisplace,colDisplace,newDim);
    result[0][1]=
     new Matrix(data,rowDisplace,colDisplace+newDim,newDim);
    result[1][0]=
     new Matrix(data,      rowDisplace+newDim,colDisplace,newDim);
    result[1][1]=
      new     Matrix(data,rowDisplace+newDim,colDisplace+newDim,newDim);
    return result;
  }
}

Tale struttura verrà utilizzata nei task di addizione e moltiplicazione, che interagiranno con la logica del prodotto di matrici implementato con il thread pool.

Pubblicazioni correlate:
08-03-2010 Una soluzione parallela per la moltiplicazione di matrici in Java (1/3)
15-03-2010 Una soluzione parallela per la moltiplicazione di matrici in Java (3/3)

Intervento di Jack Niisan a.k.a. jack0niisan del 26-05-2010 ore 17:02, Bolzano (BZ)

Plebeo
(4 interventi)
Iscritto il 23-05-2010

Ciao, volevo solo fare una osservazione, essendo io molto interessato al prodotto tra matrici in parallelo, ho deciso di provare la tecnica da te suggerita, ma un' affermazione non mi è chiara. Nel testo è scritto che partendo da una matrice nxn è possibile ricavare delle sotto-matrici di dimensioni n/2+n/2, ciò significa, se non erro, dividere "sempre" la matrice in 4 sotto-matrici che hanno metà numero di colonne e metà numero di righe, ma allora una matrice che è 16*16, non dovrebbe essere suddivisa in 4 matrici 8*8, piuttosto che 4 matrici 4*4?

Intervento di Francesco Carotenuto a.k.a. nucarote del 26-05-2010 ore 18:27, Nocera inferiore (SA)

Plebeo
(25 interventi)
Iscritto il 14-01-2009

jack0niisan ha scritto:

Ciao, volevo solo fare una osservazione, essendo io molto interessato al prodotto tra matrici in parallelo, ho deciso di provare la tecnica da te suggerita, ma un' affermazione non mi è chiara. Nel testo è scritto che partendo da una matrice nxn è possibile ricavare delle sotto-matrici di dimensioni n/2+n/2, ciò significa, se non erro, dividere "sempre" la matrice in 4 sotto-matrici che hanno metà numero di colonne e metà numero di righe, ma allora una matrice che è 16*16, non dovrebbe essere suddivisa in 4 matrici 8*8, piuttosto che 4 matrici 4*4?

Tenendo presente che tale articolo presenta solo uno stub di come potrebbe essere l'implementazione del prodotto di matrici parallelo.
Ad ogni modo, nel caso di matrici 16x16, la matrice viene suddivisa in 4 sottomatrici 8x8, così come mostrato nel codice del metodo split e che tu stesso puoi verificare. Per cui si è trattato solo di un banale errore di battitura.