Введение в принципы функционирования и применения современных мультиядерных архитектур (на примере Intel Xeon Phi)

Введение в принципы функционирования и применения современных мультиядерных архитектур (на примере Intel Xeon Phi)





ФИНТУИТ
  / НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

С.ИНТУ ИТ

    У НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ


Введение в принципы функционирования и применения современных мультиядерных архитектур (на примере Intel Xeon Phi) 2-е издание, исправленное
Гергель В.П.
Мееров И.Б.
Бастраков С.И.
Горшков А.В.
Козинов Е.А.
Линев А.В.
Сиднев А.А.
Сысоев А.В.



Национальный Открытый Университет “ИНТУИТ” 2016

2

Введение в принципы функционирования и применения современных мультиядерных архитектур (на примере Intel Xeon Phi)/ В.П. Гергель , И.Б. Мееров, С.И. Бастраков, А.В. Горшков, Е.А. Козинов, А.В. Линев, А.А. Сиднев, А.В. Сысоев - М.: Национальный Открытый Университет “ИНТУИТ”, 2016
В курсе изучаются вопросы разработки и оптимизации программного обеспечения, ориентированного на эффективное использование мультиядерных архитектур на примере сопроцессора Intel Xeon Phi.
Основная цель курса - изучить базовые принципы и сформировать навыки разработки программ, ориентированных на эффективное использование Intel Xeon Phi. При этом решаются следующие задачи: изучение современного состояния дел в области многоядерных и мультиядерных систем; изучение особенностей архитектуры и моделей использования Intel Xeon Phi, а также соответствующего системного программного обеспечения. Освоение способов разработки, сборки и запуска приложений на Intel Xeon Phi; принципов и особенностей применения технологий параллельного программирования для разработки и оптимизации расчетных программ, ориентированных на Intel Xeon Phi, включая вопросы использования инструкций SIMD, технологий OpenMP и Cilk Plus. Формирование навыков оптимизации и векторизации расчетных циклов, оптимизации работы с памятью, балансировки нагрузки при распараллеливании. Ознакомление с достаточно успешными примерами оптимизации программ, изначально не совсем подходящих для эффективного использования возможностей Intel Xeon Phi. Изучение вопросов портирования достаточно сложных прикладных пакетов на Intel Xeon Phi.
(c) ООО “ИНТУИТ.РУ”, 2014-2016
(c) Гергель В.П., Мееров И.Б., Бастраков С.И., Горшков А.В., Козинов Е.А., Линев А.В., Сиднев А.А., Сысоев А.В., 2014-2016

3

                Обзор архитектуры современных многоядерных процессоров




Параллелизм как основа высокопроизводительных вычислений. Процессоры. Ускорители вычислений.

Введение

Презентацию к лекции Вы можете скачать ссылка: здесь -http://old.intuit.ru/department/se/intsedemcp/1/Lection01.pptx.

“Citius, Altius, Fortius”¹) - девиз Олимпийских игр современности, как ни к какой другой области, применим к вычислительной технике. Воплощение в жизнь не раз видоизменявшего свою исходную формулировку, но до сих пор действующего эмпирического закона, сформулированного в 1965 г. Гордоном Муром, похоже, стало “делом чести” производителей аппаратного обеспечения. Из всех известных формулировок этого закона точку зрения потребителя/пользователя наилучшим образом отражает вариант: “производительность вычислительных систем удваивается каждые 18 месяцев”. Мы сознательно не использовали термин “процессор”, поскольку конечного пользователя вовсе не интересует, кто обеспечивает ему повышение мощности: процессор, ускоритель, видеокарта - ему важен лишь сам факт роста возможностей “за те же деньги”.

