BC/NW (35):2.1
К ВОПРОСУ ОБ ИСПОЛЬЗОВАНИИ СОВРЕМЕННЫХ МНОГОЯДЕРНЫХ МИКРОПРОЦЕССОРОВ ДЛЯ РЕШЕНИЯ ПОВСЕДНЕВНЫХ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
Гнатко О.О., Филатов А.В.
В статье написанной в соавторстве студентом и его руководителем, пойдёт речь о необходимости введения в культуру современного повседневного программирования навыков программирования многоядерных процессоров и будет предложена наиболее простая в освоении (на взгляд авторов) технология параллельного программирования.
Решение современных математических задач – очень долгий и трудоемкий процесс. С появлением вычислительной техники стало возможным решение задачи в автономном режиме: человек подает исходные данные в машину, которая, в свою очередь, выполняет вычисления по заданному алгоритму. В начале развития вычислительная техника была очень медленной и могла выдавать результат спустя часы, дни или месяцы, в зависимости от сложности задач. С одной стороны, с развитием технологий время, затрачиваемое на решение задач, стало уменьшаться, с другой стороны, стали появляться все более трудоемкие задачи, которые может решать вычислительная техника.
В течение более полувека самыми доступными для большинства пользователей были однопроцессорные вычислительные системы, снабжённые одноядерным микропроцессором (процессором). За это время фактически сформировалась настоящая культура последовательного программирования таких систем и обучения ему. Ситуация начала постепенно меняться с 2002-го года, когда IBM, а затем и AMD с Intel выпустили свои первые многоядерные процессоры. Фактически последнее десятилетие мы живём в новой эре – всеобщей доступности мультипроцессорной техники для рядовых пользователей. Поэтому теперь стоит задача всеобщего обучения технологиям параллельного программирования и формировании новой программистской культуры.
Не сегодняшний день создан ряд технологий параллельного программирования, ориентированных на широкое применение. В НИУ «МЭИ» уже пару десятков лет ведётся преподавание этих технологий, в том числе и одним из соавторов данной статьи. В статье конкретно речь коротко поидёт о технологиях программирования OpenMP и MPI. Используя их, любой более-менее подготовленный программист сможет получить ускорение решения задач за счёт использования многоядерности своего процессора.
Решение систем линейных алгебраических уравнений на многоядерных микропроцессорах.
Для начала представляем Вам результаты небольшой учебно-практической студенческой исследовательской работы.
Работа посвящена реализации решения систем линейных алгебраических уравнений (СЛАУ) средствами параллельного программирования. Основные методы решениям систем являются последовательными, их выполнение происходит на одном центральном процессоре с одним ядром, но с увеличением размерности системы сильно возрастает время нахождения результатов. Для ускорения процесса вычислений есть несколько путей. Первый – увеличение тактовой частоты процессора. Данное решение активно применялось ранее, но в настоящее время зашло в тупик. Причиной этому стало множество факторов: возрастание электропотребления, повышение тепловыделения, внутренняя архитектура процессора, ограничения технологического процесса. Второй путь – распараллеливание вычислений. В этом случае программа разбивается на группы команд, которые могут независимо выполняться на нескольких ядрах процессора или же какие-то части программы выполняются на разных ядрах процессора одновременно, но при этом обрабатываются разные данные. Данный путь более гибкий и позволяет значительно уменьшить время решения задачи.
Актуальность работы по распараллеливанию заключается в том, что решение систем алгебраических уравнений является важным математическим аппаратом и применяется как обособленно, так и в составе алгоритмов решения более сложных задач. Сокращение времени решения СЛАУ может в свою очередь заметно сократить общее время решения этих сложных задач. Примерами технологий параллельного программирования для решения такого рода задач могут выступить: OpenMP, MPI, Nvidia CUDA, OpenCL. Каждая из этих технологий специализируется на своем типе вычислительных систем, имеет достоинства и недостатки.
В работе в качестве языка программирования выбран язык C++. А поскольку программирование будет осуществлено только для ядер центрального процессора (без дополнительных ускорителей), то было решено остановиться на технологиях OpenMP и MPI.
Технология OpenMP поддерживается языками С, С++ и Фортран. Для MPI существуют реализации для языков Фортран, С, С++ и Java.
Из поддерживаемых языков был выбран С++, как наиболее доступный. Данный язык поддерживает как функциональное, так и объектно-ориентированное программирование. Так же обеспечиваются основные свойства объектно-ориентированного программирования: инкапсуляция, наследование и полиморфизм. Программист имеет доступ к управлению памяти (выделение и очистка), что позволяет оптимизировать работу с памятью вручную с одной стороны, но требует дополнительной внимательности и квалификации с другой.
Язык С++ поддерживается в среде разработки Visual Studio, которая имеет широкий набор инструментов для разработки программ. В Visual Studio, начиная с версии 2008 года, интегрирована поддержка OpenMP стандарта 2.0, благодаря чему не требуется подключение сторонних библиотек и установка дополнительных программ. Для применения технологий MPI потребуется установка соответствующих инструментов разработки и библиотеки (например: Microsoft MPI 9.0).
Системы линейных уравнений решаются либо точными методами, либо приближёнными итерационными. Для проведения экспериментов были разработаны варианты программ, выполняющих известный последовательный алгоритм точного решения систем линейных уравнений методом Гаусса и два параллельных с применением OpenMP и MPI тем же методом. Тестирование программ проводилось на персональном компьютере со следующими характеристиками:
· четырехъядерный процессор Intel Core i7-4790 3.60 GHz
· 64-разрядная ОС Windows 7 Professional
· Компилятор MS Visual Studio 2015 Community
Следует заметить, что метод Гаусса относится к точным, но при этом к сложно распараллеливаемым методам. Для сравнения времени выполнения СЛАУ и выбора оптимального режима решения проведены эксперименты с системами следующих размерностей: 100, 300, 500, 1000, 2000, 5000 и 10000 уравнений. Все размерности тестируются в каждом режиме: последовательный, параллельный с технологией OpenMP и параллельный с технологией MPI. Для параллельных программ рассчитывается коэффициент ускорения
где Tпослед – время выполнения программы в последовательном режиме,
Tпаралл - время выполнения в одном из параллельных режимов.
Результат проведенных тестирований представлен в таблице
Решение СЛАУ методом Гаусса с помощью
последовательной
программы, OpenMP и MPI программ
|
Размерность системы |
Последовательная |
OpenMP |
MPI |
||
|
Время выполнения, с |
Время выполнения, с |
Ускоре-ние |
Время выполнения, с |
Ускоре-ние |
|
|
100 |
0.001644 |
0.014467 |
0.11364 |
0.016260 |
0.10111 |
|
300 |
0.034326 |
0.040800 |
0.84132 |
0.024761 |
1.38629 |
|
500 |
0.179312 |
0.146329 |
1.22540 |
0.064773 |
2.76831 |
|
1000 |
1.376674 |
0.443259 |
3.10580 |
0.482129 |
2.85541 |
|
2000 |
10.758619 |
2.945273 |
3.65284 |
3.070530 |
3.50383 |
|
5000 |
169.638963 |
42.660871 |
3.97645 |
48.513414 |
3.49674 |
|
10000 |
1341.197741 |
364.607285 |
3.67847 |
389.500846 |
3.44338 |
Сравнение результатов времени выполнения последовательной программы и параллельных программ представлено на рис. 1. Сравнение значений ускорения в зависимости от размерности системы для программ на основе технологий OpenMP и MPI представлено на рис. 2.
Рис. 1. Зависимость
времени выполнения программы в разных
режимах от размерности СЛАУ
Рис. 2. Зависимость
коэффициента ускорения параллельных
программ от размерности СЛАУ
Технология программирования OpenMP.
Среди упоминаемых в данной статье технологий, самой простой для освоения и использования является OpenMP. Как уже отмечалось, в Visual Studio, начиная с версии 2008 года и новее, уже интегрирована поддержка OpenMP стандарта 2.0, благодаря чему не требуется подключение сторонних библиотек и установка дополнительных программ. Данное обстоятельство позволяет любому программисту с установленной у него средой Visual Studio без промедления начать создавать программы для многоядерных процессоров. Мы не будем сейчас подробно рассказывать о технологии, а проиллюстрируем её простоту конкретным простым примером программы.
Пусть в программе на языке C в которой имеются одномерные массивы X и Y, которые надо СКАЛЯРНО перемножить, и результаты сохранить в массиве Z. На рис. 3 приведены фрагменты программы. В первом фрагменте показано объявление трёх целочисленных массивов, размером в 256 элементов каждый. Во втором фрагменте приведен цикл поэлементного перемножения элементов массивов. Перед циклом написана строчка (выделена полужирным) с префиксом «#pragma omp» после чего следуют две директивы. Директива «parallel» предписывает выполнить нижеописанную конструкцию (в нашем случае это цикл for) параллельными потоками одновременно на всех ядрах процессора, а директива «for» предписывает автоматически распараллелить выполнение шагов цикла по разным потокам.
…
int i,X[256],Y[256],Z[256];
…
#pragma omp parallel for
for (i=0;i<256;i++)
Z[i]=X[i]*Y[i];
…
Рис. 3. Фрагменты программы с директивами OpenMP
Для того, чтобы компилятор Visual Studio начал «понимать» директивы OpenMP в вашей программе, необходимо включить поддержку данной технологии. На рис. 4 показан скрин, по которому можно понять, как в меню можно добраться до раздела включения поддержки OpenMP. Простота использования данной давно себя зарекомендовавшей технологии делает её доступной для повседневного использования современным, как рядовым, так и продвинутым программистом.
Для более подробного знакомства с технологией OpenMP можно воспользоваться источниками [1,2]. С более сложной в использовании, но более мощной технологией MPI можно познакомиться по источнику [3].
Рис. 4. Скрин. Включение поддержки OpenMP в Visual Studio.
Литература
1. Параллельное программирование на OpenMP. http://ccfit.nsu.ru/arom/data/openmp.pdf
2. OpenMP (главный сайт). https://www.openmp.org/
3. MPI для начинающих. https://www.opennet.ru/docs/RUS/MPI_intro/