Алгоритм работы параллельной программы

Иванов, К. К. Основы параллельной работы программ / К. К. Иванов, С. А. Раздобудько, Р. И. Ковалев. — Текст : непосредственный // Молодой ученый. — 2017. — № 7 (141). — С. 13-15. — URL: https://moluch.ru/archive/141/39880/ (дата обращения: 10.07.2023).

Статья посвящена крайне важному аспекту в работе любой вычислительной системы на сегодняшний день — параллельной работе программ.

Ключевые слова: параллельная работа программ, параллелизм, вычислительная система, процесс, поток, ресурс, процессор

Любая вычислительная система, насколько бы мощной она ни была, обладает ограниченными ресурсами. Оперативная память, устройство чтения и записи информации, процессор — все это и многое другое (речь идет, конечно же, об объектах вычислительной системы) имеет некоторые пределы. Из-за этого возникает острая необходимость использовать эти ресурсы наиболее эффективно, и именно параллельная работа программ является одним из ключевых факторов, позволяющих выполнить поставленную задачу.

Параллельное программирование на Python

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

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

Также необходимо отметить, что ресурсы вычислительной системы, о которых говорилось в начале статьи, подразделяются на несколько категорий в зависимости от того, как именно они используются, а именно на [1]:

1. Выделяемые ресурсы — это ресурсы, которые выделяются некоторому процессу и монопольно им используются.
2. Повторно распределяемые ресурсы — это ресурсы, которые могут как выделяться, так и высвобождаться прямо во время выполнения процессов.
3. Разделяемые ресурсы — это ресурсы, которые постоянно находятся в общем использовании и выделяются процессам в режиме разделения времени.
4. Многократно используемые ресурсы — это ресурсы, которые могут одновременно использоваться несколькими процессами.

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

1. Выполнение командных последовательностей различных потоков может чередоваться во время их исполнения, причем время между выполнением команд различных потоков может также изменяться.
2. При различных запусках программы возможны различные последовательности выполнения команд различных потоков.
3. Результат выполнения программы должен быть правильным вне зависимости от того, сколько времени прошло между выполнением команд различных потоков. Необходимо исключить зависимость результатов выполнения от того путем анализа взаимовлияния потоков и разработки методов их исключения [1].

Одна из проблем, которую необходимо решить для обеспечения правильной работы параллельной программы, заключается в общем использовании разделяемых ресурсов, таких, как данные, файлы, устройства и многое другое. Чтобы разрешить данную проблему, необходимо реализовать следующие функции [1]:

Отладка параллельных программ на Go. Андрей Солдатенко

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

Из всего вышеперечисленного можно сделать вывод, что один ресурс может использоваться только одним потоком с момента занятия потоком и до момента освобождения. Данный механизм называется взаимоисключением потоков. Помимо его выполнения также необходимо достичь выполнения следующих правил [1]:

1. Отсутствие взаимной блокировки одного потока другим.
2. Эффективный выбор потока, который следующим начнет работу с ресурсом, то есть выбор нужного потока за наименьшее возможное время.
3. Исключение ситуаций, когда время ожидания освобождения ресурса одним потоком приближается к бесконечности.

Крайне важно проводить определенные мероприятия для повышения эффективности параллельных программ. Основных их четыре [1]:

1. Оптимизация количества потоков. Избыточное количество потоков негативно сказывается на работе вычислительных устройств, перестает продуктивно использоваться кэш-память, становится очень сложной организация синхронизации и взаимоисключения потоков. Поэтому необходимо очень осторожно выбирать число одновременно работающих потоков.
2. Минимизация взаимодействия потоков. Чем сильнее потоки независимы друг от друга, тем меньше времени тратится на задержки, когда один поток для продолжения своей работы ждет завершения выполнения других потоков. Для выполнения данной задачи нужно стремится уменьшить число взаимодействий между потоков, повышать эффективность работы алгоритмов распределения ресурсов между потоками, обеспечения более быстрого выполнения потоков за счет исключения ситуация, когда работа одного потока прерывается другим, чье выполнение является намного более приоритетным в данный момент времени.
3. Оптимизация работы с памятью. Эффективная работа с памятью является проблемой всех программ, но для параллельных она приобретает особое значение. Самый лучший вариант — это достижение такого состояния, когда работа ведется исключительно с кэш-памятью без обращения к более медленной оперативной памятью. Тем не менее, при использовании общей памяти и нескольких устройств кэш-памяти возникают дополнительные проблемы, требующие решения:

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

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

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

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

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

