СКИПОДы 2007 полная версия (1127795), страница 26
Текст из файла (страница 26)
Данныйалгоритм расширяет миграционный алгоритм механизмом размножения блоков данных,позволяя либо многим узлам иметь возможность одновременного доступа по чтению, либоодному узлу иметь возможность читать и писать данные (протокол многих читателей иодного писателя). Производительность повышается за счет возможности одновременногодоступа по чтению, но запись требует серьезных затрат для уничтожения всех устаревшихкопий блока данных или их коррекции.При использовании такого алгоритма требуется отслеживать расположение всех блоковданных и их копий. Например, каждый собственник блока может отслеживатьрасположение его копий.Данный алгоритм может снизить среднюю стоимость доступа по чтению тогда, когдаколичество чтений значительно превышает количество записей.6.2.4 Алгоритм полного размноженияЭтот алгоритм является расширением предыдущего алгоритма.
Он позволяет многим узламиметь одновременный доступ к разделяемым данным на чтение и запись (протокол многихчитателей и многих писателей). Поскольку много узлов могут писать данные параллельно,требуется для поддержания согласованности данных контролировать доступ к ним.Одним из способов обеспечения консистентности данных является использованиеспециального процесса для упорядочивания модификаций памяти. Все узлы, желающиемодифицировать разделяемые данные должны посылать свои модификации этомупроцессу. Он будет присваивать каждой модификации очередной номер и рассылать егошироковещательно вместе с модификацией всем узлам, имеющим копиюмодифицируемого блока данных.
Каждый узел будет осуществлять модификации в порядкевозрастания их номеров. Разрыв в номерах полученных модификаций будет означатьпотерю одной или нескольких модификаций. В этом случае узел может запроситьнедостающие модификации.Все перечисленные алгоритмы являются неэффективными.
Добиться эффективности можнотолько изменив семантику обращений к памяти.6.5.1 Страничная DSMОбщая память разбивается на порции одинаковой длины - страницы или блоки. Есливыбрать длину совпадающей (или кратной) длине страницы оперативной памяти82процессоров (если их память страничная), то можно будет воспользоваться механизмомзащиты памяти для обнаружения отсутствующих страниц 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 на всех процессорах при выходе из цикла должно быть присвоено тозначение, которое было получено на витке цикла с максимальным номером (требуетсяфиксировать на каждом процессоре максимальный номер витка, на котором переменнойприсваивается значение.
При распределении витков последовательными блоками междупроцессорами достаточно фиксировать сам факт изменения переменной каждымпроцессором).83Вне цикла приведение в консистентное состояние переменной A[izer] не требуется,поскольку на каждом процессоре выполняется один и тот же оператор, которыйприсваивает одно и то же значение всем копиям переменной.6.5.3 DSM на базе объектовПоследнюю группу образуют многопроцессорные системы с объектной организациейраспределенной общей памятью.
В отличие от всех остальных рассмотренных систем,программы для объектно-ориентированной DSM системы не могут напрямую использоватьобщие переменные, а только через специальные функции-методы. Система поддержкивыполнения параллельных программ, получив запрос на использование некоторой общейпеременной, обрабатывает его, поддерживая при этом консистентное состояниеразделяемых данных. Весь контроль осуществляется только программными средствами.Втех случаях, когда для балансировки загрузки процессоров применяется миграция данных,воспользоваться соседством расположения данных в локальной памяти процессоразатруднительно.В таких случаях потери эффективности из-за доступа к данным через функции могут бытьвполне приемлемыми, поскольку они могут сполна компенсироваться тем выигрышем,который достигается балансировкой загрузки.Когерентность данных.Несколько процессоров могут разделять доступ к одной и той же памяти, если имобеспечена широкая полоса пропускания за счет использования большой многоуровневойкэш-памяти.
Поскольку процессоры одновременно работают с данными, хранящимися вединой памяти узла, в подобной архитектуре обязательно должен быть механизмподдержки когерентности данных. Когерентность данных означает, что в любой моментвремени для каждого элемента данных во всей памяти узла существует только одно егозначение, несмотря на то, что одновременно могут существовать несколько копий элементаданных, расположенных в разных видах памяти и обрабатываемых разными процессорами.Механизм когерентности должен следить за тем, чтобы операции с одним и тем жеэлементом данных выполнялись на разных процессорах последовательно, удаляя, вчастности, устаревшие копии.
В современных SMP-архитектурах когерентностьреализуется аппаратными средствами.Известны два основных класса протоколов когерентности кэш-памяти, один из которыхстроится на основе справочника (directory based). В этом случае информация о состоянииблока физической памяти содержится только в одном месте, называемом справочником(физически справочник может быть распределен по узлам системы). В протоколахнаблюдения (snooping) каждая кэш-память, которая содержит копию данных некоторогоблока физической памяти, имеет соответствующую копию служебной информации о еесостоянии.
Централизованная система записей отсутствует. Обычно кэш-памятьрасположена на общей (разделяемой) шине, и все ее контроллеры наблюдают за шиной(просматривают ее), чтобы определить, не содержат ли они копию соответствующего блока.В мультипроцессорных системах, где применяются процессоры с кэш-памятью,подсоединенные к централизованной общей памяти, популярны протоколы наблюдения,поскольку для опроса состояния кэш-памяти они могут использовать уже существующеефизическое соединение (шину памяти). Кэширование на основе каталога удваиваетпропускную способность шины, но требует более сложных аппаратных средств и вызываетдополнительные задержки при пересылке данных между памятью и обеими шинами.84В отличие от классической архитектуры NUMA, при использовании кэш-когерентногодоступа к неоднородной памяти - ccNUMA (cache coherent NUMA) все процессорыобъединены в один узел (рис. 2), причем первый уровень иерархии памяти образует их кэшпамять, а ccNUMA поддерживает когерентность внутри узла аппаратно.
В системахccNUMA распределенная память представляется единым адресным пространством. Непроисходит никакого копирования страниц или данных. Нет программной передачисообщений для синхронизации доступа. Есть просто единый массив памяти (хотяфизически он состоит из отдельных частей). Аппаратная когерентность кэш-памятиозначает, что не требуется никакого ПО для поддержки актуальности множества копийданных. Все это выполняется на аппаратном уровне так же, как в любом SMP-узле, с однимэкземпляром ОС и множеством процессоров. В свою очередь NUMA-Q - это, по сути,реализация архитектуры ccNUMA компанией Sequent.Элементарным блоком платформы NUMA-Q (рис. 3) служил квод (quad), в которомобъединялись четыре процессора, блок разделяемой памяти и шина PCI с семью слотами.Несколько кводов можно было объединить для формирования более крупного одиночногоSMP-узла с аппаратно-реализованной кэш-когерентностью.
Кэш-когерентное соединение,устанавливаемое между шинами, называлось IQ-Link. Оно было практически полностьюпрозрачно для программ, подобно обычной кэш-памяти. В традиционном смысле память вкаждом кводе не была локальной; скорее, это была одна треть адресного пространствафизической памяти, имевшая собственный адресный диапазон. Адресная картараспределялась по памяти равномерно, при этом каждый квод содержал смежную частьадресного пространства. Например, если требуемый адрес находился за пределамидиапазона локальной памяти квода, поиск распространялся на кэш-память IQ-Link, котораяназывалась удаленной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
