Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Алгоритмы _ Алгоритмы пузырьковой сортировки

Автор: Account 23.06.2011 17:39

Итак, все знают что есть такой вид сортировки, как пузырьковая. Меня интересует какие еще есть алгоритмы в этом виде сортировки кроме: последовательного и чет-нечетной перестановки? И если есть информация о них поделиться ей, если не жалко.

Автор: IUnknown 23.06.2011 20:04

http://en.wikipedia.org/wiki/Odd-even_sort (так называемая "параллельная пузырьковая") интересует? Или ты ее и называешь чет-нечетной перестановкой? http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%80%D0%B0%D1%81%D1%87%D1%91%D1%81%D0%BA%D0%BE%D0%B9 (вроде как тоже усовершенствование пузырька)?

Автор: Account 23.06.2011 21:18

Первая, действительно чет-нечет, а вот вторую не видел, спасибо. Нашел еще шейкер-сортировку

Просто нужно для курсового проекта рассмотреть варианты алгоритмов пузырьковой ,выбрать наилучший по трудоемкости для дальнейшего распараллеливания вычисления данным алгоритмом)))

Автор: Account 23.06.2011 21:55

Сортировка расческой (вроде как тоже усовершенствование пузырька) - что-то у меня она прооигрывает обычной сортировке. Вот как сделал

void combsort( double *pData, int DataSize )
{ double tmp;

int jump = DataSize;
bool swapped = true;

while (jump > 0 || swapped)
{
if (jump > 0)
jump = (jump / 1.25);
swapped = false;
for (int i = 0; i + jump < DataSize-1; i++)
if(pData[i] > pData[i + 1]) {
tmp = pData[i];
pData[i] = pData[i + 1];
pData[i + 1] = tmp;swapped = true;}

}
}

Автор: IUnknown 23.06.2011 22:18

Ты б лучше обе реализации привел, чтоб сравнить можно было... Лучше всего - целиком программу, которая показывает, где больше, а где - меньше времени. А то так знаешь, все может зависеть от многих факторов...

P.S. Вот http://en.wikipedia.org/wiki/Comb_sort#C лежит реализация "расчески на С", на кой велосипед придумывать опять? smile.gif

Автор: Account 23.06.2011 22:48

IUnknown, велосипед не придумывал выдернул код представленный с первой твоей ссылки))), но он оказался медленнее представленного тобой по последней ссылке.Походу по первой не совсем верный алгоритм.

Вот прога целиком

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;
void RandomDataInitialization(double *&pData, int& DataSize) ;
void ProcessInitialization(double *&pData, int& DataSize) ;
void ProcessTermination(double *pData);
void DummyDataInitialization(double*& pData, int& DataSize);
void Shaker(double *pData, int DataSize);
void combsort( double *pData, int DataSize );
void PrintData(double *pData, int DataSize);
const double RandomDataMultiplier = 1000.0;

int main(int argc, char *argv[]) {
double *pData = 0;
int DataSize = 0;

time_t start, finish;
double duration = 0.0;

printf("Serial bubble sort program\n");

// Process initialization // В этой функции можно менять вид заполнения массива
ProcessInitialization(pData, DataSize);

//printf("Data before sorting\n");
//PrintData(pData, DataSize); // Для проверки исходных данных

// Serial bubble sort // Виды сортировки, обычная пузырьковая, расческой, Шейкера активация на выбор
start = clock();
SerialBubble(pData, DataSize);
//combsort(pData, DataSize);
//Shaker(pData, DataSize);
finish = clock();

//printf("Data after sorting\n");
//PrintData(pData, DataSize); //Для проверки результата

duration = (finish - start) / double(CLOCKS_PER_SEC);
printf("Time of execution: %f\n", duration);

// Process termination
ProcessTermination(pData);

return 0;
}

