Параллельный алгоритм - Краткое руководство

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 - Когда все процессоры находятся далеко друг от друга (например, в разных городах)

Анализ алгоритма помогает нам определить, полезен алгоритм или нет. Как правило, алгоритм анализируется на основе времени его выполнения.(Time Complexity) и количество места (Space Complexity) это требует.

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

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

Временная сложность (время выполнения),
Общее количество используемых процессоров и
Общая стоимость.

Сложность времени

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

Время выполнения измеряется на основе времени, затраченного алгоритмом на решение проблемы. Общее время выполнения рассчитывается с момента начала выполнения алгоритма до момента его остановки. Если все процессоры не начинают и не завершают выполнение одновременно, то общее время выполнения алгоритма - это момент, когда первый процессор начал свое выполнение, до момента, когда последний процессор прекращает свое выполнение.

Сложность алгоритма по времени можно разделить на три категории:

Worst-case complexity - Когда количество времени, требуемое алгоритмом для данного ввода, равно maximum.
Average-case complexity - Когда количество времени, требуемое алгоритмом для данного ввода, равно average.
Best-case complexity - Когда количество времени, требуемое алгоритмом для данного ввода, равно minimum.

Асимптотический анализ

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

Note - Asymptoticэто состояние, при котором линия стремится пересечь кривую, но они не пересекаются. Здесь линия и кривая асимптотичны друг другу.

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

Обозначение Big O
Обозначение омега
Обозначение тета

Обозначение Big O

В математике нотация Big O используется для представления асимптотических характеристик функций. Он представляет поведение функции для больших входных данных простым и точным методом. Это метод представления верхней границы времени выполнения алгоритма. Он представляет собой наибольшее количество времени, которое может потребоваться алгоритму для завершения своего выполнения. Функция -

f (n) = O (g (n))

если существуют положительные константы c и n₀ такой, что f(n) ≤ c * g(n) для всех n где n ≥ n₀.

Обозначение омега

Нотация омега - это метод представления нижней границы времени выполнения алгоритма. Функция -

f (n) = Ω (g (n))

если существуют положительные константы c и n₀ такой, что f(n) ≥ c * g(n) для всех n где n ≥ n₀.

Тета-нотация

Тета-нотация - это метод представления как нижней, так и верхней границы времени выполнения алгоритма. Функция -

f (n) = θ (g (n))

если существуют положительные константы c₁, c₂, и n₀ такое, что c1 * g (n) ≤ f (n) ≤ c2 * g (n) для всех n где n ≥ n₀.

Ускорение алгоритма

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

ускорение =

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

Количество используемых процессоров

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

Общая стоимость

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

Общая стоимость = Сложность времени × Количество используемых процессоров

Следовательно efficiency параллельного алгоритма -

Эффективность =

Время выполнения в худшем случае последовательного алгоритма / Время выполнения в худшем случае параллельного алгоритма

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

Параллельная модель данных
Модель графа задач
Модель рабочего бассейна
Модель главного раба
Производитель потребитель или модель трубопровода
Гибридная модель

Параллельные данные

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

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

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

Example - Плотное матричное умножение.

Модель графа задач

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

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

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

Модель рабочего бассейна

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

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

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

Example - Параллельный поиск по дереву

Модель Мастер-Раб

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

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

Эта модель в целом одинаково подходит для shared-address-space или же message-passing paradigms, поскольку взаимодействие естественно двухстороннее.

В некоторых случаях задача может быть выполнена поэтапно, и задача на каждой фазе должна быть завершена до того, как можно будет сгенерировать задачу на следующих этапах. Модель ведущий-ведомый можно обобщить наhierarchical или же multi-level master-slave model в котором мастер верхнего уровня передает большую часть задач мастеру второго уровня, который далее подразделяет задачи между своими собственными подчиненными устройствами и может выполнять часть самой задачи.

Меры предосторожности при использовании модели ведущий-ведомый

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

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

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

Модель трубопровода

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

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

Example - Параллельный алгоритм факторизации LU.

Гибридные модели

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

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

Example - Параллельная быстрая сортировка

Parallel Random Access Machines (PRAM)- это модель, которая рассматривается для большинства параллельных алгоритмов. Здесь к одному блоку памяти подключено несколько процессоров. Модель PRAM содержит -

