Тема 13 — Архитектура на паметта в паралелните компютри

Назначението на паметта в компютъра е изключително ясно — да съхранява информацията и да я предава в бъдещето. Организацията на паметта е обект на задълбочено изследване в продължение на десетилетия. Понастоящем съществуват два основни подхода: вертикална (йерархична) организация и хоризонтална организация чрез разслояване на адресното пространство.

1. Вертикална (йерархична) организация на паметта

1.1. Същност и мотивация

Идеалната структурна организация на паметта е тази с едно ниво — т.нар. „плосък” модел, при който процесорът чете и записва само от една единствена памет. Подобна организация е невъзможна по две фундаментални причини:

• Един бит бърза памет е значително по-скъп от един бит бавна памет.
• С нарастване обема на паметта нараства и времето за достъп до произволен адрес при еднаква производствена технология.

Ето защо в почти всички съвременни компютри паметта е структурирана йерархично: най-близо до процесора се намира най-бързата, но с малък обем памет, а най-голямата по обем, но и с най-голямо латентно за достъп, памет е най-отдалечена.

Пирамидален модел на йерархията на паметта: от регистрите (върха) до магнитния диск (основата).

Структурата обхваща следните нива (от най-бързо към най-бавно):

1. Регистри — вградени в процесора; обем от порядъка на 1 KB; достъп за 1–3 ns.
2. L1 кеш — в чипа на процесора; 8–128 KB; достъп за 2–8 ns.
3. L2 кеш — извън чипа; 0,5–8 MB; достъп за 5–12 ns.
4. Основна (оперативна) памет — DRAM; от 61 MB до 1 GB; достъп за 10–60 ns.
5. Вторична (външна) памет — магнитни дискове; 20–100 GB; достъп от порядъка на 3–10 милиона ns.

Максималната скорост на предаване на информацията от/към паметта е известна като ширина на лентата на предаване (bandwidth). За да не зависи средната скорост на изчисление от по-тясната лента на по-ниските нива, е необходимо изчислителният процес да максимизира използването на паметта от най-високо ниво преди да се наложи презареждане от по-ниско ниво. Механизмът, осъществяващ тази динамика, се нарича виртуална организация на паметта.

Вертикалната структура на паметта осигурява:

• Подобрени работни характеристики на процесора.
• Увеличена пропускателна способност на компютъра.
• Достъп до големи количества данни за приемливо малко време.

1.2. Архитектура на кеш паметта

1.2.1. Работа на кеш паметта

Кеш паметта е ключът за осигуряване на производителност при съвременните процесори. Около 25% от инструкциите в типична програма се отнасят до паметта, поради което времето за достъп до паметта е критичен фактор. Чрез ефективното редуциране на това време кеш паметта позволява изпълнението на повече от една инструкция за цикъл в съвременните процесори.

Работата на кеш паметта се базира на локалността на обръщенията — универсално свойство на програмите независимо от техния вид (комерсиални, научни, игри). Съществуват два типа локалност:

А) Локалност по време — веднъж направено обръщение към дадена позиция от паметта, съществува голяма вероятност тя да бъде потърсена отново в близкото бъдеще. Типични примери: цикли, извиквания на подпрограми, горещи данни (броячи, стекови променливи, натрупващи се променливи).

Б) Локалност по пространство (специална локалност) — когато се адресира клетка от паметта, съседните клетки вероятно ще бъдат достъпни скоро. Типични примери: последователен поток от инструкции, обработка на матрици и низове от началото до края.

Локалността по време включва в себе си локалността по пространство, но не и обратно. Именно поради факта, че приложенията проявяват изключителна локалност по време за код и по-слаба за данни, кеш паметта се разделя на icache (за инструкции) и d-cache (за данни).

1.2.2. Включваща и изключваща организация

При включващата (inclusive) структура паметта с по-голям номер на нивото съдържа в себе си и информацията от по-ниските нива. Например L2 кеш съдържа всичко, намиращо се в L1, а оперативната памет съдържа съдържанието на L2. При тази организация общият обем на кеш паметта е равен на обема на последното ниво преди оперативната памет.