Закон Мура в общем случае гласит, что за небольшой период времени происходит удвоение количества транзисторов на кристалле²). Величина этого периода обычно составляет 1-2 года и определяется уровнем развития промышленности в конкретный момент времени. Закон Мура достигается за счёт более плотного размещения транзисторов, т.к. линейное расстояние между электродами транзисторов уменьшается (происходит уменьшение техпроцесса, определяющего размер транзисторов). В результате тепловыделение и энергопотребление транзисторов уменьшается. Как следствие, становится возможным размещение большого количества транзисторов на кристалле с сохранением прежних (или даже меньших) показателей тепловыделения и энергопотребления.

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


4

Кроме представленной выше известна и другая формулировка закона Мура: “доступная (человечеству) вычислительная мощность удваивается каждые 18 месяцев”. Зримое свидетельство этого варианта формулировки - список Top500 [106] самых высокопроизводительных вычислительных систем мира, обновляемый дважды в год. В ноябре 1993 г. был представлен 2-ой список Top500, содержащий одну вычислительную систему с производительностью больше 100 гигафлопс (Numerical Wind Tunnel производства Fujitsu). Барьер в один терафлопс был преодолен системой ASCI Red [111] производства компании Intel в 1997 г. В июне 2005 система IBM BlueGene/L имела производительность более 100 терафлопс, а уже в 31-м списке Top500 (июнь 2008 г.) впервые в истории был преодолен петафлопный порог производительности - суперкомпьютер Roadrunner [112] производства компании IBM показал на тесте LINPACK 1,026 петафлопс (всего за 15 лет пик мощности вырос на четыре порядка). А суммарная мощность систем, представленных в 31-м списке Top500, составила 11,7 петафлопс. Много это или мало? Если взять за основу, что реальная производительность хорошей “персоналки” на четырехъядерном процессоре составляет порядка 20 гигафлопс, то весь список Top500 будет эквивалентен половине миллиона таких персоналок. Очевидно, что это лишь вершина айсберга. По данным аналитической компании Gartner, общее число используемых в мире компьютеров превысило в 2008 г. 1 миллиард.

Представленные в списке Top500 данные позволяют проследить характерные тенденции развития индустрии в сфере суперкомпьютерных вычислений. Первый список Top500 датирован июнем 1993 г. и содержал 249 многопроцессорных систем с общей памятью и 97 суперкомпьютеров, построенных на основе единственного процессора; более 40% всех решений в нем были созданы на платформе, разработанной компанией Cray. Уже четырьмя годами позже в Top500 не осталось ни одного суперкомпьютера на основе единственного процессора, а взамен появилась первая система с производительностью всего в 10 гигафлопс (в 100 раз меньше, чем у лидера списка системы ASCI Red), относящаяся к довольно новому тогда виду кластерных вычислительных систем, которые сегодня занимают в Top500 более 80% списка и являются, фактически, основным способом построения суперкомпьютеров.

Основным преимуществом кластеров, предопределившим их повсеместное распространение, было и остается построение из стандартных массово выпускающихся компонентов, как аппаратных, так и программных. В 31-м списке Top500 75% систем построены на основе процессоров компании Intel, чуть больше 13% - на процессорах компании IBM и 11% - компании AMD (на двух оставшихся производителей - NEC и Cray - приходится по одной системе соответственно); 81% систем используют всего два типа сетей передачи данных: Gigabit Ethernet или Infiniband; 85% систем работают под управлением операционной системы из семейства Linux. Как видим, список использующихся программно-аппаратных компонент весьма ограничен, что является несомненным плюсом с точки зрения пользователей.

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


5

может быть названа первым в мире “персональным кластером”. Во всяком случае, уже в начале 2001 г. компания RenderCube [109] представила одноименный мини-кластер из 4-х двухпроцессорных систем, заключенных в кубический корпус со стороной всего в 42 см.

Тенденция “персонализации” супервычислений в последнее время развивается все активнее, и недавно была подхвачена в том числе и производителями видеокарт, мощности которых возросли настолько, что возникло естественное желание использовать их не только в графических расчетах, но и в качестве ускорителей вычислений общего назначения. Соответствующие решения представлены в настоящее время компанией NVIDIA (семейство NVIDIA® Tesla™) и компанией AMD (семейство ATI FireStream™) и демонстрируют - в силу специфики внутреннего устройства -потрясающую (в сравнении с универсальными процессорами) пиковую производительность, превышающую 1 терафлопс.