Набор однотипных процессоров.
Все процессоры используют общий блок памяти. Процессоры могут обмениваться данными между собой только через общую память.
Блок доступа к памяти (MAU) соединяет процессоры с единой общей памятью.

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

Чтобы решить эту проблему, в модели PRAM были наложены следующие ограничения:

Exclusive Read Exclusive Write (EREW) - Здесь никаким двум процессорам не разрешено читать или записывать в одну и ту же ячейку памяти одновременно.
Exclusive Read Concurrent Write (ERCW) - Здесь никаким двум процессорам не разрешено одновременное чтение из одного и того же места памяти, но разрешено одновременное выполнение записи в одно и то же место памяти.
Concurrent Read Exclusive Write (CREW) - Здесь всем процессорам разрешено одновременное чтение из одной и той же области памяти, но не разрешается одновременная запись в одну и ту же область памяти.
Concurrent Read Concurrent Write (CRCW) - Всем процессорам разрешено читать или записывать в одну и ту же ячейку памяти одновременно.

Есть много методов реализации модели PRAM, но наиболее известные из них -

Модель с общей памятью
Модель передачи сообщений
Параллельная модель данных

Модель общей памяти

Общая память подчеркивает control parallelism чем на data parallelism. В модели с общей памятью несколько процессов выполняются на разных процессорах независимо, но используют общее пространство памяти. Из-за любой активности процессора, если есть какие-либо изменения в какой-либо области памяти, они видны остальным процессорам.

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

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

Thread libraries- Библиотека потоков допускает одновременное выполнение нескольких потоков управления в одном и том же месте памяти. Библиотека потоков предоставляет интерфейс, который поддерживает многопоточность через библиотеку подпрограмм. Он содержит подпрограммы для
- Создание и уничтожение потоков
- Планирование выполнения потока
- передача данных и сообщений между потоками
- сохранение и восстановление контекстов потоков

Примеры библиотек потоков включают - потоки SolarisTM для Solaris, потоки POSIX, реализованные в Linux, потоки Win32, доступные в Windows NT и Windows 2000, и потоки JavaTM как часть стандартного комплекта разработки JavaTM (JDK).

Distributed Shared Memory (DSM) Systems- Системы DSM создают абстракцию совместно используемой памяти на слабосвязанной архитектуре для реализации программирования совместно используемой памяти без аппаратной поддержки. Они реализуют стандартные библиотеки и используют расширенные функции управления памятью на уровне пользователя, имеющиеся в современных операционных системах. Примеры включают систему маркировки протектора, Munin, IVY, Shasta, Brazos и Cashmere.
Program Annotation Packages- Это реализовано на архитектурах с одинаковыми характеристиками доступа к памяти. Наиболее ярким примером пакетов аннотации программ является OpenMP. OpenMP реализует функциональный параллелизм. В основном он фокусируется на распараллеливании циклов.

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

Достоинства программирования с общей памятью

Глобальное адресное пространство обеспечивает удобный подход к программированию памяти.
Благодаря близости памяти к ЦП обмен данными между процессами происходит быстро и единообразно.
Нет необходимости четко указывать обмен данными между процессами.
Накладные расходы на коммуникацию процесса незначительны.
Учиться очень легко.

Недостатки программирования с общей памятью

Он не переносится.
Управлять местонахождением данных очень сложно.

Модель передачи сообщений

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

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

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

Процессоры могут связываться друг с другом любым из следующих способов:

Двухточечная связь
Коллективное общение
Интерфейс передачи сообщений

Двухточечная связь

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

Synchronous mode - Следующее сообщение отправляется только после получения подтверждения о доставке его предыдущего сообщения, чтобы сохранить последовательность сообщения.
Asynchronous mode - Для отправки следующего сообщения получение подтверждения доставки предыдущего сообщения не требуется.

Коллективное общение

Коллективное общение включает более двух процессоров для передачи сообщений. Следующие режимы позволяют коллективное общение -

