[C++ MPI] rompicapo su cammini minimi

[vonkraun]

Ho un grafo, acquisito da file, visto solo dal processo 0, salvato come matrice di adiacenza B.

Devo trovare la matrice dei cammini minimi per raggiungere j partendo da i.
L'algoritmo da utilizzare è l'algoritmo di Floyd ed è un esercizio sulla programmazione parallela.

Il numero di vertici nverts è sempre multiplo del numero di processi (size).

L'algoritmo applicato in una versione parallela deve fare questo:

Il processo 0 ripartisce la matrice con tutti gli altri processi, assegnando ad ognuino il giusto blocco, che andrà in un vettore che ho chiamato VectorLocal di grandezza nverts*nverts/size. Ogni processo quindi è responsabile di un numero di righe della matrice pari a nverts/size ed eseguira questo codice:

for k=0 to N-1   
for i=local_i_start to local_i_end    
 for j=0 to N-1       
Ii,j(k+1) = min(Ii,j(k), Ii,k(k)+ Ik,j(k))     
endfor   
endfor 
endfor

Alla iterazione k, ogni processo, necessita di avere i valori della riga k, che però solo uno ha. Ad esempio per k=0, solo il processo 0 avrà quella riga. Si farà quindi un broadcast a tutti gli altri processi.

Il mio codice è:

for(k=0;k<nverts;k++) 	  { 	   
   if (rank == index_proc[k]){ 		//estrazione rigaK 		
      if (k>nverts/size){	 			
             index = k-nverts/size*rank; 
//mi permette di identificare il primo valore della parte di vettore locale da selezionare 			
       }else index=k;							 		
       for (l=0; l<nverts; l++){ 			   
                 rigaK[l]=VectorLocal[l+index*nverts];	//solo il processo che ha questa 
riga deve fare il broadcast e quindi copia parte del vettore locale (perchè un vettore 
locale può essere formato da diverse righe, in base al numero di processi e di vertici 
in input) in un vettore rigaK[]		 		
          }	 	   
      } 	   
    MPI_Bcast(&rigaK[0], 1, MPI_INT, index_proc[k], MPI_COMM_WORLD);   	    	   
     for(i=0;i<nverts/size;i++){ 
           for(j=0;j<nverts;j++){
         	      if (i!=j && i!=k && j!=k)  		{ 	  
vikj=arcoLocal(i,k,VectorLocal,nverts)+arcoLocal(k,j,VectorLocal,nverts); 		 
vikj=min(vikj,rigaK[k*nverts+i]);  		
	if (rank==0) insert_edge(i, j, vikj, &B, nverts);   
	} //if 		
} //for j 	   
  }//for i 	
}//for k

ma non riesco a capire la logica da seguire, causa la rigaK che deve essere confrontata ogni volta con tutte le righe di tutti i processi, infatti vikj=min(vikj,rigaK[k*nverts+i]); dovrebbe essere assolutamente sbagliato.

Se mi sono spiegato male, vi prego di guardare l'animazione presente a questo indirizzo:
http://lsi.ugr.es/jmantas/pdp/practi...hp?prac=prac02
E' quella appena al di sotto di "Floyd descomposición Unidimensional"
Non fate caso alla lingua, sono in Spagna, ma dall'animazione dovrebbe capirsi il da farsi.

Confido negli amici della notte, sto per fondere col cervello.
Grazie.

[vonkraun]

Nessuno ha capito? E' che io credo più che altro di non aver capito cosa deve fare...