Основная идея кластера в “облаке” заключается в предоставление пользователям вычислительных ресурсов кластера удалённо через сеть Internet. При этом, пользователю не нужно покупать кластер, заниматься его содержанием и обслуживанием. Кроме того, оплачиваются только потреблённые ресурсы при выполнении вычислении. Одной из популярных облачных систем является Amazon Web Services (в 41-ом списке Top500 кластер Amazon EC2 занимает 128 место с производительность 240 терафлопс).

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

Параллелизм как основа высокопроизводительных вычислений

Без каких-либо особых преувеличений можно заявить, что все развитие компьютерных систем происходило и происходит под девизом “Скорость и быстрота вычислений”. Если быстродействие первой вычислительной машины ENIAC составляло всего несколько тысяч операций в секунду, то самый быстрый на ноябрь 2012 г. суперкомпьютер Titan может выполнять уже несколько квадриллионов (10¹⁵) команд. Темп развития вычислительной техники просто впечатляет - увеличение скорости вычислений в триллионы (10¹²) раз немногим более чем за 60 лет! Для лучшего понимания необычности столь стремительного развития средств вычислительной техники часто приводят яркие аналогии, например: если бы автомобильная промышленность развивалась с такой же динамикой, то сейчас автомобили весили бы порядка 200 граммов и тратили бы несколько литров бензина на миллионы километров!

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


6

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

Не ставя целью в рамках данного курса подробное рассмотрение истории развития компьютерного параллелизма, отметим, например, организацию независимости работы разных устройств ЭВМ (процессора и устройств ввода-вывода), появление многоуровневой памяти, совершенствование архитектуры процессоров (суперскалярность, конвейерность, динамическое планирование). Дополнительная информация по истории параллелизма может быть получена, например, в [67]; здесь же выделим как принципиально важный итог - многие возможные пути совершенствования процессоров практически исчерпаны (так, возможность дальнейшего повышения тактовой частоты процессоров ограничивается рядом сложных технических проблем) и наиболее перспективное направление на данный момент времени состоит в явной организации многопроцессорности вы-числительных устройств.

Ниже будут более подробно рассмотрены основные способы организации многопроцессорности - симметричной мультипроцессорности (Symmetric Multiprocessor, SMP), одновременной многопотоковости (Simultaneous Multithreading, SMT) и многоядерности (multicore).

Симметричная мультипроцессорность

Организация симметричной мультипроцессорности (Symmetric Multiprocessor, SMP), когда в рамках одного вычислительного устройства имеется несколько полностью равноправных процессоров, является практически первым использованным подходом для обеспечения многопроцессорности - первые вычислительные системы такого типа стали появляться в середине 50-х - начале 60-х годов, однако массовое применение SMP систем началось только в середине 90-х годов.

Следует отметить, что SMP системы входят в группу MIMD (multi instruction multi data) вычислительных систем в соответствии с классификацией Флинна. Поскольку эта классификация приводит к тому, что практически все виды параллельных систем (несмотря на их существенную разнородность) относятся к одной группе MIMD, для дальнейшей детализации класса MIMD предложена практически общепризнанная структурная схема [47, 99] - см. рис. 1.1. В рамках данной схемы дальнейшее разделение типов многопроцессорных систем основывается на используемых способах организации оперативной памяти в этих системах. Данный поход позволяет различать два важных типа многопроцессорных систем - multiprocessors (мультипроцессоры, или системы с общей разделяемой памятью) и multicomputers (мультикомпьютеры, или


7

системы с распределенной памятью).

