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

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

1000	8,037	4,152	1,936	2,067	3,888	0,941	8,544
2000	59,812	30,323	1,972	15,375	3,890	8,058	7,423
3000	197,111	99,264	1,986	50,232	3,924	25,643	7,687
4000	461,785	232,507	1,986	117,220	3,939	69,946	6,602
5000	884,622	443,747	1,994	224,441	3,941	128,078	6,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. Результаты вычислительных экспериментов для параллельного алгоритма Прима

1000	0,044	0,248	0,176	0,932	0,047	1,574	0,028
2000	0,208	0,684	0,304	1,800	0,115	2,159	0,096
3000	0,485	1,403	0,346	2,214	0,219	3,195	0,152
4000	0,873	1,946	0,622	3,324	0,263	5,431	0,161
5000	1,432	2,665	0,736	2,933	0,488	4,119	0,348
6000	2,189	2,900	0,821	4,291	0,510	7,737	0,283
7000	3,042	3,236	0,940	6,327	0,481	8,825	0,345
8000	4,150	4,462	0,930	6,993	0,593	10,390	0,399
9000	5,622	5,834	0,964	7,475	0,752	10,764	0,522
10000	7,512	6,990	1,075	8,597	0,874	14,095	0,533

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

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

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

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

1000	0,044	0,405	0,248	0,804	0,932	1,205	1,574
2000	0,208	0,820	0,684	1,613	1,800	2,412	2,159
3000	0,485	1,245	1,403	2,426	2,214	3,622	3,195
4000	0,873	1,679	1,946	3,245	3,324	4,834	5,431
5000	1,432	2,122	2,665	4,068	2,933	6,048	4,119
6000	2,189	2,575	2,900	4,896	4,291	7,265	7,737
7000	3,042	3,038	3,236	5,728	6,327	8,484	8,825
8000	4,150	3,510	4,462	6,566	6,993	9,705	10,390
9000	5,622	3,991	5,834	7,408	7,475	10,929	10,764
10000	7,512	4,482	6,990	8,255	8,597	12,155	14,095

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

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

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