// Function for allocating the memory and setting the initial values
void ProcessInitialization(double *&pData, int& DataSize) {
do {
printf("Enter the size of data to be sorted: ");
scanf("%d", &DataSize);
if(DataSize <= 0)
printf("Data size should be greater than zero\n");
}
while(DataSize <= 0);

printf("Sorting %d data items\n", DataSize);

pData = new double[DataSize];

// Simple setting the data
//DummyDataInitialization(pData, DataSize);

// Setting the data by the random generator
RandomDataInitialization(pData, DataSize);
}

// Function for computational process termination
void ProcessTermination(double *pData) {
delete []pData;
}

// Function for simple setting the initial data
void DummyDataInitialization(double*& pData, int& DataSize) {
for(int i = 0; i < DataSize; i++)
pData[i] = DataSize - i;
}

// Function for initializing the data by the random generator
void RandomDataInitialization(double *&pData, int& DataSize) {
srand( (unsigned)time(0) );

for(int i = 0; i < DataSize; i++)
pData[i] = double(rand()) / RAND_MAX * RandomDataMultiplier;
}

// Serial bubble sort algorithm
void SerialBubble(double *pData, int DataSize) {
double Tmp;

for(int i = 1; i < DataSize; i++)
for(int j = 0; j < DataSize - i; j++)
if(pData[j] > pData[j + 1]) {
Tmp = pData[j];
pData[j] = pData[j + 1];
pData[j + 1] = Tmp;
}
}

void PrintData(double *pData, int DataSize) {
for(int i = 0; i < DataSize; i++)
printf("%7.4f ", pData[i]);
printf("\n");
}

void Shaker(double *pData, int DataSize){
double t;
bool exchange;

do {
exchange = false;
for(int i=DataSize-1; i > 0; --i) {
if(pData[i-1] > pData[i]) {
t = pData[i-1];
pData[i-1] = pData[i];
pData[i] = t;
exchange = true;
}
}
for(int i=1; i < DataSize; ++i) {
if(pData[i-1] > pData[i]) {
t = pData[i-1];
pData[i-1] = pData[i];
pData[i] = t;
exchange = true;
}
}
} while(exchange);

}

void combsort(double *pData, int DataSize) {
float shrink_factor = 1.247330950103979;
int gap = DataSize, swapped = 1, i; double swap;

while ((gap > 1) || swapped) {
if (gap > 1)
gap = gap / shrink_factor;

swapped = 0;
i = 0;

while ((gap + i) < DataSize) {
if (pData[i] - pData[i + gap] > 0) {
swap = pData[i];
pData[i] = pData[i + gap];
pData[i + gap] = swap;
swapped = 1;
}
++i;
}
}
}



еще надо будет добавить чет-нечет
Дальше дело за малым, прогон на проверку каждого алгоритма.

Автор: IUnknown 23.06.2011 23:09

Цитата
Походу по первой не совсем верный алгоритм.
Это надо сказать спасибо переводчикам Википедии. Вот именно поэтому я и предпочитаю работать с англоязычными источниками.

Цитата
Дальше дело за малым, прогон на проверку каждого алгоритма.
Не понял. То есть, ты считаешь, что если какая-то из написанных тобой функций будет быстрее без распараллеливания, то и при параллельном выполнении тоже она же будет быстрее? Наивный такой smile.gif Ты сначала сделай параллельные версии всех этих методов, а потом сравнивай. На 2-х ядрах, на 4-х и на 8 (если есть - еще и на большем количестве). Результаты тебя заставят удивиться, я думаю...

Автор: Account 23.06.2011 23:27

Цитата(IUnknown @ 24.06.2011 0:09) *

Это надо сказать спасибо переводчикам Википедии. Вот именно поэтому я и предпочитаю работать с англоязычными источниками.

Не понял. То есть, ты считаешь, что если какая-то из написанных тобой функций будет быстрее без распараллеливания, то и при параллельном выполнении тоже она же будет быстрее? Наивный такой smile.gif Ты сначала сделай параллельные версии всех этих методов, а потом сравнивай. На 2-х ядрах, на 4-х и на 8 (если есть - еще и на большем количестве). Результаты тебя заставят удивиться, я думаю...