1. Гергель, В. П. Высокопроизводительные вычисления для многопроцессорных многоядреных систем: Учебник. / В. П. Гергель. — М.: Издательство Московского университета, 2010. — 544 с., илл.

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

Источник: moluch.ru

Пример анализа и распараллеливания алгоритма

В качестве более сложного примера распараллеливания рассмотрим олимпиадную задачу на динамическое программирование. Прочитать условие задачи и ее последовательное решение можно тут: «Лесенка» [1]. Мы немного изменим условие, расширив диапазон подаваемых на вход значений чтобы программа считала дольше и оценка результатов распараллеливания была более наглядной. Для нас важно, что в процессе поиска решения программа перебирает множество вариантов расположения кубиков, причем эти варианты укладываются в структуру типа дерева: Из каждого узла (кроме листьев) дерева можно сгенерировать другие варианты. Наша задача — распараллелить алгоритм такой генерации. При оценке результатов распараллеливания на вход программы будут подаваться большие числа, при этом может получаться результат, не умещающийся в диапазон чисел, задаваемый int . В связи с этим тип данных счетчика заменен на unsigned long . Кроме того, в приведенной выше реализации используется рекурсия, поэтому при распараллеливании нас может интересовать опция вложенного параллелизма — получить соответствующие настройки можно функцией omp_get_nested . Ниже приведена модифицированная с учетом приведенных выше соображений программа:

#include #include «omp.h» using namespace std; unsigned long get_count(int prev_level, int n) < if (0 == n) return 1; unsigned long count = 0; for (int level = 1; level < prev_level; ++level) < if ((n — level) < 0) break; count += get_count(level, n — level); >return count; > int main() < cout >

Результаты вычисления этой программы приведены на рисунке и используются в качестве эталона для проверки корректности работы параллельных версий программы: Можно попробовать распараллелить цикл for , при отключенном вложенном параллелизме потоки должны быть созданы только для цикла самого верхнего уровня. Использовать директиву parallel for в данном случае невозможно, т.к. внутри цикла используется инструкция break :

#pragma omp parallel for reduction(+:count) for (int level = 1; level

Решить проблему можно либо распараллеливанием вручную, либо следующей модификацией кода:

unsigned long get_count(int prev_level, int n) < if (n == 0) return 1; if (n < 0) return 0; unsigned long count = 0; #pragma omp parallel for reduction(+:count) for (int level = 1; level < prev_level; ++level) < count += get_count(level, n — level); >return count; >

Видно, что теперь даже если ширина проверяемого уровня меньше ноля — выполняется рекурсивный вызов функции. Параллельная программа стала работать значительно дольше: Снижение производительности можно объяснить появившимися дополнительными затратами на вызов функции, а также тем, что объем задач потоков оказывается сильно разным: В районе отметки «40» завершилось вычисление для n=100 и началось вычисление n=150. Видно, что одно ядро чаще всего простаивает, тем не менее в системе работает два потока, добавились издержки на проверку того, нужно ли создавать новый поток в начале области parallel . Еще более плохой результат дало распараллеливание при включенном вложенном параллелизме:

Пояснения по поводу взяты с MSDN [2]:

When enabled, the environment variable can break an otherwise operational program because the number of threads increases exponentially when nesting parallel regions. For example a function that recurses 6 times with the number of OMP threads set to 4 requires 4,096 (4 to the power of 6) threads In general, the performance of your application will degrade if the number of thread exceeds the number of processors. One exception to this would be I/O bound applications.

Незначительно улучшить ситуацию позволяет использование опции планирования потоков. Загрузка ядер в процессе работы программы для schedule(dynamic, 2) приведена ниже:

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

int main() < cout auto end = omp_get_wtime(); cout >

В книге Миллера вы найдете больше примеров анализа параллельных алгоритмов — в ней показано как делать это под разные архитектуры, ведь очевидно, что алгоритм из этой статьи не подойдет для кластера…

Просмотр 0 веток ответов

Источник: pro-prof.com

Алгоритм работы параллельной программы

III Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

• Главная
• Список секций
• Информатика
• ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ В СРЕДЕ PASCALABC. NET ДЛЯ РЕШЕНИЯ ШКОЛЬНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ

ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ В СРЕДЕ PASCALABC. NET ДЛЯ РЕШЕНИЯ ШКОЛЬНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ

