ПОД (пособие) (1184372), страница 27
Текст из файла (страница 27)
Клиенты могут использовать тайм-аут для посылкиповторных запросов при отсутствии ответа сервера. Дубликаты запросов на запись могутраспознаваться путем нумерации запросов. Если несколько повторных обращений к серверуостались без ответа, приложение получит отрицательный код ответа (это обеспечит клиент).Алгоритм прост в реализации, но сервер может стать узким местом.Чтобы избежать этого, разделяемые данные могут быть распределены между несколькимисерверами. В этом случае клиент должен уметь определять, к какому серверу надообращаться при каждом доступе к разделяемой переменной.
Посылка запросов сразу всемсерверам нежелательна, поскольку не снижает нагрузку на серверы. Лучшее решение распределить данные в зависимости от их адресов и использовать функцию отображениядля определения нужного сервера.6.2.2 Миграционный алгоритмВ отличие от предыдущего алгоритма, когда запрос к данным направлялся в место ихрасположения, в этом алгоритме меняется расположение данных - они перемещаются в томесто, где потребовались. Это позволяет последовательные обращения к даннымосуществлять локально. Миграционный алгоритм позволяет обращаться к одному элементуданных в любой момент времени только одному узлу.Обычно мигрирует целиком страницы или блоки данных, а не запрашиваемые единицыданных.
Это позволяет воспользоваться присущей приложениям локальностью доступа кданным для снижения стоимости миграции. Однако, такой подход приводит к трэшингу,когда страницы очень часто мигрируют между узлами при малом количествеобслуживаемых запросов. Некоторые системы позволяют задать время, в течение которогостраница насильно удерживается в узле для того, чтобы успеть выполнить несколькообращений к ней до миграции ее в другой узел.81Миграционный алгоритм позволяет интегрировать DSM с виртуальной памятью,обеспечивающейся операционной системой в отдельных узлах. Если размер страницы DSMсовпадает с размером страницы виртуальной памяти (или кратен ей), то можно обращатьсяк разделяемой памяти обычными машинными командами, воспользовавшись аппаратнымисредствами проверки наличия в оперативной памяти требуемой страницы и заменывиртуального адреса на физический.
Конечно, для этого виртуальное адресное пространствопроцессоров должно быть достаточно, чтобы адресовать всю разделяемую память. Приэтом, несколько процессов в одном узле могут разделять одну и ту же страницу.Для определения места расположения блоков данных миграционный алгоритм можетиспользовать сервер, отслеживающий перемещения блоков, либо воспользоватьсямеханизмом подсказок в каждом узле. Возможна и широковещательная рассылка запросов.6.2.3 Алгоритм размножения для чтенияПредыдущий алгоритм позволял обращаться к разделяемым данным в любой моментвремени только процессам в одном узле (в котором эти данные находятся). Данныйалгоритм расширяет миграционный алгоритм механизмом размножения блоков данных,позволяя либо многим узлам иметь возможность одновременного доступа по чтению, либоодному узлу иметь возможность читать и писать данные (протокол многих читателей иодного писателя).
Производительность повышается за счет возможности одновременногодоступа по чтению, но запись требует серьезных затрат для уничтожения всех устаревшихкопий блока данных или их коррекции.При использовании такого алгоритма требуется отслеживать расположение всех блоковданных и их копий. Например, каждый собственник блока может отслеживатьрасположение его копий.Данный алгоритм может снизить среднюю стоимость доступа по чтению тогда, когдаколичество чтений значительно превышает количество записей.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) все процессорыобъединены в один узел (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