Я не считаю что она будет быстрее)))
Просто с видом сортировки как бы определилось, а вот алгоритм нужно выбрать по наименьшей трудоемкости, но опять же каждый алгоритм по разному ведет себя при разных объемах сортируемых данных, т.е. нужно построить график зависимости от кол-ва элементов ко времени, и уже отсюда плясать. Так как например грубо говоря дана задача отсортировать 100000 элементов. допустим прогоним эти алгоритмы, посмотрим результат. Для примеру допустим среднее от всех результатов алгоритмов 20 минут. Ставим задачу отсортировать за 4 минуты. т.е. создать кластер из подобных машин, на которй ставиться эксперимент, расчитать кол-во узлов кластера. Это все естетсвенно теоретически насчет вычислений параллельных, так как высчитать негде и нужно MPI изучать для реализации. курсовой проект такой дали.

Автор: Account 23.06.2011 23:51

Добавил чет-нечет и проводил эксперимент на сортировку 25000 элементов. Комбинированная всех уделала, разница во времени просто обалдеть можно.

Автор: Account 26.06.2011 15:36

Никак до конца не пойму применения чет-нечет алгоритма для параллельной обработки.
1 - сортировка на всех узлах
2-обмен соседних узлов (Везде приводиться один и тот же пример причем после 2 пункта в соседних процессах хранятся уже упорядоченный данные, а не просто обмененные.)

вот второй пункт не до конца понимаю, нигде в подробностях не описано. Как я понял, это объединения данных соседних узлов, сортировка этого объединенного массива и разбиение опять на две части.


Правильно ли я понимаю и где можно почитать в подробностях данного параллельного алгоритма?

Автор: IUnknown 26.06.2011 18:05

Вот по http://siber.cankaya.edu.tr/ozdogan/GraduateParallelComputing.old/ceng505/node132.html разобраться сможешь?

Автор: Account 26.06.2011 22:13

Основа понятна вот этот участок не очень особенно по распределению элементов

/* This is the CompareSplit function */ 
74 CompareSplit(int nlocal, int *elmnts, int *relmnts, int *wspace,
75 int keepsmall)
76 {
77 int i, j, k;
78
79 for (i=0; i<nlocal; i++)
80 wspace[i] = elmnts[i]; /* Copy the elmnts array into the wspace array */
81
82 if (keepsmall) { /* Keep the nlocal smaller elements */
83 for (i=j=k=0; k<nlocal; k++) {
84 if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j])) //<------Не въеду что то, как в словах это правильно озвучить
85 elmnts[k] = wspace[i++];
86 else
87 elmnts[k] = relmnts[j++];
88 }
89 }
90 else { /* Keep the nlocal larger elements */
91 for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) {
92 if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j])) //<--------------Естественно здесь тоже
93 elmnts[k] = wspace[i--];
94 else
95 elmnts[k] = relmnts[j--];
96 }
97 }
98 }

Автор: IUnknown 27.06.2011 13:38

     if (keepsmall) { /* Keep the nlocal smaller elements */ 

// Этот кусок упорядочивает в массив elmnts минимальные значения из elmnts и
// relmnts (которые получены от соседнего процесса) по возрастанию
// (сколько поместится в elmnts) Скажем, если было:
// elmnts = (27 39 54 74 90)
// relmnts = (22 38 50 65 69)
// то после выполнения нижеследующего куска кода
// elmnts = (22 27 38 39 50)

for (i=j=k=0; k<nlocal; k++) {
if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j]))
elmnts[k] = wspace[i++];
else
elmnts[k] = relmnts[j++];
}
}
else { /* Keep the nlocal larger elements */
// Соответственно, этот кусок делает то же самое, но сохраняет nlocal максимальных
// элементов из совокупности elmnts и relmnts. Т.е., если
// elmnts = (16 18 47 62 70)
// relmnts = ( 1 13 23 29 92), то в результате
// elmnts = (29 47 62 70 92)
// в упорядоченном виде
for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) {
if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j]))
elmnts[k] = wspace[i--];
else
elmnts[k] = relmnts[j--];
}
}

Автор: Account 27.06.2011 20:50

