Проектирование многопоточных архитектур для нерегулярных приложений

Большинство современных суперкомпьютеров рассчитано на эффективное исполнение рабочих нагрузок, подразумевающих большой объем операций над вещественными числами. Такие системы преимущественно создаются для задач научного моделирования, которые характеризуются высокой плотностью вычислений и локальностью (частотой обращений к одним и тем же данным), а также регулярными (легко секционируемыми) структурами данных. Для таких приложений требуются процессоры архитектуры SIMD (Single Instruction, Multiple Data) с быстрыми арифметическими модулями и высокоразвитой архитектурой кэша, сокращающей время доступа. Пропускная способность памяти и межсоединений растет гораздо медленнее, чем пиковое вычислительное быстродействие, однако для регулярных и локальных приложений это не критично.

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

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

Мотивация исследования

Cray XMT — это многоузловой суперкомпьютер, специально рассчитанный на исполнение нерегулярных приложений. Его архитектура основана на трех столпах: глобальное адресное пространство, мелкозернистая синхронизация (установка и своевременное снятие блокировки при выполнении каждой операции с данными для ускорения обработки и исключения конфликтов) и многопоточность.

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

В отличие от других высокопроизводительных систем  (High Performance Computing, HPC), XMT предоставляет общесистемную модель программирования, за счет чего упрощается реализация приложений с большими запросами к памяти и не требуется их оптимизации для повышения локальности. Хотя современные системы HPC поддерживают многопоточность, в том числе с использованием графических процессоров, они больше подходят для регулярных приложений — архитектура таких систем не рассчитана на компенсацию задержек при доступе к памяти различных узлов. Во многих случаях нет даже механизмов компенсации задержки при доступе к памяти процессоров одного узла. Более того, координация обращений к памяти и максимизация использования пропускной способности требует предварительного секционирования данных и значительных усилий программирования.

Многопоточные архитектуры

Многопоточные процессоры параллельно в едином конвейере исполняют инструкции из разных потоков управления. Существует два основных типа многопоточных процессоров: выполняющие за такт инструкции только из одного потока и выполняющие за такт инструкции из нескольких потоков.

Многие современные суперскалярные процессоры, выполняющие команды с изменением их очередности, поддерживают принцип одновременной многопоточности, например IBM Power 6 и Power 7, Intel Nehalem и Sandy Bridge. Одновременная многопоточность предусматривает выполнение нескольких потоков в каждом ядре — процессор идентифицирует независимые инструкции и одновременно выдает их на различные функциональные модули ядра. Тем самым обеспечивается высокая утилизация процессорных ресурсов.

Многопоточность процессоров, выдающих инструкции из одного потока за такт, называется временной. Такие процессоры переключаются между различными потоками, чтобы поддерживать конвейер, обычно упорядоченный, в заполненном состоянии и избегать его остановок. Временная многопоточность может быть крупнозернистой (coarse-grained) — блокирующей или мелкозернистой (fine-grained) — с чередованием. При блокирующей многопоточности переключение между потоками происходит, только когда очередная инструкция создает «блок» — продолжительную остановку. Например, это происходит при непопадании в кэш, что означает обращение к внешней памяти. Блокирующая многопоточность используется в архитектуре Intel Montecito. При многопоточности с чередованием происходит потактовое переключение от одного потока к другому — процессоры ThreadStorm в Cray XMT, а также их предшественники в Tera MTA и Cray MTA-2 реализуют именно такую многопоточность. Этот же принцип используется в ядрах Sun UltraSPARC T1, T2 и T3. Процессор UltraSPARC T1 состоит из восьми ядер, каждое с четырьмя потоками, у T2 тоже восемь ядер, но вдвое больше модулей исполнения и потоков, что позволяет за каждый такт одновременно выдавать инструкции из двух потоков. В SPARC T3 ядер вдвое больше, чем у T2, и в каждом такте ядро T3 выдает инструкцию из нового потока, однако, когда происходит длительная задержка, виновный в ней поток до ее завершения удаляется из списка запланированных инструкций.

Графические процессоры тоже имеют по несколько блоков планирования потоков (производители называют их Warp или Wavefront) в SIMD-модулях исполнения. Активизация этих планировщиков позволяет эффективно компенсировать длительные задержки при выполнении операций с памятью. Для графических процессоров характерны сотни модулей операций с плавающей запятой, высокая пропускная способность памяти, а также наличие встроенной в чип памяти, ускоряющей доступ к часто используемым данным, что более пригодно для задач регулярного характера.

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

Архитектура Cray XMT

