Суперкомпьютер экзафлопсного уровня производительности должен обрабатывать 109 потоков при производительности одного потока порядка 1 GFLOPS, однако практика использования компьютеров из Тop500 показывает, что уже на системах с миллионами потоков возникают простои процессоров в ожидании завершения чтения/записи данных, препятствующие эффективному применению и дальнейшему повышению быстродействия суперкомпьютеров. Анализ показывает [1], что без учета особенностей преодоления энергетических ограничений путем увеличения числа ядер на кристаллах и исключения длинных линий разводки сигналов, а также устранения разрыва между быстродействием логических элементов и элементов памяти дальнейшее увеличение производительности невозможно. Параллельная обработка требует особых архитектурных решений.
Преодолеть разрыв между временем выполнения команд в процессоре и временем доступа к памяти можно при создании программ, способных выявлять весь присущий конкретному алгоритму параллелизм и учитывать мельчайшие гранулы параллелизма. В этом случае появляется потенциальная возможность при ожидании одним потоком завершения обращения к памяти параллельно выполнять другие потоки [2]. Для снижения потерь производительности при переключении процессора с исполнения одного потока на выбор и начало исполнения другого можно использовать «легкие» потоки — q-треды, имеющие минимальный контекст. В этом случае программа для экзафлопсного суперкомпьютера будет представлять собой описание процесса порождения миллиардов потоков, межпотоковых коммуникаций и процедур синхронизации этих потоков, которое компилятор статически и библиотеки динамически преобразуют в совокупность потоков для конкретных ресурсов или отображают потоки на момент выполнения.
Могут использоваться отображения как в асинхронные потоки, протекающие в универсальных процессорах и имеющие собственный отдельный счетчик команд, так и в синхронные потоки, выполняемые по одному счетчику команд в разных устройствах; например, в графических процессорах общего назначения (GPGPU) Nvidia Fermi синхронно в каждом такте может протекать до 512 потоков. Синхронные потоки составляют аппаратно экономную альтернативу асинхронным, но они сложнее в программировании, а сама программа будет исполняться на гетерогенных ресурсах, и для доступных заданию гетерогенных ресурсов будет необходимо обеспечить оптимальное назначение тредов задания. Конечной целью служит автоматическое назначение, но начинать следует с создания API библиотеки требуемой совокупности ресурсов и назначения тредов на эти ресурсы. Надо уметь определять гетерогенные ресурсы, например устройства выполнения пучков синхронных тредов, и выделять в программе треды, которые должны выполняться в синхронном режиме на этих устройствах. В ходе отображения тредов на ресурсы должны формироваться межтредовые коммуникации с применением наиболее подходящего коммуникационного ресурса и режимов использования этих ресурсов (организация потоков сообщений, формирование сообщений заданной длины путем сборки из нескольких и т. д.).
Модель программирования
Одной из возможных моделей программирования экзафлопсных компьютеров является модель Parallel Random Access Model (PRAM) [3], которая базируется на архитектуре мультипроцессора с разделяемой памятью. Процессоры Pi, i=1, …, n, имеют доступ к общей памяти (Distributed Shared Memory, DSM) или секционированной общей памяти (Partitioned Global Address Space, PGAS), физически распределенной по вычислительным модулям (процессор + блок памяти), но имеющей общее адресное пространство, логически доступное всем процессорам. Программист предполагает, что команды потоков, протекающие в каждом из процессоров, выполняются синхронно, а межпроцессовые коммуникации и синхронизация осуществляются через ячейки памяти.
Имеются различные подходы к разрешению конфликтов доступа разных процессоров к одной ячейке разделяемой памяти [3], однако предпочтительным считается подход CREW (Concurrent-Read Exclusive-Write) с возможностью одновременного чтения одной и той же ячейки совокупностью процессоров, а записи только одним из процессоров. В этом случае все одновременные доступы к памяти по чтению предшествуют доступу по записи. При такой модели параллельного программирования пользователь должен только указывать, какие вычисления можно проводить параллельно. При необходимости прочитать одно и то же значение многими потоками, а потом записи вместо него в соответствующую ячейку общей памяти нового значения пользователь полагает, что при одновременном обращении к памяти у команд чтения будет преимущество перед командой записи, и этот механизм разрешения конфликта реализуется аппаратными средствами управления доступом. В свое время именно отсутствие эффективного масштабируемого аппаратного решения для разрешения конфликтов доступа к памяти привело к отказу от PRAM и переходу к модели на базе передачи сообщений, однако сегодня такое решение имеется.
Языковые средства порождения и завершения процессов
В качестве языка параллельного программирования может быть взято расширение языка Си [3], в котором для порождения и завершения асинхронных тредов в программах, написанных на традиционных языках программирования, могут быть использованы три дополнительные команды: spawn (a, n), joint и fetch_and_add (e, x). Они позволяют породить заданное параметром n количество тредов с последовательными номерами, начиная с номера a; завершить тред, исполняющий команду join; выполнить как неделимую атомарную операцию присвоения переменной, например номеру треда, значения параметра x и увеличить значение x, прибавив к x значение e.
Аналогичная, но более ограниченная модель использована в Intel Parallel Studio 2011; в ее рамках предложено расширение Cilk Plus: cilk_for, cilk_spawn и cilk_sync, где cilk_spawn порождает функцию в виде отдельного потока, который выполняется параллельно с текущим потоком, cilk_sync ожидает завершения запущенных потоков, а cilk_for распараллеливает циклы.
В качестве начального варианта генерации множества легких тредов может быть использован подход на базе OpenMP без модификации исходного кода прикладной программы для суперкомпьютера. Для трансляции исходного кода теста используется открытый компилятор Rosecompiler, заменяющий директивы OpenMP на соответствующие вызовы функций API Runtime-системы управления легкими тредами. Этот подход был опробован с библиотеками Qthreads и MAESTRO [4], однако требует исследования и модификации планировщик легких тредов, позволяющий снизить простои оборудования за счет освобождения ресурсов от простаивающих тредов.
Межпроцессовые коммуникации и синхронизации
Синхронизация, выполняемая на базе примитивов ОС, как в Unix-процессах и р-тредах IEEE Std 1003.1-1990: Portable Operating Systems Interface, означает большие задержки, поэтому в предлагаемой модели вычисления, производимые каждым процессором, представляются потоком (тредом). Для синхронизации потоков предлагается использовать механизм межтредовой синхронизации и коммуникации — добавление к каждому слову памяти full/empty (FE) бита и введение дополнительных команд обращения к памяти. Команды writeef, readfe, readff и writeff, обращающиеся к ячейке памяти, могут выполняться только после определения значения бита FE. Выполнение команды задерживается, если FE не имеет нужного значения.
Синхронизация на базе бита FE не требует специальных разделяемых переменных, таких как «замки», семафоры и др., а также механизмов синхронизации, весьма затратных по времени их определения и исполнения при миллионах тредов [2]. Кроме того, операции с применением разделяемых переменных и неделимых (атомарных) последовательностей команд, определяющих значение условия ветвления и выполняющих переход в соответствии с полученным значением, оказываются сложнее и осуществляются дольше, чем выполнение команд доступа к памяти при синхронизации динамически порождаемых легких тредов. Поэтому синхронизация на базе бита FE позволит выдавать максимально возможное в исполняемой программе количество обращений к памяти, генерируемых легкими тредами, и параллельно выполнять эти доступы в расслоенной памяти.
В компьютере CrayXMT расширение языка Си для проведения синхронизации на базе битов FE реализовано путем введения синхронизирующих переменных x$ и аппаратных функций (generic functions), обеспечивающих выполнение операций чтения и записи.
Однако использование синхронизирующих переменных имеет свои особенности: например, условный оператор if ((x$ >= 10)&&(x$ <= 100)){} выполняется корректно, если программист задумал использовать два разных значения переменной x$ при условии, что есть другой процесс, записывающий новое значение в x$ после выполнения проверки x$ >= 10. Но если программист хотел только проверить принадлежность x$ интервалу [10, 100], то возникнет тупиковая ситуация (дедлок).
Синхронизирующие переменные могут служить в качестве семафоров для создания барьеров и критических интервалов, организующих исключительный доступ одного процесса из множества процессов к переменным, разделяемым этим множеством процессов. Кроме того, синхронизирующие переменные могут использоваться для задания потоковых (dataflow) вычислений.
Потоковые вычисления
В традиционных потоковых архитектурах основу составляет ассоциативная память, в которую помещаются команды, ждущие готовности операндов. Ясно, что количество команд, одновременно извлекаемых из ассоциативной памяти, определяет производительность компьютера, поэтому объем ассоциативной памяти должен быть большим. Однако на пути создания такой памяти встают энергетические затраты и падение быстродействия при росте объема памяти. Попытки программной реализации ассоциативной памяти на базе адресуемой памяти с использованием хеш-функций, разбиение общей ассоциативной памяти на локальные блоки и определение готовности только начальных команд целых фрагментов команд не сделали оправданной практическую реализацию традиционных потоковых архитектур.
Подход на уровне контроллеров блоков памяти, выполняющих работу с FE-битами слов, представляется вполне реализуемым. Во-первых, блоков памяти может быть много, и, во-вторых, выполняется только действительно необходимая синхронизация без какого-либо предварительного разбиения программ на фрагменты команд. Реализация в процессоре внеочередного исполнения команд посредством резервирующей станции и использование контроллеров блоков памяти, выполняющих работу с битами FE, покрывают всю функциональность потоковых архитектур.
Архитектура экзафлопсного компьютера
Компьютер, реализующий подход с битами FE, строится из вычислительных модулей, каждый из которых имеет один или несколько процессорных кристаллов с подсоединенными к ним блоками памяти и интерфейсами коммуникационной среды, объединяющей все вычислительные модули (см. рисунок). Процессорный кристалл содержит накристальную коммуникационную сеть, объединяющую совокупность ядер, не обязательно одинаковых, один или несколько блоков управления памятью (Memory Management Unit, MMU), накристальные контроллеры блоков памяти, подсоединенных к кристаллу, а также один или несколько сетевых контроллеров, подключаемых к интерфейсу коммуникационной среды компьютера.
.png "Концептуальная архитектура экзафлопсного компьютера") |
| Концептуальная архитектура экзафлопсного компьютера |
Каждое ядро, из числа размещаемых на кристалле, при выполнении команды доступа к памяти обращается к накристальному блоку управления памятью, который на основе задаваемого при инициализации распределения глобального адресного пространства по блокам памяти определяет, идет ли обращение к локальному или удаленному блоку памяти. В последнем случае формируется обращение к сетевому контроллеру, который должен переслать обращение соответствующему удаленному блоку. Таким образом, выполнение в ядре команды обращения к памяти задерживается в ожидании ответа о завершении обращения к памяти из MMU. контроллер блока памяти, получив такое обращение, выполняет работу с битом FE указанной ячейки памяти. Если бит FE не имеет требуемого значения, то обращение к памяти помещается в таблицу ожидания. Строки этой таблицы содержат собственно обращение к памяти (команду чтения/записи, адрес ячейки, значения битов FE до выполнения обращения и по его завершении, а также указатель на незавершенную команду MMU). Если бит FE имеет необходимое значение, то контроллер блока памяти выполняет требуемое чтение или запись и формирует заданное значение FE. После завершения обращения к ячейке памяти должны выполняться поиск в таблице ожидания строк, соответствующих этой ячейке памяти, и проверка возможности выполнения соответствующего обращения к памяти. Если такое возможно, то обращение запускается на выполнение, а соответствующая ему строка удаляется из таблицы. Распределенность обращений в память служит гарантией высокой производительности, пропорциональной количеству используемых вычислительных модулей.
Следует отметить, что разрешением конфликтов доступа к памяти занимается контроллер блока памяти, к которому выполняется доступ, — контроллер ведет необходимые очереди запросов для разрешения конфликтов. Можно модернизировать контроллер для реализации функций спекулятивного исполнения тредов или транзакционной памяти.
Представленная функциональность контроллера блока памяти может быть расширена для спекулятивного выполнения легких тредов и реализации транзакционной памяти. Однако нужно исследовать, какой из подходов обеспечивает масштабируемое решение проблемы задания синхронизации и межтредовых коммуникаций вплоть до 109 и более тредов.
Компиляторы не всегда справляются с выявлением конфликтов при доступе к ячейкам памяти в случае динамически вычисляемых адресов, а сам факт возникновения конфликта может быть определен специальным аппаратно-программным компонентом контроллера памяти и подсистемой времени исполнения. Спекулятивное выполнение легких тредов выявляет конфликты и инициирует повторное выполнение конфликтующих тредов, обеспечивая их бесконфликтное протекание. Например, при порождении легких тредов из итераций цикла, обрабатывающего массив указателей, можно столкнуться с ситуацией, когда предыдущая итерация пытается прочитать ячейку памяти, в которую выполнена запись последующей итерацией, что приведет к ошибке. Контроллер может на основании имен тредов (значений индексной переменной) определять конфликты и разрешать их путем обращения к среде времени исполнения.
Транзакционная память обеспечивает выполнение последовательности команд как атомарной операции, делая доступным изменение памяти только в режиме атомарных операций, к числу которых принадлежит упомянутая fetch_and_add(e, x). Возможность выполнить преобразование ячейки памяти, не прибегая к пересылке туда-обратно ее значения, будет способствовать повышению эффективности работы с памятью.
Кроме сокращения времени выполнения доступа к памяти, в модели программирования для экзафлопсного суперкомпьютера должен использоваться еще один прием повышения производительности — уменьшение количества обращений к памяти за счет непосредственной передачи операндов между процессорными ядрами, минуя промежуточное хранение операндов в памяти [1].
***
Исследование и разработка программно-аппаратных средств решения проблем, стоящих перед создателями экзафлопсных суперкомпьютеров, требует анализа существующих архитектурных идей повышения производительности, создания экспериментальных компьютеров и программирования для них задач, для которых нужна производительность, недостижимая на существующих системах. Необходимо изменить представления о параллельных программах и способах отображения программных компонентов на ресурсы, провести анализ методов программно-аппаратной поддержки синхронизации потоков и межпотоковых коммуникаций с целью определения удовлетворительного варианта архитектуры, операционной системы, среды времени исполнения, средств подготовки программ и их компиляции. Сегодня наступил момент для смены парадигмы суперкомпьютерных вычислений и самой парадигмы программирования, напоминающий ситуацию начала 1990-х годов, когда на смену векторно-конвейерным пришли массово-параллельные системы на базе передачи сообщений.
Очевидно, что освоение такой парадигмы параллельных вычислений позволит повысить эффективность существующих суперкомпьютеров и создать масштабируемые программы для будущих поколений компьютеров, сократив затраты на подготовку пользователей и разработчиков.
Литература
- Корнеев В.В. Подход к программированию суперкомпьютеров на базе многоядерных мультитредовых кристаллов // НИВЦ МГУ им. М.В. Ломоносова. Научный журнал «Вычислительные методы и программирование». — 2009. — Том 10. — С. 123–128.
- K. Wheeler et al. Qthreads: An API for Programming with Millions of Lightweight Threads. Workshop on Multithreaded Architectures and Applications at IEEE IPDPS, April, 2008.
- X. Wen, U. Vishkin. FPGA-Based Prototype of a PRAM-On-ChipProcessor.CF’08, May 5–7, 2008, Ischia, Italy.
- A. Porterfield, R. Fowler, P. Horst, D. O’Brien, S. Olivier, K. Wheeler, B. Viviano. Scheduling OpenMP for Qthreads with MAESTRO. Technical Report TR-11-02, Renaissance Computing Institute, September, 2011.
Виктор Корнеев ( korv@rdi-kvant.ru ) — сотрудник НИИ «Квант» (Москва). Статья подготовлена на основе материалов доклада, представленного на Пятом Московском суперкомпьютерном форуме (МСКФ-2014, грант РФФИ 14-07-20284г).
