Многопроцессорность

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:21, 27 мая 2017.
Структура многопроцессорной системы
Многопроцессорность - использование двух или более центральных процессорных устройств (ЦПУ) внутри единой компьютерной системы. Термин также связан со способностью системы поддерживать больше одного процессора или возможностью распределения задач между ними.[Источник 1] Существует много вариантов данного термина и разница зачастую зависит от контекста, главным образом определяется как устройство ЦПУ (несколько ядер на одном кристалле, несколько кристаллов в одном пакете, или несколько пакетов в одной системной единице...).

Согласно онлайн словарям, многопроцессорная компьютерная система должна иметь два или более вычислительных единиц (многоядерных процессоров) с разделенной оперативной памятью и периферийными устройствами для того чтобы одновременно обрабатывать программные процессы. [Источник 2] Один из учебников 2009 года определяет понятие многопрограммности аналогичным образом, но не указывается что процессоры могут распределять память и устройства ввода\вывода, также определяя понятие тесно связанной системы как синоним. [Источник 3]

На уровне операционной системы многопрограммность используется для того чтобы соотнести выполнение различных процессов на отдельных ЦПУ или отдельными ядрами. Такое определение может показаться похожим на определение многозадачности, которое может использовать одно ядро для выполнения нескольких различных задач, переключаясь по времени между ними(разнесенная во времени система). Многопроцессорность вовсе не означает, что один процесс или задача обязательно выполняется более чем на одном процессоре одновременно; термин параллельных процессов используется для обозначения данного сценария. Другие же авторы предпочитают определять это как многопрограммность и сохранить термин многопроцессорности для аспекта аппаратных средств имеющих более одного процессора.[Источник 4]

В классификации Флинна многопроцессорность определяется схожим образом с MIMD машинами. Так как их конструкция очень похожа (разделенная память), многопроцессорные ЦПУ не составляют полностью класс MIMD машин, так туда включаются также передающие многоядерные устройства.

История

аналитическая машина Чарльса Бабаджа

Согласно статье в журнале "Байт" впервые идея многопроцессорности была высказана в 1842г итальянским генералом Луиджи Федерико Менабреа по поводу аналитической машины сконструированной Чарльсом Бабаджом:"Машина может быть пущена в ход чтобы дать несколько результатов одновременно, что значительно сократит время работы"

Процессорная симметрия

В многопроцессорной системе все ЦПУ могут быть равны либо некоторые резервируются для специальных целей. Комбинация аппаратного устройства и операционной системы определяет симметрию (или ее отсутствие) в данной системе. Например, соображения аппаратного или программного обеспечения могут требовать, чтобы только один конкретный ЦП отвечал на все аппаратные прерывания, тогда как все другие работы в системе могут распределяться поровну между ЦП; Или выполнение кода в режиме ядра может быть ограничено только одним конкретным ЦПУ, тогда как код пользовательского режима может быть выполнен в любой комбинации процессоров. Многопроцессорные системы зачастую проще в разработке, если такие ограничения налагаются, но они имеют тенденцию быть менее эффективными, чем системы, в которых используются все ЦПУ.

Системы, которые одинаково относятся ко всем процессорам, называются системами симметричной многопроцессорной обработки (SMP от англ. symmetric multiprocessing). В системах, где все ЦПУ не равны, системные ресурсы могут быть разделены на несколько способов, включая асимметричную многопроцессорную обработку (ASMP от англ. asymmetric multiprocessing), многоадресную обработку с неоднородным доступом к памяти (NUMA от англ. non-uniform memory access) и кластерную многопроцессорную обработку.

Инструкции и потоки данных

В многопроцессорной обработке процессоры могут использоваться для выполнения одной последовательности команд в нескольких контекстах (однонаправленная, многократная или SIMD, часто используемая при векторной обработке), несколько последовательностей команд в одном контексте (множественная инструкция, одиночная -data или MISD, используемые для избыточности в отказоустойчивых системах и иногда применяемые для описания конвейерных процессоров или гиперпотоков), или несколько последовательностей команд в нескольких контекстах (множественные инструкции, множественные данные или MIMD).

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

Тесно связанная многопроцессорная система

