автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Разработка и исследование архитектуры глобально адресуемой памяти мультитредово-потокового суперкомпьютера

0046

5917

На правах рукописи

Семенов Александр Сергеевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АРХИТЕКТУРЫ ГЛОБАЛЬНО АДРЕСУЕМОЙ ПАМЯТИ МУЛЬТИТРЕДОВО-ПОТОКОВОГО СУПЕРКОМПЬЮТЕРА

специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

- 0 ПЕН 2019

Москва - 2010

004615917

Работа выполнена в отделе архитектуры и программного обеспечения суперкомпьютеров ОАО "НИЦЭВТ".

Научный руководитель: кандидат физико-математических наук

Эйсымонт Леонид Константинович.

Официальные оппоненты: доктор физико-математических наук,

профессор

Томилин Александр Николаевич;

кандидат физико-математических наук Ефимкин Кирилл Николаевич.

Ведущая организация: ОАО "Институт Электронных

Управляющих Машин им. И. С. Брука".

Защита диссертации состоится "13" декабря 2010 г. в 10:00 часов на заседании диссертационного совета Д 212.125.01 в Московском авиационном институте (государственном техническом университете) по адресу 12599-3, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4.

С диссертацией можно ознакомиться в библиотеке Московского авиационного института.

Автореферат разослан "12" ноября 2010 г.

Ученый секретарь

диссертационного совета Д 212.125.01 к.т.н.

Корнеенкова А. В.

Общая характеристика работы Актуальность темы

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

Главные работы по решению проблем низкой реальной производительности и низкой продуктивности программирования в настоящее время ведутся фирмами Cray (проект Cascade) и IBM (проект PERCS) с целью создания суперкомпьютеров стратегического назначения (СКСН) транспетафлопсного уровня реальной производительности с перспективной мультитредово-векторной архитектурой и глобально адресуемой памятью. Эти проекты ведутся в рамках крупной американской программы DARPA HPCS, начатой в 2002 году. Всего лишь с задержкой в 4 года к работам по созданию СКСН такого же типа приступили ведущие фирмы и государственные организации Японии (проект Keisoku-Keisan-Ki) и Китая (проект "программа 863"). При этом наиболее близок к основным решениям проектов программы DARPA HPCS проект создания китайской перспективной СКСН, который предполагает создание собственного микропроцессора и собственной специальной коммуникационной сети с большой пропускной способностью и малым диаметром. В России работы по перспективной СКСН ведутся в рамках проекта "Ангара" по созданию мультитредово-потокового суперкомпьютера с глобально адресуемой памятью.

Главной задачей, решаемой в этих проектах, является преодоление так называемой проблемы «стены памяти». Суть этой проблемы состоит в сложившемся на сегодняшний день значительном отставании (сотни раз) времени выполнения операций с оперативной памятью от времени выполнения арифметико-логических операций в процессоре. Эта проблема обусловлена особенностями развития микроэлектронной компонентной базы - задержка обращения к внскристальной DRAM-памяти с учетом промахов в кэш-память дескрипторов сегментов и/или страниц может составлять 300-500 тактов процессора. Задержка обращения к коммуникационной сети может составлять десятки тысяч тактов процессора. Значимость этой проблемы усилена качественными изменениями требований перспективных прикладных программ - увеличение необходимого задаче логически неделимого объема памяти, рост доли команд обращений к памяти,

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

Наличие проблемы "стены памяти" приводит к тому, что на DIS-задачах из-за простоев процессора при ожидании данных из памяти реальная производительность (sustained performance) СКСН может деградировать до 0.1-5 % от пиковой производительности. Эта проблема также не позволяет существенно масштабировать реальную производительность при увеличении количества процессоров, используемых при выполнении задачи. В результате многие DIS-задачи практически невозможно решить за приемлемое время на существующих суперкомпьютерах.

Решение проблемы "стены памяти" позволит реально работать с глобально адресуемой памятью и перейти на одностороннее взаимодействие параллельных процессов, что важно для эффективного выполнения программ на языках класса PGAS (Partitioned Global Address Space -языки UPC, CAF), а также для перспективных языков с иерархическим описанием параллельных программ (языки Chapel, Х10 и Fortress). В целом, это позволит повысить продуктивность параллельного программирования, по оценкам мировых экспертов, в 10-40 раз.

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

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

Данная диссертационная работа посвящена разработке архитектуры глобально адресуемой памяти СКСН «Ангара», исследованию ее

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

Цель и задачи диссертационной работы

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

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

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

3. Исследование возможностей использования разработанной архитектуры глобально адресуемой памяти в сочетании с другими особенностями суперкомпьютера "Ангара" для достижения высокой реальной производительности.

4. Исследование возможности использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования РСАБ-класса.

Научная новизна работы

Полученные результаты являются новыми и состоят в следующем:

1. Разработана архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера.

2. Разработаны и исследованы блоки, имитирующие работу глобально адресуемой памяти в составе параллельной программной потактовой имитациониой модели суперкомпьютера «Ангара».

3. Показано, что применение разработанной глобально адресуемой памяти в сочетании с другими возможностями мультитредово-потокового суперкомпьютера "Ангара" в сравнении с опубликованными данными по существующим суперкомпьютерам позволяет:

— повысить реальную производительность на задачах с интенсивным нерегулярным доступом к памяти до одного-двух порядков при совпадении реальной производительности на остальных задачах;

— использовать при получении высокой реальной производительности короткие односторонние коммуникационные передачи, при помощи которых

проще создавать параллельные программы по сравнению с традиционным программированием с использованием MPI.

4. Продемонстрирована возможность использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования PGAS-класса на примере языка UPC.

Разработанная архитектура защищена патентом Российской Федерации № 2396592 "Способ организации глобально адресуемой общей памяти в многопроцессорной ЭВМ" от 21 октября 2008 года и обладает следующими основными свойствами:

— имеет сегментно-страничную организацию с двухуровневой виртуализацией адресов и широким диапазоном размеров сегментов и страниц, а также возможностью работы с сегментами сверхбольшого размера;

— обладает расширенными возможностями отображения виртуальной памяти на физическую за счет использования блочного и блочно-циклического методов, а также зашумления адресов;

— использует теги состояния в ячейках памяти и теги доступа в адресах, что позволяет выполнять мелкозернистую синхронизацию непосредственно на ячейках памяти без участия процессора;

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

Практическая ценность работы

Разработанная архитектура глобально адресуемой памяти является одним из основных архитектурных решений, принятых при разработке мультитредово-потокового суперкомпьютера "Ангара".

Программная параллельная имитационная потактовая модель мультитредово-потокового суперкомпьютера используется в ОАО "НИЦЭВТ" для отработки принципов работы суперкомпьютера "Ангара" и вариантов их аппаратной реализации, создания и отработки системного программного обеспечения, построения моделей прикладных задач.

Практическую ценность работы подтверждает акт №83/6-4328 от 26.10.2010 о внедрении архитектуры глобально адресуемой памяти мультитредово-потокового суперкомпьютера в ОАО "НИЦЭВТ".

Полученные результаты исследования возможностей реализации средств продуктивного параллельного программирования используются при реализации интерфейсов и языков PGAS-класса для суперкомпьютера "Ангара" и суперкомпьютеров поколения СКИФ-4.

Апробация работы и публикации

Основные положения работы докладывались на второй международной конференции "Параллельные вычислительные технологии" (ПАВТ-2008), на XIV международной конференции студентов, аспирантов и молодых ученых Ломоносов-2007, на научных семинарах в НИВЦ МГУ под руководством член-корр. РАН д.ф.-м. н. Вл. В. Воеводина, в ОАО "НИЦЭВТ" иод руководством к. ф.-м. н. Л. К. Эйсымонта, а также в ИПМ РАН (направление - "Программирование").

По результатам работы имеется восемь публикаций [1, 2, 3, 4, 5, 6, 7, 8), в том числе три статьи в журналах из списка ВАК [1, 6, 7] и патент РФ [5].

Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы (92 наименования). Общий объем работы составляет 224 страницы, работа содержит 89 рисунков и 23 таблицы.

Основное содержание работы

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

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

В первом разделе формулируются требования к созданию подсистемы оперативной памяти перспективных СКСН, выполнение которых необходимо для комплексного решения проблемы "стены памяти".

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

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

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

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

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

Пятое требование - поддержка низкоуровневых интерфейсов GASNet и ARMCI, используемых в runtime-системах языков программирования UPC, CAF и других, которые используют модель PGAS. Модель PGAS является более перспективной в плане обеспечения высокой продуктивности программирования и возможной эффективности работы программ по сравнению с моделью передачи сообщений MPI. Параллельные процессы в модели PGAS взаимодействуют посредством односторонних коммуникаций через общую для них память, обладающую свойством видимого пользователем неоднородного по эффективности доступа к разным ее областям.

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