Cray XMT состоит из двухсокетных сервисных узлов на процессорах AMD Opteron и специально разработанных многопоточных вычислительных узлов, имеющих по одному процессору ThreadStorm. Максимальное число вычислительных узлов в системе — 8192, предельная емкость совместно используемой памяти — 128 Тбайт. Однако самая большая из построенных на сегодня систем XMT имеет только 512 вычислительных узлов.

Каждый чип ThreadStorm представляет собой 64-разрядный процессор архитектуры VLIW, содержащий банк памяти, а также арифметический и управляющий модули. Он потактово переключается между 128 мелкозернистыми аппаратными потоками, сводя тем самым к минимуму влияние задержек доступа к памяти.

При выполнении задач система назначает программному потоку аппаратный поток, включающий в себя счетчик команд, слово состояния, набор регистров цели и исключения, а также 32 регистра общего назначения. Процессор не выдает новую инструкцию из одного и того же потока, пока предыдущая не покинула конвейер.

Поскольку операции с памятью занимают больше 21 такта, в процессоре реализован механизм упреждения, позволяющий продолжать выдачу независимых инструкций из одного потока, пока не будет завершено обращение к памяти. Размер буфера опережения определяется компилятором, но не превышает восьми инструкций. Таким образом, в каждом аппаратном потоке могут одновременно ожидать выполнения до восьми операций с памятью, а в процессоре в целом — до 1024. Операции с памятью могут выполняться с изменением очередности.

ThreadStorm имеет четырехканальный ассоциативный кэш инструкций емкостью 64 Кбайт, который может использоваться программами с высокой локальностью. Номинальная тактовая частота процессора — 500 МГц.

К сети межсоединений процессор подключается сквозным каналом HyperTransport. Сетевой адаптер не выполняет агрегацию, и в каждом сетевом пакете инкапсулируется одна операция с памятью. Сетевая подсистема основана на межсоединениях Cray SeaStar2 с топологией тор.

Каждый контроллер памяти ThreadStorm обслуживает до 8 Гбайт оперативной памяти DDR со 128-разрядной шиной и оснащен четырехканальным ассоциативным кэшем на 128 Кбайт, помогающим уменьшить задержку доступа. Для приложения совместно используемая системная память абстрагирована в виде глобального адресного пространства, а сама система может напрямую обращаться к любому участку физического банка памяти любого процессора ThreadStorm в сети межсоединений.

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

Каждому 64-разрядному слову памяти присваиваются: бит пустоты/полноты, работающий в качестве блокировщика; бит переадресации указателя, сигнализирующий о том, что область памяти содержит указатели, а не данные, что позволяет автоматически сгенерировать новое обращение к памяти; два бита-ловушки, устанавливаемые в «1», когда в области памяти происходит запись или считывание.

ThreadStorm генерирует до 500 млн обращений к памяти в секунду (million references per second, Mref/s), то есть по одному обращению за такт. Однако скорость обмена данными между контроллером и оперативной памятью может достигать только 100 Mref/s, а пропускная способность SeaStar2 — 140. В результате задержка для операций с памятью для 128-узловой системы составляет от 68 тактов при попадании в кэш локального контроллера памяти до 1200 тактов при непопадании в кэш самого удаленного контроллера.

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

Сравнение с другими архитектурами

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

Графические процессоры и UltraSPARC

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

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

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

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

Для нерегулярных приложений, работающих с большими наборами данных, обеспечивать масштабирование при исполнении на множестве графических процессов пока затруднительно, а сейчас наибольший размер памяти для графической платы — 6 Гбайт. Поскольку для различных графических чипов не существует единого механизма абстрагирования совместно используемой памяти, разработчики приложений вынуждены вручную секционировать данные, однако шина PCI Express может быть чересчур медленной для алгоритмов, опирающихся на распределенную память.

Даже несмотря на поддержку однорангового обмена данными и прямого доступа к памяти в самых новых GPU, данные, распределяемые между процессорами, по-прежнему приходится секционировать. В кластерах, когда данные проходят еще и по сети, секционирование дополнительно усложняется, и задержка при обмене данными увеличивается.

Для процессоров UltraSPARC характерны аналогичные проблемы с масштабируемостью. В них имеется механизм абстракции, позволяющий работать с совместно используемой памятью в пределах одного узла, но на многоузловых системах по-прежнему применяется традиционная схема распределенной памяти и требуются соответствующие приемы программирования. Процессоры UltraSPARC компенсируют задержку только на уровне узла и не принимают каких-либо мер по минимизации влияния сетевых задержек, возникающих в пределах кластера в целом.