Тесно связанные многопроцессорные системы содержат несколько центральных процессоров, которые подключены на уровне шины. Эти ЦПУмогут иметь доступ к центральной общей памяти (SMP или UMA) или могут участвовать в иерархии памяти как с локальной, так и с общей памятью (SM) (NUMA). IBM p690 - пример высокопроизводительной SMP-системы. Процессоры Intel Xeon доминировали на многопроцессорном рынке для бизнес-ПК и были единственным основным вариантом x86 до выпуска процессоров AMD Opteron в 2004 году. Оба процессора имели свой собственный встроенный кэш, но обеспечивали доступ к общей памяти; Процессоры Xeon через общий канал и процессоры Opteron через независимые пути к системной RAM.

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

Слабосвязанная многопроцессорная система

Слабосвязанные многопроцессорные системы (часто называемые кластерами) основаны на нескольких автономных одно- или двухпроцессорных компьютерах, соединенных через высокоскоростную коммуникационную систему (обычно используется Gigabit Ethernet). Например, кластер Linux Beowulf - слабосвязанная система.

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

Слабосвязанные многопроцессорные системы (часто называемые кластерами) основаны на нескольких автономных одно- или двухпроцессорных товарных компьютерах, соединенных через высокоскоростную коммуникационную систему (обычно используется Gigabit Ethernet). Кластер Linux Beowulf является примером слабосвязанной системы.

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

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

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

Многопроцессорная архитектура связи

Передача сообщений

  • Отдельное адресное пространство для каждого процессора.
  • Процессоры обмениваются сообщениями.
  • Процессоры обеспечивают локальные очереди сообщений.
  • Сосредоточить внимание на дорогостоящих нелокальных операциях.

Общая память

  • Процессоры взаимодействуют с общим адресным пространством
  • Процессоры взаимодействуют посредством чтения / записи в памяти
  • Легко на небольших машинах
  • Более низкая латентность
  • Архитектура SMP или NUMA

Классификация Флинна

Классификация Флинна

Многопроцессорная обработка SISD

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

Многопроцессорная обработка SIMD

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

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

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

Кроме того, программы должны быть тщательно и специально написаны, чтобы максимально использовать преимущества архитектуры, и часто должны использоваться специальные оптимизирующие компиляторы, предназначенные для создания кода специально для этой среды. Некоторые компиляторы этой категории предоставляют специальные конструкции или расширения, позволяющие программистам напрямую указывать операции, которые должны выполняться параллельно (например, инструкции DO FOR ALL в версии FORTRAN, используемые на ILLIAC IV, который был мультипроцессорным мультипроцессором SIMD).

Многопроцессорная обработка MISD

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

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

Многопроцессорная обработка MIMD

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

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

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

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

Мультипроцессорное аппаратное обеспечение UMA NUMA

Хотя у всех мультипроцессоров имеется свойство, позволяющее каждому центральному процессору обращаться ко всему пространству памяти, у некоторых мультипроцессоров есть еще одно свойство: каждое слово памяти может быть считано так же быстро, как и любое другое слово памяти. Такие машины называются UMA-мультипроцессорами (Uniform Memory Access — однородный доступ к памяти). В противоположность им NUMA-мультипроцессоры (Nonuniform Memory Access — неоднородный доступ к памяти) этим свойством не обладают. Далее станет ясно, почему существует такое различие. Сначала будут рассмотрены UMA-мультипроцессоры, а затем NUMA мультипроцессоры.[Источник 5]

UMA-мультипроцессоры с шинной архитектурой

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

Мультипроцессор с общей шиной без кэш памяти
Мультипроцессор с общей шиной с кэш памятью

Решение этой проблемы показано на рисунке выше и заключается в добавлении к каждому центральному процессору кэш-памяти. Эта память может располагаться внутри микросхемы центрального процессора, соседствовать с этой микросхемой, находиться на общей плате или быть представлена комбинацией из трех перечисленных вариантов. Поскольку многие операции чтения теперь могут быть удовлетворены за счет локальной кэш-памяти, существенно сократится объем данных, передаваемых по шине, и система сможет поддерживать большее количество центральных процессоров.8.1. Мультипроцессоры 581 Как правило, кэширование реализуется не пословно, а блоками по 32 или 64 байта. При обращении к слову в кэш обратившегося центрального процессора извлекается целый блок, называемый строкой кэша (cache line), или кэш-строкой. Каждый блок кэш-памяти маркируется как предназначенный только для чтения(в этом случае он может в одно и то же время присутствовать в нескольких кэшах)или как предназначенный для чтения и записи (в этом случае он, возможно, не присутствует ни в каких других кэшах). Если центральный процессор пытается записать слово, находящееся в одном или нескольких удаленных кэшах, аппаратура шины обнаруживает запись и выставляет на шину сигнал, информирующий все остальные кэши о записи. Если другие кэши имеют неизмененные копии, в точности соответствующие содержимому блока в памяти, они могут просто забраковать эти копии и позволить процессору, осуществляющему запись, извлечь имевшийся в кэше блок из памяти перед его изменением. Если какие-нибудь другие кэши имели измененную копию, они должны были либо записать его обратно в память перед осуществлением новой записи, либо передать его по шине непосредственно тому процессору, который осуществлял запись. Этот свод правил называется протоколом поддержки когерентности кэшей(cache-coherence protocol), и это всего лишь один из многих протоколов.

