Реферат: Удк 004. 074 А. Е. Шерстнёв, старший инженер ОАО «инэум»

УДК 004.074

А.Е. Шерстнёв, старший инженер ОАО «ИНЭУМ»,

Ю.А. Недбайло, инженер ОАО «ИНЭУМ»


Оптимизация доступа к памяти в вычислительном комплексе "Эльбрус-3S"


Аннотация

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

В статье рассматривается организация подсистемы памяти вычислительного комплекса (ВК) «Эльбрус-3S». Основное внимание уделено аппаратным оптимизациям, направленным на сокращение времени и увеличение коэффициента использования внешнего канала доступа к памяти. На уровне интерфейсной электроники время сокращается применением сквозных передач, в то время как эффективность канала обеспечивается путем оптимизации работы контроллера памяти за счет изменения порядка выполнения запросов. Устройство обмена с оперативной памятью (memory access unit, MAU) уменьшает количество обращений в память и оптимальным образом организует сбор и выдачу данных в процессор. Существенно, что эти проблемы решались для системы, в которой требовалось обеспечить корректную работу нескольких процессоров с общими данными.


1. Введение

«Эльбрус-3S» - это проектируемый ЗАО «МЦСТ» [1] многопроцессорный вычислительный комплекс, каждый процессорный модуль которого представляет собой систему – на - кристалле (System-on-Chip, SOC). На одном кристалле размещаются процессор и оборудование распределённой интерфейсной логики (chipset), «северного моста», в дальнейшем обозначаемого как системный коммутатор (Рисунок 1). Процессоры объединены в когерентную систему через высокоскоростные последовательные каналы межпроцессорного обмена, связывающие каждый процессор со всеми остальными. Система не имеет общего контроллера памяти, на одном кристалле с каждым процессором интегрирован собственный контроллер, работающий с подключенной к процессору памятью. Таким образом, «Эльбрус-3S» является системой с неоднородным доступом в память (NUMA) [2].

Рисунок 1. Структура процессорного модуля «Эльбрус-3S»


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

Одним из основных методов оптимизации доступа к памяти является реализуемое в MAU «подклеивание заявок». Это выполнение нескольких заявок путем однократного обращения к памяти, которое позволяет сократить число выдаваемых запросов и снизить общую нагрузку на подсистему памяти. Еще одним фактором оптимизации является «сквозная передача», при которой свободный контроллер способен выполнить чтение из памяти до завершения обработки запроса системным коммутатором.

С точки зрения оптимизации весьма существенен и выбор порядка обработки поступивших запросов планировщиком контроллера памяти. Конфигурацию блока планирования необходимо определить на начальном этапе разработки в зависимости от предназначения системы, которая может быть ориентирована как на оптимизацию пропускной способности (обработка больших массивов данных, потоковые вычисления), так и на сокращение времени доступа (работа в реальном масштабе времени).


^ 2. Оптимизация логики MAU

Обычны решения, при которых запросы по чтению, не обнаружившие адресуемого объекта в кэш-памяти второго уровня, попадают в очередь запросов (memory queue, MRQ) и из неё в буфер считывания (load buffer, LDB) MAU. В общем случае данные из памяти считываются блоками, содержащими несколько слов (в рассматриваемом варианте такой блок имел размер 4 двойных слова, то есть половину кэш-блока). Таким образом, если адресуемые объекты нескольких заявок находятся в пределах одного блока, то возникает возможность сократить общее количество обращений в память (и считываемых при этом блоков). Логика буфера считывания в MAU, обнаружив эту ситуацию, выполняет «подклеивание запросов», разгружающее подсистему памяти, - несколько запросов обрабатываются путем однократного считывания общего блока из памяти и последующей рассылки различных адресуемых объектов из его состава по адресам назначения.

В спроектированной системе реализовано объединение двух типов. «Обычное подклеивание» выполняется соответственно приведенному выше принципу. Адреса назначения хранятся в LDB, поэтому нетрудно объединить новый запрос со старым, просто добавив в строку буфера, хранящую информацию о старом запросе, адреса назначения нового запроса.