Цитата(IUnknown @ 27.06.2011 14:38) *

     if (keepsmall) { /* Keep the nlocal smaller elements */ 

// Этот кусок упорядочивает в массив elmnts минимальные значения из elmnts и
// relmnts (которые получены от соседнего процесса) по возрастанию
// (сколько поместится в elmnts) Скажем, если было:
// elmnts = (27 39 54 74 90)
// relmnts = (22 38 50 65 69)
// то после выполнения нижеследующего куска кода
// elmnts = (22 27 38 39 50)

for (i=j=k=0; k<nlocal; k++) {
if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j]))
elmnts[k] = wspace[i++];
else
elmnts[k] = relmnts[j++];
}
}
else { /* Keep the nlocal larger elements */
// Соответственно, этот кусок делает то же самое, но сохраняет nlocal максимальных
// элементов из совокупности elmnts и relmnts. Т.е., если
// elmnts = (16 18 47 62 70)
// relmnts = ( 1 13 23 29 92), то в результате
// elmnts = (29 47 62 70 92)
// в упорядоченном виде
for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) {
if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j]))
elmnts[k] = wspace[i--];
else
elmnts[k] = relmnts[j--];
}
}


Правильно ли я понимаю, что
wspace[i--]//<---совокупность и elmnts и relmnts

и по сути из него выбирается опять же методом сравнения(как по твоему, если бы отсортировать его и потом просто делить, привело бы к уменьшению времени выполнения данного кода ?)

Автор: IUnknown 28.06.2011 11:13

Цитата
как по твоему, если бы отсортировать его и потом просто делить, привело бы к уменьшению времени выполнения данного кода ?
С использованием MPI проверить нет возможности, а вот используя встроенную многозадачность Ады - проверил. Ночью запустил несколько тестов (все одно дежурил, делать особо нечего было, скучно smile.gif ), для 4, 8, 16 и 32-х процессов с разным количеством элементов (для простоты - кол-во элементов кратное кол-ву процессов, как и в программе по ссылке). Разницы в скорости выполнения не обнаружил. Т.е, что с CompareSplit, что с готовой сортировкой - одинаково. Это, учти, при том, что у меня есть возможность не копировать поэлементно два массива в один, а воспользоваться Array Slices, и обратно - то же самое, просто взять и вернуть часть массива, тебе же в Сях придется копировать в цикле. Можешь еще и потерять в скорости...

Автор: TarasBer 28.06.2011 11:38

В Сях можно явно передавать то, что Ада передаёт неявно - т.е. указатель на начало и границы подмассива.
Многозадачность на скольки ядрах смотрел?

Автор: IUnknown 28.06.2011 11:54

Цитата
Многозадачность на скольки ядрах смотрел?
16-ть процессоров, 8 ядер на каждом... 128, получается...

Цитата
В Сях можно явно передавать то, что Ада передаёт неявно - т.е. указатель на начало и границы подмассива.
Смотри:

   Array_Size : constant Integer := Total_Elements / Processes_Count;

type Int_Array is array (Natural range <>) of Integer;
subtype Sub_Array is Int_Array(0 .. Array_Size - 1);

-- ...

task body Sorter is
A : Int_Array(0 .. 2 * Array_Size - 1);
begin
accept Data (velmnts : Sub_Array; vrelmnts : Sub_Array) do
A(0 .. Array_Size - 1) := velmnts; -- Особенно интересует это ...
A(Array_Size .. 2 * Array_Size - 1) := vrelmnts; -- вот это ...
end Data;

if Keep_Small then -- Это дискриминант задачи ...
Sort(A);
else
Rev_Sort(A);
end if;

accept Request (Arr : out Sub_Array) do
Arr := A(0 .. Array_Size - 1); -- ... и вот это ...
end Request;
end Sorter;
Сможешь написать аналог на С без потерь на копирование?

Автор: TarasBer 28.06.2011 13:33