Во втором разделе первой главы рассматривается семейство суперкомпьютеров с мультитредовой архитектурой процессора Cray МТА-2 и Cray ХМТ (Eldorado). Мультитредовая архитектура позволяет выдавать большое количество независимых и одновременных обращений к памяти. Виртуальная память Cray ХМТ является сегментной, с возможностью распределения сегмента по всем узлам, присутствует скремблирование. Скремблирование (зашумление) любой последовательности адресов, следующих с постоянным шагом, позволяет перевести ее в последовательность адресов с равномерным случайным распределением. Это позволяет снизить конфликты обращений к вычислительным узлам и банкам памяти. Для эффективного взаимодействия параллельных процессов каждая 64-разрядная ячейка памяти имеет дополнительные теговые биты состояния.

Преимуществами организации глобально адресуемой общей памяти Cray ХМТ является простота, возможность организации мелкозернистого взаимодействия параллельных процессов при помощи теговых битов, а также возможность работы с сегментами большого объема без TLB-промахов. К недостаткам относятся: сегменты можно распределять только

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

В третьем и четвертом разделах первой главы рассматриваются суперкомпьютеры Cray XI и Cray BlackWidow (BW) с векторной архитектурой процессора. Главной особенностью виртуальной памяти Cray XI и Cray BW является двухуровневая организация с виртуальным адресом, состоящим из номера виртуального узла, номера страницы на этом виртуальном узле и смещения в странице. Эта особенность значительно упрощает реализацию глобально адресуемой памяти, что позволяет транслировать виртуальные адреса с высокой пропускной способностью. Недостаток Cray XI и Cray BW с точки зрения поддержки PGAS-языков

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

- зависимость от векторизуемости приложений. В Cray BW по сравнению с Cray XI ввели режим, эффективно поддерживающий хранение данных задачи на узлах с несмежными номерами, однако отказались от работы нескольких задач на одном узле.

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

В пятом разделе первой главы рассматривается суперкомпьютер Cray ТЗЕ. К его преимуществам относится децентрализованная организация управления памятью, так как сегментно-страничная организация глобально адресуемой памяти Cray ТЗЕ позволяет разделить вопросы защиты, распределения данных по узлам и размещения страниц на узлах. Универсальный механизм распределения данных обеспечивает аппаратную поддержку для реализации пользовательских способов распределения данных. Большое количество Е-регистров, при помощи которых происходит работа с удаленными узлами, позволяет обеспечить максимальную пропускную способность и толерантность к задержкам обращений в глобально адресуемую память. Низкие накладные расходы на синхронизацию процессов обеспечиваются в Cray ТЗЕ аппаратной поддержкой работы с очередями сообщений MQCW и барьерных операций. Недостатком Cray ТЗЕ является отсутствие возможности запускать задачу на узлах с не подряд идущими номерами.

В шестом разделе первой главы в качестве примера программно-аппаратной поддержки глобально адресуемой памяти рассматривается вариант реанимирования подхода Cray ТЗЕ и предлагается современный дешевый способ построения суперкомпьютера с глобально адресуемой общей памятью, суть которого состоит в соединении коммерческого процессора и маршрутизатора коммуникационной сети через Network Interface Controller (NIC), в котором реализуется минимальное управление обращениями в глобальную память. Отличие данного решения от Cray ТЗЕ заключается в упрощении процедуры трансляции адреса. По мнению авторов решения, вычислительные возможности современных процессоров превосходят возможности коммуникационных сетей, поэтому определением номера узла и подсчетом смещения внутри этого узла может заниматься процессор, выполняя, таким образом, алгоритм распределения. Недостаток данного конкретного решения заключается в отсутствии поддержки мелкозернистой синхронизации, недостатки подхода - в отсутствии комплексности решения, зависимости от существующей коммерческой аппаратуры.

Анализ показывает, что глобально адресуемая память ни одного из рассмотренных суперкомпьютеров полностью не удовлетворяет всем требованиям. При разработке архитектуры такой памяти в СКСН "Ангара" предпринята попытка выполнить все требования при помощи выработки комплексного решения, с учетом недостатков и преимуществ, выявленных при анализе.

Во второй главе описывается разработанная архитектура глобально адресуемой памяти, а также приводится общее описание СКСН "Ангара".

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

Суперкомпьютер "Ангара" содержит вычислительные узлы, соединенные коммуникационной сетью, оптимизированной для достижения большой суммарной пропускной способности при передаче коротких пакетов. В качестве вариантов реализации такой сети рассматриваются 4D- и 5Б-торы с адаптивной бездедлоковой передачей пакетов. Вычислительный узел (далее просто узел) суперкомпьютера "Ангара" содержит: многоядерный мультитредово-потоковый микропроцессор (вариант J7 или J10) с

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

В одном ядре микропроцессора может одновременно выполняться несколько задач. Каждой задаче ставится в соответствие один домен защиты, причем одна из задач ядра - обязательно операционная система.

Физическая и виртуальная память данных адресуется до байта, однако основным рабочим объектом памяти является 64-разрядное слово (ячейка), базовый адресуемый элемент памяти, выровненный по 8-байтовой границе.

Каждой 64-разрядной ячейке памяти поставлены в соответствие два внешних теговых бита состояния ячейки, один - это full/empty - бит (fe-бит), а другой extag-бит - который имеет единичное значение, если в младших трех разрядах соответствующей тегу ячейки в качестве тегового бита fvvd, trapO или trapl установлен хотя бы один разряд. Выполнение операций с памятью зависит от значения теговых битов состояния ячейки и от поля управления доступом из адреса, на этом построена низкоуровневая синхронизация при работе с памятью.

Например, рассмотрим доступ к адресуемой ячейке памяти в одном из режимов синхронизации Synchronize. Операция чтения в режиме Synchronize выполняется только для состояния full адресуемой ячейки памяти. Если к этой ячейке не подключены "треды-писатели" (см. далее), то микропроцессор сначала выполняет ожидание, то есть производится повторное выполнение соответствующей команды до тех пор, пока либо не выполнится условие выполнения команды, либо количество повторов этой, команды не превысит значение, установленное в специальном регистре. Повтор выполнения команды производится автоматически функциональным устройством LSU для работы с командами обращений в память без выдачи тредом дополнительных команд. Если количество повторов команды оказалось больше установленного значения в специальном регистре, то возбуждается исключительная ситуация. Обработка этой ситуации состоит в установке в адресуемой ячейке trapO-бита и организации привязанного к ней списка структур-ссылок на "треды-читатели" этой ячейки. Факт наличия этого списка распознается далее уже по выставленному trapO-биту. Активация тредов этого списка произойдет только после записи значения в эту ячейку. Операция записи в режиме Synchronize выполняется только для состояния empty адресуемой ячейки. Если же состояние этой ячейки full, то также производится сначала ожидание, которое может закончиться записью или установкой trapO-бита и подключением к ячейке списка тредов, но это уже будут "треды-писатели". В конечном итоге происходит успешная запись в ячейку и full/empty-бит ее состояния устанавливается равными full.

Физическое адресное пространство узла составляет 256 Гбайт. В системе допускается использовать до 32768 узлов, соответственно, максимальный объем адресуемой памяти - 8 Пбайт. Физический адрес состоит из номера узла, смещения в локальной памяти узла и поля управления доступом, в общей сложности 64 разряда.

Задача оперирует виртуальными адресами (VA) данных. VA содержит номер сегмента задачи, смещение в сегменте, а также служебную информацию. При помощи виртуальных V-сегментов и их свойств реализована защита данных задачи и их распределение по физической памяти узлов. Свойства V-сегмента описываются его дескриптором, который хранится в специальной таблице дескрипторов V-сегментов в памяти каждого узла, занятого задачей. Для ускорения доступа к таблице дескрипторов V-сегментов используется кэш дескрипторов (VTLB). Имеются два типа V-сегментов - обычные (размер от 128 байт до 256 Гбайт) и суперсегменты (размер от 128 Кбайт до 256 Тбайт). Суперсегменты введены для работы с данными очень большого объема как с единым целым, а также чтобы уменьшить промахи при обращении к VTLB.

Способ отображения V-сегментов на физическую память задается дескриптором V-сегмента. V-сегмент отображается на 2Р узлов со смежными номерами, начиная с узла с номером First Node Number (Р и First Node Number заданы в дескрипторе).

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

Распределение (отображение) на физические адреса может быть блочно-циклическим и блочным, в зависимости от поля Distribution Туре дескриптора V-сегмента. В случае блочного распределения размер блока z, отведенного в узле для данного сегмента, вычисляется как z = размер сегмента / 2Р - в каждом узле только один блок сегмента. При блочно-циклическом распределении сегмент циклически распределяется по узлам блоками размером В = 4DistributionType+3 64 байт до 25б Кбайт). Причем

сначала между N=2P узлами распределяются первые N блоков, затем -вторые N и т.д., в одном узле может быть несколько блоков сегмента.

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

доступу к банкам памяти.

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