Для дальнейшей систематики мультипроцессоров учитывается способ построения общей памяти. Возможный подход - использование единой (централизованной) общей памяти (shared memory) - см. рис. 1.2. Такой подход обеспечивает однородный доступ к памяти (uniform memory access, UMA) и служит основой для построения векторных параллельных процессоров (parallel vector processor, PVP) и симметричных мультипроцессоров (symmetric multiprocessor, SMP). Среди примеров первой группы -суперкомпьютер Cray T90, ко второй группе относятся IBM Server, Sun StarFire, HP Superdome, SGI Origin и др.

Одной из основных проблем, которые возникают при организации параллельных вычислений на такого типа системах, является обеспечение информационной целостности (когерентности) кэшей (cache coherence problem).


Рис. 1.1. Классификация многопроцессорных вычислительных систем

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

Существует две методики дублирования данных их кэша в оперативную память: обратная запись (write back) и сквозная запись (write through). При использовании сквозной записи в кэш все записываемые данные сразу дублируются в оперативной памяти. При использовании обратной записи данные помещаются только в кэш и переписываются в оперативную память только тогда, когда необходимо освободить строку кэша. При использовании этих методик может нарушиться информационная


8

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

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

Обеспечение однозначности кэшей обычно реализуется на аппаратном уровне. Аппаратные методы позволяют выполнять действия, необходимые для обеспечения когерентности данных, только в тех случаях, когда это требуется при выполнении программы, что приводит к более эффективному использованию кэшей. Существует множество аппаратных методов обеспечения информационной целостности данных. Более подробно об этом можно прочитать в [1]. Мы рассмотрим метод с использованием про-токола MESI.

Протокол MESI основан на введении четырёх состояний для каждой строки кэша:

modified (строка была изменена и изменения не отражены в оперативной памяти), exclusive (данные в строке кэша и оперативной памяти одинаковы, в остальных кэшах этих данных нет),
shared (данные в строке кэша и оперативной памяти одинаковы, в каких-то других кэшах этих данные тоже присутствуют),

invalid (строка содержит недостоверные данные).

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


9

при промахе может выполняться по-разному в зависимости от состояния других кэшей. Если в каком-либо кэше содержится копия строки в состоянии exclusive или shared, то данные загружаются в кэш из оперативной памяти, а строка помечается как shared в этих кэшах. Если в каком-либо кэше содержится копия строки в состоянии modified, то этот кэш заблокирует чтение из памяти и инициирует запись строки в оперативную память, после чего изменит состояние строки на shared. Если ни в одном из кэшей нет копии строки, то блок данных загружается из оперативной памяти, а строка помечается как exclusive. Операция записи при промахе инициирует чтение блока данных из оперативной памяти и устанавливает состояние строки в значение modified. При этом, если в каком-либо кэше находилась копия данных в состоянии modified, то сначала данные из этого кэша записываются в оперативную память, а строка помечается как invalid. Все кэши, которые содержали копию данных в состоянии shared или exclusive переходят в состояние invalid.

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

На данный момент широко используется модифицированный протокол MESI в котором добавлено дополнительное состояние, позволяющее эффективнее решать проблему когерентности данных за счёт загрузки требуемых данных из соседнего кэша, а не из оперативной памяти. Intel использует протокол MESIF, AMD - MOESI.

Наличие общих данных при выполнении параллельных вычислений приводит к необходимости синхронизации взаимодействия одновременно выполняемых потоков команд. Так, если изменение общих данных требует для своего выполнения некоторой последовательности действий, то необходимо обеспечить взаимоисключение (mutual exclusion), с тем чтобы эти изменения в любой момент времени мог выполнять только один командный поток. Задачи взаимоисключения и синхронизации относятся к числу классических проблем, и их рассмотрение при разработке параллельных программ является одним из основных вопросов параллельного программирования.

Общий доступ к данным может быть обеспечен и при физически распределенной памяти (при этом, естественно, длительность доступа уже не будет одинаковой для всех элементов памяти) - см. рис. 1.2. Такой подход именуется как неоднородный доступ к памяти (non-uniform memory access, или NUMA). Среди систем с таким типом памяти выделяют:


10