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

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

Рис.1. Ресурс параллелизма и использование данных
Рис.1. Ресурс параллелизма и использование данных

 

Ресурс параллелизма в современных суперкомпьютерах растет невероятными темпами — первое значение в 1 MFLOPS было получено в 1966 году на компьютере CDC-6600, содержащем единственный процессор, и до настоящего времени именно увеличение степени параллелизма определяло рост производительности. Все специалисты сходятся во мнении, что на экзафлопсных суперкомпьютерах одновременно будут работать сотни миллионов и миллиарды параллельных процессов и нитей, а если это так, то как обеспечить эффективность их взаимодействия при выполнении приложения?

Эффективное использование данных уже давно стало серьезной проблемой, и еще в середине 90-х годов она удостоилась даже специального термина — «стена памяти» [1]. Задержка при обращении процессора к оперативной памяти для большинства современных систем лежит в диапазоне 150–300 тактов, и пока нет доступных технологий, которые могли бы это значение принципиально уменьшить. Основным решением на сегодня является использование иерархии памяти, однако тут же возникает вопрос: как обеспечить работу с данными в программах и алгоритмах, адекватную введенной иерархии?

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

Универсальный характер применимости локальности сначала удивляет, но вместе с этим он легко объясняется многими естественными принципами. Простой физический принцип «чем ближе расположены — тем быстрее взаимодействие» находит отражение почти во всех элементах архитектуры вычислительных систем. Более того, необходимость учета локальности возникает и из-за постоянного поиска компромисса между разумной стоимостью и разумными характеристиками компонентов суперкомпьютеров. Хорошо бы тогда и для всей оперативной памяти иметь латентность, как у кэш-памяти первого уровня, но пока это технологически сложно и чрезмерно дорого, а отсюда и возникает иерархия памяти, отражающая локальность. Хорошо бы в суперкомпьютерах для быстрой связи каждого узла с любым другим иметь топологию коммуникационной сети «полный граф», но это технологически сложно и дорого, а отсюда компромиссы в виде более простых решений: решетка, кольцо, толстое дерево, N-мерный тор, Dragonfly и другие — где взаимодействие с непосредственными соседями всегда происходит быстрее. Следует отметить и тот факт, что локальность свойственна и нашему стилю написания программ, и используемым структурам данных, многим технологиям программирования и используемым конструкциям языков высокого уровня.

Локальность всюду

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

Иерархия памяти — очень важное понятие, прямо связанное с эффективностью. Для любой современной вычислительной платформы легко написать два варианта программы, реализующих один и тот же алгоритм, но отличающихся друг от друга на порядок по времени работы, причем без использования избыточных операций и каких-либо специальных задержек. Интересно и то, что сама идея иерархии памяти появилась давно. Например, уже в компьютере ILLIAC-IV (1967 год) каждый процессорный элемент имел 6 регистров и 2048 слов оперативной памяти. Кроме того, для всей системы были предусмотрены два диска по 1 Гбит каждый и барабан для долговременного хранения данных объемом 1012 бит с однократной записью — иерархия памяти в четыре уровня была уже тогда.

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

Еще большее значение имеет локальность данных в системах с распределенной памятью. Во время работы параллельной программы происходит обмен данными между процессами, на скорость которого влияют и латентность, и пропускная способность, и другие характеристики коммуникационной сети. Чем меньше обменов, тем меньше задержек и выше эффективность программ. Как распределить данные по памяти вычислительных узлов, чтобы минимизировать обмен в процессе выполнения программы? Это исключительно серьезная математическая задача [2], которая далеко не всегда имеет простое решение, однако эта задача принципиально важна для разработки масштабируемых приложений для экзафлопсных суперкомпьютеров, и именно поэтому проектирование алгоритмов без интенсивного обмена данными (communication free algorithms) является одним из приоритетных направлений исследований для всего суперкомпьютерного сообщества.

Заметим, что понимание важности описания локальности расположения данных для создания масштабируемых и переносимых приложений привело к появлению отдельного класса технологий параллельного программирования, опирающихся на модель PGAS (Partitioned Global Address Space). Яркими представителями этого класса являются языки UPC, Coarray Fortran, Fortress, Chapel и X10.

Смежный, но очень важный для систем с распределенной памятью вопрос — топология коммуникационной сети и ее учет параллельными приложениями. Главная проблема заключается в том, чтобы обеспечить хорошее соответствие между локальностью взаимодействия параллельных процессов в приложении и близостью вычислительных узлов. Интересные данные были приведены на конференции ISC 2013 об опыте использования суперкомпьютера Blue Waters в Центре суперкомпьютерных приложений — если из 4116 узлов, выделяемых приложению, всего 1 узел (0,02% от общего числа) выбивается из связного пула узлов и выделяется где-то в другой области коммуникационной сети, то падение эффективности работы приложения на такой конфигурации может достигать 30% и более. Подобные примеры накладывают жесткие требования не только на качество работы планировщиков заданий, которые обязательно должны учитывать локальность при выделении ресурсов приложениям. Здесь важно понимать и четко описывать структуру взаимодействия параллельных процессов внутри самих приложений, но эта информация доступна далеко не всегда. Если в приложении, например, явным образом используется понятие MPI-топологии, то задача упрощается, но в общем случае она очень непроста.

