Алгоритм — это последовательность шагов, которые принимают входные данные от пользователя и после некоторых вычислений выдают выходные данные. Параллельный алгоритм — это алгоритм, который может выполнять несколько команд одновременно на разных устройствах обработки, а затем объединять все отдельные выходные данные для получения окончательного результата.
Параллельная обработка
Легкая доступность компьютеров наряду с ростом Интернета изменила способы хранения и обработки данных. Мы живем в эпоху, когда данные доступны в изобилии. Каждый день мы имеем дело с огромными объемами данных, которые требуют сложных вычислений, и это тоже, в короткие сроки. Иногда нам нужно извлекать данные из похожих или взаимосвязанных событий, которые происходят одновременно. Именно здесь нам требуется параллельная обработка, которая может разделить сложную задачу и обработать ее несколькими системами для быстрого вывода результатов.
Параллельная обработка необходима, когда задача заключается в обработке огромного объема сложных данных. Примеры включают в себя: доступ к большим базам данных, тестирование самолетов, астрономические расчеты, атомная и ядерная физика, биомедицинский анализ, экономическое планирование, обработка изображений, робототехника, прогнозирование погоды, веб-сервисы и т. Д.
Что такое параллелизм?
Параллелизм — это процесс обработки нескольких наборов инструкций одновременно. Это уменьшает общее время вычислений. Параллелизм может быть реализован с помощью параллельных компьютеров, то есть компьютеров со многими процессорами. Параллельные компьютеры требуют параллельного алгоритма, языков программирования, компиляторов и операционной системы, поддерживающей многозадачность.
В этом уроке мы обсудим только параллельные алгоритмы . Прежде чем двигаться дальше, давайте сначала поговорим об алгоритмах и их типах.
Что такое алгоритм?
Алгоритм — это последовательность инструкций для решения проблемы. При разработке алгоритма мы должны учитывать архитектуру компьютера, на котором будет выполняться алгоритм. Согласно архитектуре, существует два типа компьютеров —
- Последовательный компьютер
- Параллельный компьютер
В зависимости от архитектуры компьютеров, у нас есть два типа алгоритмов —
-
Последовательный алгоритм — алгоритм, в котором некоторые последовательные шаги инструкций выполняются в хронологическом порядке для решения проблемы.
-
Параллельный алгоритм . Задача делится на подзадачи и выполняется параллельно для получения отдельных выходных данных. Позже, эти отдельные выходы объединяются, чтобы получить конечный желаемый результат.
Последовательный алгоритм — алгоритм, в котором некоторые последовательные шаги инструкций выполняются в хронологическом порядке для решения проблемы.
Параллельный алгоритм . Задача делится на подзадачи и выполняется параллельно для получения отдельных выходных данных. Позже, эти отдельные выходы объединяются, чтобы получить конечный желаемый результат.
Нелегко разделить большую проблему на подзадачи . Подзадачи могут иметь зависимость данных между ними. Поэтому процессоры должны общаться друг с другом, чтобы решить проблему.
Было обнаружено, что время, необходимое процессорам для связи друг с другом, больше, чем фактическое время обработки. Таким образом, при разработке параллельного алгоритма необходимо учитывать правильную загрузку ЦП, чтобы получить эффективный алгоритм.
Чтобы правильно спроектировать алгоритм, мы должны иметь четкое представление об основной модели вычислений на параллельном компьютере.
Модель вычисления
Как последовательные, так и параллельные компьютеры работают с набором (потоком) инструкций, называемых алгоритмами. Этот набор инструкций (алгоритм) инструктирует компьютер о том, что он должен делать на каждом этапе.
В зависимости от потока команд и потока данных компьютеры можно разделить на четыре категории:
- Компьютеры с одним потоком команд, с одним потоком данных (SISD)
- Один поток инструкций, компьютеры с несколькими потоками данных (SIMD)
- Множественный поток команд, компьютеры с одним потоком данных (MISD)
- Компьютеры с несколькими потоками команд, несколькими потоками данных (MIMD)
SISD Компьютеры
Компьютеры SISD содержат один блок управления, один блок обработки и один блок памяти .
В компьютерах этого типа процессор принимает единый поток инструкций от блока управления и работает с единым потоком данных из блока памяти. Во время вычислений на каждом этапе процессор принимает одну инструкцию от блока управления и оперирует единственными данными, полученными из блока памяти.
SIMD Компьютеры
SIMD-компьютеры содержат один блок управления, несколько блоков обработки и общую память или сеть взаимосвязей .
Здесь один единственный блок управления отправляет инструкции всем процессорам. Во время вычислений на каждом шаге все процессоры получают единый набор инструкций от блока управления и работают с различным набором данных из блока памяти.
Каждый из блоков обработки имеет свой собственный локальный блок памяти для хранения как данных, так и инструкций. В компьютерах SIMD процессоры должны общаться между собой. Это делается общей памятью или сетью соединений .
В то время как некоторые из процессоров выполняют набор инструкций, остальные процессоры ждут своего следующего набора инструкций. Инструкции от блока управления решают, какой процессор будет активным (выполнять инструкции) или неактивным (дождаться следующей инструкции).
MISD Компьютеры
Как следует из названия, компьютеры MISD содержат несколько блоков управления, несколько блоков обработки и один общий блок памяти .
Здесь каждый процессор имеет свой собственный блок управления, и они имеют общий блок памяти. Все процессоры получают инструкции по отдельности от своего собственного блока управления, и они работают с одним потоком данных в соответствии с инструкциями, которые они получили от своих соответствующих блоков управления. Этот процессор работает одновременно.
MIMD Компьютеры
Компьютеры MIMD имеют несколько блоков управления, несколько блоков обработки и общую память или сеть взаимосвязей .
Здесь каждый процессор имеет свой собственный блок управления, локальный блок памяти и арифметико-логический блок. Они получают различные наборы инструкций от своих соответствующих блоков управления и работают с различными наборами данных.
Компьютер MIMD, который разделяет общую память, известен как мультипроцессоры, в то время как те, которые используют сеть взаимосвязи, известны как мультикомпьютеры .
В зависимости от физического расстояния между процессорами мультикомпьютеры бывают двух типов:
Мультикомпьютер — когда все процессоры находятся очень близко друг к другу (например, в одной комнате).
Распределенная система — когда все процессоры находятся далеко друг от друга (например, в разных городах)