Принципы разработки параллельных методов | Статья в журнале «Молодой ученый»

Библиографическое описание:

Иванов К. К., Раздобудько С. А., Ковалев Р. И. Принципы разработки параллельных методов // Молодой ученый. — 2017. — №3. — С. 30-32. — URL https://moluch.ru/archive/137/38412/ (дата обращения: 22.07.2018).



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

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

В общем, разработку параллельного алгоритма можно разделить на следующие этапы [1]:

1) Дифференциация вычислений на самостоятельные компоненты;

2) Определение связей между компонентами вычислений;

3) Объединение компонентов в наборы или их детализация;

4) Распределение наборов компонентов между процессорами.

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

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

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

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

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

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

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

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

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

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

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

Литература:

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


Похожие статьи

Обзор методов организации параллельных вычислений

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

Основы параллельной работы программ | Статья в журнале...

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

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

При использовании ПЛИС в качестве аппаратной основы универсального вычислительного ускорителя нужно учитывать основные недостатки ПЛИС по сравнению со специализированной для решения конкретной задачи интегральной схемой(ASIC) ([2], [3])

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого кристалла без учета моментного воздействия подробно описан в [7].

. Начальные данные для соответствующей задачи Коши таковы: Численный алгоритм.

Многоагентная ассоциативная вычислительная система

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

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

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

Общая схема метода вариаций в пространстве управлений

Вычислительный эксперимент.

Сравнительный анализ результатов решения задачи при точности вычислений 10-3.

Оптимизация алгоритма выравнивания биологических...

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

Задачи подобного типа могут быть решены с использованием параллельных вычислительных структур

Более доступным вариантом является использование параллелизма на уровне GPU.

Конфигурирование и тестирование производительности...

Ключевые слова: вычислительный кластер, кластер рабочих станций (COW), массивно-параллельная обработка (MPP)

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

Параллельная реализация алгоритма для описания...

Описанный вычислительный алгоритм для решения системы уравнений (1) по формулам (2)–(9) реализован в виде параллельной программы для компьютеров с графическими

Распараллеливание вычислений производится на этапах метода расщепления.

Обзор методов организации параллельных вычислений

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

Основы параллельной работы программ | Статья в журнале...

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

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

При использовании ПЛИС в качестве аппаратной основы универсального вычислительного ускорителя нужно учитывать основные недостатки ПЛИС по сравнению со специализированной для решения конкретной задачи интегральной схемой(ASIC) ([2], [3])

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого кристалла без учета моментного воздействия подробно описан в [7].

. Начальные данные для соответствующей задачи Коши таковы: Численный алгоритм.

Многоагентная ассоциативная вычислительная система

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

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

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

Общая схема метода вариаций в пространстве управлений

Вычислительный эксперимент.

Сравнительный анализ результатов решения задачи при точности вычислений 10-3.

Оптимизация алгоритма выравнивания биологических...

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

Задачи подобного типа могут быть решены с использованием параллельных вычислительных структур

Более доступным вариантом является использование параллелизма на уровне GPU.

Конфигурирование и тестирование производительности...

Ключевые слова: вычислительный кластер, кластер рабочих станций (COW), массивно-параллельная обработка (MPP)

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

Параллельная реализация алгоритма для описания...

Описанный вычислительный алгоритм для решения системы уравнений (1) по формулам (2)–(9) реализован в виде параллельной программы для компьютеров с графическими

Распараллеливание вычислений производится на этапах метода расщепления.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Обзор методов организации параллельных вычислений

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

Основы параллельной работы программ | Статья в журнале...

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

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

При использовании ПЛИС в качестве аппаратной основы универсального вычислительного ускорителя нужно учитывать основные недостатки ПЛИС по сравнению со специализированной для решения конкретной задачи интегральной схемой(ASIC) ([2], [3])

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого кристалла без учета моментного воздействия подробно описан в [7].

. Начальные данные для соответствующей задачи Коши таковы: Численный алгоритм.

Многоагентная ассоциативная вычислительная система

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

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

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

Общая схема метода вариаций в пространстве управлений

Вычислительный эксперимент.

Сравнительный анализ результатов решения задачи при точности вычислений 10-3.

Оптимизация алгоритма выравнивания биологических...

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

Задачи подобного типа могут быть решены с использованием параллельных вычислительных структур

Более доступным вариантом является использование параллелизма на уровне GPU.

Конфигурирование и тестирование производительности...

Ключевые слова: вычислительный кластер, кластер рабочих станций (COW), массивно-параллельная обработка (MPP)

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

Параллельная реализация алгоритма для описания...

Описанный вычислительный алгоритм для решения системы уравнений (1) по формулам (2)–(9) реализован в виде параллельной программы для компьютеров с графическими

Распараллеливание вычислений производится на этапах метода расщепления.

Обзор методов организации параллельных вычислений

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

Основы параллельной работы программ | Статья в журнале...

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

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

При использовании ПЛИС в качестве аппаратной основы универсального вычислительного ускорителя нужно учитывать основные недостатки ПЛИС по сравнению со специализированной для решения конкретной задачи интегральной схемой(ASIC) ([2], [3])

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого кристалла без учета моментного воздействия подробно описан в [7].

. Начальные данные для соответствующей задачи Коши таковы: Численный алгоритм.

Многоагентная ассоциативная вычислительная система

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

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

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

Общая схема метода вариаций в пространстве управлений

Вычислительный эксперимент.

Сравнительный анализ результатов решения задачи при точности вычислений 10-3.

Оптимизация алгоритма выравнивания биологических...

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

Задачи подобного типа могут быть решены с использованием параллельных вычислительных структур

Более доступным вариантом является использование параллелизма на уровне GPU.

Конфигурирование и тестирование производительности...

Ключевые слова: вычислительный кластер, кластер рабочих станций (COW), массивно-параллельная обработка (MPP)

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

Параллельная реализация алгоритма для описания...

Описанный вычислительный алгоритм для решения системы уравнений (1) по формулам (2)–(9) реализован в виде параллельной программы для компьютеров с графическими

Распараллеливание вычислений производится на этапах метода расщепления.

Задать вопрос