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

       

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


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

Для оценки длительности ? базовой скалярной операции выбора минимального значения проводилось решение задачи поиска всех кратчайших путей при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций – в результате для величины ? было получено значение 7,14 нсек. Эксперименты, выполненные для определения параметров сети передачи данных, показали значения латентности и пропускной способности ? соответственно 130 мкс и 53,29 Мбайт/с. Все вычисления производились над числовыми значениями типа int, размер которого на данной платформе равен 4 байта (следовательно, w=4).

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

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

Кол-во вершинПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессора8 процессоровВремяУскорениеВремяУскорениеВремяУскорение
10008,0374,1521,9362,0673,8880,9418,544
200059,81230,3231,97215,3753,8908,0587,423
3000197,11199,2641,98650,2323,92425,6437,687
4000461,785232,5071,986117,2203,93969,9466,602
5000884,622443,7471,994224,4413,941128,0786,907


Рис. 10.4.  Графики зависимости ускорения параллельного алгоритма Флойда от числа используемых процессоров при различном количестве вершин графа

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


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


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

Для оценки длительности ? базовой скалярной операции проводилось решение задачи нахождения минимального охватывающего дерева при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций – в результате подобных экспериментов для величины ? было получено значение 4,76 нсек. Все вычисления производились над числовыми значениями типа int, размер которого на данной платформе равен 4 байта (следовательно, w=4).

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

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

Кол-во вершинПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессора8 процессоровВремяУскорениеВремяУскорениеВремяУскорение
10000,0440,2480,1760,9320,0471,5740,028
20000,2080,6840,3041,8000,1152,1590,096
30000,4851,4030,3462,2140,2193,1950,152
40000,8731,9460,6223,3240,2635,4310,161
50001,4322,6650,7362,9330,4884,1190,348
60002,1892,9000,8214,2910,5107,7370,283
70003,0423,2360,9406,3270,4818,8250,345
80004,1504,4620,9306,9930,59310,3900,399
90005,6225,8340,9647,4750,75210,7640,522
100007,5126,9901,0758,5970,87414,0950,533


Рис. 10.7.  Графики зависимости ускорения параллельного алгоритма Прима от числа используемых процессоров при различном количестве вершин в модели

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

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

Количество вершинПоследовательный алгоритмПараллельный алгоритм2 процессора4 процессора8 процессоров
10000,0440,4050,2480,8040,9321,2051,574
20000,2080,8200,6841,6131,8002,4122,159
30000,4851,2451,4032,4262,2143,6223,195
40000,8731,6791,9463,2453,3244,8345,431
50001,4322,1222,6654,0682,9336,0484,119
60002,1892,5752,9004,8964,2917,2657,737
70003,0423,0383,2365,7286,3278,4848,825
80004,1503,5104,4626,5666,9939,70510,390
90005,6223,9915,8347,4087,47510,92910,764
100007,5124,4826,9908,2558,59712,15514,095


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

Как можно заметить из табл. 10.4 и рис. 10.8, теоретические оценки определяют время выполнения алгоритма Прима с достаточно высокой погрешностью. Причина такого расхождения может состоять в том, что модель Хокни менее точна при оценке времени передачи сообщений с небольшим объемом передаваемых данных. Для уточнения получаемых оценок необходимым является использование других более точных моделей расчета трудоемкости коммуникационных операций – обсуждение этого вопроса проведено в лекции 3.



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