Вычисления проводились на процессоре Intel(R) Core(TM) Duo 2 Centrino 2 CPU P8400 (2.24GHz); 4096MB RAM.

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

 

Размер массива	Последовательный алгоритм	Параллельный алгоритм	Ускорение	Эффективность
100000	0.015	0.017	0.88	0.44
500000	0.125	0.115	1.08	0.54
700000	0.154	0.136	1.13	0.57
1000000	0.22	0.171	1.28	0.64
5000000	1.27	0.86	1.47	0.74

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

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

Сравнение теоретических и практических результатов (p=2)

 

Размер массива	Практическое время	Теоретическое время
100000	0.017	0.012
500000	0.115	0.07
700000	0.136	0.09
1000000	0.171	0.13
5000000	0.86	0.75

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