Учебники

Параллельный алгоритм – структура

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

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

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

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

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

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

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

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

  • Единственный связанный список
  • Двусвязный список
  • Круговой связанный список

Единственный связанный список

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

Единственный связанный список

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

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

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

Круговой связанный список

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

Круговой связанный список

Массивы

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

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

  • В динамически объявленных массивах размер и размер массива известны во время выполнения.

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

В динамически объявленных массивах размер и размер массива известны во время выполнения.

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

Сеть гиперкубов

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