Второй, вновь введенный тип объединения заявок, позволяет применить этот принцип и в случае, когда в буфере LDB недостаточно места для сохранения всех адресов назначения. При поступлении нескольких запросов с одинаковым адресом считывания та их часть, которая не может быть по этой причине подклеена к уже размещенным в буфере «первичным запросам», превращается во «вторичные запросы». Они сохраняются в свободных ячейках буфера. Когда данные, считанные по первичным запросам, отдаются в процессор, проверяется наличие вторичных запросов, и процедура выдачи в процессор выполняется также и для них.


^ 3. Буфер приёма данных и сбора когерентных ответов


Назначение данного устройства – сбор и выдача данных в процессор при выполнении когерентного чтения, когда при обращении по определенному адресу приоритет отдается данным, хранящимся в кэш-памяти (таким образом избегается считывание «устаревших» данных из оперативной памяти). С этой целью системный коммутатор помимо передачи запроса в контроллер памяти производит рассылку запросов проверки когерентности во все процессоры системы.

Таким образом, в четырёхпроцессорной системе данные могут прийти в процессор по одному из направлений:

контроллеры памяти – 2

каналы межпроцессорного обмена – 3

контроллер ввода-вывода.

А поскольку данные по каждому запросу могут прийти дважды – из памяти и, возможно, из кэш-памяти одного из процессоров по соответствующему каналу – буфер приема данных должен дождаться ответов на запросы проверки когерентности («когерентных ответов») от каждого процессора.

Время и последовательность прихода данных и ответов недетерминирована, поэтому приём со всех направлений должен производиться параллельно и независимо. На основании собранной информации принимается решение о выдаче данных, пришедших по тому или иному запросу LDB, включая «вторичные».

С учётом всех требований, общая структура буфера включает следующие элементы:

входные регистры

блок памяти принятых данных

блок памяти когерентных ответов

логика формирования сигналов готовности данных к выдаче

таблица «первичных» строк

приоритетная схема выбора строки для выдачи данных

В результате, реализована следующая схема приема данных:



Рисунок 2. Входные регистры буфера приёма данных и сбора когерентных ответов MAU.

Входные регистры по назначению можно разделить на две группы – приёмные регистры, накапливающие данные блоками по 4 двойных слова, и регистры ожидания записи в блок памяти принятых данных. Естественным требованием при формировании групп было сокращение числа регистров - в то же время их число должно было исключить возможность переполнения. Принимаемые из межпроцессорного канала данные сохраняются в приёмном регистре, откуда могут быть отправлены в порт записи, если он свободен. Если порт записи занят, а по каналу передаётся следующий блок, данные с приёмного регистра передаются на регистр ожидания данного канала. (Каждый интерфейс за исключением интерфейса одного из двух контроллеров памяти имеет свой регистр ожидания). Выбор одного из регистров (приемного или ожидания), данные с которого будут сохраняться в блоке памяти принятых данных, осуществляется арбитром в соответствии с аппаратно-фиксированной приоритетной схемой. Порядок освобождения входных регистров может нарушаться, когда все возможные когерентные ответы об отсутствии данных в кэш-памяти приходят раньше самих данных, и логика буфера принимает решение выдать данные сразу после их поступления. В этом случае производится внеочередная запись – данные записываются в блок памяти, несмотря на приоритеты, а не занятый ими регистр ожидания может быть использован для приёма данных с любого из пяти направлений. Таким образом, регистры ожидания фактически являются общим промежуточным буфером для всех источников. Это позволяет избежать переполнения входных регистров, если пропускная способность порта блока памяти принятых данных(4 двойных слова / такт) больше суммарной пропускной способности интерфейсов от всех источников(3.5 двойных слова / такт).

Блок памяти когерентных ответов собирает их от кэш-памяти каждого процессора без каких-либо задержек и формирует признак состояния данных (модифицированы/не модифицированы) для каждой строки LDB.