При централизованном способе в каждом узле область данных сегмента начинается с физического адреса из поля Segment Base дескриптора V-сегмента. В этом случае VA транслируется сразу в физический адрес. Так как задача централизованного планирования физической памяти в узлах сложна, то введен децентрализованный способ.

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

Схема процесса трансляции VA в физический адрес или GVA изображена на рис. 1.

В отличие от V-сегментов, номера R-сегментов являются общими для всей системы. В каждом узле фрагмент R-сегмента образует локальную виртуальную память, состоящую из страниц размером по 16 Кбайт, 1 Мбайт, 64 Мбайт или 4 Гбайт. Размер страниц указан в дескрипторе V-сегмента и при трансляции переносится в GVA. GVA содержит достаточно информации для формирования физического адреса в целевом узле - для этого в этом узле остается только определить начальный адрес страницы R-сегмента, который хранится в дескрипторе страницы R-сегмента.

Дескрипторы страниц R-сегмента кэшируются в специальной кэшпамяти RPTLB. При промахе в RPTLB необходимо обратиться к таблице дескрипторов страниц R-сегмента в памяти узла. Ее адрес указан в дескрипторе R-сегмента. Хотя каждый R-сегмент имеет уникальный номер в пределах всей системы, но в узле, как правило, используется ограниченное число R-сегментов, поэтому для хранения их дескрипторов используется хешированная таблица дескрипторов R,-cerMeiiTOB RST (Real Segment Table) с разрешением конфликтов методом цепочек. Схема трансляции GVA в физический адрес на целевом узле изображена на рис. 2.

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

Организацией глобально адресуемой памяти выполняется первое требование: через логически единое адресное пространство возможен доступ

Дескриптор данных домена защиты

Виртуальный адрес УА

Рис. 1. Схема трансляции виртуального адреса в глобальный виртуальный или физический адреса в суперкомпьютере "Ангара".

I НбшрЙГТ Номер

| страницы | странице

Физический адрес

:±

Смещение в узле

