Тестирование алгоритма проводился на системе с характеристиками:
Intel(R) Core(TM) 2 Duo (2 GHz); 3072MB RAM.
Таблица 1. Результаты тестов:
|
Объем выборки |
Число ядер процессора |
Время выполнения (послед) |
Время выполнения (паралл) |
Ускорение |
Эффективность |
|
1000000 |
2 |
0.14 |
0.094 |
1.489361702 |
0.744680851 |
|
2000000 |
2 |
0.312 |
0.219 |
1.424657534 |
0.712328767 |
|
5000000 |
2 |
0.984 |
0.75 |
1.312 |
0.656 |
|
10000000 |
2 |
2.781 |
2.109 |
1.318634424 |
0.659317212 |
|
20000000 |
2 |
8.594 |
5.469 |
1.57140245 |
0.785701225 |
|
50000000 |
2 |
44.562 |
25.313 |
1.7604393 |
0.88021965 |
Для тестируемой системы, используя MPI_Wtime, найдена латентность, пропускная способность системы и, используя обычный clock, время операции перестановки элементов массива.
α = 0,000003с
t = 1.5*10^(-9)c
Так как элементы массива - простой int, w = 4.
Для формулы вычисления времени, затрачивающегося на параллельный алгоритм, n2...nk = 0, так как процессов только 2, n1 = 3/4.
Таблица 2. Сравнение теоретических и полученных результатов
|
Объем выборки |
Число ядер процессора |
Время выполнения (теор) |
Время выполнения (практ) |
|
1000000 |
2 |
0,208605738 |
0.094 |
|
2000000 |
2 |
0,417955076 |
0.219 |
|
5000000 |
2 |
1,047356706 |
0.75 |
|
10000000 |
2 |
2,098457012 |
2.109 |
|
20000000 |
2 |
4,204407625 |
5.469 |
|
50000000 |
2 |
10,53579561 |
25.313 |
Такому различию результатов одно обьяснение - каждый раз результаты быстрой сортировки разные, всё зависит от элементов массива, то есть от того как он делится. Из-за немодифицированности алгоритма он медленнее, чем предполагалось теоритически, считает большое количество элементов.