Barrier - Барьерный режим возможен, если все процессоры, участвующие в обмене данными, работают с определенным блоком (известным как barrier block) для передачи сообщений.
Broadcast - Вещание бывает двух видов -
- One-to-all - Здесь один процессор с одной операцией отправляет одно и то же сообщение всем другим процессорам.
- All-to-all - Здесь все процессоры отправляют сообщение всем другим процессорам.

Передаваемые сообщения могут быть трех типов:

Personalized - Уникальные сообщения отправляются всем остальным процессорам назначения.
Non-personalized - Все процессоры назначения получают одно и то же сообщение.
Reduction - При сокращенной трансляции один процессор группы собирает все сообщения от всех других процессоров в группе и объединяет их в одно сообщение, к которому могут получить доступ все остальные процессоры в группе.

Достоинства передачи сообщений

Обеспечивает низкоуровневый контроль параллелизма;
Он портативный;
Меньше подвержен ошибкам;
Меньше накладных расходов при параллельной синхронизации и распределении данных.

Недостатки передачи сообщений

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

Библиотеки передачи сообщений

Есть много библиотек для передачи сообщений. Здесь мы обсудим две из наиболее часто используемых библиотек передачи сообщений:

Интерфейс передачи сообщений (MPI)
Параллельная виртуальная машина (PVM)

Интерфейс передачи сообщений (MPI)

Это универсальный стандарт для обеспечения связи между всеми параллельными процессами в системе с распределенной памятью. Большинство обычно используемых платформ параллельных вычислений предоставляют по крайней мере одну реализацию интерфейса передачи сообщений. Он был реализован как набор предопределенных функций, называемыхlibrary и могут вызываться из таких языков, как C, C ++, Fortran и т. д. MPI быстрые и переносимые по сравнению с другими библиотеками передачи сообщений.

Merits of Message Passing Interface

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

Demerits of Message Passing Interface

Для параллельного алгоритма требуется больше изменений в программировании;
Иногда бывает трудно отладить; и
Плохо работает в сети связи между узлами.

Параллельная виртуальная машина (PVM)

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

Features of PVM

Очень проста в установке и настройке;
Несколько пользователей могут использовать PVM одновременно;
Один пользователь может выполнять несколько приложений;
Это небольшой пакет;
Поддерживает C, C ++, Fortran;
Для данного запуска программы PVM пользователи могут выбрать группу машин;
Это модель передачи сообщений,
Расчет на основе процессов;
Поддерживает гетерогенную архитектуру.

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

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

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

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

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

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

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

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

Связанный список
Arrays
Сеть гиперкуба

Связанный список

Связанный список - это структура данных, имеющая ноль или более узлов, соединенных указателями. Узлы могут занимать или не занимать последовательные ячейки памяти. Каждый узел состоит из двух или трех частей - однойdata part который хранит данные, а два других link fieldsкоторые хранят адрес предыдущего или следующего узла. Адрес первого узла хранится во внешнем указателе, называемомhead. Последний узел, известный какtail, вообще не содержит адреса.

Есть три типа связанных списков -

Односвязный список
Двусвязный список
Циркулярный связанный список

Односвязный список

Узел односвязного списка содержит данные и адрес следующего узла. Внешний указатель называетсяhead хранит адрес первого узла.

Двусвязный список

Узел двусвязного списка содержит данные и адрес как предыдущего, так и следующего узла. Внешний указатель называетсяhead хранит адрес первого узла и внешний указатель, называемый tail хранит адрес последнего узла.

Циркулярный связанный список

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

Массивы

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

В statically declared arrays, размер и размер массивов известны во время компиляции.
В dynamically declared arrays, размер и размер массива известны во время выполнения.

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

Сеть гиперкуба

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

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

Разделяй и властвуй
Жадный метод
Динамическое программирование
Backtracking
Ветвь и граница
Линейное программирование

Разделяй и властвуй метод

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

Подход «разделяй и властвуй» включает следующие шаги на каждом уровне:

Divide - Исходная проблема разделена на подзадачи.
Conquer - Подзадачи решаются рекурсивно.
Combine - Решения подзадач объединяются, чтобы получить решение исходной проблемы.

Подход «разделяй и властвуй» применяется в следующих алгоритмах:

Бинарный поиск
Быстрая сортировка
Сортировка слиянием
Целочисленное умножение
Обращение матрицы
Умножение матриц

