Данный проект реализует вычисление площади многоугольника, заданного списком координат вершин, с использованием параллельного программирования на OpenMP.
Цель - показать, как можно ускорить вычисления за счет распараллеливания задач.
Для вычисления площади многоугольника используется формула Гаусса:
Где (x_i, y_i) - координаты вершин многоугольника.
OpenMP позволяет параллелить циклы, что эффективно увеличивает скорость выполнения программы на многоядерных процессорах. В нашем случае, основная вычислительная нагрузка приходится на цикл, который суммирует произведения координат. Этот цикл был распараллелен с использованием OpenMP.
Параллельное вычисление позволяет распределить нагрузку между несколькими ядрами процессора. В данном случае, цикл, который суммирует произведения координат, разбивается на несколько частей, каждая из которых выполняется в отдельном потоке. Это существенно сокращает время выполнения по сравнению с однопоточным вычислением, особенно на многоядерных процессорах.
Использование директивы reduction в OpenMP обеспечивает потокобезопасность для переменной sum.
- Директива
reduction(+:sum)создает копии переменнойsumдля каждого потока. - Каждый поток выполняет свои вычисления на своей копии
sum. - После завершения всех потоков, значения копий складываются в основную переменную
sum.
Таким образом, обеспечивается корректность и безопасность выполнения параллельных операций на общей переменной.
touch input.txt && g++ input_creator.cpp && ./a.outПосле этого остается ввести необходимое кол-во строек.
Для macos приходится попотеть и кривыми схемами устанавливать llvm ОБЯЗАТЕЛЬНО ИЗ brew, поскольку apple в какой-то момент решили сломаться. Решение тут, ну и множество вопросов на stack overflow.
После настройки запустить можно следующим образом (предварительно подготовив файл для запуска).
mkdir -p build && cd build && cmake .. && makeДля запуска с замером времени использовать
time ./openmp_examplesДля создания тестовых данных была написана программа input_creator.cpp, которая быстро генерировала множество точек на окружности в какой-нибудь файл.
Файлы для испытаний будут прикреплены к основному заданию.
Стоит отметить, что в процессе исследования выяснилось, что чтение из файла занимает существенное время работы,
поэтому было решено изменять время работы подсчета площади многоугольника непосредственно в коде с помощью библиотеки ctime.
Также было замечено, что логика работы и скорость на macos с arm и x86_64 существенно отличается. Как правило на arm-ах выигрыша от многопоточки от чего-то не выходит, возможное объяснение есть тут
Apple сломала совместимость с openmp и использование clang++ компилятора из homebrew значительно медленнее работает не смотря на то, что я указываю архитектуру и т.д.
В результате такого исследования было решено тестировать на WSL с процессором x86_64.
Кол-во потоков: 4
Прирост производительности почти незаметен, а изменение кол-ва потоков скорее ведет к спаду производительности, чем к приросту.
| кол-во вершин | время работы однопоточного режима | многопоточка OpenMP (2 потока) | многопоточка OpenMP (4 потока) | многопоточка OpenMP (8 потоков) | многопоточка OpenMP (16 потоков) | Вывод |
|---|---|---|---|---|---|---|
| 100 | 0.000003000 | 0.000207000 (new) | 0.000005000 (new) | 0.000074000 (new) | 0.000095000 (new) | однопоотчка быстрее |
| 1 000 000 | 0.130138000 | 0.009471000 (old) | 0.008775000 (new) | 0.013615000 (new) | 0.018686000 (new) | 2 и 4 потока были самыми оптимальными |
| 100 000 000 | 3.490356000 | 0.833055000 (old) | 0.935590000 (old) | 1.913427000 (old) | 3.118724000 (old) | 2 и 4 потока были самыми оптимальными |
Распараллеливание вычислений с использованием OpenMP позволяет значительно ускорить процесс за счет эффективного использования ресурсов многоядерных процессоров.
Однако для процессоров arm на макбуках производительность не вырастает, как ожидалось. Скорее всего это связанно с необходимостью устанавливать сторонних библиотек unix. И в условиях столь малой задачи расходы на конкурентный доступ значительно используя многопоточку значительно выше, чем работа однопоточная.
Я уверен, что если бы задача занимала более продолжительное время, то прирост производительности был бы значительно выше.