Дескриптор страницы I Кашаьш адрес | I страницы [

Таблица страниц Я-сегмскга

Базовый адрес таблицы страниц

Размер таблицы с/урвниц

Таблица К>Т Я-сетментпв

Дескриптор Нчгегмеята

Дескриптор 11<егмеяг» Дескриптор Нчммента

Дескршпор I Дескриптор 1 И-ссгмента I Н-сегмеет'а |

Рис. 2. Схема трансляции глобального виртуального адреса в физический адрес в суперкомпьютере "Ангара".

к 8 Пбайт распределенной памяти.

V- и R- сегменты разработанной архитектуры глобально адресуемой памяти обеспечивают виртуализацию адресного пространства и высокогранулированную сегментную защиту по сравнению с организацией памяти в Cray BlackWidow. По сравнению с Cray ХМТ введенный уровень глобальных виртуальных адресов вводит возможность децентрализованного управления локальной памятью каждого из узлов за счет разделения вопросов защиты и отображения данных от вопросов их размещения в локальной памяти узлов, что вместе с введением страниц разного размера выполняет требование об экономном управлении памятью.

В глобально адресуемой памяти "Ангара" по сравнению с Cray ХМТ усилено управление отображением данных: при отображении на физическую память адресного пространства сегмента можно в дескрипторе этого сегмента задавать последовательность вычислительных узлов, в модулях памяти которых он может располагаться. Также при отображении на памяти выбранного множества вычислительных узлов можно использовать либо блочное, либо блочно-циклическое отображение. Оставлена возможность Cray ХМТ скремблирования номеров узлов, но появилась отдельная возможность скремблирования банков памяти. По аналогии с Cray ХМТ у каждой 64-разрядной ячейки памяти существуют дополнительные теговые биты, хорошо зарекомендовавшие себя для осуществления мелкозернистой синхронизации, что вместе с расширенным набором атомарных операций обеспечивает выполнение требования о мелкозернистой синхронизации параллельных процессов.

Для большей гибкости в СКСН "Ангара" по аналогии с Cray BlackWidow введена возможность использования для отображения данных сегмента задачи на не обязательно подряд идущую последовательность номеров узлов.

В третьей главе описывается параллельная программная имитационная потактовая модель СКСН "Ангара", а также разработанные блоки, имитирующие работу глобально адресуемой памяти в этой модели, необходимые для исследования возможностей применения разработанной архитектуры глобально адресуемой памяти при решении прикладных задач. Модель является параллельной программой, написанной на языке Charm++, позволяет моделировать СКСН "Ангара" в полном объеме и масштабируется по производительности до 256 двухпроцессорных (восьмиядерных) узлов суперкомпьютера МВС-ЮОК в МСЦ РАН.

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

отслеживания обращений к памяти. Из LSU виртуальный адрес обращения к памяти передается в блок MMU для трансляции. Если адресуемая память - это локальная память узла А, то запрос на выполнение передается в контроллер памяти EDI и далее во внекристальную DRAM-память. Если адресуемая память принадлежит другому узлу, то запрос передается сначала в блок MSU, а потом в N1, в котором аппаратно формируется короткий пакет с командой обращения к памяти, который через коммуникационную сеть передается в целевой узел В. В узле В команда обращения к памяти поступает через блоки N1 и MSU в блок MMU, в котором, если необходимо, происходит трансляция глобального виртуального адреса в физический, после чего выполняется обращение к EDI и DRAM-памяти узла В. Результат обращения возвращается через блоки MSU и N1 узла В и далее через коммуникационную сеть в узел А в обратном порядке.

Таблица 1. Задержки различных обращений к памяти в тактах процессора с учетом накладных расходов на трансляцию виртуальных адресов в тактах микропроцессоров J7 (500 МГц) и J10 (2 ГГц).

Вид адресации и вариант трансляции J7 J10

Обращение по физическому адресу в кэш данных 21 21

Обращение по физическому адресу в DRAM-пaмять (промах в кэш данных) 64 97

Обращение по виртуальному адресу в кэш данных 34 34

Обращение по виртуальному адресу в DRAM-пaмять 77 110

Обращение по виртуальному адресу в DRAM-пaмять с промахом в УТЬВ и RPTLB 271 370

Обращение по виртуальному адресу в DRAM-пaмять соседнего узла, расстояние 1 426 593

Обращение по виртуальному адресу в DRAM-пaмять узла на расстоянии 7 832 1789

Блок трансляции адресов, внутрикристальная сеть, кэш данных, внекристальная память, маршрутизатор сети и сетевые линки имеют реальные характеристики по задержкам и пропускной способности, их влияние отражено в табл. 1. В этой таблице приведены полученные на модели для вариантов микропроцессора J7 (500 МГц) и J10 (2 ГГц) и внекристальной DRAM памяти DDR2 (800 МГц) задержки обращений к памяти своего и удаленного узла при разных вариантах адресации и выполнении процессов

трансляции.

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

Исследования развиваемой реальной производительности были проведены на общепринятых тестах из пакета HPCChallenge с граничными значениями пространственно-временной локализации обращений к памяти: dgemm, HPL - умножение матриц и тест Linpack (лучшие значения временной и пространственной локализации); FFT - одномерное преобразование Фурье (хорошая временная, плохая пространственная локализация); STREAM - пересылка векторов (плохая временная, хорошая пространственная локализация); Random Access - тест нерегулярных обращений к памяти (худшие значения временной и пространственной локализации). В исследованиях также использовались тесты АРЕХ-МАР и PUT/GET.

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

Проведенные исследования показывают, что несмотря на задержки, вносимые блоком MMU при трансляции виртуального адреса, производительность однопроцессорных программ dgemm, STREAM Triad, FFT и RandomAccess, работающих по виртуальным адресам на небольшом числе тредов незначительно отличается от производительности программ, работающих по физическим адресам. При большом числе тредов выдается большое количество одновременных обращений в память, режимы работы по виртуальным и физическим адресам эквивалентны из-за толерантности мультитредового процессора к задержкам, причем это свойство верно даже при небольшом количестве каналов (конвейеров) трансляции адреса (1 для J7 и 2 для J10).

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

Istanbul (4xAMD8431), 16 тредов

"Ангара" J7,2 ядра по 64 треда

1001

100'

65536

Рис. 3. АРЕХ-поверхности платы с 4 процессорами AMD Istanbul и процессора "Ангара" J7.

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

Исследования возможной эффективности подсистемы памяти также были проведены с использованием синтетического теста АРЕХ-МАР. Тест АРЕХ-МАР строит зависимость характеристики доступа к памяти в зависимости от параметров пространственной (L) и временной (а) локализации. Полученные на этом тесте интегральные оценки в виде АРЕХ-поверхностей показывают резкое улучшение показателей эффективности доступа к памяти в СКСН "Ангара" для режимов плохой пространственно-временной локализации. АРЕХ-поверхность для одного узла имеет вид практически горизонтальной плоскости, а не "горки", характерной для коммерческих процессоров, см. рис. 3.

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

Второй этап исследований был связан с рассмотрением работы множества узлов.

АРЕХ-поверхности для многоузлового варианта теста АРЕХ-МАР представлены па рис. 4. Также, как и в одноузловом случае, видно резкое улучшение характеристик доступа к памяти в СКСН "Ангара" для режимов

256 узлов Cray X1

256 узлов "Ангара" J7

О DI

L

Рис. 4. АРЕХ-поверхности 256 процессоров Cray XI и "Ангара" J7.

плохой пространственно-временной локализации, причем даже в сравнении с суперкомпьютером с векторной архитектурой Cray XI. Таким образом, тест АРЕХ-МАР демонстрирует достижение основной цели разработки СКСН "Ангара" - эффективной работы с глобально адресуемой памятью большого объема с приблизительно равными показателями в разных режимах пространственно-временной локализации.

В табл. 2 представлены результаты выполнения выбранных тестов из пакета HPCChallenge и задачи BFS поиска вширь в графе, на самых мощных на октябрь 2010 года суперкомпьютерах и СКСН "Ангара". Тесты для СКСН "Ангара" написаны на языке ассемблера этой системы, а взаимодействие параллельных процессов производится командами считывания и записи из оперативной памяти. Тесты для остальных суперкомпьютеров написаны на языке С с использованием библиотеки MPI.

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

На DIS-задаче FFT реальная производительность (по отношению к пиковой) СКСН "Ангара" лучше примерно от 3 (J10) до 19 (.17) раз. Абсолютная производительность только для J10 превышает производительность Cray ХТ5. Для другой DIS-задачи BFS доступны результаты только для суперкомпьютера IBM BlueGene/L, и если приводить производительность к одному узлу, то СКСН "Ангара" лучше примерно от 14 (J7) до 63 (J10) раз. Таким образом, разработанная глобально адресуемая память позволяет развивать реальную производительность на DIS-задачах до 1-2 порядков большую, чем на существующих суперкомпьютерах.

Таблица 2. Сравнение суперкомпьютеров на тестах с разной локализацией обращений к памяти. ПС - пропускная способность, - умножение матриц, ® - используется 32768 узлов.

Система IBM BG/P IBM BG/L Cray XT5 Ангара 37 Ангара J10

Тактовая частота 0.85 0.7 2.6 0.5 2

микропроцессора, ГГц

Количество ядер (тредов в ядре) 4 1 6 2(64) 8 (128)

Пиковая производительность 13.6 5.6 62.4 4 128

микропроцессора, Гфлопс

ПС DRAM-памяти, Гбайт/с 5.6 13.6 12.8 25.6 204.8

Дуплексная ПС липка сети, 0.425 0.175 4.8 / 4/ 12/

Гбайт/с / тип сети (тор) / 3D / 3D 3D 4D 4D

Дуплексная ПС интерфейса 5.1 2.1 3.2 8 48

микропроцессора с сетью, Гбайт/с

Число используемых 32768 65536 32768 8192 4096

процессоров

HPL, Тфлопс 450.3 259.2 1533.7 24.8* 380.9*

(81%) (71%) (66%) (83%) (73%)

FFT, Гфлопс 5080 2311 10699 6140 15131

(0.9%) (0.6%) (0.5%) (19%) (3%)

RandomAccess, GUPS 117.13 35.47 37.69 150.7 602.9

BFS, Миллионов дуг в секунду - 7655« - 26675 63251

Тесты умножения матриц, FFT и BFS для СКСН "Ангара" имеют гетерогенную мультитредовую вычислительную модель. Использование распределенных в глобально адресуемой памяти данных сочетается в ней с локализацией данных в памяти узлов. Если изначальной (статической) локализации данных не хватает, то она обеспечивается подкачками, что выполняется специально выделенными в программе тредами. Тест BFS использует также локализацию вычислений при данных. Она осуществляется посредством команд запуска тредов на удаленных узлах и позволяет добиться рекордных результатов.

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

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

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

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

Рассмотрим требование о поддержке разработанной глобально адресуемой памятью реализаций низкоуровневых интерфейсов GASNet и ARMCI, а также языка PGAS-класса UPC. Анализ набора функций GASNet и ARMCI и их семантики показал, что низкоуровневые интерфейсы удобно реализуются с использованием большого количества тредов и глобальной адресации. Основу оценки составил стандартный PUT/GET-тест операций записи/чтения с памятью удаленного узла. Полученная для СКСН реальная пропускная способность особенно для коротких пакетов не достижима в системах на базе коммерчески доступных компонентов.

Реализация языка UPC для СКСН "Ангара" обладает преимуществами по сравнению с реализацией UPC, например, на Cray XI. Во-первых,

существует возможность эффективной трансляции указателей UPC на глобальную память в виртуальный адрес разработанной глобально адресуемой памяти. Во-вторых, для достижения высокой производительности на СКСН "Ангара" требуется распараллеливание программы на треды, что гибче и проще, чем векторизация программ, необходимая для достижения высокой производительности на Cray XI. В третьих, СКСН "Ангара" позволяет эффективно использовать короткие коммуникационные передачи, что позволит достигать высокой производительности при использовании удобных поэлементных обращений к памяти удаленных узлов. Глобально адресуемая память СКСН "Ангара" обладает всеми функциональными свойствами организации памяти Cray XI, что с учетом известного положительного опыта реализации UPC на Cray XI позволяет говорить о том, что разработанная глобально адресуемая память поддерживает реализацию языка UPC на СКСН "Ангара".

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

В заключении диссертационной работы перечисляются ее основные результаты.

Основные результаты работы

1. Разработана архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера.

2. Разработаны и исследованы блоки, имитирующие работу глобально адресуемой памяти в составе параллельной программной потактовой имитационной модели суперкомпьютера «Ангара».

3. Показано, что применение разработанной глобально адресуемой памяти в сочетании с другими возможностями мультитредово-потокового суперкомпьютера "Ангара" в сравнении с опубликованными данными по существующим суперкомпьютерам позволяет:

— повысить реальную производительность на задачах с интенсивным нерегулярным доступом к памяти до одного-двух порядков при совпадении реальной производительности на остальных задачах;

— использовать при получении высокой реальной производительности короткие односторонние коммуникационные передачи, при помощи которых проще создавать параллельные программы по сравнению с традиционным программированием с использованием MPI.

4. Продемонстрирована возможность использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования PGAS-класса на примере языка UPC.

Работы автора по теме диссертации

[1] Фролов A.C., Семенов A.C., Корж A.A., Эйсымонт Л.К. Программа создания перспективных суперкомпьютеров // Открытые системы. - 2007.

- №9. - С. 21-29.

[2] Семенов A.C. Распределенная общая память суперкомпьютера, предназначенного для решения задач большой размерности // Ломоносов -2007: XIV Международная конференция студентов, аспирантов и молодых ученых; секция "Вычислительная математика и кибернетика": Тезисы докладов. - М.: - Издательский отдел факультета ВМиК МГУ, МАКС Пресс, 2007. - С. 73.

[3] Семенов A.C., Эйсымонт Л.К. Параллельное умножение матриц на суперкомпьютере с мультитредово-потоковой архитектурой // Программные системы и инструменты. - М.: - Издательство факультета ВМиК МГУ, 2007.

- №8. - С. 106-117.

[4] Семенов A.C. Одномерное быстрое преобразование Фурье на суперкомпьютере с мультитредово-потоковой архитектурой // Параллельные вычислительные технологии (ПаВТ'2008): Труды международной научной конференции (Санкт-Петербург, 28 января - 1 февраля 2008 г.). -Челябинск: - Издательство ЮУрГУ, 2008. - С. 224-231.

[5] Патент РФ №2396592. Способ организации глобально-адресуемой общей памяти в многопроцессорной ЭВМ. Семенов A.C., Слуцкин А.И., Соколов A.A., Эйсымонт Л.К. 2008.

[6] Аверичева Д.Л., Семенов A.C., Фролов A.C. Поиск вширь в графе на суперкомпьютере с мультитредово-потоковой архитектурой // Информационные технологии. - М.: - Издательство "Новые технологии", 2009. - №7. - С. 7-12.

[7] Семенов A.C., Соколов A.A., Эйсымонт Л.К. Архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. - 2009. - №1. - С. 50-61.

[8] Моделирование российского суперкомпьютера "Ангара" на суперкомпьютере / Эйсымонт Л.К., Семенов A.C., Соколов A.A. [и dp.J // В сборнике "Суперкомпыотерные технологии в науке, образовании и промышленности" под редакцией: академика В.А. Садовничего, академика Г.И. Савина, чл.-корр. РАН Вл.В. Воеводина. - М.: Издательство Московского университета, 2009. - С. 145-150.

Тираж 100 экз. Отпечатано в Московском авиационном институте

(государственном техническом университете) г. Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4. http: //www.mai.ru/

Введение

Актуальность темы.

Цель и задачи работы.

Основные результаты работы.

Научная новизна работы

Практическая ценность работы.

Доклады и публикации.

1 Проблемы организации глобально адресуемой памяти суперкомпьютеров и обзор их решений

1.1 Требования к организации глобально адресуемой памяти

1.2 Методика разработки и исследования глобально адресуемой памяти мультитредовопотокового суперкомпьютера.

1.3 Архитектура глобально адресуемой памяти в серии суперкомпьютеров Тега МТА, Cray МТА

2, Cray ХМТ

1.4 Архитектура глобально адресуемой памяти суперкомпьютера Cray XI.

1.5 Архитектура глобально адресуемой памяти суперкомпьютера Cray BlackWidow.

1.6 Архитектура глобально адресуемой памяти суперкомпьютера Cray ТЗЕ.

1.7 Программ но-аппаратная поддержка глобально адресуемой памяти

1.8 Итоговый анализ суперкомпьютеров перед разработкой глобально адресуемой памяти мультитредово-потокового суперкомпьютера.

1.9 Выводы.

2 Глобально адресуемая память мультитредово-потокового суперкомпьютера

2.1 Общее описание суперкомпьютера "Ангара" и его глобально адресуемой памяти

2.2 Базовые адресуемые элементы памяти.

2.3 Команды обращения в память.

2.4 Физическая память.

2.5 Виртуальная память.

2.5.1 Уровень V-сегментов - защита и управление распределением по узлам.

2.5.2 Уровень R-сегментов - управление размещением данных внутри узлов.

2.6 Трансляция виртуальных номеров узлов в логические.

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

2.8 Выводы.

3 Имитационная модель мультитредово-потокового СКСН "Ангара"

3.1 Общее описание имитационной модели.

3.2 Моделирование выполнения команд работы с памятью.

3.3 Моделирование коммуникационной сети.

3.4 Моделирование блока MMU трансляции адресов.

3.5 Итоговые задержки обращений к памяти.

3.6 Выполнение имитационной модели на суперкомпьютере.

3.7 Выводы.

4 Исследование эффективности разработанной архитектуры глобально адресуемой памяти

4.1 Методика оценочного тестирования па основе тестов HPCChallenge и АРЕХ-поверхностей.

4.2 Эффективность реализации виртуальной памяти.

4.2.1 Оценка влияния ограничений аппаратной реализации виртуальной памяти на производительность суперкомпьютера.

4.2.2 Моделирование промахов при обращении к VTLB и RPTLB.

4.3 Оценка производительности суперкомпьютера при решении различных прикладных задач.

4.3.1 АРЕХ-МАР.

4.3.2 STREAM

4.3.3 RandomAccess.

4.3.4 FFT.

4.3.5 Умножение матриц.

4.3.6 Поиск вширь в графе.

4.3.7 Общий анализ производительности.

4.4 Оценка поддержки предложенной архитектурой памяти перспективных языков программирования на примере UPC.

4.4.1 Чтение-запись из удаленной памяти.

4.4.2 Оценка поддержки ARMCI.

4.4.3 Оценка поддержки GASNet.

4.4.4 Оценка поддержки языков PGAS на примере языка UPC.

4.5 Оценка функциональности глобально адресуемой памяти при решении задач

4.6 Выводы.

Актуальность темы

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

Главные работы по решению проблем низкой реальной производительности и низкой продуктивности программирования в настоящее время ведутся фирмами Cray (проект Cascade) и IBM (проект PERCS) с целью создания суперкомпьютеров стратегического назначения (СКСН) транспетафлопсного уровня реальной производительности с перспективной мультитредово-векторной архитектурой и глобально адресуемой памятью. Эти проекты ведутся в рамках крупной американской программы DARPA HPCS, начатой в 2002 году. Всего лишь с задержкой в 4 года к работам по созданию СКСН такого же типа приступили ведущие фирмы и государственные организации Японии (проект Keisoku-Keisan-Ki) и Китая (проект "программа 863"). При этом наиболее близок к основным решениям проектов программы DARPA HPCS проект создания китайской перспективной СКСН, который предполагает создание собственного массово-мультитредового микропроцессора и собственной специальной коммуникационной сети с большой пропускной способностью и малым диаметром.

В России работа по перспективной СКСН ведутся с 2000 года в рамках разных НИОКР, а с 2005 года - в рамках проекта "Ангара" по созданию мультитредово-потокового суперкомпьютера с глобально адресуемой памятью.

Главной задачей, решаемой в этих проектах, является преодоление так называемой проблемы «стены памяти». Суть этой проблемы состоит в сложившемся на сегодняшний день значительном отставании (сотни раз) времени выполнения операций с оперативной памятью от времени выполнения арифметико-логических операций в процессоре. Эта проблема обусловлена особенностями развития микроэлсктронной компонентой базы — задержка обращения к внекристальной DRAM-памяти с учетом промахов в кэш-память дескрипторов сегментов и/или страниц может составлять 300-500 тактов процессора. Задержка обращения к коммуникационной сети может составлять десятки тысяч тактов процессора. Значимость этой проблемы усилена качественными изменениями требований перспективных прикладных программ - увеличение необходимого задаче логически неделимого объема памяти, рост доли команд обращений к памяти, нарастающее ухудшение пространственно-врсмснной локализации обращений к памяти (нерегулярность). Следует отметить важность приложений с интенсивной нерегулярной работой с памятью (сокращенно DIS-задачн), особенно в областях обеспечения национальной безопасности.

Наличие проблемы ''стены памяти" приводит к тому, что на DIS-задачах пз-за простоев процессора при ожидании данных из памяти реальная производительность (sustained performance) СКСН может деградировать до 5-0.1 % от пиковой производительности. Эта проблема также не позволяет существенно масштабировать реальную производительность при увеличении количества процессоров, используемых при выполнении задачи. В результате многие DIS-задачи практически невозможно решить за приемлемое время на су и чествующих суперкомпьютерах.

Решение проблемы "стены памяти" позволит реально работать с глобально адресуемой памятью и перейти на одностороннее взаимодействие параллельных процессов, что важно для эффективного выполнения программ на языках нового поколения класса PGAS (Partitioned Global Address Space - языки UPC, CAF), а также для перспективных языков с иерархическим описанием параллельных программ (языки Chapel, Х10 и Fortress). В целом, это позволит повысить продуктивность параллельного программирования, по оценкам мировых экспертов - в 10-40 раз.

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

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

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

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

Цель и задачи работы

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

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

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

3. Исследование возможностей использования разработанной архитектуры глобально адресуемой памяти в сочетании с другими особенностями суперкомпьютера "Ангара" для достижения высокой реальной производительности.

4. Исследование возможности использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования РСАЭ-класса.

Основные результаты, выносимые на защиту

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

1. Разработана архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера.

2. Разработаны и исследованы блоки, имитирующие работу глобально адресуемой памяти в составе параллельной программной потактовой имитационной модели суперкомпьютера «Ангара».

3. Показано, что применение разработанной глобально адресуемой памяти в сочетании с другими возможностями мультитредово-потокового суперкомпьютера "Ангара" в сравнении с опубликованными данными по существующим суперкомпьютерам позволяет: повысить реальную производительность на задачах с интенсивным нерегулярным доступом к памяти до одного-двух порядков при совпадении реальной производительности на остальных задачах; использовать при получении высокой реальной производительности короткие односторонние коммуникационные передачи, при помощи которых проще создавать параллельные программы по сравнению с традиционным программированием с использованием MPI.

4. Продемонстрирована возможность использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования PGAS-класса на примере языка UPC.

Научная новизна работы

Полученные результаты являются новыми. Разработанная архитектура защищена патентом Российской Федерации № 2396592 "Способ организации глобально адресуемой общей памяти в многопроцессорной ЭВМ" от 21 октября 2008 года и обладает следующими основными свойствами: имеет сегмеитпо-страничную организацию с двухуровневой виртуализацией адресов и широким диапазоном размеров сегментов и страниц, а также возможностью работы с сегментами сверхбольшого размера; обладает расширенными возможностями отображения виртуальной памяти на физическую за счет использования блочного и блочно-циклического методов, а также зашумления адресов; использует теги состояния в ячейках памяти и теги доступа в адресах, что позволяет выполнять мелкозернистую синхронизацию непосредственно на ячейках памяти без участия процессора; включает набор атомарных операций для односторонних взаимодействий параллельных процессов, векторных операций чтения-записи, операций синхронизации обращений к памяти.

Практическая ценность работы

Разработанная архитектура глобально адресуемой памяти является одним из основных архитектурных решений, принятых при разработке мультитредово-потокового суперкомпьютера "Ангара", которая ведется в ОАО "НИЦЭВТ" с 2006 года.

Программная параллельная имитационная потактовая модель мультитредово-потокового суперкомпьютера используется в ОАО "НИЦЭВТ" для отработки принципов работы суперкомпьютера "Ангара" и вариантов их аппаратной реализации, создания и отработки системного программного обеспечения, построения моделей вычислений прикладных задач.

Практическую ценность работы подтверждает акт №83/6-4328 от 26.10.2010 о внедрении архитектры глобально адресуемой памяти мультитредово-потокового суперкомпьютера в ОАО "НИЦЭВТ".

Полученные результаты исследования возможностей реализации средств продуктивного параллельного программирования используются при реализации интерфейсов и языков РСАБ-класса для суперкомпьютера

Ангара" и суперкомпьютеров поколения СКИФ-4.

Доклады и публикации

Основные положения работы докладывались на второй международной конференции "Параллельные вычислительные технологии" (ПАВТ-2008), на XIV международной конференции студентов, аспирантов и молодых ученых Ломоносов-2007, на научных семинарах в НИВЦ МГУ под руководством член-корр. д.ф.-м. н. Вл. В. Воеводина, в ОАО "НИЦЭВТ" под руководством к. ф.-м. н. Л. К. Эйсымонта, а также в ИПМ РАН (направление -"Программирование").

По материалам диссертации опубликовано восемь работ [1, 2, 3, 4, 5, б, 7, 8], в том числе три [1, 6, 7] из списка ВАК и патент РФ [5].

Краткое содержание работы

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

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

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

В четвертой главе приводятся результаты проведенных автором исследований на имитационной модели. С помощью тестов пакета НРС-ОтПенце на одном узле исследуются вопросы влияния накладных расходов на трансляцию адреса на производительность программ. Затем на мультипроцессорных вариантах тех же тестов производится общая оценка производительности системы и оценка функционального богатства и гибкости возможностей глобально адресуемой памяти.

В заключении перечисляются основные результаты работы.

Автор выражает искреннюю и глубокую благодарность руководителю работы к.ф.-м. н. Леониду Константиновичу Эйсымонту, а также коллегам по совместной работе - Александру Фролову, Алексею Соколову, Дмитрию Макагону, Дарье Аверичевой, Валерию Горохову и Александру Румянцеву.

Эти выводы подтверждают выполнение требования об эффективности доступа к памяти в разных режимах пространственно-временной локализации

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

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

В качестве языка с моделью PGAS взят язык UPC. Реализация языка UPC для СКСН "Ангара" обладает преимуществами по сравнению с реализацией UPC, например, на Cray XI. Во-первых, преимущество связано с наличием сегментов и суперсегментов, которые позволяют более гибкую и гранулированную работу с отдельными объектами в "Ангаре" по сравнению с Cray XI. Также, как и в Cray XI, для СКСН "Ангара" возможна эффективная трансляция указателей UPC на глобальную память в виртуальный адрес глобально адресуемой памяти. Во-вторых, для достижения высокой производительности на СКСН "Ангара" требуется распараллеливание программы на треды, что гибче и проще, чем векторизация программ, необходимая для достижения высокой производительности на Cray XI. Глобально адресуемая память СКСН "Ангара" обладает всеми функциональными свойствами организации памяти Cray XI, что с учетом известного положительного опыта реализации языков PGAS на Cray XI позволяет говорить о том, что разработанная глобально адресуемая память поддерживает удобную и эффективную реализацию PGAS-языков на СКСН "Ангара".

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

Заключение

В диссертационной работе получены следующие основные результаты:

1. Разработана архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера.

2. Разработаны и исследованы блоки, имитирующие работу глобально адресуемой памяти в составе параллельной программной потактовой имитационной модели суперкомпьютера «Ангара».

3. Показано, что применение разработанной глобально адресуемой памяти в сочетании с другими возможностями мультитредово-потокового суперкомпьютера "Ангара" в сравнении с опубликованными данными по существующим суперкомпьютерам позволяет: повысить реальную производительность на задачах с интенсивным нерегулярным доступом к памяти до одного-двух порядков при совпадении реальной производительности на остальных задачах; использовать при получении высокой реальной производительности короткие односторонние коммуникационные передачи, при помощи которых проще создавать параллельные программы по сравнению с традиционным программированием с использованием MPI.

4. Продемонстрирована возможность использования разработанной архитектуры глобально адресуемой памяти при реализации перспективных языков параллельного программирования PGAS-класса на примере языка UPC.

1. Фролов A.C., Семенов A.C., Корснс A.A., Эйсымонт J1.K. Программа создания перспективных суперкомпьютеров // Открытые системы. - 2007. - №9. - С. 21-29.

2. URL: http://www.osp.ru/os/2007/09/4566841/ (дата обращения: 15.06.2010).

3. Семенов A.C., Эйсымонт Л.К. Параллельное умножение матриц на суперкомпьютере с мультитредово-потоковой архитектурой // Программные системы и инструменты. М.: - Издательство факультета ВМиК МГУ, 2007. - №8. - С. 106-117.

4. URL: http: //omega. sp. susu. ас. ru/books/conf erence/PaVT2008/ papers/fullpapers/024.pdf (дата обращения: 21.06.2010).

5. Патент РФ №2396592. Способ организации глобально-адресуемой общей памяти в многопроцессорной ЭВМ. Семенов A.C., Слуцкин A.PL, Соколов A.A., Эйсымонт JI.K. 2008.

6. Аверичева Д.Л., Семенов A.C., Фролов A.C. Поиск вширь в графе па суперкомпьютере с мультитредово-потоковой архитектурой // Информационные технологии. М.: - Издательство "Новые технологии", 2009. - Ж7. - С. 7-12.

7. Семенов A.C., Соколов A.A., Эйсымонт Л.К. Архитектура глобально адресуемой памяти мультитрсдово-потокового суперкомпьютера // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес.- 2009. №1. - С. 50-61.

8. URL: http://www.electronics.ru/pdf/l2009/1962.pdf (дата обращения: 21.06.2010).

9. DARPA's HPCS Program: History, Models, Tools, Languages / Dongarra J., Graybill R., Harrod W. et al.J // Advances in Computers.- 2008. Vol. 72. - P. 1-100.

10. URL: http://netlib.org/utk/people/JackDongarra/PAPERS/adv-comp-darpa-08.pdf (дата обращения: 14.06.2010).10j Ubiquitous High Performance Computing (OHPC). DARPA-BAA-10-37, 2010.11J Omnipresent High Performance Computing (OHPC). DARPA-BAA-10-78, 2010.

11. URL: http://www.darpa.mil/tcto/docs/DARPAOHPCBAA-10-78.pdf (дата обращения: 21.10.2010).

12. Слуцкин А.И., Эйсымонт JI.K. Российский суперкомпьютер с глобально адресуемой памятью // Открытые системы. 2007. - №9.- С. 42-51.

13. URL: http://www.osp.ru/os/2007/09/4569294/ (дата обращения: 15.06.2010).

14. Митрофанов В.В., Слуцкин А.И., Эйсымонт Л.К. Суперкомпьютерные технологии для стратегически важных задач // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. 2008. - №7. - С. 66-79. URL: http://www.electronics.ru/pdf/72008/1923.pdf (дата обращения: 15.06.2010).

15. UPC Language Specifications, vl.2. Lawrence Berkeley National Lab Tech Report LBNL-59208, 2005.

16. URL: http://www.gwu.edu/~upc/docs/upcspecsl-2.pdf (дата обращения: 25.06.2010).

17. Numrich R., Reid J. Co-Array Fortran for Parallel Programming // SIGPLAN Fortran Forum. New York, NY, USA: ACM, 1998. - Vol. 17, N. 2. - P. 1-31.

18. URL: http://www.cs.ucla.edu/~palsberg/course/cs239/papers/ numrich.pdf (дата обращения: 14.06.2010).

19. Numrich R., Reid J. Co-Arrays in the Next Fortran Standard // SIGPLAN Fortran Forum. New York, NY, USA: ACM, 2005. - V. 24.- N. 2. P. 4-17.

20. URL: ftp://ftp.nag.co.uk/sc22wg5/N1701-N1750/N1724.pdf (дата обращения: 14.06.2010).

21. Cray XI Evaluation Status Report / Dunigan Т., Oliker L., Vetter J. et al.J / Oak Ridge National Laboratory, ORNL/TM-2004/13, 2004. URL: http://www.netlib.org/utk/people/JackDongarra/PAPERS/ CRAYEvaluation.pdf (дата обращения: 14.06.2010).

22. Nishtala R., Hargrove P., Bonachea D., Yelick K. Scaling Communication-Intensive Applications on BlueGene/P Using One-Sided Communication and Overlap // Proceedings of the 23rd International

23. Parallel and Distributed Processing Symposium. Rome, Italy, 2009. URL: http://gasnet.cs.berkeley.edu/nishtala-upc-bgp-final.pdf (дата обращения: 17.06.2010).

24. Bader D., Feo J. Advanced Scientific Computing Research: Delivering Computing for the Frontiers of Science. Faciilities Division Strategic Plan for High Performance Computing Resources. Technical Report, 2007.

25. URL: http://www.er.doe.gov/ascr/About/

26. ASCRstrategicplan073004final.pdf (дата обращения: 08.06.2010).

27. ARMCI Webpage. Электронный ресурс]. URL: http://www.emsl. pnl.gov/docs/parsoft/armci/ (дата обращения: 08.06.2010).

28. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1. 90.3656&rep=repl&type=pdf (дата обращения: 17.06.2010).

29. Abts D., Thompson J., Schwoerer G. Architecture Support for Mitigating DRAM Soft Errors in Large-Scale Supercomputers / Cray Inc., 2007. URL: http://selse3.selse.org/Papers/20AbtsP.pdf (дата обращения: 08.06.2010).

30. Cray BlackWidow: a Highly Scalable Vector Multiprocessor / Abts D., Bataineh A., Scott S. et al.J // Proceedings of the 2007 ACM/IEEE Conference on Supercomputing. New York, NY, USA: ACM, 2007. - P. 1-12.

31. URL: http://sc07.supercomputing.org/schedule/pdf/pap392.pdf (дата обращения: 21.06.2010).

32. Cray/MTA Principles of Operation / Cray Inc., 2005.

33. Feo J., Harper D., Kahan S., Konecny P. Eldorado // Proceedings of the 2nd Conference on Computing Frontiers. New York, NY, USA: ACM, 2005. - P. 28-34.

34. URL: www-csag.ucsd.edu/teaching/cse294/20050711-eldorado.docдата обращения: 14.06.2010).