При изключващата (exclusive) организация — въведена от AMD при серията Duron — L1 и L2 съдържат различна информация. Поради голям обем L1 (128 KB) и малък L2 (64 KB) включващата организация е практически невъзможна. При изключващата организация общият обем е сумата от обемите на всички нива, но за сметка на по-сложни алгоритми за управление.

1.2.3. Методи за свързване: асоциативност

Когато процесорът изисква байт от паметта, трябва бързо да се определи дали желаният блок се намира в кеш паметта (cache hit или cache miss), неговата позиция и позицията на търсения байт вътре в блока. За целта се използва спомагателна памет (tag RAM), в която за всеки фрейм се съхраняват признаци (тагове).

Съществуват три метода за свързване:

Пълна асоциативност — всеки блок от оперативната памет може да бъде свързан към всеки фрейм на кеш паметта. Претърсва се цялата tag RAM, което при по-голяма кеш памет носи значителни закъснения. Не се използва широко.

Директно съответствие (direct-mapped) — всеки блоков фрейм се свързва с определено подмножество от основната памет. Броят на търсенията в tag RAM е минимален, но е налице риск от колизии: когато два или повече блока, нужни едновременно, се конкурират за един и същ фрейм, ефективността на кеширането рязко пада.

n-кратна (частична) асоциативност (set-associative) — комбинация от горните два. Определени подмножества от паметта могат да се поместят в определени групи фреймове. Например при четирикратна асоциативност (four-way set associative) кеш паметта е разделена на групи от по четири фрейма. Намалява закъсненията при търсене в сравнение с пълната асоциативност, и едновременно снижава вероятността от колизии в сравнение с директното съответствие.

Директното съответствие е еднопътна асоциативна кеш памет; пълно асоциативна кеш памет е n-кратно асоциативна, при която n е равно на общия брой блокове.

1.2.4. Стратегии за заместване

При постъпване на нов блок трябва да се реши кой съществуващ блок да бъде заместен. Най-разпространената стратегия е LRU (Least Recently Used) — замества се блокът, използван преди най-много време. Тя отчита локалността на обръщенията, за разлика от по-простите FIFO, LIFO или произволно заместване.

1.2.5. Стратегии за запис

При операция запис от страна на процесора съществуват две стратегии:

• Write-back — модифицираната информация се записва само в L1 кеш; обновяването на останалите нива се извършва едва при заместване на блока. По-добра производителност, тъй като по-рядко се налага прехвърляне.
• Write-through — информацията се записва едновременно по всички нива. По-лесно поддържане на валидността в многопроцесорни системи и при интензивен вход/изход.

1.2.6. Съгласуваност на данните в кеш паметите (Cache Coherence)

В паралелни компютри от тип SMP (Symmetrical Multiple Processors), където множество процесори с вградена кеш памет споделят обща памет, е налице проблем с кохерентността (coherence) на данните. Когато процесор #1 модифицира копие на операнд в своя кеш, копията в кешовете на останалите процесори стават невалидни.

Решението е въвеждане на „подслушване” (snooping) на системния интерфейс на хардуерно ниво. Един от най-разпространените протоколи е MESI, при който всяка кешова линия може да е в едно от четири състояния:

• Modified — линията е модифицирана; копието в основната памет е невалидно.
• Exclusive — единствено копие в кеш паметта; основната памет е валидна.
• Shared — повече от един кеш съдържа копие; копието в основната памет е валидно.
• Invalid — кешовата линия е невалидна.

1.2.7. Размер на кешовия блок

С увеличаване размера на блока се реализира по-добре локалността по пространство, но само до определен предел. При постоянен обем на кеш паметта по-голям блок означава по-малко блокове в кеша, по-малко набори и по-голяма вероятност от пропуск (cache miss). Освен това голям блок може да „замърсява” кеша с неизползвани данни и да изчерпва ширината на лентата на пропускане на шината.

1.2.8. Латентност и пропускателна способност

Латентността е времето между изпращане на заявката от процесора и получаване на отговора. Включва: времето до достигане на паметта, времето за намиране на информацията и времето за връщане на данните.

Пропускателната способност е реалното количество предадена информация за единица време. Максималната пропускателна способност е теоретична стойност, недостижима на практика поради необходимостта от резервиране на шината за адресиране и управление. Ефективната пропускателна способност нараства значително при използването на Burst Mode — при едно обръщение към паметта се предава цял блок (например 32 байта), като само първото предаване изисква пълно закъснение, а останалите следват без изчакване.

