Ответы 190 страниц (1184228), страница 19

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

Текст из файла (страница 19)

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

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

6.5.1 Страничная DSM

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

К этому же типу DSM (не знающих заранее ничего о содержимом памяти) можно отнести и аппаратные реализации на базе кэшей (Convex SPP).

6.5.2 DSM на базе разделяемых переменных

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

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

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

s = 0;

izer = 0;

for (i = 1; i < L2-1; i++)

{

r = A[i-1]*A[i+1];

C[i] = r;

s = s + r*r;

if (A[i]==0) { izer = i};

}

A[izer] = 1;

Переменные внутри цикла используются в следующих режимах:

А - только на чтение;

r - приватно (фактически не является разделяемой);

C - раздельно используется (любой элемент массива изменяется не более, чем одним процессом, и никакой процесс не читает элемент, изменяемый другими);

s - редукционная переменная, используемая для суммирования;

izer - переменная, хранящая индекс последнего нулевого элемента массива А;

Приведения в консистентное состояние переменных A и r - не требуется.

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

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

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

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

6.5.3 DSM на базе объектов

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

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

Когерентность данных.

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

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

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

В отличие от классической архитектуры NUMA, при использовании кэш-когерентного доступа к неоднородной памяти - ccNUMA (cache coherent NUMA) все процессоры объединены в один узел (рис. 2), причем первый уровень иерархии памяти образует их кэш-память, а ccNUMA поддерживает когерентность внутри узла аппаратно. В системах ccNUMA распределенная память представляется единым адресным пространством. Не происходит никакого копирования страниц или данных. Нет программной передачи сообщений для синхронизации доступа. Есть просто единый массив памяти (хотя физически он состоит из отдельных частей). Аппаратная когерентность кэш-памяти означает, что не требуется никакого ПО для поддержки актуальности множества копий данных. Все это выполняется на аппаратном уровне так же, как в любом SMP-узле, с одним экземпляром ОС и множеством процессоров. В свою очередь NUMA-Q - это, по сути, реализация архитектуры ccNUMA компанией Sequent.

Элементарным блоком платформы NUMA-Q (рис. 3) служил квод (quad), в котором объединялись четыре процессора, блок разделяемой памяти и шина PCI с семью слотами. Несколько кводов можно было объединить для формирования более крупного одиночного SMP-узла с аппаратно-реализованной кэш-когерентностью. Кэш-когерентное соединение, устанавливаемое между шинами, называлось IQ-Link. Оно было практически полностью прозрачно для программ, подобно обычной кэш-памяти. В традиционном смысле память в каждом кводе не была локальной; скорее, это была одна треть адресного пространства физической памяти, имевшая собственный адресный диапазон. Адресная карта распределялась по памяти равномерно, при этом каждый квод содержал смежную часть адресного пространства. Например, если требуемый адрес находился за пределами диапазона локальной памяти квода, поиск распространялся на кэш-память IQ-Link, которая называлась удаленной. Доступ к ней осуществлялся с такой же скоростью, как и к локальной памяти квода. Если и в кэш-памяти IQ-Link данные не удавалось найти, отсылался запрос на шину IQ-Link. После того как требуемое значение загружалось из другого квода, оно сохранялось в удаленной кэш-памяти IQ-Link запрашивающего квода.

Топологии мультипроцессорных коммутационных сетей.

Типы внутренних связей.

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

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

Рис. 11.9 Мультипроцессорная система со слабо связанными процессорами (многомашинный вычислительный комплекс).

Рис. 11.10 Мультипроцессорная система с сильно связанными процессорами.

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

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

11.10 Организация «главный — подчиненный»

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

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

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

Статические и динамические коммуникаторы.

С миру по нитке…

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

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

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

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

Во многих системах (EXPRESS, PVM, P4, PARMACS и др.) механизм задач реализуется с помощью библиотечных вызовов. Накоплен большой опыт использования подобных систем; предпринимаются попытки унификации. Проект стандарта MPI (Message Passing Interface) [13] представляет собой стандартный набор библиотечных интерфейсов для передачи сообщений.

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

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

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

Характеристики

Список файлов ответов (шпаргалок)