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

Question

У меня вопрос относительно измерений времени выполнения в параллельных программах (я использовал C++, но я думаю, что вопрос более общий).

Некоторые короткие пояснения: 3 потока работают параллельно (pthread), решая одну и ту же проблему по-разному. Каждый поток может передавать информацию другому потоку (например, частичные решения, полученные одним потоком, но не другим) для ускорения других потоков, в зависимости от его собственного состояния/доступной информации в его собственных расчетах. Весь процесс останавливается, как только первый поток готов. Теперь я хотел бы иметь уникальное измерение времени для оценки времени выполнения от начала до устранения проблемы. (В конце концов, я хочу определить, будет ли использование синергетических эффектов параллельным вычислением быстрее, чем вычисление на одном потоке).

На мой взгляд, проблема в том, что (из-за того, что операционная система приостанавливает/приостанавливает отдельные потоки), точка, когда информация передается в процессе, не детерминирована в каждом состоянии процесса. Это означает, что некоторая информация получена после xxx единиц времени процессора в потоке 1, но она не может контролироваться, независимо от того, получает ли поток 2 эту информацию после yyy или zzz единиц времени процессора, затраченного на его вычисления. Предполагается, что эта информация в любом случае завершила бы расчет потока 2, время выполнения потока 2 было либо yyy, либо zzz, в зависимости от действия операционной системы.

Что я могу сделать для получения детерминированного поведения для сравнения времени выполнения? Могу ли я заказать операционную систему для запуска каждого потока «без помех» (на многоядерном компьютере)? Есть ли что-то, что я могу сделать для реализации (C++) - основы?

Или существуют другие понятия для оценки времени выполнения (времени) таких реализаций?

С наилучшими пожеланиями Мартин

Answer 1

Каждый раз, когда кто-то использует термины «детерминированный» и «многоядерной» в одном предложении, он устанавливает тревогу звон :-)

Есть две большие источники индетерминизма в вашей программе: 1) операционная система, которая добавляет шум к таймингам потоков через решения по джиттеру ОС и планирования; и 2) алгоритм, потому что программа следует по другому пути в зависимости от порядка, в котором происходит связь (частичных решений).

Как программист, вы почти ничего не можете сделать о шуме ОС.Стандартная ОС добавляет много шума даже для программы, работающей на выделенном (покоящемся) узле. Специальные операционные системы для вычислительных узлов каким-то образом уменьшают этот шум, например Blue Gene systems exhibit significantly less OS noise and therefore less variation in timings.

Что касается алгоритма, вы можете ввести детерминизм в свою программу, добавив синхронизацию. Если два потока синхронизируются, например, для обмена частичными решениями, то порядок вычислений до и после синхронизации является детерминированным. Ваш текущий код является асинхронным, так как один поток «отправляет» частичное решение, но не ожидает, что он будет «принят». Вы можете преобразовать это в детерминированный код, разделив вычисление на этапы и синхронизируя потоки после каждого шага. Например, для каждого потока:

1. Compute один шаг
2. частичное решение записи (если таковые имеются)
3. Барьерный - ждать всех других потоков
4. Read частичные решения от других потоков
5. Повтор 1 -4

Конечно, мы не ожидаем, что этот код также будет работать, потому что теперь каждый поток должен ждать завершения всех остальных потоков их вычисления, прежде чем перейти к следующему шагу.

Лучший подход, вероятно, заключается в том, чтобы просто принять недетерминизм и использовать статистические методы для сравнения ваших таймингов. Запустите программу много раз для заданного количества потоков и запишите диапазон, среднее и стандартное отклонение таймингов. Этого может быть достаточно для того, чтобы вы знали, например. максимальное время вычислений для всех прогонов для заданного количества потоков, или вам может понадобиться статистический тест, например Student's t-test, для ответа на более сложные вопросы типа «насколько уверен, что увеличение от 4 до 8 потоков уменьшает время выполнения?». Как говорит DanielKO, колебания в таймингах - это то, что на самом деле будет испытывать пользователь, поэтому имеет смысл измерять их и количественно оценивать их статистически, а не стремиться к их устранению в целом.

Answer 2

Какая польза от такого измерения?

Предположим, вы можете каким-либо надуманным способом настроить планировщик ОС таким образом, чтобы потоки без проблем (даже косвенными событиями, такими как другие процессы с использованием кешей, MMU и т. Д.), Будут реалистичными для фактического использование параллельной программы?

Для современной ОС довольно редко допускается применение приложения для управления общей обработкой прерываний, управления памятью, планирования потоков и т. Д. Если вы не говорите напрямую с металлом, ваши детерминированные измерения будут не только непрактичными, но и пользователи вашей программы никогда не будут испытывать их (если они не будут одинаково близки к металлу, как при измерениях).

Итак, мой вопрос: зачем вам такие строгие условия для измерения вашей программы? В общем случае, просто принимайте колебания, так как это, скорее всего, увидит пользователи. Если ускорение определенного алгоритма/реализации настолько незначителен, чтобы быть неотличимым от фонового шума, это более полезная информация для меня, чем знание фактической доли ускорения.