Д.Ю. Перов, Н.Ю. Поляков (ЗАО «МЦСТ», ОАО «ИНЭУМ им. И.С. Брука»)
D. Perov, N. Polyakov
ОБЕСПЕЧЕНИЕ УПОРЯДОЧЕННОСТИ ВЫПОЛНЕНИЯ DMA-ОПЕРАЦИЙ В NUMA-СИСТЕМАХ МЕТОДОМ ПРЕДВАРИТЕЛЬНОГО КЭШИРОВАНИЯ
DMA OPERATIONS ORDER SUPPORT IN NUMA SYSTEMS BY MEANS OF DMA CACHING METHOD
Рассматривается проблема упорядоченного выполнения DMA-операций. Описывается механизм предварительного кэширования как один из способов решения проблемы. Приводятся подробности реализации данного механизма в СнК «Эльбрус-4С+». Описываемый метод сравнивается с другими известными методами решения проблемы.
Ключевые слова: Эльбрус, архитектура, NUMA, DMA, упорядочивание, DMA-кэш, когерентность, консистентность.
This paper concerns the DMA ordering problem. We consider DMA caching method as one of the problem’s decisions. The details of DMA cache realization for the SoC «Elbrus-4C+» are described. The DMA caching method is compared with other methods.
Key words: Elbrus, architecture, NUMA, DMA, ordering, DMA cache, coherency, consistency.
Введение
Постоянное увеличение производительности процессоров сопровождается ростом таких характеристик компьютера, как объем оперативной памяти, пропускная способность каналов памяти и каналов ввода-вывода, связывающих центральную часть с локальными и удаленными периферийными устройствами. Последний показатель в большой степени обусловлен развитием интернет-технологий, постоянно ужесточающих требования к скорости передачи данных в сетевых соединениях. Так, согласно прогнозам CISCO, средняя скорость в одном соединении возрастет с 9,1 Мбит/с в 2011 году до 34,5 Мбит/с в 2016 году, т.е. в 3,8 раз [1]. Кроме того, растет скорость обмена данными по другим интерфейсам. Так, например, на смену SATA 2.0 (2,4 Гбит/с), появившемуся в 2002 году, всего через 6 лет пришел SATA 3.0 (6 Гбит/с). Аналогично увеличивается скорость и таких интерфейсов, как PCI Express, USB. Кроме того, на смену некоторым медленным интерфейсам приходят новые, например Thunderbolt. Однако для полноценного использования возможностей быстрых интерфейсов требуется поддержка со стороны центрального процессора.
1. Проблема упорядоченности DMA-обращений
В настоящее время для обмена данными между периферийными устройствами и центральным процессором используется механизм прямого доступа в оперативную память – Direct Memory Access (DMA). Механизм DMA используют такие устройства, как жесткий диск, сетевая карта, PCI устройства и другие.
Особенностью некоторых периферийных интерфейсов (например, PCI Express) является то, что операции DMA-записи данных в память имеют тип posted (почтовый), т.е. ответ на такой запрос не требуется. Операция считается завершенной сразу после её выдачи из устройства, а DMA-обмен, состоящий из posted операций, – после выдачи операции записи последнего элемента пересылаемого массива.
В NUMA-системах эта особенность может привести к некорректному завершению DMA-обмена. В зависимости от способа индикации завершенности обмена (регистр периферийного устройства или дескриптор в оперативной памяти) можно выделить два сценария возникновения ошибки. В первом случае DMA-обмен завершается в памяти позднее, чем процессор прочтет статусный регистр и начнет читать записанный в память массив, т.е. происходит переупорядочивание операций. Второй случай аналогичен первому за исключением того, что меняется порядок выполнения операции DMA-записи элемента массива и DMA-записи дескриптора. Такое может случиться, если эти операции выполняют запись в модули памяти, физически подключенные к разным процессорам. Соответственно, возникают две задачи. Первая состоит в том, чтобы обеспечить порядок исполнения, при котором результат DMA-записи становится известен процессорам раньше, чем изменение статусного регистра периферийного устройства. Вторая задача – обеспечение упорядоченности операций DMA-записи друг относительно друга, т.е. результаты двух операций DMA-записи должны быть видны процессорам системы в том же порядке, в котором были отправлены из устройства (консистентность памяти).
В NUMA-системах гарантировать упорядоченность двух операций DMA-записи в модули памяти разных процессоров можно только при наличии контроля их завершения, вследствие которого в некоторой точке системы (назовем её точкой упорядоченности) DMA-запросы на запись должны становиться non-posted (непочтовыми). Через эту точку должны проходить все ответы на процессорные чтения. В обобщенной структуре NUMA-системы, показанной на рис. 1, такой точкой может быть либо южный мост, либо северный мост процессора, к которому подключено периферийное устройство.
Рис. 1. Обобщенная структура NUMA-системы
Наиболее очевидным решением вышеописанных задач является выполнение DMA-записей атомарно, т.е. таким образом, что очередная DMA-запись или ответ на процессорное чтение отправляется только после полного завершения предыдущей DMA-записи. Данный способ надежен, но не применим к системам, требующим высоких скоростей обмена, ибо при его использовании отсутствует конвейерность выполнения операций.
2. Метод предварительного кэширования
Принцип консистентности памяти в применении к процессорным операциям, реализуемым в соответствии с политикой write back кэш-памяти, достигается следующим образом. При выполнении ядром когерентных записей в общую память системы сначала проверяется наличие и состояние данных в своей кэш-памяти и кэш-памяти каждого из других ядер. Запись допускается только после того, как целевая строка памяти окажется в кэш-памяти ядра, а ядро получит права на модификацию строки [2]. В данном случае точкой упорядоченности служит кэш-память ядра, т.к. несмотря на то, что после выполнения записи кэш-строка может и не выталкиваться в память, все последующие чтения по адресу этой строки будут возвращать данные записи в силу когерентности системы.
Подобную схему можно использовать для выполнения DMA-записи. Перед тем как отправить в память запрос на запись, из точки упорядоченности отправляется запрос на владение целевой строкой, который ведет к ее вычеркиванию из кэш-памяти всех ядер. В ответ приходят данные из памяти (подложка записи) и, возможно, данные из кэш-памяти одного из ядер. Далее в точке упорядоченности данные записи, пришедшие из периферийного устройства, накладываются по маске на подложку, и модифицированная строка отправляется в память. Получается своего рода кэш-память (далее – DMA-кэш), которую необходимо опрашивать наряду с кэш-памятью каждого ядра при проверке когерентности, т.к. DMA-кэш может оказаться владельцем строки. Таким образом, DMA-запись считается завершенной в момент модификации подложки, ибо в ответ на процессорные чтения по данному адресу будут возвращаться модифицированные данные.
Для достижения упорядоченности DMA-операций наложение данных на подложку должно выполняться в порядке прихода DMA-запросов. Так, если для некоторого запроса данные ещё не модифицированы (вследствие незавершенности предыдущих запросов или задержки в получении владения строкой), то в ответ на процессорные чтения по адресам, совпадающим с адресами последующих DMA-запросов, будет возвращаться либо сообщение об отсутствии данных (если владение не получено), либо подложка (если владение получено). Ответы на процессорные чтения также должны выдаваться из точки упорядоченности после модификации данных всех предыдущих DMA-запросов.
Существенным преимуществом данного метода является возможность конвейерного исполнения запросов. Так, запросы на владение можно отправлять сразу по приходу DMA-запроса, а запросы на запись модифицированной строки в память – сразу после модификации подложки; таким образом, получение владения осуществляется для нескольких запросов одновременно. К недостаткам метода относится увеличение трафика каналов межпроцессорных связей (при запросах в память других процессоров) за счет передачи подложки в точку упорядоченности DMA-запросов, т.к. при атомарном выполнении DMA-запросов подложка может модифицироваться в северном мосте процессора, в память которого выполняется запись.
В несколько модифицированном виде данный метод используется фирмой Intel в южном мосте Intel 5520 Chipset [3]. Ключевое отличие состоит в том, что права владения DMA-кэш получает без данных. Это уменьшает загруженности межпроцессорных связей, но усложняет механизмы поддержания когерентности в случае DMA-записи данных объемом менее кэш-строки.
3. DMA-кэш в СнК «Эльбрус-4С+»
Система на кристалле (СнК) «Эльбрус-4С+» включает в себя восемь универсальных ядер с архитектурой «Эльбрус», объединенных общей кэш-памятью 3-го уровня ($L3). Обмен данными между $L3, памятью, южным мостом и другими процессорами осуществляется посредством северного моста – контроллера системных взаимодействий (System Interconnect Controller, SIC). Кроме того, контроллер имеет три канала межпроцессорной связи для объединения до четырех СнК в ccNUMA-систему (кластер).
Поддержка когерентности СнК осуществляется посредством кэш-справочника памяти, который входит в состав SIC каждой СнК и состоит из двух частей. Первая часть хранит состояния строк $L3 всех процессоров системы кроме своего, вторая часть хранит состояние строк всех DMA-кэшей кластера. Особенностью выполнения операций записи в СнК семейства «Эльбрус» является то, что сначала в устройство назначения отправляется информационная часть запроса (адрес, код операции и другие параметры), данные отправляются только после получения от этого устройства сообщения типа «выдай данные».
Точка упорядоченности находится в SIC. При запросе на владение строкой в SIC процессора, к которому подключена память (home-процессор), отправляется запрос типа Read Invalidate (RI), т.е. чтение с вычеркиванием из всех кэш-памятей. При записи модифицированной строки отправляется запрос типа Write Back (WB).
Протокол поддержки когерентности с точки зрения кэш-справочника включает три состояния строки:
Invalid (I) – строки в DMA-кэше нет;
Modified (M) – в DMA-кэше находятся наиболее свежие данные, которых может не быть в памяти; строка из этого состояния может перейти в состояние Owned в случае ее запроса по чтению без вычеркивания из кэш-памяти (snoop-read) или в Invalid в случае запроса с вычеркиванием (snoop-RI);
Owned (O) – строка DMA-кэша была запрошена по чтению, и переданные в ответ данные отсутствуют в памяти; теперь для выполнения записи в эту строку необходимо повторно выполнить запрос RI.
С точки зрения DMA-кэша состояния Modified и Owned необходимо разделить:
False Modified (FM) – владение строкой получено, но модификация ещё не может быть выполнена, т.к. не завершена модификация данных для предыдущих DMA-запросов; в ответ на snoop-read и snoop-RI будет выдана подложка;
True Modified (TM) – модификация данных завершена; в ответ на snoop-read и snoop-RI будут выданы модифицированные данные;
Owned (O) – строка в состоянии False Modified была запрошена по snoop-read; в ответ выдаются немодифицированные данные; для выполнения DMA-записи необходимо повторно выполнить RI;
Owned Modified (OM) – строка в состоянии True Modified запрошена по snoop-read; в ответ выдаются модифицированные данные; для выполнения DMA-записи нет необходимости повторно выполнять Read Invalidate, т.к. запросчик уже получил данные записи; для завершения DMA-записи выполняется WB.
Таким образом, переходы из FM в TM и из O в OM не видны кэш-справочнику.
Возможность «отбора строки» у DMA-кэша по snoop-read или snoop-RI необходима во избежание взаимной блокировки запросов (deadlock). На рис. 2 изображена одна из таких ситуаций. Периферийные устройства, подключенные к разным процессорам, одновременно выполняют DMA-запись сначала в память другого процессора, затем в память своего. Запросы на владение строкой отправляются в home-процессор, причем запросы по одному адресу должны выполняться атомарно. Порядок постановки запросов в очередь 1 является наиболее вероятным, ибо время передачи запроса внутри процессора всегда меньше времени его передачи по каналам межпроцессорных связей. Запросы, поступившие в очередь 1 первыми, выполнятся, и DMA-кэш процессора 0 получит права владения строкой A, а процессора 1 – строкой B. Далее, если запретить передачу прав владения строкой другой кэш-памяти до завершения записи (выдачи WB), запросы, помещенные в очередь 2 первыми, никогда не выполнятся, и вся система перейдет в состояние deadlock.
Рис. 2. Взаимная блокировка DMA-запросов
Переход системы в состояние зацикливания (livelock) вследствие бесконечного перехода прав на строку от одной кэш-памяти к другой и обратно в рамках данной системы невозможен. Как только запрос, стоящий в очереди 2 первым, получит права на строку (ответы на такие запросы никогда не блокируются), она будет модифицирована и перейдет в состояние TM. В этот момент запрос становится фактически завершенным, и права на строку этим DMA-кэшем запрашиваться больше не будут, несмотря на то что данные ещё не записаны в память. Таким образом, права на строку будут запрашиваться и отдаваться до тех пор, пока строка не перейдет в состояние TM (в худшем случае – пока запрос на запись этой строки не станет первым в очереди 2).
На рис. 3 представлена полная диаграмма состояний строки DMA-кэша. Действия SIC при переходах между состояниями строк приведены в табл. 1.
Рис. 3. Диаграмма состояний строки DMA-кэша
Таблица 1
Таблица переходов состояний строки DMA-кэша
Состояние строки \ входящая операция
|
snoop-read
|
snoop-RI
|
Завершился сбор ответов на RI
|
Сообщение «дай данные»
|
I
|
–
|
–
|
переход в FM
|
Выдача новых данных с признаком no write (nw)
|
FM
|
выдача в ответ немодифицированных данных
отправка повторного RI
переход в O
|
выдача в ответ немодифицированных данных
отправка повторного RI
переход в I
|
–
|
–
|
O
|
выдача в ответ немодифицированных данных
отправка повторного RI
сохранение O
|
выдача в ответ немодифицированных данных
отправка повторного RI
переход в I
|
переход в FM
|
–
|
TM
|
выдача в ответ модифицированных данных
переход в OM
|
выдача в ответ модифицированных данных
переход в I
|
–
|
выдача данных
переход в I
|
OM
|
выдача в ответ модифицированных данных
сохранение OM
|
выдача в ответ модифицированных данных
переход в I
|
–
|
выдача данных
переход в I
|
Следует отметить, что метод предварительного кэширования позволяет выполнять DMA-записи в строгом порядке (strong ordering) и при этом обеспечивать высокий темп обмена благодаря возможности конвейерного выполнения запросов. Можно выделить следующие стадии: 1) отправка запроса на владение (RI) – выполняется в любом порядке для всех поступивших запросов; 2) отправка запроса на запись модифицированной строки в память (WB) – выполняется в порядке прихода запросов; 3) выдача данных – данные выдаются в порядке прихода сообщений типа «дай данные».
Существует также третий метод обеспечения упорядоченности – введение барьерных операций [4]. Однако он не применим в том случае, когда нельзя изменить исходный код программы или драйвера.
Заключение
В заключение следует отметить, что приведенная выше реализация метода предварительного кэширования может быть усовершенствована. Например, стандарт PCI Express [5] позволяет программисту помечать DMA-запросы признаком нестрогой упорядоченности (relaxed ordering), а также упорядоченности запросов только для одного устройства (ID-based ordering). Использование этих признаков в DMA-кэше позволяет выполнять модификацию некоторых строк вне очереди, что дает возможность в некоторых случаях получить прирост в реальной пропускной способности каналов ввода-вывода.
Литература
1. Cisco Visual Networking Index: Forecast and Methodology, 2011-2016. // White Paper. – Cisco, 2012.
2. Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1, 2012.
3. Debendra Das Sharma Intel 5520 Chipset: An I/O Hub Chipset for Server, Workstation, and High End Desktop. – Hot Chips 21, 2009, Session 2.
4. Shuwei Bai [et al.] Barrier Synchronization for CELL Multi-Processor Architecture. – First IEEE International Conference on Ubi-media Computing, 2008, p. 155 158.
5. PCI Express Base Specification. – Revision 2.1. – PCI-SIG, 2009.
|