35. Konecny P. Introducing the Cray XMT / Cray Inc., 2007.

36. URL: http://www.nccs.gov/wp-content/uploads/2007/08/konecny paper.pdf (дата обращения: 15.06.2010).

37. Тега principles of operation / National Partnership for Advanced Computational Infrastructure: Archives, Tera Computer Company, 1998.

38. Characterizing Applications on the Cray MTA-2 Multithreading Architecture / Alain S., Roth P., Vetter J. et al.J // Proceedings of CUG Conference. 2006.

39. URL: http://ft.ornl.gov/pubs-archive/2006-05cug06mta2.pdfдата обращения: 14.06.2010).

40. Early Experience with Scientific Programs on the Cray MTA-2 / Anderson W., Hess D., Briggs P., Khoklov A. et al.J // Proceedings of the 2003 ACM/IEEE Conference он Supercomputing. Phoenix, AZ, USA, 2003.

41. URL: http://www.sc-conference.org/sc2003/paperpdfs/pap271.pdf (дата обращения: 08.06.2010).

42. Bokhari S., Sauer J. Sequence Alignment on the Cray MTA-2 // Proceedings of the 17th International Symposium on Parallel and Distributed Processing. Washington, DC, USA: IEEE Computer Society, 2003. -P. 152.1.