Жадный метод

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

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

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

Динамическое программирование

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

Рекурсивный алгоритм для рядов Фибоначчи - пример динамического программирования.

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

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

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

Ветвь и граница

Алгоритм ветвей и границ - это метод оптимизации для получения оптимального решения проблемы. Он ищет лучшее решение для данной проблемы во всем пространстве решения. Границы оптимизируемой функции объединяются со значением последнего лучшего решения. Это позволяет алгоритму полностью находить части пространства решений.

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

Линейное программирование

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

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

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

Ячеистая сеть

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

Общее количество узлов = (количество узлов в строке) × (количество узлов в столбце)

Ячеистую сеть можно оценить с использованием следующих факторов:

Diameter
Ширина бисекции

Diameter - В ячеистой сети самый длинный distanceмежду двумя узлами находится его диаметр. P-мерная ячеистая сеть, имеющаяkP узлов имеет диаметр p(k–1).

Bisection width - Ширина бисекции - это минимальное количество ребер, которое необходимо удалить из сети, чтобы разделить ячеистую сеть на две половины.

Умножение матриц с использованием ячеистой сети

Мы рассмотрели SIMD-модель 2D ячеистой сети с циклическими соединениями. Мы разработаем алгоритм для умножения двух массивов n × n с использованием n ² процессоров за определенный промежуток времени.

Матрицы A и B имеют элементы a _ij и b _ij соответственно. Элемент обработки PE _ij представляет собой a _ij и b _ij . Расположите матрицы A и B таким образом, чтобы у каждого процессора была пара элементов для умножения. Элементы матрицы A будут двигаться влево, а элементы матрицы B - вверх. Эти изменения положения элементов в матрице A и B представляют каждый элемент обработки PE новой парой значений для умножения.

Шаги в алгоритме

Расположите две матрицы в шахматном порядке.
Вычислить все произведения, a _ik × b _kj
Подсчитайте суммы по завершении шага 2.

Алгоритм

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Сеть гиперкуба

Гиперкуб - это n-мерная конструкция, в которой ребра перпендикулярны друг другу и имеют одинаковую длину. N-мерный гиперкуб также известен как n-куб или n-мерный куб.

Особенности Hypercube с ^2k узлами

Диаметр = k
Ширина бисекции = 2 ^{k – 1}
Количество ребер = k

Умножение матриц с использованием сети гиперкуба

Общая спецификация сетей Hypercube -

Позволять N = 2^m- общее количество процессоров. Пусть это будут процессоры P _0, P ₁ … ..P _N-1 .
Пусть i и i ^b - два целых числа, 0 <i, i ^b <N-1, и его двоичное представление отличается только позицией b, 0 <b <k – 1.
Рассмотрим две матрицы размера n × n, матрицу A и матрицу B.
Step 1- Элементы матрицы A и матрицы B назначаются n ³ процессорам, так что процессор в позиции i, j, k будет иметь _ji и b _ik .
Step 2 - Весь процессор в позиции (i, j, k) вычисляет продукт

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 - Сумма C (0, j, k) = ΣC (i, j, k) для 0 ≤ i ≤ n-1, где 0 ≤ j, k <n – 1.

Блок-матрица

Блочная матрица или разделенная матрица - это матрица, в которой каждый элемент сам представляет собой отдельную матрицу. Эти отдельные разделы известны какblock или же sub-matrix.

пример

На рисунке (а) X - это блочная матрица, где A, B, C, D - сами матрицы. На рисунке (f) показана полная матрица.

Блочное умножение матриц

Когда две блочные матрицы являются квадратными матрицами, они умножаются так же, как мы выполняем простое умножение матриц. Например,

Сортировка - это процесс расположения элементов в группе в определенном порядке, то есть по возрастанию, убыванию, алфавиту и т. Д. Здесь мы обсудим следующее:

Сортировка перечислением
Сортировка нечетно-четным транспонированием
Параллельная сортировка слиянием
Сверхбыстрая сортировка

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

Сортировка перечислением

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

Следовательно, для любых двух элементов a _i и a _j должен выполняться любой из следующих случаев:

_я <а _J
а _я > а _j
а _я = а _j

Алгоритм

