Потоковая безопасность доступа к памяти только для чтения

Question

Я реализовал гравитационный алгоритм Барнса-Хата в C следующим образом:

1. Постройте дерево из сгруппированных звезд.
2. Для каждой звезды пройдитесь по дереву и примените гравитационные силы от каждого соответствующего узла.
3. Обновление звездных скоростей и положений.

Этап 2 является самым дорогим этапом, и поэтому реализуется параллельно путем деления множества звезд. Например. при 1000 звездах и 2 потоках один поток обрабатывает первые 500 звезд, а второй поток обрабатывает вторые 500.

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

Меня беспокоит то, что два потока одновременно обращаются к одному и тому же ресурсу (а именно к дереву). Я не добавил никакой синхронизации к рабочим потоков, так что, вероятно, в какой-то момент они попытаются прочитать из того же места. Хотя доступ к дереву только для чтения, я не уверен на 100%, что он безопасен. Когда я это проверил, это сработало, но я знаю, что это не гарантия правильности!

Вопросы

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

Обновление Результаты тестов для любопытных:

Машина: процессор Intel Atom N270 @ 1,60 ГГц, процессор 800 МГц, объем кэш-памяти 512 КБ

Threads      real      user      sys
      0    69.056    67.324    1.720
      1    76.821    66.268    5.296
      2    50.272    63.608   10.585
      3    55.510    55.907   13.169
      4    49.789    43.291   29.838
      5    54.245    41.423   31.094

0 означает отсутствие потоков; 1 и выше означает, что порождает множество рабочих потоков, а основной поток ожидает их. Я не ожидал бы значительного улучшения чего-либо, кроме двух потоков, так как он полностью связан с процессором, и это число ядер. Интересно, что нечетное число потоков немного хуже, чем четное число.

Глядя на sys становится очевидным, что создание потоков стоит затрат. В настоящее время он создает потоки для каждого кадра (так что создается N * 1000 потоков). Это было легко запрограммировать (в течение моих 15 минут в поезде этим утром). Мне нужно немного подумать о том, как повторно использовать темы ...

Обновление # 2 Я заставил его использовать пул потоков, синхронизированных с двумя барьерами. Это не имеет заметного преимущества в производительности по сравнению с воссозданием потоков в каждом кадре.

Answer 1

Вы не указываете, как структурированы ваши данные, но в целом чтение памяти из нескольких потоков одновременно безопасно и не вызывает проблем с производительностью.Проблемы возникают, только если кто-то пишет.

Интересно, что вы говорите, что из двух потоков вы получаете ускорение только на 30%.Если у вас в противном случае простаивающая машина, два или более ЦП и только общие данные, предназначенные только для чтения (т. Е. Нет синхронизации), я ожидаю увидеть улучшение скорости на 50%.Это говорит о том, что ваша операция на самом деле завершается так быстро, что накладные расходы на создание потока становятся значительными в ваших цифрах.Вы работаете на многопоточном процессоре?

Answer 2

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

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