Пример: при шина 133 MHz, 8 байта ширина, блок 32 байта — ефективна пропускателна способност нараства от около 266 MB/s (при единично предаване) до около 607,5 MB/s (при Burst Mode).

2. Хоризонтална организация

При хоризонталната организация целта не е намаляване на времето за достъп (както при вертикалната), а увеличаване на броя на достъпите за единица време. Тази организация засяга само основната памет и се прилага когато кеш паметта е невъзможна или нецелесъобразна — например във векторните компютри и компютрите с потоково управление.

Най-простата хоризонтална организация разбива паметта физически на две половини с едновременен достъп — командите в едната, данните в другата. Това по същество е Харвардската архитектура, реализирана за пръв път в компютъра STRECH на IBM. В съвременните процесори именно така е организиран достъпът до L1 кеш (icache / d-cache).

Хоризонталната организация (разслоена памет, memory interleaving) може да бъде изградена по два начина:

2.1. Пакетна обработка (batch memory)

Паметта е физически разбита на N модула; при всяко обръщение се четат N последователни думи паралелно. Ако N = 2^k и M = 2^m, старшите m разряда от (m+k)-разрядния адрес се изпращат към всички модули, а младшите k разряда определят коя от N-те думи да се чете първа. Прочетените думи се поместват в буфери и при следващото обръщение се четат от там с N пъти по-висока скорост от времето за достъп до отделния модул.

Тази структура е идеална при последователен достъп (вектори), но при произволен достъп (програми с много преходи) средното време за достъп при последователност с интервал q е: qt/N при q ≤ N и t при q > N.

2.2. Конвейерна памет (pipeline memory)

Фиксаторите са поставени на адресните шини, което позволява за всеки модул да се използва свой относителен адрес. Управлява се от контролер на паметта, обработващ заявките последователно: при свободен модул адресът се буферира и операцията стартира; при зает модул заявката се задържа. При конвейерна обработка се постига N-кратно ускорение за последователни заявки, при условие, че в N последователни заявки нито един модул не се използва повече от веднъж.

Двата метода постигат едни и същи N-кратни ускорения за последователни адреси. Може да се докаже, че при произволна равномерна последователност с интервал, различен от N, N-кратно разслоената памет работи поне два пъти по-бързо от единичен модул.

3. Разположение на данните в паметта

При разслоената памет е критично важно как се разпределят данните по модулите. Разгледаме съхранение на матрица X(4,4) в четирикратно разслоена памет.

Стандартно (row-major) разпределение — елементите се подреждат по редове. Безконфликтен достъп до елементи от един ред или по диагонали, но конфликт при достъп по стълб (всички елементи на стълба са в един модул).

Скосено (skewed) разпределение — ред i се смества с i позиции. Осигурява безконфликтен паралелен достъп едновременно по редове и по стълбове, но не и по диагоналите. Езикът TRANQUIL за ILLIAC-IV е предвиждал оператори STRAIGHT и SKEWED за управление на начина на разместване.

Напълно безконфликтна организация — използват се повече модули памет от броя на процесорите. Може да се докаже, че за степен на паралелизъм N броят на модулите M трябва да бъде първото просто число по-голямо от N. В компютъра BSP на Burroughs с 512 процесора са използвани 521 модула памет (първото просто число над 512).

Резюме

• Йерархичната организация на паметта е мотивирана от компромиса цена/скорост/обем: регистри → L1/L2/L3 кеш → RAM → диск.
• Кеш паметта експлоатира локалността на обръщенията (по време и по пространство), за да намали ефективното латентно за достъп.
• Три метода на асоциативност управляват кеш-паметта: директно съответствие (бързо, склонно към колизии), пълна асоциативност (гъвкава, бавна) и n-кратна асоциативност (компромисно решение, широко прилагано).
• Протоколът MESI решава проблема с кохерентността на данните в SMP системи чрез четири-стойностна машина на състоянията за всяка кешова линия.
• Хоризонталната (разслоена) организация увеличава броя достъпи за единица време чрез N-кратно разслояване на адресното пространство между N модула памет.
• Правилното разпределение на данните в паметта (скосено или простo-числова организация) е предпоставка за безконфликтен паралелен достъп.