Мультипроцессор с общей шиной с кэш памятью и собственной памятью процессора

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

UMA-мультипроцессоры, использующие координатные коммутаторы

Даже при самом удачном кэшировании использование одной шины сводит масштаб UMA-мультипроцессора всего лишь к 16 или 32 центральным процессорам. Чтобы преодолеть этот барьер, нужен другой тип сети обмена данными. Простейшая схема подключения n центральных процессоров к k модулям памяти — это координатный коммутатор (crossbar switch). Координатный коммутатор десятилетиями использовался для коммутации телефонных переговоров, чтобы произвольным образом соединить группу входных линий с набором выходных линий. В каждом пересечении горизонтальной (входной) и вертикальной (выходной) линий стоит элемент коммутации, небольшой выключатель, который может пропускать или не пропускать электрический сигнал, то есть быть включенным или выключенным в зависимости от того, должны или не должны соединяться горизонтальная и вертикальная линии. На рис. 8.3, а изображены три одновременно включенных элемента,позволяющие соединяться следующим парам «центральный процессор — модуль памяти»: (001, 000), (101, 101) и (110, 010). Можно составить и множество других комбинаций. Фактически число комбинаций равно количеству различных способов расстановки восьми ладей на шахматной доске, при которых ни одна из этих фигур не находилась бы под ударом другой.

Коммутатор 2 × 2: а — с двумя входными, A и B, и двумя выходными, X и Y, линиями; б — формат сообщения

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

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

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

Мультипроцессоры UMA, использующие многоступенчатые схемы коммутации

Координатный коммутатор: а — три одновременно включенных элемента; б — открытый элемент коммутации; в — закрытый элемент коммутации

На рисунке показана совершенно другая мультипроцессорная архитектура, построенная на простых коммутаторах 2 × 2. У такого коммутатора есть два входа и два выхода.

Сообщения, поступающие по любой входной линии, могут быть скоммутированы на любую выходную линию. Для решения наших задач сообщения будут содержать до четырех частей. В поле Module (Модуль) сообщается, какой модуль памяти следует использовать. В поле Address (Адрес) указывается адрес в этом модуле. В поле Opcode (Код операции) предоставляется операция, например READ или WRITE. И наконец, необязательное поле Value (Значение) может содержать операнд, например 32-разрядное слово, которое нужно записать с помощью операции WRITE. Коммутатор проверяет содержимое поля Module и использует его для определения того, куда должно быть послано сообщение — на линию X или на линию Y.

С помощью коммутатора 2 × 2 можно построить самые разные большие многоступенчатые коммутаторные сети (multistage switching networks), рассмотренные в Adams etal. (1987), Garofalakis and Stergiou (2013), Kumar and Reddy (1987). Одна из возможных схем, упрощенная сеть омега (omega network), относящаяся к эконом-классу, показана на рисунке ниже. Здесь с помощью 12 коммутаторов восемь центральных процессоров подключаются к восьми модулям памяти. В общем, для n центральных процессоров и n модулей памяти понадобится log2 n ступеней с n/2 коммутаторами на каждую ступень, а всего (n/2) log2 n коммутаторов, что значительно лучше, чем n2 элементов коммутации, особенно для больших n.

Схема коммутации омега

