Архитектура многопроцессорных систем с неоднородным доступом к памяти



Содержание

  1. Введение
  2. На протяжении длительного времени прогресс в области микропроцессоров фактически отождествлялся со значением тактовой частоты. Закон Мура гласит, чтоколичество транзисторов, размещаемых на кристалле интегральной схемы, удваивается каждые 24 месяца, но возможно в ближайшее время он перестанет работать.В двухтысячном  году в корпоративных планах производителей микропроцессоров значилось, что уже к концу десятилетия будет преодолен барьер в 10 ГГц. Но эти планы оказались неосуществимы.

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

    Память в современных процессорах имеет иерархическую структуру. Кэш-память реализована на кристалле процессора, с целью улучшить время обращения к памяти. Однако может возникнуть проблема, заключающаяся в том, что локальные кэши процессоров содержат данные не согласованные с данными хранящимися в оперативной памяти. Для решения этой проблемы был разработан алгоритм когерентности, который называетсяMESI. Работа алгоритма когерентности влияет на производительность всей системы. В многопоточных приложениях может возникнуть ситуация, когда разные объекты делят одну и ту же кэш-линию процессора. Такую проблему называют ложным разделением данных илиfalsesharing. Если происходитfalsesharing, то система должна согласовать данные в кэшах каждого процессора. Чтобы оптимизировать программу и более эффективно использовать кэш процессора, необходимоулучшить пространственную и временную локальность, а также необходимо заранее выравнивать код и данные.Часто разработчики  не задумываются об этих особенностях, что является причиной медленного выполнения разработанного программного обеспечения. Возможно, применяется неэффективный алгоритм или разработчики нерезультативно работают с массивами или со структурами данных в многопоточной среде.

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

    1. постановка задачи

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

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

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

    1. Описание предметной области
      1. Многопроцессорные системы

    У всех мультипроцессоров каждый центральный процессор может адресоваться ко всей памяти. Однако по характеру доступа к памяти эти машины делятся на два класса. Мультипроцессоры, у которых каждое слово данных может быть считано с одинаковой скоростью, называются UMA-мультипроцессорами (Uniform Memory Access — однородный доступ к памяти). В противоположность им мультипроцессоры NUMA (NonUniform Memory Access— неоднородный доступ к памяти) этим свойством не обладают. [1]

    1. Архитектура многопроцессорных систем с общей шиной

    В основе простейшей архитектуры мультипроцессоров лежит идея общей шины (см. рисунок 3.1).

    Рисунок 3.1- Многопроцессорная система с обшей памятью

    Несколько центральных процессоров и несколько модулей памяти одновременно используют одну и ту же шину для общения друг с другом. Когда центральный процессор хочет прочитать слово в памяти, он сначала проверяет, свободна ли шина. Если шина свободна, центральный процессор выставляет на нее адрес нужного ему слова, подает несколько управляющих сигналов и ждет, пока память не выставит нужное слово на шину данных. Если шина занята, центральный процессор просто ждет, пока она не освободится. В этом заключается проблема данной архитектуры. При двух или трех центральных процессорах состязанием за шину можно управлять. При 32 или 64 центральных процессорах шина будет постоянно занята, а производительность системы будет полностью ограничена пропускной способностью шины. При этом большую часть времени центральные процессоры будут простаивать. [1]

    Чтобы решить эту проблему необходимо добавить каждому центральному процессору кэш. Кэш может располагаться на кристалле центрального процессора. Так как большее количество обращений к памяти будет удовлетворенно кэшем, возможно будет использовать большее число процессоров. Как правило, кэширование выполняется не для отдельных слов, а для блока данных по 32 или по 64 байта. При обращении к слову весь блок считывается в кэш центрального процессора, обратившегося к слову. [1]

    1. Архитектура многопроцессорных систем с неоднородным доступом к памяти

    В вычислительных системах с неоднородным доступом к памяти реализована технология NUMA (Non-Uniform Memory Access). Технология неоднородного доступа к памяти позволяет создавать крупномасштабные вычислительные системы. В архитектуре NUMA память физически распределена между процессорами, но логически общедоступна. Это позволяет сохранить преимущества архитектуры с единым адресным пространством, а также ощутимо расширить возможности масштабирования ВС. Архитектура NUMA систем показана на рисунке 3.2.

    Рисунок 3.2 - Архитектура мультипроцессоровNUMA

    У машинNUMA есть ключевые характеристики, которые отличают их от других мультипроцессоров.

    • Имеются два или более узлов, каждый из которых может быть представлен процессорным элементом с кэш-памятью.
    • Каждый узел имеет локальную память, которая рассматривается как часть глобальной памяти системы.
    • Узлы соединены посредством высокоскоростной сети.
    • Поддерживается единое адресное пространство, то есть любой узел имеет доступ к памяти других узлов, однако время доступа к локальной памяти существенно меньше времени обращения к удаленной памяти.
    • Когерентность кэшей обычно поддерживается аппаратными средствами (ccNUMA), но возможен вариант без таких средств (nccNUMA).
    • Вычислительная система управляется единой операционной системой, как в SMP, но возможен вариант с разбиением, где каждый раздел работает под управлением своей операционной системой.
      1. Многоядерные процессоры

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

    Рисунок 3.3 - Структура многоядерного процессора

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

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

    В многоядерных процессорах каждое ядро может поддерживать технологиюSMT (Simultaneous multithreading), позволяющую выполнять несколько потоков вычислений на каждом ядра. На процессорах, выпускаемых компанийIntel, данная технология называетсяHyper-threading. В процессорах с поддержкойHyper-Threading, набор регистров имеется у каждого логического процессора, но не поддерживается одновременное выполнение инструкций выборки/декодирования в двух потоках. Такие инструкции будут выполняться поочередно.

    Рассмотрим пример, когда применение технологииHyper-Threadingоправдано. Предположим, что процессор выполняет поток инструкций первого логического процессора. Выполнение потока может приостановиться по одной из причин:

    • произошёл промах при обращении к кэшу;
    • неверно предсказано ветвление;
    • ожидается результат предыдущей инструкции.

    Центральный процессор при включенной поддержкеHyper-Threading не будет простаивать, а передаст управление второму логическому процессору. Следовательно, пока один логический процессор ожидает, вычислительные ресурсы  процессора будут использованы другим логическим процессором.

    1. Кэш память

    На ранних компьютерах иерархия памяти была представлена три уровнями: регистры процессора, оперативная память и память на внешних носителях. Чтобы уменьшить разницу в скорости работы центрального процессора и оперативной памяти, системные инженеры приняли решение разместить на кристалле процессора маленькуюSRAM память, которую они назвали кэш-памятью. Скорость обращения к кэшу первого уровня равнялся 4 тактам процессора.  В дополнении к кэшу первого уровня было принято решении создать кэш второго уровня большего размера. Скорость обращения за данными хранящимися в кэшеL2 равняется 10 тактам процессора. Современные процессоры включают еще больший кэш, называемыйL3 кэш, находящийся между кэшемL2 и основной памятью и доступ к которому равен 50 тактам процессора. Основная структура одинакова для кэша любого уровня.[2]

    1. Структура кэша

    Рассмотрим компьютерную систему, где адрес памяти равенm бит и имеетсяM = 2m уникальных адресов. Кэш организован как массив, состоящий изS=2s множеств. На рисунке 3.4 показан пример множественно-ассоциативного кэша.

    Каждое множество состоит из кэш-линий. Каждая линия содержит блок данных размеровB=2b байт, бит корректности, который показывает, что в кэш-линии хранится значимая информация и таг поле равноеt =m – (b +s) бит. Таг поле уникально идентифицирует кэш-линию в конкретном множестве. [2]

    Обычно, структуру кэша можно представить в виде кортежа(S,E,B,m).Емкость кэша вычисляется, какС =S *E *B без учета битов поля таг  и бита корректности. Когда центральному процессору поступает инструкция чтения данных из памяти по адресуA, он посылает адресA в кэш. Если в кэше хранится копия данных по адресуA, то блок данных немедленно отправляетсяCPU. Кэш может найти запрашиваемые данные, просто извлекая биты из адреса, подобно хэш-таблицы с чрезвычайно простой хэш-функцией. Логическое разделение адреса на составные части показана на рисунке 3.4.

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

    Рисунок 3.4 - Структура множественно-ассоциативного кэша

    Будем предполагать, что у нас имеется система сCPU, регистрами, кэшем первого уровня и оперативной памятью. КогдаCPU выполняет инструкцию чтения данных, он запрашивает их из кэшаL1. Если в кэше имеется копия запрашиваемых данных, то этоcachehit и данные будут незамедлительно возвращены центральному процессору. Однако, если происходитcachemiss, т.е. запрашиваемые данные отсутствуют, кэшL1 запросит копию данных из оперативной памяти. Пример промаха по кэшу показан на рисунке 3.5. Прежде чем извлечь блок данных необходимо выполнить три шага: выбрать множество, определить кэш-линию, извлечь данные.

    Рисунок 3.5 - Пример возникновения промаха по кэшу

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

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

    Множественно-ассоциативный кэш подобен кэшу прямого отображения за исключением того, что множество содержит более одной кэш-линии. Если данные имеются в кэше, то происходитcachehit, иначеcachemiss.Если во множестве есть свободная линия, то данные запрошенные из оперативной памяти будут скопированы в неё.  Иначе будет применен алгоритм замещения, который выберет линию, которая будет замещена. Например, политикаleastfrequentlyused (LRU) замещает линию, которая наименее часто использовалась. Политикаleastrecentlyused (LRU)вытесняет линию, которая не использовалась дольше всех. Алгоритм Белади, считается наиболее эффективным алгоритмом замещения, замещает ту кэш-линию, данные в которой не потребуется в течение длительного времени, как правило, на практике этот алгоритм не реализуется. ПолитикаRandom Replacement (RR) случайным образом выбирает кандидата на замещение и отбрасывает его при необходимости освободить место в кэше. Этот алгоритм не требует хранить историю обращений к кэш-линии. Из-за своей простоты использовался в процессорахARM.

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

    1. Ложное разделение данных

    В симметричных мультипроцессорных системах, каждый процессора имеет  локальный кэш. Система должна гарантировать согласованность данных в кэшах процессоров. Ложное разделение данных (Falsesharing) происходит, когда потоки, выполняющиеся на разных процессорах, изменяют переменные, которые находятся в одной и той же строке кэша. Это делает строку кэша недействительной, заставляя систему задействовать механизм когерентности кэша, что вредит производительности всей системы. [7]

    Ложное разделение данных – это хорошо известная проблема, влияющая на производительность в многопроцессорных системах. На рисунке 3.7, показан пример возникновения ложного разделения данных.

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

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

    Рисунок 3.7 - Ситуация приводящая кFalsesharing

    Листинг 3.1 - Пример кода, в котором не учитывается проблемаFalse sharing

    double sum=0.0, sum[NUM_THREADS];

    #pragma omp parallel num_threads(NUM_THREADS)

    {

     int id = omp_get_thread_num();

     sum[id] = 0.0;

     #pragma omp for

     for (i = 0; i < N; i++)

       sum[id] += x[i] * y[i];

     #pragma omp atomic

     sum +=sum[id];

    }

    На рисунке 3.7, потоки 0 и 1, обращаются к переменным, которые хранятся в смежных адресах памяти и делят одну и ту же кэш-линию. Хотя потоки изменяют разные переменные, кэш-линия становится недействительной, заставляю систему обновить память для поддержки когерентности кэша. Для обеспечения согласованности данных в нескольких кэшах процессоры компанииIntel реализуют алгоритмMESI. При первой загрузке строки кэша, процессора маркирует её, как строку с эксклюзивным доступом. Пока кэш-линия помечена как эксклюзивная, последующие операции с данной кэш-линией могут свободно использовать хранящиеся в ней данные. Если процессор замечает, что другим процессором используется та же кэш-линия, он помечает ее, как кэш-линию с общим доступом. Если в одном из процессоров кэш-линия помечается, как модифицированная, то для всех других процессоров она становится недействительной. Ложное разделение данных может заметно ухудшить производительность приложения. Компиляторы могут оптимизировать код, устраняя ситуацию ложного разделения данных. Но для этого необходимо скомпилировать программу с оптимизацией, иначе проблема ложного разделения данных не будет рассматриваться компилятором.

    1. Основная часть
      1. Взаимодействие user spaceс kernel space

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

    Таблица 4.1 - Самые распространенные специальные файловые системы

    Название

    Точка монтирования

    Описание

    bdev

    Нет

    Блочные устройства

    binfnt_misc

    Любая

    Различные исполняемые форматы

    eventpollfs

    Нет

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

    pipefs

    Нет

    Каналы

    ргос

    /proc

    Общая точка доступа к структурам данных ядра

    rootfs

    Нет

    Предоставляет пустой корневой каталог на этапе загрузки

    shim

    Нет

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

    mqueue

    Любая

    Используется для реализации очередей сообщений POSIX

    sockfs

    Нет

    Сокеты

    sysfs

    /sys

    Общая точка доступа к системным данным

    tmpfs

    Любая

    Временные файлы (хранятся в оперативной

    памяти, если не выполняется подкачка)

    usbfs

    /proc/bus/usb

    USB-устройства

    devfs

    /dev

    Динамическая файловая система, предназначенная для управления файлами устройств

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