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

Эксперименты осуществлялись на вычислительном кластере Нижегородского университета на базе процессоров 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 процессораВремяУскорениеВремяУскорение

10000	0,001422	0,002210	0,643439	0,003270	0,434862
20000	0,002991	0,004428	0,675474	0,004596	0,650783
30000	0,004612	0,006745	0,683766	0,006873	0,671032
40000	0,006297	0,008033	0,783891	0,009107	0,691446
50000	0,008014	0,009770	0,820266	0,010840	0,739299

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

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

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

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

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

10000	0,001422	0,002959	0,480568	0,007509	0,189373
20000	0,002991	0,004557	0,656353	0,009826	0,304396
30000	0,004612	0,006118	0,753841	0,012431	0,371008
40000	0,006297	0,008461	0,744238	0,017009	0,370216
50000	0,008014	0,009920	0,807863	0,019419	0,412689

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

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

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

Количество элементовПараллельный алгоритм2 процессора4 процессора

1000	0,002684	0,002959	0,002938	0,007509
20000	0,004872	0,004557	0,004729	0,009826
30000	0,007100	0,006118	0,006538	0,012431
40000	0,009353	0,008461	0,008361	0,017009
50000	0,011625	0,009920	0,010193	0,019419

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

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

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

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

10000	0,001422	0,001521	0,934911	0,003434	0,414094
20000	0,002991	0,002234	1,338854	0,004094	0,730581
30000	0,004612	0,003080	1,497403	0,005088	0,906447
40000	0,006297	0,004363	1,443273	0,005906	1,066204
50000	0,008014	0,005486	1,460809	0,006635	1,207837

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

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

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

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

Количество элементовПараллельный алгоритм2 процессора4 процессора

10000	0,001280	0,001521	0,001735	0,003434
20000	0,002265	0,002234	0,002321	0,004094
30000	0,003289	0,003080	0,002928	0,005088
40000	0,004338	0,004363	0,003547	0,005906
50000	0,005407	0,005486	0,004175	0,006635

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

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

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

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

10000	0,001422	0,001485	0,957576	0,002898	0,490683
20000	0,002991	0,002180	1,372018	0,003770	0,793369
30000	0,004612	0,003077	1,498863	0,004451	1,036172
40000	0,006297	0,003859	1,631770	0,004721	1,333828
50000	0,008014	0,005041	1,589764	0,005242	1,528806

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

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

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

Количество элементовПараллельный алгоритм2 процессора4 процессора

10000	0,001281	0,001485	0,001735	0,002898
20000	0,002265	0,002180	0,002322	0,003770
30000	0,003289	0,003077	0,002928	0,004451
40000	0,004338	0,003859	0,003547	0,004721
50000	0,005407	0,005041	0,004176	0,005242

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

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

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

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

10000	0,001422	0,001513	0,939855	0,001166	1,219554
20000	0,002991	0,002307	1,396489	0,002081	1,437290
30000	0,004612	0,003168	1,455808	0,003099	1,488222
40000	0,006297	0,004542	1,386394	0,003819	1,648861
50000	0,008014	0,005503	1,456297	0,004370	1,833867

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

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

Количество элементовПараллельный алгоритм2 процессора4 процессора

10000	0,001533	0,001513	0,001762	0,001166
20000	0,002569	0,002307	0,002375	0,002081
30000	0,003645	0,003168	0,003007	0,003099
40000	0,004747	0,004542	0,003652	0,003819
50000	0,005867	0,005503	0,004307	0,004370

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

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

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