Схему электрической разводки в сети омега часто называют идеальным тасованием (perfect shuffle), поскольку перемешивание сигналов на каждой ступени походит на колоду карт, поделенную на две части, а затем перемешиваемую путем заведения одних карт за другие. Чтобы разобраться с работой сети омега, предположим, что центральному процессору 011 понадобилось прочитать слово из модуля памяти 110. Центральный процессор посылает сообщение READ коммутатору 1D, в котором в поле Module содержится значение 110. Коммутатор берет первый (то есть самый левый) бит из 110 и использует его для маршрутизации. Если значение равно 0, сообщение направляется на верхний выход, а если 1, сообщение направляется на нижний выход. Поскольку бит содержит 1, сообщение направляется через нижний выход на коммутатор 2D. Все коммутаторы второй ступени, включая 2D, используют для маршрутизации второй бит. В данном случае он также равен 1, поэтому теперь сообщение направляется через нижний выход к коммутатору 3D. Там уже тестируется третий бит, который равен 0. Следовательно, сообщение направляется через верхний выход и попадает, как и требовалось, к модулю памяти 110. Путь, по которому проходит это сообщение, помечен на рисунке буквой a.

По мере прохождения сообщения по схеме коммутации самые левые биты номера модуля утрачивают свое значение. Ими можно воспользоваться снова, записывая в них номер входящей линии, чтобы ответ смог отыскать обратный путь. Для пути a входные линии имеют номера 0 (верхний вход 1D), 1 (нижний вход 2D) и 1 (нижний вход 3D). Ответ будет направлен назад с помощью значения 011, только на этот раз чтение из него будет производиться справа налево. В это же время центральному процессору 001 требуется записать слово в модуль памяти 001. Здесь происходит аналогичный процесс: сообщение направляется по верхнему,опять по верхнему и по нижнему выходам, этот путь помечен буквой b. Когда сообщение дойдет до адресата, его поле Module будет содержать значение 001, представляющее пройденный им путь. Поскольку рассмотренные запросы не используют одни и те же коммутаторы, линии и модули памяти, они могут выполняться параллельно. Теперь посмотрим, что произойдет, если центральный процессор 000 одновременно с этим захочет обратиться к модулю памяти 000. Его запрос вступит в конфликт с запросом центрального процессора 001 на коммутаторе 3A. Одному из них придется подождать. В отличие от координатного коммутатора, сеть омега представляет собой блокирующуюся сеть (blocking network). Не все наборы запросов могут обрабатываться одновременно. При использовании линий или коммутаторов могут возникать конфликты как между запросами к памяти, так и между ответами от памяти.

Возникает потребность в равномерном распределении обращений к модулям памяти. Одна из распространенных технологий предусматривает использование младших разрядов в качестве номера модуля. Рассмотрим, к примеру, байт-ориентированное адресное пространство компьютера, который в основном обращается к целым 32-разрядным словам. Два младших разряда обычно имеют значение 00, но следующие три бита будут распределены равномерно. За счет использования этих трех битов в качестве номера модуля последовательные слова будут находиться в последовательных модулях. Система памяти, в которой следующие друг за другом слова находятся в разных модулях, называется чередующейся (interleaved). Чередующиеся системы памяти позволяют добиться максимального распараллеливания, потому что большинство обращений к памяти осуществляется к следующим друг за другом адресам. Для более эффективного распространения потока данных можно также разработать неблокирующиеся схемы коммутации, предлагающие несколько путей от каждого центрального процессора к каждому модулю памяти.

Мультипроцессоры NUMA

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

NUMA-машины обладают тремя ключевыми характеристиками, которые присущи им всем и которые в совокупности отличают их от других мультипроцессоров:

  1. В области видимости всех центральных процессоров находится единое адресное пространство.
  2. Доступ к удаленной памяти осуществляется с помощью команд LOAD и STORE.
  3. Доступ к удаленной памяти осуществляется медленнее, чем доступ к локальной.

Когда время доступа к удаленной памяти не скрыто (по причине отсутствия кэширования), система называется NC-NUMA (No Cache-coherent NUMA — NUMA без согласованного кэширования). При наличии согласованной кэш-памяти система называется CC-NUMA (Cache-Coherent NUMA — NUMA с согласованным кэшированием). В настоящее время самым популярным подходом при создании больших мультипроцессоров CC-NUMA является мультипроцессор на основе каталогов (directory-based multiprocessor). Идея заключается в ведении базы данных, сообщающей, где находится каждая кэш-строка и каково ее состояние. При обращении к кэш-строке запрашивается база данных, чтобы определить, где она находится и какая информация в ней содержится — неизмененная или измененная. Поскольку эта база данных должна запрашиваться при выполнении каждой команды, обращающейся к памяти, она должна поддерживаться исключительно быстродействующей специализированной аппаратурой, откликающейся за доли такта шины.