Преимущества XMT

Архитектура XMT специально рассчитана на многоузловое масштабирование и предоставляет простую общесистемную модель программирования благодаря механизму абстрагирования совместно используемой памяти, ее горизонтальной организации и мелкозернистой синхронизации. Программа с большими потребностями в памяти может пользоваться всей доступной памятью XMT, не требуя от программиста реструктуризации кода.

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

Помимо простой модели программирования XMT отличается от других архитектур более высокой эффективностью, когда данные не помещаются в память одного узла (или одной платы в случае графического процессора), а также когда ввиду сильной нерегулярности доступа становятся бесполезными кэш или скоординированные обращения к памяти. Например, программист имеет возможность реализовать простой алгоритм поиска в ширину (Breadth-First Search, BFS), не заботясь о перемещении данных и оптимизации доступа к памяти, но получить при этом хорошее быстродействие и масштабируемость. Еще один пример — поиск подстроки по алгоритму Ахо-Корасик с очень большим словарем. На кэширующих процессорах, когда подстрока есть в кэше, процедура сопоставления выполняется быстро. В противном случае процесс замедляется, поскольку процессору приходится извлекать последовательности из памяти. Доступ к словарю непредсказуем, поэтому группировка обращений к памяти затруднена. Когда алгоритм сверяет каждую последовательность со всем словарем (самый худший случай), на архитектурах, оптимизированных для регулярного доступа, происходит деградация производительности. С другой стороны, когда тот же алгоритм сопоставляет лишь малое число последовательностей и есть возможность использовать кэш (лучший случай), на XMT пиковое быстродействие не обязательно будет столь же высоким, как на других архитектурах. Однако горизонтальная иерархия памяти системы обеспечивает стабильность быстродействия, поэтому производительность на XMT в лучшем случае не очень сильно отличается от худшего.

Моделирование XMT

Для исследования возможностей XMT был разработан симулятор, имитирующий на сервере с 48 ядрами (процессоры Opteron 6176SE) полноценную 128-процессорную систему XMT. Пиковое быстродействие имитируемой системы составляет 250 килотактов в секунду, а систематическая погрешность для большого набора типовых нерегулярных приложений не превышает 10%. На симуляторе работают «родные» для XMT приложения, поддерживаются все архитектурные особенности системы, реализована параметрическая модель, упрощенно, но точно описывающая события взаимодействия с сетью и памятью, в том числе конфликты при захвате блокировок. С помощью симулятора были выявлены узкие места архитектуры XMT и предложены соответствующие усовершенствования.

Вначале оценивалось влияние операций с памятью на общее время исполнения приложений на 128-процессорном XMT. Для этого симулятор был оснащен счетчиками, обновлявшимися всякий раз, когда конвейер останавливался в ожидании завершения выполнения запросов к памяти. На рис. 1, а показано время исполнения на симуляторе алгоритма поиска подстроки Ахо-Корасик со словарем из 20 тыс. наиболее распространенных английских слов и входным набором из случайных символов ASCII с равномерным распределением и средней длиной 8,5 байта.

Рис. 1. Влияние операций с памятью на общее время выполнения алгоритма поиска подстроки Ахо-Корасик в зависимости от числа активных процессоров на симуляторе 128-узлового Cray XMT: а — общее время исполнения приложения; б — доля времени, затрачиваемого на операции с памятью. Глобальное совместно используемое адресное пространство благодаря скремблированию однородно распределяется между 128 физическими банками памяти

Даже когда в системе при операциях с памятью используются не все процессоры, адресное пространство все равно скремблируется для распределения по всем узлам. Как видно из рис. 1, б, доля времени, которое система тратит на ожидание доступа к памяти, остается стабильной на уровне около 70% до тех пор, пока число активных процессоров не достигает 16. Однако, когда активны больше 16 процессоров, общее время исполнения перестает уменьшаться, а время, затрачиваемое системой на ожидание доступа к памяти, растет и при 128 активных процессорах превышает 90%.

Чтобы выяснить причину этого явления, был проанализирован трафик обращений к памяти на сетевых адаптерах и контроллерах памяти. На рис. 2 показан входящий трафик одного из сетевых адаптеров, когда активны все 128 процессоров. Сплошная линия отражает число входящих обращений, запрашивающих доступ к сетевому адаптеру, а пунктирная — максимальный объем обращений в секунду, который способен обслужить адаптер (140 Mref/s для двунаправленного трафика). На рисунке видно, что во многих сегментах приложения запрошенный объем операций превышает доступную пропускную способность адаптера, из-за чего останавливается обслуживание обращений к удаленной памяти и задерживается исполнение в целом.