43. Bader D., Madduri K. Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2 // Proceedings of the 2006 International Conference on Parallel Processing, 2006. -P. 523-530.

44. URL: http://www.cc.gatech.edu/~bader/papers/

45. MultithreadedBFS-ICPP2006.pdf (дата обращения: 14.06.2010).

46. Cieslewicz J., Berry J., Hendrickson В., Ross K. Unlocking Parallelism in Database Operations: Insights from a Massively Multithreaded Architecture. Technical Report SAND 2005-7065C / Sandia National Laboratories, 2005.

47. Cray XMT Brings New Energy to High-Performance Computing / Chavarria D., Nieplocha J., Scherrer C. et al.] // SciDAC Review: Fall, 2008. P. 36-41.

48. URL: http ://cass-mt.pnl.gov/docs/pubs/crayscidacrevfall08. pdf (дата обращения: 08.06.2010).

49. Kahan S., Копеспу Р. "МАМА!": a Memory Allocator for Multithreaded Architectures // Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York, NY, USA: ACM, 2006. - P. 178-186.

50. US Patent 6922766B2. Remote Translation Mechanism for a Multinode System. Scott S. 2004.

51. URL: http ://www.google.com/patents/download/6922766Remote translationmechanismfor.pdf?id=SOYUAAAAEBAJ&output=pdf&sig= ACfU3U0K2LXjySoiSDBQ3ElFk9I-iEf6A&source=gbsoverviewr&cad=0 (дата обращения: 17.06.2010).

