Căutarea binară paralelă

Algoritmul de căutare binară paralelă se bazează pe împărțirea secvenței în care se face căutarea în P subsecvențe de aceeași lungime. La fiecare pas, fiecare din cele P procesoare verifică dacă o valoare x se află în subsecvența atribuită procesorului respectiv, prin compararea valorii lui x cu valorile aflate pe pozițiile start și end, care marchează capetele subsecvenței unui procesor.

Dacă un procesor a găsit valoarea x în subsecvența sa, acesta va anunța celelalte procesoare despre acest lucru, iar apoi toate cele P procesoare vor căuta în subsecvența respectivă, care va fi împărțită în alte P subsecvențe, căutarea trecând la pasul următor.

Spre deosebire de versiunea serială, unde se verifică dacă elementul căutat se află pe poziția mijlocie din secvență, la versiunea paralelizată se verifică dacă elementul se află pe una din pozițiile de start și de end din secvență (dacă se află pe una dintre aceste poziții, înseamnă că am găsit elementul în secvență).

Se poate observa că operațiile de căutare a valorii x în subsecvențe de către fiecare procesor de la fiecare pas se pot realiza în paralel. Totuși, toate operațiile de căutare de la un pas trebuie să fie finalizate în totalitate înainte de trecerea la următorul pas, așadar în acest caz este nevoie de o barieră după fiecare pas de căutare.

O reprezentare grafică a algoritmului de căutare binară paralelă se poate observa în imaginea de mai jos, unde operațiile cu aceeași culoare pot fi realizate în paralel, liniile de aceeași culoare reprezintă indicii start și end ai fiecărei subsecvențe, specifice fiecărui procesor, iar simbolurile cu roșu reprezintă bariere.