Я так понял, тут фишка в том, что velmnts и vrelmnts могут храниться в совсем разных областях памяти и всё равно компилятор умеет убирать копирование?
Ну грубо говоря, можно написать класс "располовиненный массив" с перегруженным оператором []. Правда, это уже не совсем чистый Си, но на Си принцип тот же. А вообще, чё там Си, да хоть на ассемблере. Дизассембелирую твой код и посмотрю.

Другое дело, что одна и та же конструкция языка высокого уровня может в зависимости от контекста скомпилироваться в принципиально разные вещи. То есть если переписать этот пример на Си именно для располовиненного массива, то алгоритм пузырька изуродуется до неузнаваемости, и если мне понадобится подредактировать уже изуродованный алгоритм, то я тупо задолбаюсь. А если это "уродование" делает компилятор, сохраняя исходник в чистоте, то всё в порядке.

Я вот что не пойму. Ты хочешь сказать, что твой компилятор умеет анализировать всё, что будет делаться над массивом и сделать вывод о том, что его вообще есть смысл хранить по частям (отдельные половинки в разных областях памяти)? Что-то я не заметил у ГНАТа высокий уровень интеллекта (я даже не смог заставить заменить вызов функции подсчёта суммы элементов константного массива на значение). Или я не заметил какой-то простой нюанс? Или у тебя не ГНАТ, а коммерческий мегакомпилятор?

Автор: IUnknown 28.06.2011 14:28

Цитата
Я вот что не пойму. Ты хочешь сказать, что твой компилятор умеет анализировать всё, что будет делаться над массивом и сделать вывод о том, что его вообще есть смысл хранить по частям (отдельные половинки в разных областях памяти)? <...> Или у тебя не ГНАТ, а коммерческий мегакомпилятор?
Я ничего не хочу сказать, я констатирую факт: если я вызываю вместо CompareSplit готовую функцию сортировки - это фактически не влияет на скорость выполнения задачи. Как буду дежурить опять - попробую погонять для очень больших значений Total_Elements, может, там что прояснится. Да, разумеется, используется GNAT Pro (другого здесь просто нет) и, разумеется, не под Windows.

Автор: Account 28.06.2011 15:05

Вот что меня еще смущает , погонял сортировку алгоритмом расческой, так на моем ноуте Dual-Core 2.1 GHz . 2 гига ОЗУ, 100000 элементов сортирует показывает за 0.062 с. 30000000 примерно за 21 секунду.
Это реально? Просто что то сомнения гложат в этом направлении.
а так еще надумал что тогда при таких результатах можно для распараллеливания использовать чет-нечет алгоритм, а для сортировки на узлах расческой.

Автор: TarasBer 28.06.2011 15:58

То есть у тебя получился ЛИНЕЙНЫЙ рост времени? Забавно. Думаю, дело в погрешности измерений.

Автор: Account 28.06.2011 20:31

Цитата(TarasBer @ 28.06.2011 16:58) *

То есть у тебя получился ЛИНЕЙНЫЙ рост времени? Забавно. Думаю, дело в погрешности измерений.


Это только по алгоритму расческой по астольным все путем
Код
        Последов.  Чет-нечет     Шейкер    Расчёской
5000     0.235000    0.235000    0.313000    0.000000
10000    0.782000    0.704000    1.047000    0.000000
20000    2.906000    2.640000    3.953000    0.016000
30000    6.484000    5.828000    8.719000    0.015000
40000    11.515000    10.234000    15.453000    0.016000
50000    17.844000    16.485000    23.906000    0.016000
100000    75.140000    68.063000    97.125000    0.062000


код всех применяемых сортировок и рабочей проги в одном из ранних постов, сам алгоритм расчески брался с американской вики, по ссылки предоставленой IUnknown, там называется http://en.wikipedia.org/wiki/Comb_sort#C. Алгоритм работает нормально, проверял на малых количествах чисел. Так что да же не знаю что тут сказать. Дело думается не в погрешности.

Автор: IUnknown 28.06.2011 21:13

Цитата
погонял сортировку алгоритмом расческой, так на моем ноуте Dual-Core 2.1 GHz . 2 гига ОЗУ, 100000 элементов сортирует показывает за 0.062 с. 30000000 примерно за 21 секунду.
Это реально? Просто что то сомнения гложат в этом направлении.
Это реально. В одном из описаний алгоритма встречал вот такое:

