next up previous contents
Next: Problem konika szachowego Up: Przykłady algorytmów Previous: Prosty algorytm obliczania sumy   Spis rzeczy


Algorytm sortowania

Przedstawiony algorytm sortowania jest oparty na standardowym algorytmie quicksort. Różnica polega na tym, że w pierwszym kroku procesor główny losuje spośród danych wejściowych N-1 wartości \( x_{1}<x_{1}<...<x_{N-1} \) (gdzie N to liczba procesorów wirtualnych, \( x_{k} \) są umieszczane w tablicy limits), a następnie uruchamia procesory wirtualne o indeksach o 0 do N-1. Procesor o numerze k przepisuje następnie do swojej pamięci podręcznej wszystkie elementy x spełniające zależność \( x_{k}\leq x<x_{k+1} \) (przy czym \( x_{0} \)=MIN_VALUE, a \( x_{N} \)=MAX_VALUE), obliczając jednocześnie liczbę elementów mniejszych od \( x_{k} \). W kolejnym kroku każdy z procesorów za pomocą zwykłego algorytmu quicksort sortuje swój fragment pamięci. Na koniec posortowany blok jest przepisywany z powrotem do pamięci globalnej.

shared data_size;                // ilość danych

shared N;                        // liczba procesorów wirtualnych

shared data[0..4194303];         // dane do posortowania

shared limits[0..32];            // pomocnicza tablica

 

local proc;                      // indeks procesora

local buffer[0..4194303];        // bufor w pamięci podręcznej

local first;                     // zmienne pomocnicze

local last;

local min;

local max;

 

// poniższa funkcja służy do przepisania danych spełniających

// odpowiednie warunki z pamięci podręcznej do bufora

function copy_to_buffer(data_size)

local pom_buffer[0..data_size];

local i;

begin

first:=0; last:=-1; 

blockread(data,pom_buffer,data_size); 

for i:=0 to data_size-1 do

if pom_buffer[i]<min then first:=first+1;

else if pom_buffer[i]<max then

begin
last:=last+1;

buffer[last]:=pom_buffer[i];

end;
end;

 

// funkcja służąca do posortowania elementów tablicy buffer

// poczynając od komórki o numerze first, a kończąc na last

// jest ona wywoływana rekurencyjnie (zwykły algorytm quicksort)

function quicksort(first,last)

local begin1;

local end1;

local divider;

local pom;

begin

if first>=last then return 0;

if last-first=1 then

if buffer[first]<=buffer[lastthen return 0;

else

begin
pom:=buffer[first];

buffer[first]:=buffer[last];

buffer[last]:=pom;

end;
                                 

divider:=buffer[random(last-first+1)+first];

begin1:=first;

end1:=last;

while end1>begin1 do

if buffer[begin1]<=divider then begin1:=begin1+1;

else if buffer[end1]>divider then end1:=end1-1;

else

begin
pom:=buffer[begin1];

buffer[begin1]:=buffer[end1];

buffer[end1]:=pom;

end;
quicksort(first,begin1-1);

quicksort(end1,last);

end;

 

// funkcja sprawdzająca czy podany jako parametr element występuje

// w tablicy limits

function limits_contain(element,max)

local i;

begin

for i:=1 to max do
if limits[i]=element then return 1;
return 0;
end;

 

// funkcja służąca do ustalania granic dla danych, którymi będą

// się zajmować procesory wirtualne

function set_limits(proc)

local i;

local j;

local l;

begin

for i:=1 to proc-1 do
begin
l:=data[random(data_size)];

while limits_contain(l,i-1)=1 do l:=data[random(data_size)];

limits[i]:=l;

end;
 

for i:=1 to proc-2 do

for j:=i+1 to proc-1 do
if limits[i]>limits[jthen
begin
l:=limits[i];

limits[i]:=limits[j];

limits[j]:=l;

end;
   

limits[0]:=MIN_VALUE;

limits[proc]:=MAX_VALUE;

end;

 

// część główna programu

begin

if N<2 then
begin
blockread(data,buffer,data_size);

quicksort(0,data_size-1);

blockwrite(buffer,data,data_size);

end;
else
begin
set_limits(N);

 

for proc:=0 to N-1 pardo

begin
min:=limits[proc];

max:=limits[proc+1];

copy_to_buffer(data_size);

quicksort(0,last);

blockwrite(buffer,data[first],last+1);

end;
end;
end. Jeśli dysponujemy N procesorami wirtualnymi, to średni czas działania algorytmu dla losowych danych wynosi \( O\left( \frac{M}{N}\log \frac{M}{N}\right) \), gdzie M jest rozmiarem danych (pesymistyczny koszt algorytmu to \( O\left( \left( \frac{M}{N}\right) ^{2}\right) \)).


next up previous contents
Next: Problem konika szachowego Up: Przykłady algorytmów Previous: Prosty algorytm obliczania sumy   Spis rzeczy
Łukasz Maśko
2000-04-17