Рис. 2. Насыщение полосы пропускания сетевого интерфейса при выполнении алгоритма поиска подстроки Ахо-Корасик на 128-узловой XMT-подобной системе, когда все ее процессоры активны. Сплошная линия отражает число входящих обращений, запрашивающих доступ к сетевому адаптеру, пунктирная линия — максимальный объем обращений, который может обслужить сетевой адаптер (140 Mref/s для двунаправленного трафика). Во многих сегментах приложения запрошенный уровень операций значительно превышает доступную пропускную способность сетевого адаптера, что приводит к остановке обслуживания обращений к удаленной памяти и общей задержке исполнения

Что касается контроллеров памяти, то было обнаружено, что насыщение полосы пропускания выражено гораздо меньше, чем на сетевом адаптере. Хотя, казалось бы, это контрастирует с усредненным темпом обращений, данное явление обусловлено равномерным скремблированием адресов. Например, на 128-узловой конфигурации за счет скремблирования процессор генерирует в среднем один локальный адрес и 127 удаленных из 128 возможных узлов назначения. Таким образом, только одно локальное обращение использует канал контроллера, а все удаленные проходят через сетевой адаптер. Однако входящие обращения от других узлов проходят как через адаптер, так и через контроллер памяти. Если учесть сумму входящих и исходящих обращений, очевидно, что канал сетевого адаптера более загружен трафиком, чем канал контроллера.

Усовершенствования

Исходя из результатов моделирования, была разработана усовершенствованная многоядерная системная архитектура на базе XMT, обеспечивающая максимальную общую производительность системы.

Архитектура

Как показано на рис. 3, предлагаемая архитектура включает в себя множество ThreadStorm-подобных ядер, в которых каждый аппаратный поток имеет выделенный регистровый файл и очередь загрузки/сохранения (Load/Store Queue, LSQ). Все LSQ обмениваются информацией с модулем скремблирования, который равномерно распределяет обращения по всем банкам памяти системы. В каждом процессоре также имеется несколько независимых контроллеров памяти, каждый из которых соединен интерфейсом со своим внешним банком памяти. Все компоненты объединены сетью на кристалле топологии 2D Mesh с коммутацией пакетов, и каждый оснащен выделенным маршрутизатором. Интегрированный сетевой адаптер соединяет процессор с остальными узлами системы. Задержка при прохождении данных по сети на кристалле составляет меньше 2% от средней общесистемной задержки при обращениях к памяти.

Рис. 3. Многоядерная процессорная архитектура на базе XMT

Оценка быстродействия

Данная архитектура оценивалась с помощью симулятора на примере XMT-подобной системы, состоящей из 32 узлов, и при этом число ядер в процессоре изменялось от 1 до 16, а число независимых контроллеров памяти, приходящихся на процессор, — от 1 до 8. Пропускная способность сетевого адаптера была назначена равной 670 Mref/s (впятеро больше, чем у нынешней сети XMT SeaStar2, и примерно такой же, как у межсоединений Cray Gemini), а пропускная способность контроллеров памяти — в 200 Mref/s (вдвое больше, чем у нынеших каналов памяти DDR в XMT). Значения задержки и пропускной способности при моделировании были заданы в соответствии с планами развития спецификаций сети межсоединений и памяти DDR3.

На рис. 4 показаны результаты оценки на примере трех тестовых задач: уже использовавшееся в предыдущих экспериментах приложение поиска подстроки по Ахо-Корасик; BFS, стандартный элемент приложений, в которых используются структуры данных на основе графов; перемножение матриц, типичный регулярный алгоритм, который был включен в тест в целях оценки влияния предложенных инженерных решений на обработку более стандартных приложений. Сплошная линия на рисунках отражает «идеал» быстродействия, когда в сети и интерфейсах памяти отсутствуют конфликты блокировок и нет насыщения. Эти линии показывают, что тесты достаточно удачно распараллелены, чтобы масштабироваться по мере роста числа ядер у процессоров.

Рис. 4. Время исполнения трех тестовых приложений в зависимости от числа ядер на процессор на 32-узловой XMT-подобной системе предложенной многоядерной архитектуры: а — поиск подстроки по Ахо-Корасик; б — BFS (400 тыс. вершин, 400 соседей у каждой вершины); в — умножение матриц (2000х2000 элементов). Для каждого приложения показаны результаты при различном числе интерфейсов памяти на процессор

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

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

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

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