procedure ENUM_SORTING (n)

begin
   for each process P_1,j do
      C[j] := 0;
		
   for each process P_{i, j} do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

Сортировка нечетно-четным транспонированием

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

Алгоритм

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

Параллельная сортировка слиянием

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

Алгоритм

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

Сверхбыстрая сортировка

Гипербыстрая сортировка - это реализация быстрой сортировки на гиперкубе. Его шаги следующие -

Разделите несортированный список между каждым узлом.
Отсортируйте каждый узел локально.
Из узла 0 транслируйте медианное значение.
Разделите каждый список локально, а затем обменяйте половинки по самому высокому измерению.
Повторите шаги 3 и 4 параллельно, пока размер не достигнет 0.

Алгоритм

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;
	
   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then
		
      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif
      
      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for
		
   sort B using sequential quicksort;
	
end HYPERQUICKSORT

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

Разделяй и властвуй
Поиск в глубину
Поиск в ширину
Поиск лучшего первого

Разделяй и властвуй

Подход «разделяй и властвуй» включает следующие шаги на каждом уровне:

Divide - Исходная проблема разделена на подзадачи.
Conquer - Подзадачи решаются рекурсивно.
Combine - Решения подзадач объединяются, чтобы получить решение исходной проблемы.

Бинарный поиск - это пример алгоритма «разделяй и властвуй».

Псевдокод

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

Поиск в глубину

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

Шаги поиска в глубину

Рассмотрим узел (корень), который ранее не посещался, и отметьте его посещенным.
Посетите первый соседний узел-преемник и отметьте его посещенным.
Если все узлы-преемники рассматриваемого узла уже посещены или у него больше нет узла-преемника, вернитесь к его родительскому узлу.

Псевдокод

Позволять v - вершина, с которой начинается поиск в Graph G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

Поиск в ширину

Поиск в ширину (или BFS) - это алгоритм поиска в дереве или структуре данных неориентированного графа. Здесь мы начинаем с узла, затем посещаем все соседние узлы на том же уровне, а затем переходим к соседнему узлу-преемнику на следующем уровне. Это также известно какlevel-by-level search.

Шаги поиска в ширину

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

Псевдокод

Позволять v - вершина, с которой начинается поиск в Graph G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Поиск лучшего первого

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

Шаги поиска лучшего первого

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

Псевдокод

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure

Граф - это абстрактное обозначение, используемое для представления связи между парами объектов. График состоит из -

Vertices- Связанные объекты в графе называются вершинами. Вершины также известны какnodes.
Edges - Ребра - это звенья, соединяющие вершины.

Есть два типа графиков -

Directed graph - В ориентированном графе ребра имеют направление, т. Е. Ребра переходят из одной вершины в другую.
Undirected graph - В неориентированном графе ребра не имеют направления.

Раскраска графика

Раскраска графа - это метод присвоения цвета вершинам графа таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет. Некоторые проблемы с раскраской графа -

Vertex coloring - Способ раскраски вершин графа так, чтобы никакие две соседние вершины не имели одинаковый цвет.
Edge Coloring - Это метод присвоения цвета каждому краю, чтобы никакие два соседних края не имели одинаковый цвет.
Face coloring - Он назначает цвет каждой грани или области плоского графа, чтобы никакие две грани, имеющие общую границу, не имели одинаковый цвет.

Хроматический номер

Хроматическое число - это минимальное количество цветов, необходимое для раскрашивания графика. Например, хроматическое число следующего графика - 3.

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

Шаги по раскраске графа

Установите начальное значение каждого процессора в n-мерном массиве равным 1.
Теперь, чтобы назначить конкретный цвет вершине, определите, назначен ли этот цвет соседним вершинам или нет.
Если процессор обнаруживает одинаковый цвет в соседних вершинах, он устанавливает его значение в массиве равным 0.
После выполнения n ² сравнений, если какой-либо элемент массива равен 1, это допустимая окраска.

Псевдокод для раскраски графов

