Vytvorí sa hashtabuľka do ktorej sa uložia hodnoty obsadenia pozícií v tabuľke (náhodne). Takto vytvorená tabuľka sa rozdelí podľa počtu procesov na jednotlivé časti. Tieto časti sa odošlú, spolu s hašovacím reťazcom do ostatných procesov. Otestuje sa, či jednotlivé časti vrátené funkciou Scatter sú obsadené. V prípade, že nie je daná časť obsadená, nájde miesto pre nový prvok. Miesto pre nový prvok nájde tak, že sa pozícia v hash tabuľke presúva s krokom STEP, kde zaznamenávame počet prechodov a pozíciu v hash tabuľke. Ak je daná časť obsadená nastaví počet prechodov a pozíciu na nekonečno (-1). Hlavný proces prijíma od ostatných (slave) procesov informácie o počte prechodov a pozícii a tieto hodnoty testuje pre možnosť uloženia reťazca na danú pozíciu. Riešenie problému je škálovateľné, je možné počítať na ľubovoľnom počte procesov.
Kód v cpp
#include <mpi.h> #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> #define HASHTABLESIZE 10 #define WORDSIZE 6 #define STEP 3; int doHash(char* word) { int i,hash = 0; for(i = 0; i < strlen(word); i++) hash += (int)word[i]; return hash % HASHTABLESIZE; } int main(argc, argv) int argc; char *argv[]; { int size, rank; int hashtable[HASHTABLESIZE], *dataChunk; char word[WORDSIZE]; int i, full,placed,runs, hash, position, *sendcounts, *offsets, chunkSize, zvysok, bounds[2], retbuf[2]; MPI_Status status; /* Initialize MPI */ MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); chunkSize = HASHTABLESIZE / size; zvysok = HASHTABLESIZE % size; if (rank == 0) { //hashtabulka, 0=volne,1=obsadene hashtable[0] = 1; hashtable[1] = 1; hashtable[2] = 1; hashtable[3] = 1; hashtable[4] = 0; hashtable[5] = 1; hashtable[6] = 0; hashtable[7] = 0; hashtable[8] = 0; hashtable[9] = 1; strcpy(word, "hasho"); //hashovany retazec for(i = 0; i < HASHTABLESIZE; i++) { if(hashtable[i] == 0) printf("%d: -\n", i); else printf("%d: obsadene\n", i); } sendcounts = (int*) malloc(size*sizeof(int)); offsets = (int*) malloc(size*sizeof(int)); for(i = 0; i < size; i++) { if(i < zvysok) { sendcounts[i] = chunkSize + 1; offsets[i] = i * (chunkSize + 1); } else { sendcounts[i] = chunkSize; offsets[i] = (zvysok*(chunkSize+1)) + ((i-zvysok) * chunkSize); } } } MPI_Bcast(word,WORDSIZE,MPI_CHAR,0,MPI_COMM_WORLD); chunkSize = rank < zvysok ? chunkSize+1 : chunkSize; dataChunk = (int*) malloc(sizeof(int)* chunkSize); /* int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm); */ MPI_Scatterv(hashtable, sendcounts, offsets, MPI_INT, dataChunk, chunkSize, MPI_INT, 0, MPI_COMM_WORLD); if(rank < zvysok) bounds[0] = rank * (chunkSize); //chunksize je uz o jedna vacsi else bounds[0] = (zvysok*(chunkSize+1)) + ((rank-zvysok) * chunkSize); bounds[1] = bounds[0] + chunkSize; //check ci nema svoj segment plny full = 1; //na zac. akoze plny, ak najdem neobsadene - set 0(=neplny) for(i = 0; i < chunkSize; i++) { if(dataChunk[i] == 0) { full = 0; break; } } if(full == 0) //nie je plny - najdi miesto pre novy prvok { hash = doHash(word); runs = 0; //pocet prechodov hashtabulkou placed = 0; //umiestnene do tab? while(placed == 0 && runs < chunkSize) { if(hash >= bounds[0] && hash < bounds[1]) { i = hash-bounds[0]; //local index if(dataChunk[i] == 0) placed = 1; } if(placed == 0)//nema miesto { do { hash += STEP; if(hash >= HASHTABLESIZE) { runs++; hash -= HASHTABLESIZE; } } while (hash<bounds[0] || hash>=bounds[1]); } } retbuf[0] = runs; //pocet prechodov - da/neda sa ulozit ? retbuf[1] = hash; //pozicia } else //full { retbuf[0] = -1; //neda sa ulozit retbuf[1] = -1; } if(rank == 0) { i=STEP; printf("\nhash: %d, step: %d\n", doHash(word), i); printf("master %d: runs=%d pos=%d\n",rank,retbuf[0],retbuf[1]); for(i = 1; i < size; i++) { MPI_Recv(bounds, 2, MPI_INT, i, 1, MPI_COMM_WORLD, &status); printf("slave %d: runs=%d pos=%d\n", i, bounds[0], bounds[1]); if(bounds[0] != -1 && (bounds[0]<retbuf[0] || (bounds[0]==retbuf[0] && bounds[1] < retbuf[1]) || retbuf[0] == -1)) //compare runs { retbuf[0] = bounds[0]; retbuf[1] = bounds[1]; } } //final result if(retbuf[0] == -1) printf("neda sa ulozit\n"); else printf("ulozene na: %d\n", retbuf[1]); } else { MPI_Send(retbuf,2,MPI_INT,0,1,MPI_COMM_WORLD); } MPI_Finalize(); return (EXIT_SUCCESS); }