Весьма интересно то, как идеи локальности отражаются в технологиях программирования. В технологии OpenMP предусмотрены два класса переменных: локальные (private) и глобальные (shared). Если нить использует свои локальные переменные, то все происходит без каких-либо задержек и проблем. Но если необходим доступ к глобальной переменной, то начинаются вопросы. Где физически расположить глобальную переменную, чтобы доступ к ней из любой нити был бы одинаково быстрым? Как обеспечить синхронизацию доступа для сохранения корректности данных? Сразу возникает необходимость синхронизации и использования механизмов критической секции или семафоров, и, как следствие, неизбежно падает эффективность.

Другой пример «нелокальности» — коллективные операции в MPI, вовлекающие, как правило, все параллельные процессы приложения. На практике отсутствие локальности в организации параллелизма всегда оборачивается проблемами с эффективностью и масштабируемостью приложений, поэтому использование таких операций стараются минимизировать. Для алгоритмов, в которых не требуется барьерная синхронизация, ввели даже специальное название: synchronization free algorithms, подчеркивая практическую важность этого свойства.

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

Локальность на практике

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

Мощным средством, дающим хорошее представление о свойствах локальности реальных приложений, является построение профиля работы приложения с памятью [3] — последовательности чисел (адресов) в памяти, расположенных в том порядке, в котором к ним происходят обращения при выполнении программы. Как часто этим пользуются на практике? Вряд ли можно назвать это распространенным явлением. На рис. 2 показаны четыре профиля, отвечающие различным приложениям. По вертикали отложены виртуальные адреса данных, к которым происходит обращение, а по горизонтали — порядковый номер обращения: чем правее расположено обращение, тем позже оно произошло. Ясно, что программа, профиль которой изображен на рис. 2, а, обладает крайне плохой как пространственной, так и временнóй локальностью, что станет причиной заведомо низкой эффективности. Профиль на рис. 2, б показывает чуть лучшие свойства, но до высоких показателей еще далеко, а программы, чьи профили изображены на рис. 2, в и 2, г, явно обладают хорошими свойствами локальности.

Рис. 2. Профили работы с памятью реальных программ
Рис. 2. Профили работы с памятью реальных программ

 

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

Еще одним мощным средством исследования реальных свойств программ является анализ данных мониторинга системного уровня, описывающих характеристики программно-аппаратной среды суперкомпьютеров во время исполнения приложений. В основе подхода Job Digest [4], развиваемого в НИВЦ МГУ, лежит анализ данных от аппаратных датчиков: реальная загрузка процессоров, реальная производительность, особенности использования коммуникационной сети, интенсивность операций ввода-вывода, появление свопинга и т. д. Эти и другие параметры дают содержательную информацию о многих свойствах параллельных приложений. В том числе и о свойствах локальности. На рис. 3 показаны два графика,иллюстрирующих ситуацию с промахами в кэш-память второго уровня для двух разных приложений. Ясно, что у первого приложения локальность использования данных не составляет проблем, однако у второго на локальность явно нужно обратить внимание.

 

Рис. 3. Job Digest: иллюстрация кэш-промахов для отражения локальности использования данных в приложениях
Рис. 3. Job Digest: иллюстрация кэш-промахов для отражения локальности использования данных в приложениях

 

***

Свойство локальности отлично согласуется с возможностями технологий для разумного построения суперкомпьютеров экзафлопсной производительности, а сама идея локальности естественна и отражает окружающий мир, поэтому неудивительно, что нерегулярные приложения проигрывают приложениям с хорошими свойствами локальности. Более того, суперкомпьютеры будущего будут учитывать свойства локальности, что подтверждается даже соображениями энергопотребления — жизненно важного для экзафлопсных систем. Энергозатраты на выполнение одной арифметической операции составляют 100 пДж (1 пДж = 10-12 Дж), в то время как энергозатраты на перемещение данных в пределах узла — 4800 пДж, что ставит жесткое требование к минимизации перемещений данных и снова указывает на актуальность свойства локальности.

Литература

  1. Wulf W.A., McKee S.A., Hitting the Memory Wall: Implications of the Obvious. Computer Architecture News, vol. 23, no. 1, Mar. 1995, pp. 20-24.
  2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
  3. Воеводин Вад.В. Визуализация и анализ профиля обращений в память // Вестник Южно-Уральского государственного университета. Сер. Математическое моделирование и программирование. 2011. № 17(234). с. 76-84.
  4. Адинец А., Брызгалов П., Воеводин В., Жуматий С., Никитенко Д., Стефанов К. Jobdigest — подход к исследованию динамических свойств задач на суперкомпьютерных системах // Вестник Уфимского государственного авиационного технического университета. 2013. № 17, 2 (55). c. 131-137.

Владимир Воеводин (voevodin@parallel.ru) — зам. директора, Вадим Воеводин (vadim_voevodin@mail.ru) — научный сотрудник НИВЦ МГУ. Статья подготовлена на основе материалов доклада, представленного на IV Московском суперкомпьютерном форуме (МСКФ-2013, грант РФФИ 13-07-06046г). Работа выполнена при поддержке Минобрнауки РФ (госконтракт № 14.514.11.4103), стипендии Президента РФ (СП-6815.2013.5) и РФФИ (грант 13-07-00787).