ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 2 Современные компьютеры и подсистема памяти Д. ф.- м. н., профессор А. Г. Тормасов Базовая кафедра « Теоретическая и Прикладная Информатика », МФТИ

Тема Краткий обзор необходимых для понимания дальнейшего изложения основ архитектуры компьютерных систем на базе Intel x86 Рассматриваются с точки зрения прикладного программиста только те компоненты, которые : явно влияют на производительность программы и на поведение которых программист может прямо или косвенно влиять при выборе способа реализации программ и алгоритмов Теоретическая и Прикладная Информатика, МФТИ 2

Архитектура фон Неймана Основные характеристики Программы хранятся в памяти Память разделяется между данными и программами Последовательная модель исполнения Удобно для создания алгоритмов Но : сейчас компьютеры работают НЕ ТАК С одной точки зрения, это похоже на реальные компьютеры С другой, это некая абстракция со своими ограничениями Теоретическая и Прикладная Информатика, МФТИ 3

Типовой PC CPU, один или несколько RAM – системная память Набор системной логики (chipset) Северный мост (Northbridge) Южный мост (Southbridge) Теоретическая и Прикладная Информатика, МФТИ 4

CPU Обычно содержит несколько независимых потоков исполнения Планирование исполнения и контекстные переключения Имитация многозадачности и контекстные переключения, прерывания Тяжесть переключений ( зависит от ОС и типа переключения, обычно велика ) Кэш Быстрая память, многоуровневая, улучшает производительность Interconnect ( соединитель ) Соединяет процессоры и память разных уровней ( включая кэши ) набор аппаратных соединений, имеющих определенную пропускную способность Если не хватает, процессор просто будет ждать ! SMP (symmetric multi processing) NUMA (non uniform memory access). Теоретическая и Прикладная Информатика, МФТИ 5 Работа основных компонент

Кэширование Современные системы используют множество кэшей ( данные, инструкции, TLB и тд ) Многие кэши иерархические Некоторые расположены непосредственно около процессора Обычно гипертреды разделяют L1 Ядра обычно разделяют L2 ( парами ) L3 обычно общий для всех Теоретическая и Прикладная Информатика, МФТИ 6 Шина памяти L3L2L1i L1d

Кэширование Теоретическая и Прикладная Информатика, МФТИ 7 Шина памяти При обращении процессора к памяти сначала проверяется нет ли искомого адреса в кэше Cache miss ( неприсутствие ) o обращение к кэшу o обращение к памяти o освобождение места в кэше o загрузка в кэш (!) o передача в процессор Cache hit ( присутствие ) o обращение к кэшу o передача в процессор Шина памяти

Когерентность кэшей Синхронизация разных кэшей MESI Modifed ( модифицировано ) – линия присутствует только в текущем кэше, и является грязной Exclusive ( уникально ) – линия присутствует только в текущем кэше, и соответствует содержанию памяти ( чистая "). Shared ( разделяемо ) – линия может присутствовать в других кэшах, и соответствует содержанию памяти ( чистая "). Invalid ( недействительно ) – линия недействительна. Теоретическая и Прикладная Информатика, МФТИ 8

Гранулярность кэша Локальность : Используем адрес скоро будем его использовать еще раз берем из кэша Используем адрес скоро будем использовать соседний адрес берем из той же линии кэша Коэффициент попаданий в кэш Мера эффективности Зависит от локальности Нет смысла хранить каждое слово в кэше ( как адресовать ? Не эффективно...) Память разбивается на фиксированные куски – « линии кэша » (32 или 64 байта ) Всегда одинаково выровнены При считывании 1 слова читается целиком вся линия Растет количество обращений к основной памяти Как лучше обращаться к a[i,j]? При записи используется Write Combination Buffer Если недостаточно данных в линии – считывается из памяти перед записью Запись 64 байт подряд – 1 транзакция Запись 63 байт подряд – 8 (!) транзакций Теоретическая и Прикладная Информатика, МФТИ 9