Чтобы конкретизировать идею мультипроцессора, основанного на каталогах, рассмотрим простой (гипотетический) пример — систему, состоящую из 256 узлов, каждый узел которой состоит из одного центрального процессора и 16 Мбайт оперативной памяти, с которой этот процессор связан по локальной шине. Общий объем памяти составляет 232 байт, которые поделены на 226 кэш-строк по 64 байт каждая. Память статически распределена по узлам, где диапазон адресов 0–16 M выделен узлу 0, 16 M–32 M — узлу 1 и т. д. Узлы связаны схемой соединений, показанной на рисунке ниже. Каждый узел содержит также записи каталога для 218 64-байтовых кэш-строк, включающих в себя 224 байт памяти. Предположим на время, что строка может храниться не более чем в одном кэше.

Чтобы понять, как работает каталог, проследим за командой LOAD из центрального процессора 20, которая ссылается на кэш-строку. Сначала центральный процессор,выдающий команду, передает ее своему блоку управления памятью (MMU), который осуществляет преобразование команды в физический адрес, например 0x24000108. MMU разбивает этот адрес на три части, показанные на рис. 8.6, б. В десятичной форме эти три части представляют собой узел 36, строку 4 и смещение 8. Блок управления памятью видит, что слово памяти, на которое делается ссылка, из узла 36, а не из узла 20, поэтому он отправляет сообщение с запросом через схему соединений к узлу 36, выясняя, находится ли эта строка 4 в кэше, и если да, то где именно.

а — мультипроцессор на основе каталогов, содержащий 256 узлов; б — разделение 32-разрядного адреса памяти на поля; в — каталог в узле 36

Когда запрос по схеме соединений поступает к узлу 36, он направляется к аппаратуре каталога. Эта аппаратура обращается по индексу в свою таблицу, состоящую из 218 запи сей, по одной для каждой своей кэш-строки, и извлекает запись 4. На рисунке показано, что строки в кэше нет, поэтому аппаратура извлекает строку 4 из локальной оперативной памяти, отправляет ее обратно узлу 20 и обновляет запись каталога 4, показывая, что теперь строка находится в кэше на узле 20. Рассмотрим второй запрос, на этот раз касающийся строки 2 узла 36. На рисунке, в показано, что эта строка присутствует в кэше на узле 82. В этот момент аппаратура может обновить запись каталога, чтобы она сообщала, что строка теперь находится на узле 20, а затем отправить сообщение узлу 82, предписывая ему передать строку узлу 20 и аннулировать свой кэш. Заметьте, что даже так называемый мультипроцессор с общей памятью не обходится без передачи на внутреннем уровне большого количества сообщений.

В качестве небольшого отступления подсчитаем, сколько памяти уходит на каталоги.У каждого узла имеется 16 Мбайт оперативной памяти и 2^18 записей длиной 9 бит для ведения учета этой памяти. Итак, на каталог уходит около 9 х 2^18 бит на 16 Мбайт, или около 1,76 %, что вполне приемлемо (если не обращать внимания на то, что это должна быть высокоскоростная память, что, разумеется, повышает ее стоимость). Даже если использовать кэш-строки длиной 32 байта, издержки составят только 4 %. При кэшстроках длиной 128 байт они будут меньше 1 %.

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

Источники

  1. Раджагопал (1999 год). Введение в кластерный сервер Microsoft Windows NT: программирование и администрирование. CRC Press. п. 4. ISBN 978-1-4200-7548-9.
  2. multiprocessor// yourdictionary.com[2017-2017]. Дата обращения: 07.03.2017. URL: http://www.yourdictionary.com/multiprocessor
  3. Rv Englander (2009). Архитектура компьютерного оборудования и системного программного обеспечения. Информационно-технологический подход. (4-е изд.). Уайли. п. 265
  4. Ашок Арора (2006). Основы информатики. Лакшми Публикации. п. 149. ISBN 978-81-7008-971-1.
  5. Таненбаум Э., Бос Х. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015. — 1120 с.:ил. — (Серия «Классика computer science»). ISBN 978-5-496-01395-6