52. Cray Assembly Language (CAL) for Cray XI Systems Reference Manual, version 1.2 / Cray Corporation, 2003.

53. URL: http ://docs.cray.com/books/S-2314-51/S-2314-51-manual.pdf (дата обращения: 14.06.2010).

54. Bell С., Chen W., Bonachea D., Yelick K. Evaluating Support for Global Address Space Languages on the Cray XI // Proceedings of the International Conference on Superconiputing. New York, NY, USA: ACM, 2004. - P. 184-195.

55. URL: http://upc.lbl.gov/publications/xl-gas--ics04.pdf (дата обращения: 14.06.2010).

56. Dunigan T., Vetter J., White III JWorley P. Performance Evaluation of the Cray XI Distributed Shared-Memory Architecture // IEEE Micro. Los Alarnitos, CA, USA: IEEE Computer Society Press, 2005. - Vol. 25, N. 1. - P. 30-40.

57. URL: http://www.csm.ornl.gov/~dunigan/hoti04.pdf (дата обращения: 14.06.2010).

58. El-Ghazawi Т., Contonnet F., Yao Y., Vetter J. Evaluation of UPC on the Cray XI // Proceedings of the 47th Cray User Group Conference.- 2005.

59. URL: http://www.gwu.edu/~upc/publications/cug05.pdf (дата обращения: 25.06.2010).

60. ORNL Cray XI Evaluation Status Report. Technical Report ORNL/TM-2004/13 / Agarwal P., Dongarra J., Dunigan T. et al / Oak Ridge National Laboratory, 2004.

61. URL: http://icl.cs.utk.edu/newspub/submissions/

62. CRAYEvaluation.pdf (дата обращения: 17.06.2010).

63. Shmerri Programming Manual / Quadrics Supercomputing World Ltd., 2001.

64. URL: http://staff.psc.edu/oneal/compaq/ShmemMan.pdf (дата обращения: 22.09.2010).

65. Scott S., Abts D., Kim J., Dally W. The BlackWidow High-Radix Clos Network // ACM SIGARCH Computer Architecture News. New York, NY, USA: ACM, 2006. - Vol. 34, N. 2. - P. 16-28.

66. URL: http://cva.Stanford.edu/publications/2006/ISCAYARC.pdf (дата обращения: 21.06.2010).

67. Cray XT5h 1.0 Software Release Overview S-2475-10 / Cray Corporation, 2008.

68. Scott S. Synchronization and Communication in the T3E Multiprocessor // Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems.- New York, NY, USA: ACM, 1996. P. 26-36.

69. URL: http://pages.cs.wise.edu/~markhill/Misc/asplos96t3e comm.pdf (дата обращения: 17.06.2010).

70. Anderson E., Brooks J., Grassl C., Scott S. Performance of the Cray T3E Multiprocessor // Proceedings of the 1997 ACM/IEEE Conference on

71. Supercomputing. New York, NY, USA: ACM, 1997. - P. 1-17.

72. URL: http://userweb.es.utexas.edu/users/dburger/teaching/cs395t-s08/papers/8t3e.pdf (дата обращения: 17.06.2010).

73. US Patent 5835925. Using External Registers to Extend Memory-Reference Capabilities of a Microprocessor. Fromm E. 1998.

74. URL: http://www.google.com/patents/download/5835925Using externalregisterstoexte.pdf?id=nIMYAAAAEBAJ&output=pdf&sig= ACfU3U01ob0mDGU2XSfmT4vdUwDfHB5vQ&source=gbsoverviewr&cad=0 (дата обращения: 17.06.2010).

75. Alpha 21164 Microprocessor Hardware Reference Manual / Digital Eqiopment Corporation, 1995.

76. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0. Электронный ресурс]. URL: http:// hpff .rice.edu/versions/hpf2/hpf-v20/index.html (дата обращения: 15.06.2010).

77. URL: http://sc07.supercomputing.org/schedule/pdf/pap282.pdf (дата обращения: 25.06.2010).

78. Underwood К., Levenhagen M., Rodrigues A. Simulating Red Storm: Challenges and Successes in Building a System Simulation // International Parallel and Distributed Processing Symposium. 2007.

79. URL: https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/rs-sim.pdfдата обращения: 25.06.2010).

80. The Adaptive Bubble Router / Puente V., Izu C., Beivide R. et al./ // Journal of Parallel Distributed Computing. Orlando, FL, USA: Academic Press, Inc., 2001. - Vol. 61, N. 9. - P. 1180-1208.

81. URL: http://www.ate.unican.es/investigacion/publicaciones/ publicacionesf iles/publ12.pdf (дата обращения: 17.06.2010).

82. US Patent 7117330. Synchronization Techniques in a Multithreaded Environment. Alverson G., Callahan C., Kahan S. et al.]. 2003.

83. URL: http://www.google.com/patents/download/7117330

84. Synchronizationtechniquesina.pdf?id=VvN6AAAAEBAJ&output= pdf&sig=ACfU3U2aWeijzP61UrGP-aqXVsj5AuliAg&source=gbs overviewr&cad=0 (дата обращения: 08.06.2010).

85. Cell Broadband Engine Programming Handbook / IBM Corporation, 2006.