В результате, по итогам процесса приема данных из оперативной памяти, кэш-памяти процессоров и сбора когерентных ответов для каждой строки буфера данных (соответствующей «первичному» запросу) формируется сигнал готовности к выдаче, а также сигналы освобождения строки в LDB и интерфейсной логики.

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

Приоритетная схема выбора строки для выдачи данных не влияет на среднее время доступа, однако способно существенно повлиять на разброс во времени доступа в случае неравномерного интенсивного прихода данных и когерентных ответов. Поэтому была выбрана относительно сложная схема, опирающаяся на порядок поступления данных в LDB и возраст запросов. Не вдаваясь в подробности реализации, отметим лишь, что удалось спроектировать схему, вносящую достаточно небольшую задержку (около 0.8 нс) в критический участок принятия решения и занимающую достаточно небольшую площадь (около 0.01 мм2), по данным оценочного синтеза. В результате, из всех строк, готовых к обслуживанию, всегда сначала выбирается та, запрос по которой пришёл раньше остальных.

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


^ Системный коммутатор

Системный коммутатор выполняет функции «северного моста», т.е. обеспечивает обмен между процессорным ядром, локальной оперативной памятью и внешними по отношению к данному процессорному модулю абонентами (другими процессорами системы, «южным мостом»). Более детально функциональность коммутатора можно определить так:

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

Буферизация и арбитраж запросов в оперативную память от пяти источников

Поддержание очерёдности выполнения запросов

Обеспечение когерентности при доступе в оперативную память для всех абонентов в системе

Внутреннее устройство коммутатора имеет следующую структуру:



Рисунок 3. Устройство системного коммутатора

Рассмотрим вкратце назначение каждого из блоков. Поскольку по межпроцессорному каналу данные передаются в пакетном режиме, при приёме очередного пакета необходимо выполнить его преобразование к виду, удобному для внутренней обработки. Для этого служит коммутатор пакетов. Суммарный темп поступления запросов в память в многопроцессорной системе превышает скорость работы контроллера памяти, поэтому во входном буфере запросов производится их промежуточная буферизация для исключения необходимости блокировки запросчика или загрузки канала повторяющимися запросами. Из памяти входного буфера запросы выбираются на обработку в конвейер 5-входовым арбитром с круговым приоритетом. В то время как на обработку одного запроса требуется несколько тактов, конвейер позволяет разделить полный цикл выполнения запроса на несколько стадий и поддерживать тем самым непрерывный поток запросов. Следует отметить, что число стадий в конвейере уменьшено с 5(в конвейере чипсета «Эльбрус-3М») до 3. Буфер ожидания служит для обеспечения очерёдности выполнения запросов, а также для поддержания когерентности в многопроцессорной системе. При отсутствии блокировок, запрос с выхода конвейера передаётся в модуль интерфейса с контроллерами памяти, в котором производится пересинхронизация параметров запроса на частоту контроллера памяти.

При разработке системного коммутатора (как и при разработке других блоков, имеющих отношение к подсистемы памяти) особое внимание было уделено максимизации производительности при доступе в память. В системном коммутаторе используются оптимизации, преследующие три основные цели:

Минимизация времени доступа в память (для операций чтения),

Увеличение эффективности работы конвейера

Эффективная работа с относительно большим, по сравнению с системой «Эльбрус-3М», числом запросчиков(5).

Для достижения первой цели в блоках системного коммутатора, отвечающих за доставку запроса в контроллер памяти (входной буфер запросов, конвейер), организовано несколько уровней сквозных передач (bypass). Это позволяет при пустых очередях буфера запросов начинать выполнение первого чтения до окончания обработки запроса в конвейере, сокращая тем самым полное время выполнения операции на 6 процессорных тактов(12 нс). В том случае, если выполнение чтения было преждевременным, в контроллер памяти отсылается сообщение об отмене команды. В дополнение, системный коммутатор позволяет параллельное использование контроллеров памяти, когда обработкой одного запроса одновременно занимаются оба контроллера. Это эквивалентно удвоению ширины интерфейса с модулями памяти и сокращает время выполнения любой операции на 2 такта контроллера памяти (=8нс) за счёт уменьшения количества открытых страниц.

