Тестирование реализованных последовательной и параллельной версий алгоритма
проводилось на следующих машинах:
1) Intel® Pentium® Processor T4300 @ 2.10GHz 3.25GB RAM;
2) Intel(R) Core(TM) 2 Quad CPU @ 2.41GHz 3.25GB RAM.
Результаты тестов представлены в следующей таблице:
Практические результаты (время работы программ в секундах, "Без
у.п.д" - без учета передачи данных)
|
Количество
элементов |
Время
работы программы |
|
последов. |
на
2х
процессах |
Ускорение |
на 4х
процессах |
Ускорение |
|
Общее |
Без
у.п.д. |
Общее |
Без
у.п.д. |
Общее |
|
100
000 |
0.031 |
0.0249 |
0.0254 |
1.22 |
0.01467 |
0.01563 |
1.98 |
|
500
000 |
0.14 |
0.1177 |
0.1196 |
1.17 |
0.06971 |
0.07256 |
1.57 |
|
1 000
000 |
0.334 |
0.1734 |
0.1775 |
1.88 |
0.10647 |
0.11156 |
2.99 |
|
5 000
000 |
1.498 |
0.8345 |
0.8520 |
1.76 |
0.53316 |
0.56873 |
2.63 |
|
10 000 000 |
3.325 |
1.6852 |
1.7303 |
1.92 |
1.31856 |
1.47007 |
2.26 |
|
30 000
000 |
9.391 |
5.3098 |
5.4147 |
1.73 |
3.67527 |
3.82968 |
2.45 |
Как видно из полученных результатов мы
не получаем максимального ускорения при сравнительно небольших размерах массива. Данный факт можно объяснить
тем, что при размерах массива меньше одного миллиона сортировка слиянием
показывает весьма неплохие результаты, т.е. среди других видов сортировок она занимает далеко не последнее место, поэтому упорядочивание небольшого
числа элементов занимает сравнительно небольшое время и на одном
процессе. При больших же размерах массива мы затрачиваем дополнительное времени на пересылку
большого объема данных от одного процесса другому, что так же
сказывается на времени работы программы. Так, при работе на
"четырехядерной машине" отсутсвие серьезного выигрыша связано с тем,
что между блоками ядер (т.к. ядра объеденены в два блока по два
ядра), происходит "явная передача данных", тогда как при
работе на двухядерном процессоре с его стороны возможна оптимизация передачи данных,
т.е. как таковая она может и не происходить. Так же очевидно, что
при увеличении колличества процессов, мы увеличиваем колличество передач
данных и, так как функции передачи данных
являются блокирующими,- мы не получаем ожидаемого существенного уменьшения времени
работы программы.
