Вычислительные эксперименты для оценки эффективности параллельного варианта метода быстрой сортировки Использовался вычислительный узел на базе процессора AMD Turion(tm) X2 Ultra Dural-Coral Mobile ZM-80 2.1 Hz кэш L2 4 Мб, 4 Гб RAM под управлением операционной системы Microsoft Windows 7 Ultimate. Разработка программ проводилась в среде Microsoft Visual Studio 2005. Результаты вычислительных экспериментов приведены в таблице. Времена выполнения алгоритмов указаны в секундах.

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

 

Размер массива	Последовательный алгоритм	Параллельный алгоритм (2 процессора)	Теоретическое время (2 процессора)	Ускорение
30000000	51.463	73.796	73.796	0.69
50000000	122.224	133.49	110.8	0.91
60000000	206.33	147.704	122.56	1.4
70000000	228.43	159.45	132.2	1.44
80000000	263.61	187.53	155.54	1.51

На эффективность работы как последовательного, так и параллельного алгоритма быстрой сортировки сильно влияет результат выбора ведущего элемента. Поэтому для того, чтобы получить неслучайные результаты эксперимента, его нужно проводить несколько раз и усреднять значения для каждого n. Результаты приведены в таблице.

Основные характеристики коммуникационной сети были вычислены экспериментальным способом. На используемой ЭВМ: латентность (как время на передачу сообщения нулевой длины; ~0.0002 с) и достижимая пропускная способность (количество мегабайт в секунду; ~60 МБайт/с), что позволило сравнить практические результаты с теоретическими.

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