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

Парадигмы параллельного программирования

Статья, написанная студентами для студентов. Обзор предметной области
Парадигма параллельного программирования «клиенты и серверы»
Парадигма параллельного программирования «производители и потребители»
Парадигма параллельного программирования «взаимодействующие равные»
Заключение
Список использованных источников

1 Обзор предметной области

• итеративный параллелизм;
• рекурсивный параллелизм;
• «клиенты и серверы»;
• «производители и потребители»;
• взаимодействующие равные.

Итеративный параллелизм – процессы выполняют циклические вычисления, решая одну задачу (итерации одного цикла) [2, c. 3]. Чаще всего встречается в вычислениях, выполняемых на нескольких процессорах.

Рекурсивный параллелизм может использоваться, когда в программе есть одна или несколько рекурсивных процедур (функций), и их вызовы независимы, т.е. каждый из них работает над своей частью общих данных. Рекурсивный параллелизм используется для решения таких комбинаторных проблем, как сортировка, планирование (задача коммивояжера) и игры (шахматы и другие) [3, c. 9].

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

2 Парадигма параллельного программирования «клиенты и серверы»

Клиенты и серверы – наиболее распространенная модель взаимодействия в распределенных системах, от локальных сетей до всемирной сети Интернет [3, c. 9]. В этой модели реализуется две части: клиент и сервер.

Чаще всего они располагаются на разных машинах, и обычно один сервер обслуживает многих клиентов [4, c. 32]. Клиент отправляет запрос серверу и ждет ответа. Сервер ожидает запр сов от клиентов, а затем действует в соответствии с этими запросами и возвращает ответ клиенту. Иногда клиент может «исполнить» роль сервера, если сам будет получать запросы. Аналогично сервер будет выступать в роли клиента, если ему потребуется обращаться с запросами к другим программам [4].

Например, рассмотрим запрос по World Wide Web, который возникает, когда пользователь открывает новый адрес URL в окне программы-браузера. Web-браузер является клиентским процессом, выполняемым на машине пользователя. Адрес URL косвенно указывает на другую машину, на которой расположена Web-страница. Сама Web-страница доступна для процесса- сервера, выполняемого на другой машине. Этот процесс-сервер читает Web- страницу, определяемую адресом URL, и возвращает ее на машину клиента [3, c. 17].

Отношения программировании между клиентом аналогичны и сервером отношениям в параллельном между программой, вызывающей подпрограмму, и самой подпрограммой в последовательном программировании. Более того, как подпрограмма может быть вызвана из нескольких мест программы, так и у сервера обычно есть много клиентов. Запросы каждого клиента должны обрабатываться независимо, однако параллельно может обрабатываться несколько запросов, подобно тому, как одновременно могут быть активны несколько вызовов одной и той же
процедуры [3, c. 18].

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

Клиенты обычно представляют собой множество потоков.
Одна из классических «задач о спящем парикмахере» описывает отношение в системах «клиент-сервер». У парикмахера есть одно рабочее место и приемная с несколькими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли там ожидающие клиенты. Если они есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.

Каждый приходящий клиент смотрит на то, что делает парикмахер. Если парикмахер спит, то клиент будит его и садится в кресло. Если парикмахер работает, то клиент идет в приёмную. Если в приёмной есть свободный стул, клиент садится и ждёт своей очереди. Если свободного стула нет, то клиент уходит [5].

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

Клиенты образуют очередь, которая является ограниченной. Посетители уходят, если нет свободных кресел в зале ожидания. То есть придется создавать и отправлять на выполнение новые потоки (потоки-клиенты), что не является достоинством [6, c. 90].

3 Парадигма параллельного программирования «производители и потребители»

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

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

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

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

Классическим примером являются конвейеры в ОС Unix. Рассмотрим взаимодействие команд:
$ps –Af | grep mc.
Вертикальная черта «|» между командами обозначает конвейер т.е. выход одной команды переназначается на вход другой команды, таким образом, в приведенном выше примере результат выполнения ps –Af будет передан команде grep , которая произведет трансформацию входного потока в соответствии с маской (в данном случае на выходе будут все строки, содержащие подстроку « mc ») [8, c. 22].

Потоки могут быть связаны с файлами особого типа – каналами. Канал – это буфер (очередь типа FIFO) между процессом-производителем ипроцессом-потребителем. Процесс-производитель записывает данные в конец очереди, а процесс-потребитель читает данные из ее начала, при этом символы удаляются. В общем случае канал – это тот самый ограниченный буфер, поэтому производитель при необходимости ожидает, пока в буфере появится свободное место для очередной порции данных, а потребитель при необходимости ждет появления в буфере данных [8, c. 23].

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

4 Парадигма параллельного программирования взаимодействующие равные

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

Распределение работ в таком приложении либо фиксировано заранее, либо динамически определяется во время выполнения [8, c. 16]. Одним из распространенных способов динамического распределения работ является «портфель задач». Портфель задач, как правило, реализуется с помощью разделяемой переменной, доступ к которой в один момент времени имеет только один процесс [3, c. 26].

Вычислительная задача делится на конечное число подзадач. Как правило, каждая подзадача должна выполнить однотипные действия над разными данными. Подзадачи нумеруются, и каждому номеру определяется функция, которая однозначно отражает номер задачи на соответствующий ему набор данных. Создается переменная, которую следует выполнять следующей. Каждый поток сначала обращается к портфелю задач для выяснения текущего номера задачи, после этого увеличивает его, потом берет соответствующие данные и выполняет задачу, затем обращается к портфелю задач для выяснения следующего номера задачи [8, c. 28].

Естественно должен быть предусмотрен механизм остановки процессов при исчерпывании всего множества задач, как в «производителях и потребителях».

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

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

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

Проблема реализации этого алгоритма в том, что доступ к портфелю задач должен быть безопасным. Если между взятием новой задачи и увеличением счетчика работа выполняющего их потока прервется, то некоторую задачу, возможно, отработают несколько потоков. [8, c. 29].

Заключение

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

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

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

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

Список использованных источников

1. Роганов Е.А. Основы информатики и программирования: Учебное пособие — М.: МГИУ, 2001. — 315 с.
2. Парадигмы параллельного программирования [Электронный ресурс] : лекционный материал. – Режим доступа: http://staff.mmcs.sfedu.ru/~dubrov/files/sl_parallel_05_paradigm.pdf
3. Востокин С.В. Обзор области параллельных вычислений [Электронный ресурс]: учебное пособие. – Режим доступа: http://www.williamspublishing.com/PDF/5-8459-0388-2/part.pdf
4. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++: Пер. с англ. – М. Издательский дом «Вильямс», 2004. – 672 с. : ил. – Парал. тит. англ.
5. Проблема спящего парикмахера [Электронный ресурс] : Википедия – свободная энциклопедия – Режим доступа: https://ru.wikipedia.org/wiki/Проблема_спящего_парикмахера.html
6. Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем [Электронный ресурс] : курс лекций. – Нижегородский государственный университет им. Ломоносова. – Режим доступа: http://www.unn.ru/pages/e-library/methodmaterial/2010/7.pdf
7. Методы взаимодействия процессов [Электронный ресурс] : курс «Основы современных операционных систем. – НОУ «ИНТУИТ» – Режим доступа: http://www.intuit.ru/studies/courses/641/497/lecture/11282?page=1
8. Карепова Е.Д., Кузьмин Д.А., Легалов А.И., Редькин А.В., Удалова Ю.В., Федоров Г.А. Средства разработки параллельных программ. Учебное пособие. Красноярск 2007

Источник