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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Массивы

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

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

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

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

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

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