Параллельная внешняя память
-
Обзор модели PEM
- Модель PEM — это вычислительная модель с иерархией памяти, включающей основную память и кэши.
- Процессоры совместно используют основную память, но каждый кэш является эксклюзивным для одного процессора.
- Сложность ввода-вывода в модели PEM определяется количеством параллельных блоков, передаваемых между основной памятью и кэшем.
-
Конфликты чтения/записи
- В модели PEM нет прямой связи между процессорами, поэтому они взаимодействуют косвенно через основную память.
- Возникают конфликты чтения/записи при одновременном доступе нескольких процессоров к одному блоку в основной памяти.
-
Алгоритмы решения конфликтов
- Существуют три варианта решения проблемы экипажа: одновременное чтение и запись, одновременное чтение и исключительная запись, и исключительное чтение и запись.
- Первый подход к решению проблемы экипажа заключается в сериализации операций записи, что приводит к
- P
- параллельным блочным передачам.
- Второй подход требует
- O
- (
- log
-
- ))
- параллельных передач блоков и дополнительного блока для каждого процессора.
-
Сравнение с другими моделями
- Модель PEM может быть использована для решения задач, таких как многоходовое разделение и выбор, с оптимальной сложностью ввода-вывода.
- Сложность сортировки в модели PEM зависит от количества процессоров и размера входных данных.
-
Рекомендации
- Модель PEM является важным инструментом для анализа и оптимизации параллельных алгоритмов.