86. Kale L., Krishnan S. Charm++: Parallel Programming with Message-Driven Objects // Parallel Programming using C-H- / G. Wilson, P. Lu.- Cambridge, Mass.: MIT Press, 1996. P. 175-213.

87. Performance Modeling and Programming Environments for Petaflops Computers and the Blue Gene Machine / Kale L., Adve S., Padua D. etal.J // 18th International Parallel and Distributed Processing Symposium, 2004.

88. DRAMSim2. University of Maryland. Электронный ресурс]. URL: http://www.ece.urad.edu/dramsim (дата обращения: 21.09.2010).

89. TN-47-02 DDR2 Technical Note / Micron, 2005.

90. Top500. Электронный ресурс]. URL: http://www.top500.org (дата обращения: 25.06.2010).

91. Dongarra J., Luszczek PPetitet A. Linpack Benchmark: Past, Present, Future // Concurrency and Computation: Practice and Experience, 2003. Vol. 15. - P. 1-18.

92. URL: http://www.netlib.org/utk/people/JackDongarra/PAPERS/ hplpaper.pdf (дата обращения: 14.06.2010).

93. HPC Challenge Benchmarks. Электронный ресурс]. URL: http:// icl.cs.utk.edu/hpcc (дата обращения: 11.06.2010).

94. Dongarra J. , Luszczek P. Introduction to the HPCChallenge Benchmark Suite. Technical Report UT-CS-05-544 / University of Tennessee, 2005. URL: http://icl.cs.utk.edu/proj ectsfiles/hpcc/pubs/ hpcc-challenge-benchmark05.pdf (дата обращения: 14.06.2010).

95. Shan H., Strohmaier E. Apex-Map: A Global Data Access Benchmark to Analyze HPC Systems and Parallel Programming Paradigms // Proceedings of the 2005 ACM/IEEE Conference on Supercomputing. Washington, DC, USA: IEEE Computer Society, 2005.

96. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1. 123.5567&rep=repl&type=pdf (дата обращения: 25.06.2010).

97. Shan H., Strohmaier E. Performance Characteristics of the Cray XI and their Implications for Application Performance Tuning // Proceedings of the 18th Annual International Conference on Supercomputing. New York, NY, USA: ACM, 2004. - P. 175-183.

98. URL: https://ftg.lbl.gov/ApeX/ics04.pdf (дата обращения: 25.06.2010).

99. Weinberg J., McCracken M., Strohmaier E., Snavely A. Quantifying1.cality In The Memory Access Patterns of HPC Applications // Proceedings of the 2005 ACM/IEEE Conference on Supercomputing. Washington, DC, USA: IEEE Computer Society, 2005.

100. URL: http://www.sdsc.edu/pmac/publications/pubs/weinberg051ocality.pdf (дата обращения: 25.06.2010).

101. Волков Д., Фролов А. Оценка быстродействия нерегулярного доступа к памяти // Открытые системы. 2008. - №1. - С. 15-19. URL: http://www.osp.ru/os/2008/01/4836914/ (дата обращения: 14.06.2010).

102. Cooley J., Tukey J. An Algorithm For The Machine Calculation of Complex Fourier Series // Mathematics of Computation. 1965. - P. 297301.

103. URL: http://www.amath.Washington.edu/~narc/win08/papers/cooley-tukey.pdf (дата обращения: 14.06.2010).

104. Chen L., Ни ZLin J., Gao G. Optimizing Fast Fourier Transform on a Multi-core Architecture // Proceedings of the IEEE International Parallel and Distributed Processing Symposium, 2007. P. 1-8.

105. URL: http://www.capsl.udel.edu/pub/doc/papers/P0HLL2007-L0NG. pdf (дата обращения: 15.06.2010).

106. Krishnan M., Nieplocha J. SRUMMA: A Matrix Multiplication Algorithm Suitable for Clusters and Scalable Shared Memory Systems // Proceedings of the 18th International Parallel and Distributed Processing Symposium. 2004. - Vol. 1. - P. 70b.

107. URL: http://hpc.pnl.gov/proj ects/sruraraa/srumma-ipdps04.pdf (дата обращения: 17.06.2010).

108. Krishnan M., Nieplocha J. Optimizing Performance on Linux Clusters Using Advanced Communication Protocols: Achieving Over 10 Teraflops on a 8.6 Teraflops Linpack-Rated Linux Cluster / Advanced Computing Technology Laboratory, 2005.

109. URL: http://hpc.pnl.gov/projects/srumma/lci.pdf (дата обращения: 17.06.2010).74J HPCS SSCA2 Graph Analysis Benchmark Specifications v2.1. / Bader D., Feo J., Koester D. et al.J. 2006.

110. URL: http://www.graphanalysis.org/benchmark/HPCS-SSCA2

111. Graph-Theoryv2.1. pdf (дата обращения: 14.06.2010).

112. Bader D., Cong G., Feo J. On the Architectural Requirements for Efficient Execution of Graph Algorithms // Proceedings of the 2005 International Conference on Parallel Processing. Washington, DC, USA: IEEE Computer Society, 2005. - P. 547-556.

113. URL: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid= 4657C87EB37FF0692213B2178427CC07?doi=10.1.1.124.318&rep= repl&type=pdf (дата обращения: 14.06.2010).

114. Lumsdaine A., Gregor D., Hendrickson В., Berry J. Challenges in Parallel Graph Processing // Parallel Processing Letters. 2007. - Vol. 17, N. 1. - P. 5-20.

115. URL: http://www.sandia.gov/"bahendr/papers/graphs-and-machines.pdf (дата обращения: 15.06.2010).

116. Villa О., Scarpazza D., Petrini F., Peinador J. Challenges in Mapping Graph Exploration Algorithms on Advanced Multi-core Processors. // Proceedings of the 21st International Parallel and Distributed Processing Symposium. 2007. - P. 1-10.

117. URL: http://hpc.pnl.gov/people/fabrizio/papers/ipdps07-graphs. pdf (дата обращения: 25.06.2010).

118. Agariual V., Petrini F., Pasetto D., Bader D. Scalable Graph Exploration on Multicore Processors // Proceedings of the 2010 ACM/IEEE Supercomputing Conference (SC10) New Orleans, LA, 2010.

119. URL: http://www.cc.gatech.edu/~bader/papers/

120. ScalableGraphMulticore-SC10.pdf (дата обращения: 14.10.2010).

121. BO. Global Arrays Homepage. Электронный ресурс]. URL: http:// www.emsl.pnl.gov/docs/global (дата обращения: 21.10.2010).

122. Evaluation of Remote Memory Access Communication on the Cray ХТЗ / Tipparaju VKot A., Nieplocha J. et al.j // Proceedings of the 21th International Parallel and Distributed Processing Symposium. Long Beach, California, USA, 2007. - P. 1-7.

123. URL: http://crtc.wm.edu/papers/conf75.pdf (дата обращения: 17.06.2010).

124. Kißpnei^ee M.B., Мошкин Д.В., Полунин М.А., Эйсымонт Л.К. Суперкластеры между прошлым и будущим // Открытые системы. - 2008. - №8. - С. 40-47.

125. URL: http://www.osp.ru/os/2008/08/5661383/ (дата обращения: 15.06.2010).

126. Bonachea D. GASNet Specification, vl.l. Technical Report CSD-02-1207. / UC Berkeley, 2002.

127. URL: http://digitalassets.1ib.berkeley.edu/techreports/ucb/ text/CSD-02-1207.pdf (дата обращения: 15.06.2010).

128. Lurnetta S. Culler D. Managing Concurrent Access for Shared Memory Active Messages // Proceedings of the 12th International Parallel Processing Symposium. Washington, DC, USA: IEEE Computer Society, 1998.

129. URL: http://users.crhc.illinois.edu/steve/papers/ipps98.pdf (дата обращения: 15.06.2010).

130. Introduction to UPC and Language Specification. CCS-TR-99-157 / Carlson W., Draper J., Culler D., Yelick K. et al.J // IDA Center for Computing Sciences, 1999.

131. URL: http://upc.lbl.gov/publications/upctr.pdf (дата обращения: 25.06.2010).

132. The Berkley UPC Compiler. Электронный ресурс]. URL: http:// upc.lbl.gov (дата обращения: 25.06.2010).

133. GCC UPC homepage. Электронный ресурс]. URL: http://www. intrepid.com (дата обращения: 25.06.2010).

134. IBM XL UPC compiler. Электронный ресурс]. URL: http ://www. alphaworks.ibm.com/tech/upccompiler (дата обращения: 25.06.2010).

135. HP UPC compiler homepage. Электронный ресурс]. URL: h30097. www3.hp.com/upc (дата обращения: 25.06.2010).

136. URL: http ://www.gwu.edu/~upc/publications/IPDPSupc04.pdfдата обращения: 14.06.2010).

137. URL: http://www.gwu.edu/~upc/publications/ipdps05.pdf (дата обращения: 14.06.2010).