Совокупно опишу три модели памяти, их ключевые свойства и как они влияют на проектирование алгоритмов и систем.
1) Совместная (shared) память
- Что это: несколько потоков/процессов имеют прямой доступ к общему адресному пространству (общие переменные). Аппаратно — UMA/NUMA, кэш‑коhеренс.
- Ключевые характеристики: общая адресная абстракция, кэш‑коерентность, аппаратная/программная поддержка атомарных операций. Модель согласованности (sequential consistency, weak/relaxed) задаёт, какие перестановки операций допустимы.
- Влияние на дизайн:
- Синхронизация: нужны мьютексы, семафоры, атомарные примитивы и барьеры для корректности; стоимость синхронизации и сильная согласованность ухудшают масштабируемость.
- Локальность и кэш‑эффекты: важно минимизировать ложное совместное использование (false sharing) и работать по локальным данным (NUMA-aware allocation).
- Модель для алгоритмов: PRAM (EREW/CREW/CRCW) даёт теоретическую основу; на практике оптимизируют доступы к кэшу, уменьшают синхронизацию и используют lock‑free/ wait‑free структуры.
- Производительность: время ≈ $T=T_{comp}+T_{sync}+T_{cache\_coh}$, где $T_{sync}$ и накладные на когерентность могут доминировать при высокой конкуренции.
2) Виртуальная память
- Что это: процесс видит собственное логическое адресное пространство, ОС/ММU переводит виртуальные адреса в физические с использованием страниц, TLB, страничного обмена.
- Ключевые характеристики: трансляция адресов, TLB‑попадания/промахи, страничные ошибки (page faults), политика замещения (LRU, CLOCK и т.д.), память может быть «внешней» (swap, mmap).
- Влияние на дизайн:
- Локальность доступа: алгоритмы должны обеспечивать хорошую пространственно‑временную локальность (обход по строкам массива, блочная обработка), чтобы минимизировать TLB/страничные промахи.
- Работа с объёмами > ОЗУ: проектирование внешней (out‑of‑core) логики, деление на блоки размером страницы/страничного набора.
- Стоимость промаха: страничный промах стоит на порядки дороже чтения из RAM, поэтому нужно оценивать «рабочее множество» (working set) и выбирать структуры/порядки, уменьшающие кеш‑ и страничные промахи.
- В системах: использование mmap, предварительное резервирование/huge pages, оптимизация TLB (управление степенью параллелизма и степенью локальности).
- Формула затрат (упрощённо): $T\approx T_{mem}+P_{pf}\cdot T_{pf}$, где $P_{pf}$ — вероятность страничного промаха, $T_{pf}$ — его стоимость.
3) Распределённая (distributed) память
- Что это: каждый узел имеет свою локальную память; взаимодействие только через явные сообщения (RPC, MPI, sockets). Абстракция — сообщение/трансляция данных.
- Ключевые характеристики: высокая латентность межузловых операций, ограниченная пропускная способность, отказоустойчивость/частичные отказы, отсутствие общей последовательной памяти.
- Влияние на дизайн:
- Коммуникационная стоимость: алгоритмы учитывают латентность и ширину полосы; модель затрат часто представляют как $T_{comm}=\alpha +\beta m$ (латентность $\alpha$ + коэффициент на байт $\beta$·размер сообщения $m$). Итоговое время: $T=T_{comp}+\sum T_{comm}+T_{sync}$.
- Разделение данных и балансировка: важны дешёвая локальная работа, минимизация объёма и частоты сообщений, правильный шардинг/репликация данных.
- Согласованность и отказоустойчивость: необходимо проектировать протоколы репликации и согласования (CP/CA в CAP), учитывать задержки при достижении консенсуса; требуются алгоритмы устойчивые к частичным отказам (Paxos, Raft) — это меняет как структуру данных, так и задержки.
- Подходы к алгоритмам: BSP/LogP/PRAM (для теории) и практические модели: MapReduce, bulk‑synchronous, потоковые решения. Алгоритмы ориентированы на минимизацию коммуникации и согласований, компромисс между точностью и скоростью (скетчинги, асинхронные обновления).
- Надёжность: дублирование, хранение состояний, устойчивые к сетевым сбоям механизмы.
Краткие практические выводы для проектирования алгоритмов/систем:
- Выбирайте модель, соответствующую топологии и затратам: shared — удобство и быстрая локальная синхронизация; virtual — оптимизировать локальность обращения; distributed — минимизировать коммуникации и проектировать репликацию/консенсус.
- Оптимизируйте локальность (пространственную и временную) для уменьшения кэша/TLB/страничных промахов.
- Минимизируйте синхронизацию и частоту глобальных барьеров в shared и distributed средах.
- Моделируйте затраты явно: используйте $T=T_{comp}+T_{comm}+T_{sync}$ с конкретными параметрами ($\alpha ,\beta$) при выборе алгоритма/параметров.
- На распределённых системах отдавайте приоритет устойчивости и согласованности, когда это критично; в высокопроизводительных вычислениях — предпочитайте слабую согласованность и асинхронность, чтобы скрыть задержки.
Если нужно, могу кратко привести примеры алгоритмов/структур под каждую модель.