Эффективная работа конвейера подразумевает отсутствие блокировок, связанных с запретом выполнения очередного запроса. Эта проблема была отчётливо заметна при отладке чипсета «Эльбрус-3М». Но отрицательные последствия данного явления скрывались за счёт малого числа процессоров(2). Данная проблема решена путём разделения блокировок на два типа – случайная и долговременная. При случайной блокировке происходит перезапуск запроса в конвейере. В случае долговременной блокировки очередь от соответствующего запросчика в буфере запросов тормозится до исчезновения блокирующего условия. При этом в конвейер поступают запросы только от активных (незаблокированных) запросчиков.


^ Оптимизирующий контроллер памяти

В разрабатываемом ВК «Эльбрус-3s» используется оперативная память наиболее распространённого на данный момент стандарта DDR2[2]. Выбор стандартного типа памяти позволяет понизить конечную стоимость комплекса и упростить обслуживание, при сохранении приемлемого уровня производительности. В то время как оптимизации в системном коммутаторе призваны, главным образом, сократить задержку доступа в память, вносимую чипсетом, принцип работы контроллеров направлен на повышение пропускной способности.

Исследование проблемы повышения эффективности интерфейса с оперативной памятью опирается на утверждение, что при одинаковой частоте и ширине шины данных максимальная производительность контроллера памяти будет при максимальной загрузке шины данных, т.е. минимальном количестве пустых циклов. Пустые циклы возникают при выполнении вспомогательных операций активации и предзаряда строк[2]. Очевидной предпосылкой к оптимизации является сокращение числа данных операций, что подразумевает работу в пределах одной страницы памяти. Другими словами, требуется локальность обращений в память не на уровне виртуальной адресации отдельно взятого процесса(этого не достаточно для многозадачной/многопроцессорной системы), а на уровне физических адресов, что в общем случае недоступно даже ОС, не говоря о пользовательских программах. В качестве решения был избран вариант динамического изменения порядка следования обращений в память на уровне контроллера памяти. Аналогичные подходы могут быть применены как на уровне компиляции[4], так и на уровне MAU процессора. Но для многозадачной, а более того, многопроцессорной системы эффективность программного переупорядочивания запросов значительно падает[5]. Положительной стороной избранного метода является то, что он не требует анализа алгоритма выполняемой задачи, а также модификации программного обеспечения.

Среди множества возможных принципов организации механизма изменения порядка следования запросов, ограниченного необходимостью практической реализации, был выбран алгоритм последовательного сужения множества запросов, исполнение которых оптимально с учётом выбранной политики переупорядочивания. Выбор очередного запроса производится при помощи конвейеризированной последовательной системы фильтров (рис. 4), подключенной к 16-ячеечному буферу запросов. Количество запросов, среди которых производится переупорядочивание, ограничивается несколькими критериями:

Увеличение размера входного буфера запросов приводит к понижению частоты работы контроллера из-за усложнения логики переупорядочивания.

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

Согласно проведённому тестированию[6] увеличение количества ячеек с 4 до 16 даёт средний прирост производительности в 27%, в то время как увеличение размера с 16 до 64 добавляет только 3%.

16-ячеечный буфер хорошо согласуется с размером буфера ожидания системного коммутатора.

Тип фильтров и порядок их соединения определяют политику оптимизации, производимую контроллером. Краткое описание фильтров, используемых в данной версии контроллера, приведено на рисунке 4.

Т.к. конфигурация планировщика задаётся на стадии разработки всего кристалла и не может быть изменена, важно правильно выбрать алгоритм фильтрации запросов. Разрабатываемый вычислительный комплекс не ориентирован на узкоспециализированные задачи, поэтому целесообразно производить выбор алгоритма переупорядочивания, исходя из интегральных критериев оценки – максимизации использования канала и минимизации среднего времени выполнения запроса. Это соответствует некоторой комбинации политики максимального количества открытых строк и политики приоритетов типов запросов.



