Машина, на которой производилось тестирование, имела процессор Intel Core 2 Quad Q6600 (2,40 ГГц) и 3,25 МБ оперативной памяти.

Графы, на которых проводилось тестирование, были получены путём преобразования дампов баз данных ряда вики-сетей. Статьи были превращены в вершины, ссылки — в рёбра.

Попробуем подсчитать теоретическое ускорение, например, для случая, когда граф wow просчитывается на двух процессах. Эксперименты показали следующее значение констант из раздела Анализ эффективности:

• α = 1,9 * 10^-9 c;
• β = 3,52 * 10^-8 c;
• k = 6;
• l = 5,57 * 10^-5 c;

Подставив их в теоретическую формулу, получим ускорение, равное 1,995. Однако видно, что экспериментальное ускорение намного хуже. Дело в том, что в данном случае нагрузка распределяется по процессам неравномерно.

Граф устроен так: есть одна крупная компонента сильной связности, в которой 29888 вершин; следующая по величине компонента насчитывает 17 вершин; а абсолютное большинство оставшихся вершин образуют компоненты размера один. Так как время обработки вершины пропорционально величине её компоненты, ясно, что большая часть уходит на обсчёт вершин из наибольшей компоненты. Однако среди половины графа, достающейся первому процессу, этих вершин 18108, а среди той, которую обсчитывал второй, только 11780. В предположении, что обсчёт всех остальных вершин занимает незначительное время, время параллельной работы пропорционально большему из этих чисел, а последовательной — их сумме. Таким образом, теоретическая оценка ускорения (без учёта коммуникации) составит (18108 + 11780) / 18108 ≈ 1,65, что достаточно близко к экспериментально полученному значению.