Абрамова И.А. 1
1 МБОУ СОШ 83
Гаврилова И.В. 1
1 МБОУ СОШ №83, г. Ногинск-9

Автор работы награжден дипломом победителя II степени

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке «Файлы работы» в формате PDF

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

Суперкомпьютеры насчитывают миллионы ядер, смартфоны — гораздо меньше, но и здесь не обойтись без параллельных вычислений. Поэтому знакомство с этим термином должно происходить в процессе школьного обучения и необходимо знакомиться с непривычным нам ранее «параллельным» мышлением.

В проекте рассматривается среда программирования PascalABC.NET, поскольку она широко используется в образовательных учреждениях. Для данного проекта важно то, что в PascalABC.NET реализованы средства параллельного программирования в виде директив OpenMP. Таким образом, чтобы показать некоторые возможности параллельного программирования не предполагается изучение дополнительных языков программирования и установки нового программного обеспечения.

Что такое OpenMP

OpenMP – технология для программирования на системах с общей памятью. Именно поэтому данная технология применяется для достижения поставленных в работе целей в отличие от MPI (передача сообщений – для систем с распределенной памятью). В стандарт OpenMP входят спецификации набора директив компилятора, процедур и переменных среды.

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

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

• Изучить возможность применения параллельного программирования в школьной программе;
• Сравнить время выполнения последовательной и параллельной программ;
• Оценить эффективность каждого из методов;
• Понять от чего зависит время выполнения;

• Изучение и анализ времени вычислений некоторых задач по информатике при использовании одноядерных и многоядерных процессоров
• Изучение возможности применения PascalABC.net для обучения параллельного программирования в школе

В среде PascalABC.net написаны параллельная и последовательная программы для некоторых задач школьного курса по информатике (программированию). Производится сравнение и анализ результатов. Выясняются причины несовпадения с ожидаемыми результатами или же подтверждаются прогнозы. Осознание возможности применения параллельного программирования в PascalABC.net.

• В современном мире даже в телефонах используются технологии параллельного программирования, но пользователь не знает для чего это им нужно;
• Суперкомпьютеры, с помощью которых наука открывает все новые и новые горизонты, нуждаются в квалифицированных специалистах;

РЕШЕНИЕ ЗАДАЧ

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

Задача 1. Определение частоты употребления буквы «а» в тексте.

Задача могла быть поставлена в общем виде, например, сколько раз встречается некий символ, введенный пользователем с помощью устройства ввода (например, клавиатуры). Тем не менее, на время выполнения программы это бы не повлияло (на время поиска данного символа), следовательно, и на выводы о распараллеливании, поэтому рассмотрен более простой вариант.

Результатом выполнения программы должно быть число — сколько раз в тексте встречается данная буква.

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

Для сравнения времени выполнения программ, выполняется сначала последовательная, а затем параллельная.

В параллельной программе использована директива parallel for reduction. Каждое ядро выполняет свою часть работы, добавляя каждый раз единицу в приватную переменную (счетчик для каждого ядра изначально свой), а затем происходит сложение в одну общую переменную.

SHARED Применяется к переменным, которые необходимо сделать общими.

PRIVATE Применяется к переменным, которые необходимо сделать приватными. При входе в параллельную область для каждой нити создается отдельный экземпляр переменной, который не имеет никакой связи с оригинальной переменной вне параллельной области (Приложение, рис.1).

Время выполнения последовательной программы – 60 мс.

Время выполнения параллельной программы – 26 мс.

Результаты (количество букв в тексте) совпадают.

Таким образом, получаемускорение

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

Задача 2. Нахождение среднего арифметического элементов одномерного массива.

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

Здесь используется директива parallel for reduction, так как для того чтобы ускорить время выполнения распараллеливается цикл со сложением всех данных в массиве чисел в одну переменную.

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

Задача простая, но для того чтобы увеличить время выполнения, в сторонний файл записываются промежуточные вычисления как для последовательной, так и для параллельной программы.

Была встречена проблема с реализацией, выходом из которой оказалась необходимость введения локальных переменных.

Время выполнения было быстрее то у параллельной, то у последовательной программы.

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

Периодически при запуске программ могли возникать ошибки выполнения, причиной которых является следующее: (Приложение, рис. 2). Пакет ввода-вывода по умолчанию не обеспечивает надлежащей синхронизации потоков (нитей).

Ниже приведена диаграмма для 10 запусков программы. На диаграмме можно заметить, что большинство значений достаточно близки друг к другу, тем не менее, в большинстве случаев параллельная программа все же быстрее.

