Параллельный алгоритм - Введение

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

Параллельная обработка

Легкая доступность компьютеров вместе с ростом Интернета изменила способ хранения и обработки данных. Мы живем в эпоху, когда данные доступны в изобилии. Каждый день мы имеем дело с огромными объемами данных, которые требуют сложных вычислений, причем в короткие сроки. Иногда нам нужно получить данные из похожих или взаимосвязанных событий, которые происходят одновременно. Здесь мы требуемconcurrent processing которые могут разделить сложную задачу и обработать ее несколькими системами для получения результата в кратчайшие сроки.

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

Что такое параллелизм?

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

В этом уроке мы обсудим только parallel algorithms. Прежде чем двигаться дальше, давайте сначала обсудим алгоритмы и их типы.

Что такое алгоритм?

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

• Последовательный компьютер
• Параллельный компьютер

В зависимости от архитектуры компьютеров у нас есть два типа алгоритмов:

• Sequential Algorithm - Алгоритм, в котором несколько последовательных шагов инструкций выполняются в хронологическом порядке для решения проблемы.

• Parallel Algorithm- Задача разделена на подзадачи и выполняется параллельно для получения индивидуальных результатов. Позже эти отдельные выходы объединяются вместе, чтобы получить окончательный желаемый результат.

Нелегко разделить большую проблему на sub-problems. Подзадачи могут иметь зависимость между данными. Следовательно, процессоры должны взаимодействовать друг с другом, чтобы решить проблему.

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

Чтобы правильно разработать алгоритм, мы должны иметь четкое представление об основных model of computation в параллельном компьютере.

Модель вычисления

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

В зависимости от потока инструкций и потока данных компьютеры можно разделить на четыре категории:

• Компьютеры с одним потоком инструкций, с одним потоком данных (SISD)
• Одиночный поток инструкций, компьютеры с множественным потоком данных (SIMD)
• Компьютеры с несколькими потоками инструкций, с одним потоком данных (MISD)
• Несколько потоков инструкций, компьютеры с несколькими потоками данных (MIMD)

Компьютеры SISD

Компьютеры SISD содержат one control unit, one processing unit, и one memory unit.

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

SIMD-компьютеры

Компьютеры SIMD содержат one control unit, multiple processing units, и shared memory or interconnection network.

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

Каждый из блоков обработки имеет свой собственный блок локальной памяти для хранения как данных, так и инструкций. В компьютерах SIMD процессоры должны обмениваться данными между собой. Это делаетсяshared memory или по interconnection network.

В то время как некоторые процессоры выполняют набор инструкций, остальные процессоры ожидают следующего набора инструкций. Инструкция от блока управления решает, какой процессор будетactive (выполнить инструкции) или inactive (ждите следующей инструкции).

Компьютеры MISD

Как следует из названия, компьютеры MISD содержат multiple control units, multiple processing units, и one common memory unit.

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

Компьютеры MIMD

MIMD-компьютеры имеют multiple control units, multiple processing units, и shared memory или же interconnection network.

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

Запись

• Компьютер MIMD с общей памятью известен как multiprocessors, в то время как те, которые используют межсетевые соединения, известны как multicomputers.

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

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

  • Distributed system - Когда все процессоры находятся далеко друг от друга (например, в разных городах)