Цитата
"Пузырек" сортирует 10К элементов за 1.36 сек, тогда как "Расческа" - те же 10К элементов сортирует всего за 0.0042 сек., всего на 10% дольше, чем стандартный С-шный qiucksort(). Удивительно, что такое небольшое изменение алгоритма "пузырька" приводит к результатам, сравнимым с QuickSort. Более того, "Расческа" не требует никаких специальных действий для того, чтобы исключить потерю времени при обработке уже упорядоченных последовательностей.
Так что не сомневайся, это действительно очень быстрый метод...

Автор: Account 28.06.2011 21:30

Цитата(IUnknown @ 28.06.2011 22:13) *


Так что не сомневайся, это действительно очень быстрый метод...


Спасибо, а то что то меня это напрягало...

Автор: Account 29.06.2011 17:41

IUnknown, случаем не знаешь иностранных ресурсов(в наших путного не нашел ничего), где можно посмотреть графическое ( в виде графиков) отражение трудоемкости методов сортировки и их алгоритмов?

Автор: IUnknown 29.06.2011 17:55

У меня где-то был даже PDF, в котором сведены графики для некоторых алгоритмов сортировок (именно в параллельном варианте), вечером поищу...

Автор: Account 29.06.2011 19:57

IUnknown, заранее благодарю.
Еще вопрос такой. Ранее ты (если лучше на Вы, то скажи) давал ссылку на вот этот http://siber.cankaya.edu.tr/ozdogan/GraduateParallelComputing.old/ceng505/node132.html. не пойму вот что где тут цикл ,ведь по сути дела не один раз ведь нужно пройтись по четным и нечетным процессам или процессорам. Вижу только один раз сортировку(локальную), которая выполняется я так понимаю на всех узлах

qsort(elmnts, nlocal, sizeof(int), IncOrder); 