Время выполнения последовательной и параллельной программ

Ниже приведена таблица сравнения полученного времени для других 10 запусков данной программы (на процессоре с другими характеристиками).

В некоторых случаях ускорение превосходит все ожидания. Возможно, это связано с кэш-попаданиями и кэш-промахами.

О кэш-попаданиях и кэш-промахах.

Между процессором и ОЗУ используется быстродействующая буферная память. Буферная память скрыта от программиста в том смысле, что он не может ей адресовывать и может даже не знать о ее существовании. Поэтому такая скрытая буферная память получила название КЭШ памяти, от английского слова Cache – тайник. Работа КЭШ памяти прозрачна, то есть невидима для пользователя.

Процессор в основном работает с данными, находящимися в КЭШ-памяти, и только при их отсутствии в КЭШ, вынужден обращаться к ОЗУ.

Поскольку буферная память более быстродействующая, чем ОЗУ, то использование КЭШ ведет к увеличению производительности компьютера. Причем производительность персонального компьютера будет тем больше, чем больше данных находится в КЭШ памяти, и, следовательно, персональный компьютер будет меньше обращаться к медленной оперативной динамической памяти.

При работе с КЭШ памятью преобладают операции чтения, а операции записи составляют меньше 10% трафика памяти. Операция чтения происходит за меньшее время, чем операция записи, поскольку строка из КЭШ памяти может быть прочитана в то же самое время, когда читаются и сравниваются теги строки и адреса. При КЭШ попадании прочитанная строка или ее часть немедленно передаются процессору. При КЭШ промахе от заранее прочитанной строки нет никакой пользы.

Вывод: На данной задаче достаточно трудно показать плюсы параллельного программирования, тем более в рассматриваемой среде – PascalABC.net. Тем не менее, на этой программе можно удачно показать реальную работу нескольких ядер одновременно, если добавить вывод промежуточных результатов.

В случае с одним ядром промежуточных результатов гораздо больше, поскольку все вычисления одно ядро выполняет последовательно. При запуске параллельной программы промежуточных результатов (частичных сумм) будет гораздо меньше. Причем чем больше ядер, тем меньше количество этих сумм (что тоже ограничено – слишком большое количество ядер приведет к временным задержкам, поскольку работы будет меньше, чем «рабочих»). Кроме того, и сами промежуточные суммы в последовательной и параллельной программе будут отличаться, что также можно продемонстрировать школьникам.

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

Усложним вычислительную задачу.

Задача 3.Нахождение среднего арифметического матрицы.

Для подсчета эффективности необходимо знать, сколько ядер будет использоваться во время распараллеливания, поэтому программа запрашивает у пользователя эту информацию. В среде PascalABC.net нет возможности определить количество нитей (потоков), поэтому программа просит пользователя явно указать это число.

После нахождения среднего арифметического находим ускорение (время последовательной программы делим на время параллельной). Для того чтобы получить эффективность, ускорение делим на количество используемых ядер. Ранее мы сами анализировали ускорение, здесь же все вычисления прямо в программе.

Кроме того, при использовании 2 ядер последовательная программа оказывается быстрее параллельной. Но при запуске на 4 ядрах параллельная все же быстрее (Приложение, рис.3). Это также наглядно демонстрирует возможности параллельных вычислений и может использоваться учителем на уроках.

Задача 4. Определение частоты употребления букв русского алфавита в тексте

Используя знания, которые были получены при решении задачи №1, подсчитаем количество каждой из букв русского алфавита в 1 и 2 томах романа Толстого «Война и мир».

Алгоритм прост: Встретил букву «а», добавь единицу в ячейку массива с номером 1, встретил «Б» — в ячейку с номером 2 и т.д.

Для того чтобы потом удобнее было выводить результаты, буквам присваиваются значения с помощью таблицы (кодировка Windows (CP1251)). Для «Ё» прописываем вручную, так как данная буква находится отдельно от всех. Одновременно с выводом буквы и ее количества складываем получившиеся данные, чтобы получить количество букв в исходном тексте. Получим вероятность с помощью деления количества для одной буквы на общее количество букв. В программе определяем эффективность и ускорение по той же формуле, что и в предыдущей задаче.

Ниже приведена диаграмма с данными по нескольким запускам программы.

Таблица сравнения полученного времени выполнения последовательной и параллельной программ. Также приведено ускорение и эффективность.

Запуск

Источник: school-science.ru