Агрегация обращений к памяти

В XMT каждая операция с удаленной памятью инкапсулируется в короткий сетевой пакет, что обеспечивает мелкозернистость трафика, однако короткие сообщения обычно перегружают неоптимизированные сети вследствие низкого соотношения заголовок/полезная нагрузка. Чтобы компенсировать это явление, в некоторых системах межсоединений выполняется агрегация коротких пакетов. Обычно это делается либо на аппаратном уровне с помощью специализированных маршрутизаторов, как в чипе-концентраторе для многопроцессорных модулей IBM Power7, либо программно посредством драйверов и API. Однако второй подход трудно реализовать в XMT-подобных машинах, где при каждой операции чтения/записи выполняется прямое обращение к сетевой памяти без какого-либо промежуточного программного уровня.

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

Аппаратный механизм агрегации

Механизм агрегации действует путем буферизации до D обращений к памяти к одному и тому же узлу назначения (DST) за временное окно из W тактов. Когда достигается D обращений к памяти или истекает временное окно, механизм отправляет все обращения в буфер на DST в одном сетевом пакете с общим заголовком. На рис. 5 показана блок-схема такого аппаратного механизма. LSQ различных ядер соединены интерфейсом с логикой выбора, идентифицирующей DST для каждого обращения к памяти. Логика выбора через DST обращается к одному из FIFO-буферов, в которых агрегируются сведения об обращениях к памяти, включая адрес, значение, коды операции и управляющие биты.

Буфер FIFO имеется у каждого узла в системе, и каждый буфер вмещает D обращений. Когда в буфере находятся D обращений, логика создания пакетов формирует сетевой пакет со всем содержимым буфера и общим заголовком. Каждый буфер FIFO также имеет вычитающий счетчик с начальным значением W. По достижении счетчиком нуля, даже если буфер не полон, срабатывает логика создания пакета. Если буфер заполняется до достижения нуля, модуль немедленно отправляет пакет и устанавливает счетчик равным W. Модуль логики выборочной остановки не позволяет процессору генерировать дальнейшие обращения к тем же DST, когда буфер полон, но сетевой пакет сформировать нельзя, — например, когда логика агрегации занята созданием другого пакета.

Рис. 5. Аппаратный механизм агрегации обращений к памяти

В системе, поддерживающей большое количество узлов, реализация буфера FIFO для каждого DST может потребовать большого объема встроенной в процессор памяти, и чтобы уменьшить эту потребность, можно использовать многоступенчатые и иерархические схемы агрегации, когда каждый буфер накапливает обращения к памяти определенной группы узлов. Затем один из узлов группы распределяет обращения по конечным пунктам назначения. Недостатком этого подхода будет более высокая сложность логики агрегации и увеличенная задержка. Однако с дальнейшим увеличением числа потоков на процессор задержка может быть компенсирована.

Анализ масштабируемости

Описанный механизм агрегации был реализован на имитаторе 32-узловой системы XMT. Вначале оценивались различные соотношения размера буфера D и длины временного окна W. Выяснилось, что оптимальные значения — это: D = 16 и W = 32. Но данный результат, очевидно, зависит от числа узлов в машине, поскольку время заполнения буферов и средняя сетевая задержка с числом узлов увеличиваются.

Был повторно проведен анализ масштабируемости многоядерной конфигурации, показанной ранее на рис. 4, с использованием тех же трех тестов. На рис. 6 сравниваются результаты, полученные с логикой агрегации и без нее; в данном случае у каждого процессора было по два контроллера памяти — это и есть оптимальное количество. Во всех тестах рост производительности оказался существенным, приближающимся к идеалу. Хотя механизм агрегации увеличивает задержку выполнения операций с удаленной памятью (из-за необходимости выдерживать временные окна и затрат на формирование пакета), это компенсируется способностью ядер обрабатывать большое число потоков.

Рис. 6. Время исполнения трех тестовых приложений в зависимости от количества ядер на процессор на 32-узловой XMT-подобной системе предложенной многоядерной архитектуры со встроенным механизмом агрегации: а — поиск подстроки по Ахо-Корасик; б — BFS; в — умножение матриц. Для каждого приложения результаты показаны с включенной и выключенной логикой агрегации. У каждого процессора по два контроллера памяти

***

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

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

Антонино Тумео, Симоне Секки, Оресте Вилья ({antonino.tumeo , simone.secchi , oreste.villa}@pnnl.gov) — научные сотрудники Тихоокеанской северо-западной национальной лаборатории (США).