Рисунок 4. Функциональная схема блока планирования.

Прежде всего, необходимо определить возможные варианты конфигурации планировщика, т.е. какие фильтры можно менять местами. Всё множество фильтрующих устройств делится на два класса:

Фильтры, поддерживающие корректность доступа в память: фильтр зависимости по данным, фильтр возраста, фильтр протокольных блокировок.

Фильтры, определяющие политику изменения порядка: фильтр переоткрытия строк, фильтр последней выполненной операции, фильтр приоритета операций чтения.

Очевидно, что наличие фильтров первого типа необходимо для любой конфигурации контроллера. На первых местах системы фильтров целесообразно разместить фильтр зависимости и фильтр протокольных блокировок. На выходе фильтрующей системы устанавливается фильтр возраста, выбирающий единственный (наиболее старый) запрос на исполнение. Для краткости ограничимся рассмотрением двух фильтров второго типа: a)фильтра переоткрытия строк и b)фильтра приоритета операций чтения.

Последовательность a → b. Благодаря фильтру a, данная комбинация ориентирована в первую очередь на работу с открытыми строками, т.е. подразумевает локальность обращений, что характерно для большинства пользовательских задач. Далее происходит отфильтровывание всех запросов записи.

Последовательность b → a. Чтениям отдаётся высший приоритет, даже если они адресуются в закрытую строку. Применение данной политики имеет смысл только для систем, в которых наиболее критичным параметром является время доступа к данным, поскольку сокращение задержки по каждому чтению в отдельности может стать причиной неполной загрузки канала при нелокальном доступе. Данная конфигурация больше подходит для систем реального времени.


Заключение

При проектировании комплекса «Эльбрус-3S» была решена одна из основных задач – организация эффективного когерентного доступа в память в системе с большим числом процессоров(до 8). Во всех основных блоках процессорного модуля, отвечающих за обработку запросов в оперативную память, были приняты меры по сокращению задержки и увеличению пропускной способности. Определение начальной конфигурации планировщика запросов в контроллере памяти производилось, исходя из теоретических предположений. Подготовлено несколько конфигураций планировщика. Целью дальнейшей работы является определение конфигурации, оптимальной для большинства типовых задач, на прототипе системы.

Сравнение общих характеристик подсистемы памяти «Эльбрус-3S» и системы предыдущего поколения «Эльбрус-3М» приведено в таблице 1:






«Эльбрус-3М»

(2 процессора)

«Эльбрус-3S»

(1 процессор)

«Эльбрус-3S»

(4 процессора)

Пропускная способность, Гб/с

12.8

8

14

Время доступа, нс

180

70

108(среднее)

Максимальный объём, Гб

32

32

128

^ Таблица 1. Сравнительная характеристика систем «Эльбрус-3М» и «Эльбрус-3S»


Список литературы.

1. www.mcst.ru

2. A. Ahmed et al., “AMD Opteron Shared-Memory MP Systems”, www.amd.com?????

DDR2 SDRAM Specification. Revision JESD79-2B //JEDEC Solid State Technology Association, January 2005

http://www.jedec.org

DDR3 SDRAM Specification. Revision JESD79-3 //JEDEC Solid State Technology Association, June 2007

S.A. Moyer, “Access Ordering and Effective Memory Bandwidth”, Ph.D. Thesis, Department of Computer Science, Univ. of Virginia, Technical Report CS-93-18, USA April 1993

Zhichun Zhu, Zhao Zhang, “A Performance Comparison of DRAM Memory System Optimizations for SMT Processors” //Dept. of Electrical & Computer Engineering University of Illinois at Chicago, USA 2005

Scott Rixner, William J. Dally, Ujval J. Kapasi, Peter Mattson, and John D. Owens. “Memory Access Scheduling” //Computer Systems Laboratory, Stanford University, Stanford, CA 94305, USA 2000

Иванов А.А Контроллер памяти системы е3м //МЦСТ, 2006