begin

   create the processors P(i₀,i₁,...i_n-1) where 0_i_v < m, 0 _ v < n
   status[i0,..i_n-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if a_j,k=1 and i_j=i_kthen
            status[i₀,..i_n-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Минимальное связующее дерево

Остовное дерево, сумма веса (или длины) всех его ребер меньше, чем все другие возможные остовные деревья графа G, называется остовным деревом. minimal spanning tree или же minimum cost spanningдерево. На следующем рисунке показан взвешенный связный граф.

Некоторые возможные остовные деревья приведенного выше графика показаны ниже -

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

Для реализации минимального связующего дерева затрат используются следующие два метода:

Алгоритм Прима
Алгоритм Крускала

Алгоритм Прима

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

Шаги алгоритма Прима

Выберите любую вершину, скажем v ₁ Графа G.
Выберите ребро, скажем e ₁ графа G, так чтобы e ₁ = v ₁ v ₂ и v ₁ ≠ v ₂ и e ₁ имел минимальный вес среди ребер, инцидентных v ₁ в графе G.
Теперь, после шага 2, выберите минимально взвешенное ребро, приходящееся на v ₂ .
Продолжайте это, пока не будет выбрано n – 1 ребро. Вотn количество вершин.

Минимальное остовное дерево -

Алгоритм Крускала

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

Шаги алгоритма Крускала

Выберите кромку минимального веса; скажем, e ₁ из Графика G и e ₁ не является петлей.
Выберите следующее ребро с минимальным весом, подключенное к e ₁ .
Продолжайте это, пока не будет выбрано n – 1 ребро. Вотn количество вершин.

Минимальное остовное дерево приведенного выше графа -

Алгоритм кратчайшего пути

Алгоритм кратчайшего пути - это метод поиска пути с наименьшей стоимостью от исходного узла (S) до конечного узла (D). Здесь мы обсудим алгоритм Мура, также известный как алгоритм поиска в ширину.

Алгоритм Мура

Обозначьте исходную вершину S и пометьте ее i и установить i=0.
Найдите все непомеченные вершины, смежные с вершиной, помеченной i. Если с вершиной S не соединены никакие вершины, то вершина D не соединена с S. Если есть вершины, соединенные с S, пометьте ихi+1.
Если помечено D, перейдите к шагу 4, иначе перейдите к шагу 2, чтобы увеличить i = i + 1.
Остановитесь после того, как будет найдена длина кратчайшего пути.

Параллельный алгоритм - Краткое руководство

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

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

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

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

Компьютеры SISD

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

Компьютеры MISD

Компьютеры MIMD

Запись

Сложность времени

Асимптотический анализ

Обозначение Big O

Обозначение омега

Тета-нотация

Ускорение алгоритма

Количество используемых процессоров

Общая стоимость

Параллельные данные

Модель графа задач

Модель рабочего бассейна

Модель Мастер-Раб

Меры предосторожности при использовании модели ведущий-ведомый

Модель трубопровода

Гибридные модели

Модель общей памяти

Достоинства программирования с общей памятью

Недостатки программирования с общей памятью

Модель передачи сообщений

Двухточечная связь

Коллективное общение

Достоинства передачи сообщений

Недостатки передачи сообщений

Библиотеки передачи сообщений

Интерфейс передачи сообщений (MPI)

Параллельная виртуальная машина (PVM)

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

Связанный список

Односвязный список

Двусвязный список

Циркулярный связанный список

Массивы

Сеть гиперкуба

Разделяй и властвуй метод

Жадный метод

Динамическое программирование

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

Ветвь и граница

Линейное программирование

Ячеистая сеть

Умножение матриц с использованием ячеистой сети

Шаги в алгоритме

Алгоритм

Сеть гиперкуба

Особенности Hypercube с 2k узлами

Умножение матриц с использованием сети гиперкуба

Блок-матрица

пример

Блочное умножение матриц

Сортировка перечислением

Алгоритм

Сортировка нечетно-четным транспонированием

Алгоритм

Параллельная сортировка слиянием

Алгоритм

Сверхбыстрая сортировка

Алгоритм

Разделяй и властвуй

Псевдокод

Поиск в глубину

Шаги поиска в глубину

Псевдокод

Поиск в ширину

Шаги поиска в ширину

Псевдокод

Поиск лучшего первого

Шаги поиска лучшего первого

Псевдокод

Раскраска графика

Хроматический номер

Особенности Hypercube с ^2k узлами