Тестирование реализованных последовательной и параллельной версий алгоритма проводилось на ЭВМ со следующей конфигурацией:
Intel(R) Core(TM) Duo CPU T2300 (1.66GHz); 1024MB RAM.
Результаты тестов представлены в таблице 1.
Таблица 1. Результаты экспериментов
|
Объем выборки |
Число ядер процессора |
Время выполнения (послед) |
Время выполнения (паралл) |
Ускорение |
Эффективность |
|
100000 |
2 |
0.025601 |
0.027104 |
0.944546 |
0.472273 |
|
200000 |
2 |
0.052273 |
0.053008 |
0.986134 |
0.493067 |
|
400000 |
2 |
0.079812 |
0.079814 |
0.999974 |
0.499987 |
|
400000 |
2 |
0.105175 |
0.103001 |
1.021106 |
0.510553 |
|
500000 |
2 |
0.131548 |
0.127379 |
1.032729 |
0.516365 |
|
600000 |
2 |
0.156423 |
0.147263 |
1.062201 |
0.531110 |
|
700000 |
2 |
0.186596 |
0.173961 |
1.072631 |
0.536317 |
|
800000 |
2 |
0.213400 |
0.185878 |
1.148064 |
0.574032 |
|
900000 |
2 |
0.243864 |
0.205865 |
1.184582 |
0.592291 |
|
1000000 |
2 |
0.277180 |
0.223671 |
1.239231 |
0.619615 |
Экспериментальным способом были вычислены основные характеристики коммуникационной сети используемой ЭВМ: латентность (как время на передачу сообщения нулевой длины; ~0.000140 с) и достижимая пропускная способность (количество мегабайт в секунду; ~70 МБайт/с), что позволило сравнить практические результаты с теоретическими (таблица 2).
Таблица 2. Сравнение теоретических и полученных результатов
|
Объем выборки |
Число ядер процессора |
Время выполнения (теор) |
Время выполнения (практ) |
|
100000 |
2 |
0.180060 |
0.027104 |
|
200000 |
2 |
0.034678 |
0.053008 |
|
300000 |
2 |
0.052398 |
0.079814 |
|
400000 |
2 |
0.070119 |
0.103001 |
|
500000 |
2 |
0.087927 |
0.127379 |
|
600000 |
2 |
0.109923 |
0.147263 |
|
700000 |
2 |
0.121495 |
0.173961 |
|
800000 |
2 |
0.140723 |
0.185878 |
|
900000 |
2 |
0.158774 |
0.205865 |
|
1000000 |
2 |
0.174297 |
0.223671 |
Из таблицы 2 видно, что наблюдаемое время сортировки несколько превосходит ожидаемое (на приведенных объемах выборки, в среднем, в 1.3 раза). Но мы также видим, что с увеличением объема выборки, полученные в экспериментах значения все ближе приближаются к теоретическим оценкам (т.е. с увеличением объема входных данных, погрешность вычислений уменьшается). Отсюда можно сделать вывод, что реализация алгоритма проведена довольно успешно.
