Теория и практика параллельных вычислений

       

Результаты вычислительных экспериментов


Эксперименты осуществлялись на вычислительном кластере Нижегородского университета на базе процессоров Intel Xeon 4 EM64T, 3000 МГц и сети Gigabit Ethernet под управлением операционной системы Microsoft Windows Server 2003 Standard x64 Edition и системы управления кластером Microsoft Compute Cluster Server.

Для оценки длительности ? базовой скалярной операции алгоритма сортировки проводилось решение задачи упорядочивания при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций – в результате выполненных экспериментов для величины ? было получено значение 10,41 нсек. Эксперименты, выполненные для определения параметров сети передачи данных, показали значения латентности

и пропускной способности ? соответственно 130 мкс и 53,29 Мбайт/с. Все вычисления производились над числовыми значениями типа double, размер которого на данной платформе равен 8 байт (следовательно w=8).

Результаты вычислительных экспериментов приведены в табл. 9.2. Эксперименты выполнялись с использованием двух и четырех процессоров.

Таблица 9.2. Результаты вычислительных экспериментов для параллельного алгоритма пузырьковой сортировки

Количество элементовПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессораВремяУскорениеВремяУскорение
100000,0014220,0022100,6434390,0032700,434862
200000,0029910,0044280,6754740,0045960,650783
300000,0046120,0067450,6837660,0068730,671032
400000,0062970,0080330,7838910,0091070,691446
500000,0080140,0097700,8202660,0108400,739299


Рис. 9.1.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма пузырьковой сортировки

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


Вычислительные эксперименты для оценки эффективности параллельного варианта сортировки Шелла осуществлялись при тех же условиях, что и ранее выполненные (см. п. 9.3.6).

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

Таблица 9.4. Результаты вычислительных экспериментов для параллельного алгоритма сортировки Шелла

Количество элементовПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессораВремяУскорениеВремяУскорение
100000,0014220,0029590,4805680,0075090,189373
200000,0029910,0045570,6563530,0098260,304396
300000,0046120,0061180,7538410,0124310,371008
400000,0062970,0084610,7442380,0170090,370216
500000,0080140,0099200,8078630,0194190,412689


Рис. 9.4.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма сортировки Шелла

Сравнение времени выполнения эксперимента и теоретической оценки Tp из (9.7) приведено в таблице 9.5 и на рис. 9.5.

Таблица 9.5. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма сортировки Шелла

Количество элементовПараллельный алгоритм2 процессора4 процессора
10000,0026840,0029590,0029380,007509
200000,0048720,0045570,0047290,009826
300000,0071000,0061180,0065380,012431
400000,0093530,0084610,0083610,017009
500000,0116250,0099200,0101930,019419


Рис. 9.5.  График зависимости экспериментального и теоретического времени проведения эксперимента на двух процессорах от объема исходных данных




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

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

Таблица 9.6. Результаты вычислительных экспериментов по исследованию параллельного алгоритма быстрой сортировки

Количество элементовПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессораВремяУскорениеВремяУскорение
100000,0014220,0015210,9349110,0034340,414094
200000,0029910,0022341,3388540,0040940,730581
300000,0046120,0030801,4974030,0050880,906447
400000,0062970,0043631,4432730,0059061,066204
500000,0080140,0054861,4608090,0066351,207837

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

Сравнение времени выполнения эксперимента и теоретической оценки Tp из (9.11) приведено в таблице 9.7 и на рис. 9.8.


Рис. 9.7.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма быстрой сортировки

Таблица 9.7. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма быстрой сортировки

Количество элементовПараллельный алгоритм2 процессора4 процессора
100000,0012800,0015210,0017350,003434
200000,0022650,0022340,0023210,004094
300000,0032890,0030800,0029280,005088
400000,0043380,0043630,0035470,005906
500000,0054070,0054860,0041750,006635




Рис. 9.8.  График зависимости экспериментального и теоретического времени проведения эксперимента на двух процессорах от объема исходных данных




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

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

Таблица 9.8. Результаты вычислительных экспериментов для параллельного алгоритма обобщенной быстрой сортировки

Количество элементовПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессораВремяУскорениеВремяУскорение
100000,0014220,0014850,9575760,0028980,490683
200000,0029910,0021801,3720180,0037700,793369
300000,0046120,0030771,4988630,0044511,036172
400000,0062970,0038591,6317700,0047211,333828
500000,0080140,0050411,5897640,0052421,528806


Рис. 9.9.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма обобщенной быстрой сортировки

Сравнение времени выполнения эксперимента и теоретической оценки Tp из (9.12) приведено в таблице 9.9 и на рис. 9.10.

Таблица 9.9. Сравнение экспериментального и теоретического времен выполнения параллельного алгоритма обобщенной быстрой сортировки

Количество элементовПараллельный алгоритм2 процессора4 процессора
100000,0012810,0014850,0017350,002898
200000,0022650,0021800,0023220,003770
300000,0032890,0030770,0029280,004451
400000,0043380,0038590,0035470,004721
500000,0054070,0050410,0041760,005242


Рис. 9.10.  График зависимости экспериментального и теоретического времени проведения эксперимента на четырех процессорах от объема исходных данных




Вычислительные эксперименты для оценки эффективности параллельного варианта сортировки с использованием регулярного набора образцов осуществлялись при тех же условиях, что и ранее выполненные (см. п. 9.3.6).

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

Таблица 9.10. Результаты вычислительных экспериментов для параллельного алгоритма сортировки с использованием регулярного набора образцов

Количество элементовПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессораВремяУскорениеВремяУскорение
100000,0014220,0015130,9398550,0011661,219554
200000,0029910,0023071,3964890,0020811,437290
300000,0046120,0031681,4558080,0030991,488222
400000,0062970,0045421,3863940,0038191,648861
500000,0080140,0055031,4562970,0043701,833867


Рис. 9.12.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма сортировки с использованием регулярного набора образцов

Таблица 9.11. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма сортировки с использованием регулярного набора образцов

Количество элементовПараллельный алгоритм2 процессора4 процессора
100000,0015330,0015130,0017620,001166
200000,0025690,0023070,0023750,002081
300000,0036450,0031680,0030070,003099
400000,0047470,0045420,0036520,003819
500000,0058670,0055030,0043070,004370

Сравнение времени выполнения эксперимента и теоретической оценки Tp из (9.17) приведено в таблице 9.11 и на рис. 9.13.


Рис. 9.13.  График зависимости экспериментального и теоретического времени проведения эксперимента на четырех процессорах от объема исходных данных



Содержание раздела