Далее я так понимаю код для распределения данных между процессами
for (i=0; i<npes-1; i++) { 
58 if (i%2 == 1) /* Odd phase */
59 MPI_Sendrecv(elmnts, nlocal, MPI_INT, oddrank, 1, relmnts,
60 nlocal, MPI_INT, oddrank, 1, MPI_COMM_WORLD, &status);
61 else /* Even phase */
62 MPI_Sendrecv(elmnts, nlocal, MPI_INT, evenrank, 1, relmnts,
63 nlocal, MPI_INT, evenrank, 1, MPI_COMM_WORLD, &status);

потом объединение и разбиение снова, но ведь это все не один раз должно произойти?
А то надо блок схему чертить, а я что то не догоню.

Автор: IUnknown 29.06.2011 21:06

Цитата
Далее я так понимаю код для распределения данных между процессами
Неправильно понимаешь. Это не код основного приложения. Это код, выполняющийся на каждом ядре. То есть, на каждом ядре сначала выполняется сортировка локальных данных, а потом начинается цикл, в течении которого это ядро связывается с соседними и обменивается с ними информацией, после чего полученную от соседа информацию совмещает (это CompareSplit) со своей локальной (это тоже сортировка, я ж показывал тебе выше, что таким образом совокупность elmnts + relmnts поддерживается в упорядоченном состоянии). В итоге каждое ядро содержит свою порцию данных, которые при объединении дают отсортированный массив.

Цитата
ведь это все не один раз должно произойти?
Угу. Полная сортировка - один раз, перед началом процесса. А потом - доупорядочивание с учетом данных, полученных по обмену с соседним процессом - в цикле. Причем, учитывая, что соседний процесс также получает данные из текущего (MPI_Sendrecv пересылает информацию в обе стороны: текущий elmnts -> соседний relmnts, и соседний elmnts -> текущий relmnts) - картинка складывается...

Для полноты картины не хватает пересылки порции реального массива в каждый процесс, и потом - объединения всех данных обратно в один массив-результат. Но я, к сожалению, MPI не очень хорошо владею, что называется, "читаю", но не пишу, поэтому добавить это не смогу...

Автор: Account 29.06.2011 22:15

А количесвто пересылок, выражается трудоемкостью алгоритма чет-нечет(n в квадрате) ?

Автор: IUnknown 29.06.2011 22:45

Каждый процесс посылает свою часть данных всем остальным процессам, и получает в ответ их данные. Это было не совсем верно: каждый с каждым не взаимодействует, скажем, если работают 6 процессов - то смысла связывать 2 и 5-ый нет: второй связывается только с теми, с кем он граничит, т.е., с 1-ым и с 3-им. Также, как пятый - только с 4-ым и с 6-ым. Но вот эти действия повторяются по количеству запущенных процессов, чтобы изменения в старших процессах (тех, которые контролируют максимальные индексы исходного массива) через промежуточные процессы достигли младших (контролирующих минимальные индексы), и наоборот. То есть, количество пересылок зависит от количества параллельно выполняемых процессов.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.1604&rep=rep1&type=pdf лежит PDF (165 Кб, англ.), о котором я говорил. Пока больше ничего вменяемого не нашлось.

Автор: Account 29.06.2011 23:14

IUnknown, огромное тебе спасибо за все. Очень помог.

Автор: Account 29.06.2011 23:36

Кстати, а вот с какого процесса начинается объединение блоков и их разделение.
например если если заполнить массив к убыванию 24 23 22 21 и так далее, а отсортировать естественно по возрастанию. Допустим имеем 24 числа, и 4 процессора. каждому по 6 чисел, 1 и 4 процессоры могут только взаимодействовать с 2 и 3 соответственно, тогда как 2 и 3 как с друг другом так и с ними, получается что будет 6 операций объединений и разделений или нет?

Автор: IUnknown 30.06.2011 2:11

Во-первых, я чуть-чуть поправил свой предыдущий пост, см. выше.

Теперь касаемо твоего вопроса: да, будет 6 сообщений между процессами. И 12 пересортировок (после каждого обмена сообщениями каждый процесс пересортировывает данные у себя). Вот, я прогнал тут свой код на этих данных (добавил служебные сообщения, кто кому что передал и кто от кого что получил):

Array :
24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
ID = 0 Even_Rank = 1 Accepted_From = 1
ID = 2 Even_Rank = 3 Accepted_From = 3
Sorter : ID = 0 Accepted_From = 1
Sorter : ID = 2 Accepted_From = 3
Sorter : ID = 1 Accepted_From = 0
Sorter : ID = 0 Accepted_From = -1
Sorter : ID = 3 Accepted_From = 2
ID = 1 Odd_Rank = 2 Accepted_From = 2
Sorter : ID = 2 Accepted_From = 1
Sorter : ID = 1 Accepted_From = 2
Sorter : ID = 3 Accepted_From = -1
ID = 0 Even_Rank = 1 Accepted_From = 1
Sorter : ID = 0 Accepted_From = 1
ID = 2 Even_Rank = 3 Accepted_From = 3
Sorter : ID = 0 Accepted_From = -1
Sorter : ID = 1 Accepted_From = 0
Sorter : ID = 2 Accepted_From = 3
Sorter : ID = 3 Accepted_From = 2
ID = 2 Odd_Rank = 1 Accepted_From = 1
Sorter : ID = 2 Accepted_From = 1
Sorter : ID = 1 Accepted_From = 2
Sorter : ID = 3 Accepted_From = -1
Result :
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24


При получении от (-1) пересортировки не производится, потому что фактически не было изменения данных, (-1) у меня - аналог MPI_PROC_NULL, так что его можно не считать. Остальных Sorter-ов ровно 12 штук. С какого процесса всё начинается - это без разницы: все процессы начинают работать одновременно, и пары процессов пересылают сообщения друг другу тоже одновременно (если ты запускаешь программу на машине с достаточным количеством ядер/процессоров).


Автор: Account 30.06.2011 2:28

Еще раз спасибо, разжевал и в рот положил можно сказать, теперь все ясно.