Фальшивое разделение Одна линия кэша содержит данные, относящиеся к разным потокам Каждая модификация данных одним потоком вызывает сброс кэша для второго потока ( и его постоянное перезачитывание из памяти ) Данные реально не разделяются, но накладные расходы как при разделении Следствие гранулярности кэшей и протокола синхронизации int sumLocal[N_THREADS]; … void ThrFnc(thread_data *p) { … int id = p->threadId; sumLocal[id] = 0; … for (i=0; i

Фальшивое разделение Первый поток пишет в свой элемент своей копии линии кэша Эта же линия кэша второго потока инвалидируется ( копия сбрасывается ) Второй поток пытается писать в свой элемент линии кэша – перед этим кэш зачитывается из памяти То же самое происходит и с первым потоком... Теоретическая и Прикладная Информатика, МФТИ 11 Шина памяти MESI

Разные соединители SMP NUMA Теоретическая и Прикладная Информатика, МФТИ 12 Interconnect

Что тут неэффективно ? Поток 1 Поток 2 Теоретическая и Прикладная Информатика, МФТИ 13 { … // получить ссылку // на данные соседа int *pFlag = GetFromRemote(); … while ( !(*pFlag) ) ; … } { int flag = FALSE; … // передать ссылку на // локальную переменную GiveToRemote(&flag); … flag = TRUE; … }

Проблема кэширования Х 86: черезвычайно разветвленная система паралелизма на уровне инструкций Море оптимизаций Много исполнительных блоков, глубокая конвейеризация, суперскалярность, параллельное планирование, умозрительное исполнение инструкций, гигантские буферы для переупорядочения, многоуровневое кэширование Ограничение производительности изза кэширования Черезвычайно низкий уровень промахов по данным и командам Высокая цена промаха, от 10 до 1000 тактов, и увеличивается исторически Работа инструкции в тактах : с регистром 1, кэшом L1 ~3, кэшом L2 ~15, памятью ~200! Закон Мура : удвоение производительности ЦПУ за ~2 года Но : удвоение производительности памяти за ~6 лет, экспоненциальная яма надо все больше уровней кэширования В результате, даже ~5% промахов может доминировать в производительности ! Теоретическая и Прикладная Информатика, МФТИ 14

Доминирующие потери 1985 год : ошибки страниц Локальность данных не так уж важна 1995 год : исполняемые инструкции Локальность данных не так уж важна Важно количество параллельно запускаемых инструкций, доступ к памяти не очень дорог 2005 год : промахи кэшей Локальность данных снова важна ! Не важно количество параллельно запускаемых инструкций, зато доступ к памяти очень дорог Теоретическая и Прикладная Информатика, МФТИ 15

Думай о данных, а не о коде ! В старые времена мы считали инструкции как синоним времени исполнения ( предсказуемо ) Сейчас производительность определяется схемой доступа к памяти Много разименований a->b->с… много промахов кэша : лишний уровень доступа – ЗЛО Много уровней абстракции ( типа SOAP->XML->DOM…) много конверсий, и каждая прогон через кэш – ЗЛО ( не говорите этого любителям ООП, это их хлеб !) Теоретическая и Прикладная Информатика, МФТИ 16

Выводы Современные компьютеры достаточно далеко отошли от классической схемы фон Неймана, все выглядит просто, но на самом деле... Существуют скрытые ( без явных команд контроля ) устройства, скорость работы которых определяет скорость работы компьютера ( система кэширования и поддержки когерентности ) Сейчас доминируют потери, вызванные « дороговизной » промахов кэша – за ними надо следить и их надо избегать ; шаблон доступа к памяти часто определяет производительность в целом При написании программ : Конверсии из формата в формат, многоуровневые структуры – избегать ! Разделяемые данные – терпимо ( на чтение, через кэширование ) Изменяемые данные – терпимо ( как можно локальнее ) Изменяемые + разделяемые данные – избегать ! 17 Теоретическая и Прикладная Информатика, МФТИ

(с) А. Тормасов, г. Базовая кафедра « Теоретическая и Прикладная Информатика » ФУПМ МФТИ crec.mipt.ru_ Для коммерческого использования курса просьба связаться с автором. Теоретическая и Прикладная Информатика, МФТИ 18