Измерьте параллельное ускорение в рандомизированных алгоритмах

У меня есть рандомизированная программа с последовательными и параллельными вариантами. Природа этой программы такова, что время ее выполнения сильно зависит от ее "удачи". Он регулярно принимает значения от 1 секунды до 2 минут в, казалось бы, геометрическом шаблоне распределения. Параллельные варианты показывают аналогичное поведение с разными номерами.

Каким же «хорошим» способом измерить параллельное ускорение в этом случае? У меня есть возможность просто использовать среднее / медианное значение измеренных значений как репрезентативное для «времени выполнения».

Как бы я объяснил такой подход и есть ли (статистически / математически) лучший способ рассчитать ускорение?

РЕДАКТИРОВАТЬ: Спасибо user3666197, который отметил некоторые очень важные технические детали, необходимые для получения хороших данных. Я сделал домашнее задание и хочу уточнить свой вопрос.

Я сделал свой тестовый процесс максимально надежным:

  • тесты выполняются с семенами, с которыми можно воспроизводить результаты.
  • каждая конфигурация повторяется несколько раз (~ 400 раз) с разными начальными числами внутри скрипта

У меня остается вопрос: Как подойти к расчету ускорения для этой программы.

Что я сделал:

Среднее время последовательной работы составляет около 8,38, медиана - 4,8, что является большой разницей. Для 2 потоков среднее время выполнения составляет 4,36, а среднее время выполнения - 2,42. Если я разделю последовательное на параллельное, я получу ускорение на 1,92 (среднее значение) и 1,992 (среднее значение). Для 4 потоков аналогично: означает: время выполнения 2,25 и 3,72 ускорения, медианы: 1,12 медиана и 4,3 ускорения (суперлинейная). Аналогичные числа существуют для 8 потоков.

Я пытаюсь визуализировать данные по-разному. Графики

Гистограмма показывает распределение времени выполнения с использованием различных потоков, как и прямоугольная диаграмма справа. Видно, что видно некоторое ускорение.

Если я объединю измерения на основе семян, я получу пары времен: последовательное и параллельное. Одна из моих первых идей заключалась в том, чтобы вычислить ускорение путем вычисления наклона линии регрессии, однако кажется, что линия регрессии не «суммирует» данные должным образом и имеет ограниченную ценность. На нижнем правом графике показаны только точки для 4 потоков.


parallel-processing benchmarking parallelism-amdahl
person Samuel Pilz    schedule 01.03.2018    source источник
comment
Я измеряю время с помощью команды unix /usr/bin/time. Однако использование любой другой метрики мало что изменит: программе может повезти быстро добраться до решения или может потребоваться больше времени для выполнения своей задачи на основе раздачи.   -  person Samuel Pilz    schedule 01.03.2018

Ответы (2)


arrow_upward
0
arrow_downward

Я бы порекомендовал вам вычислить ускорение на основе среднего арифметического времени выполнения достаточно большого набора измерений. Убедитесь, что вы правильно объяснили, что представляют собой числа. Может быть трудно гарантировать, что у вас есть достаточно большие настройки для расчета правильного среднего с определенной уверенностью, тем более, что ваши образцы не распределяются нормально. Включите свои выводы о распределении и конфиденциальности. Обязательно просуммируйте время выполнения, прежде чем вычислять ускорение.

Существует отличная статья Торстена Хефлера и Роберто Белли, в которой подробно освещает ваши проблемы. В частности, разделы 2.1.1 и 3.

person Zulan    schedule 05.03.2018
comment
Действительно ли среднее арифметическое является правильным измерением? Обратите внимание, что в моем случае это примерно вдвое больше медианы. А другие метрики возвращают даже другие значения. Какой из них самый лучший и почему? - person Samuel Pilz; 05.03.2018
comment
Подумайте об этом как о преобразовании вопроса к ускорению выполнения N казней. Общее время выполнения N казней. Это время имеет гораздо более узкое распределение и поэтому подходит для сравнения и вычисления ускорения. Ускорение для этой составной операции такое же, как если бы вы вычисляли его по среднему времени выполнения. Медиана гораздо более проблематична, если распределение отличается для последовательного / параллельного случая. В особых случаях могут быть аргументы в пользу других показателей, но это самый общий. В любом случае важно четко описать распределение и способ вычисления метрики. - person Zulan; 05.03.2018

arrow_upward
0
arrow_downward

Как измерить параллельное ускорение по сравнению с чистым [SERIAL] кодом?

Всегда будьте количественными и систематическими.

Это означает как минимум:

1) используйте все систематические шаги для контролируемой повторяемости теста
2) сравните яблоки с яблоками, в т. управляемая начальная установка для рандомизаторов
3) лучше всего, генерировать все батареи тестов как сценарии, автоповторяющиеся эксперименты
4) записывать производительность (общее время и время локальных секций) в UUID # -различимых журналах тестов 5) собирайте скорее популяции тестовых прогонов размером 1E + 3 ~ 1E + 4, а не просто несколько единиц отдельных испытаний

Учитывая, что ваше решение уже реализовано как в режиме чистого [ПОСЛЕДОВАТЕЛЬНОГО] выполнения кода, так и в каком-то другом [CONCURRENT] или даже [PARALLEL], наиболее точным шагом является сравнение продолжительности сквозного тестирования.

Довольно часто используются монотонные часы с разрешением лучше, чем ~ [us] в [TIME]-области.

Для получения дополнительных сведений о внутренних особенностях лучше всего просмотрите переформулированный закон Амдала и критику из первоначальной формулировки параллельного ускорения без ограничений по использованию ресурсов.

person user3666197    schedule 01.03.2018