Э. Таненбаум - Архитектура компьютера (1127755), страница 177
Текст из файла (страница 177)
При наличии нескольких запросов от нескольких пользователей для обработки каждого запроса задействуется разное количество процессоров на разное время. Поэтому кластеру необходим планировщик, определяющий, когда запускать каждое из заданий. В простейшей модели планировщику заданий достаточно знать, сколько процессоров требуется для выполнения каждого задания. В этой модели задания выстраиваются строго в порядке НЕО (рис.
8.38, а). Когда первое задание начинает выполняться, планировщик проверяет, достаточно ли процессоров для выполнения следующего по порядку задания. Если да, то оно тоже начинает выполняться, и т. д. Если нет, то система ждет, пока не освободится достаточное количество процессоров. В нашем примере кластер содержит 8 процессоров, но он вполне мог бы содержать 128 в блоках по 16 штук (получилось бы 8 групп процессоров), или в какой-нибудь другой комбинации.
Группа процессоров Группа процессоров Группа процессоров я а й Ш Рис. 8.38. Выполнение заданий в кластере (серым цветом показаны простаивающие процессоры]: в порядке Р)ГО (е); без блокирования начала очереди (б); путем заполнения прямоугольника в системе координат процессоры — время (в) В более сложном алгоритме планирования удается избежать блокирования начала очереди. В этом случае все задания, для которых не хватает процессоров, пропускаются, а на выполнение ставится первое же задание, процессоров для которого достаточно. Всякий раз, когда завершается выполнение задания, очередь из оставшихся заданий проверяется в порядке НЕО (рис.
8.38, б). Еще более сложный алгоритм требует, чтобы заранее было известно, сколько процессоров нужно для выполнения каждого задания и сколько времени на это потребуется. Располагая этой информацией, планировщик заданий может попытаться заполнить заданиями прямоугольник в системе координат процессоры— время (рис.
8.38, в). Это особенно эффективно, когда задания получены днем, а выполняться должны ночью. В этом случае планировщик заданий получает всю необходимую информацию заранее, и может выполнять задания в опти- мальном порядке. ьзультикомпьютеры 691 Общая память на прикладном уровне Из наших примеров видно, что мультикомпьютеры поддаются масштабированию гораздо лучше, чем мультипроцессоры. Этот факт привел к возникновению систем передачи сообщений, таких как МР1. Многим программистам эта модель не нравится, и они предпочли бы иметь иллюзию общей памяти, даже если ее на самом деле не существует.
Если бы удалось достичь этой цели, это было бы прекрасно во всех отношениях: и в отношении удешевления аппаратуры (по крайней мере, на уровне каждого узла), и в отношении удобства программирования. Можно сказать, что это был бы Священный Грааль параллельных вычислений. Многие исследователи пришли к выводу, что общую память не обязательно строить на архитектурном уровне — существуют другие пути. Из рис. 8.17 видно, что есть несколько уровней, на которых можно организовать общую память. Далее мы узнаем, как ввести общую память в программную модель мультикомпьютера, если аппаратно она не поддерживается. Распределенная общая память Один из классов систем с общей памятью на прикладном уровне — это системы со страничной организацией памяти.
Этот класс систем известен под аббревиатурой 1)ЯМ (Ейзгг1Ьцтег1 8Ьагес1 Мепюгу — распределенная общая память). Идея проста: ряд процессоров в мультикомпьютере совместно используют общее виртуальное адресное пространство со страничной организацией. Самый простой вариант — каждая страница хранится в ОЗУ только одного процессора. На рис. 8.39, а мы видим общее виртуальное адресное пространство, которое состоит из 16 страниц, распределенных между четырьмя процессорами. Когда процессор обращается к странице в своем локальном ОЗУ, чтение и запись происходят без задержки. Если же процессор обращается к странице другого ОЗУ, происходит ошибка отсутствия страницы.
Однако вместо того чтобы искать отсутствующую страницу на диске, операционная система посылает сообщение в узел, в котором находится данная страница, чтобы извлечь ее из локального адресного пространства и отправить по назначению. После получения страницы она снова отображается на память, а приостановленная команда выполняется заново, как и при обычной ошибке отсутствия страницы. На рисунке 8.39, б мы видим ситуацию после того, как процессор 0 получил ошибку отсутствия страницы 10, после чего та была передана из процессора 1 в процессор О.
Впервые идея была реализована в машине?Ъ'У (1271. В ней мультикомпьютер обладает полнофункциональной секвенциально состоятельной общей памятью. В целях повышения производительности возможны разнообразные варианты оптимизации. Первая оптимизация в 1УУ вЂ” страницы, предназначенные только для чтения, могли присутствовать одновременно в нескольких узлах. В случае ошибки отсутствия страницы в запрашивающую машину посылается копия этой страницы, но оригинал остается на месте, поскольку нет никакой опасности конфликтов. На рис. 8.39, в показана ситуация, когда два процессора совместно используют общую страницу 10, предназначенную только для чтения. Но даже при такой оптимизации трудно достичь высокой производительности, особенно когда один процесс записывает несколько слов в верхней части какой-либо страницы, а другой процесс на другом процессоре в это же время запи- 692 Глава 8. Параллельные компьютерные архитектуры сывает несколько слов в нижней части той же страницы.
Поскольку разрешено существование только одной копии атой страницы, страница постоянно должна передаваться туда и обратно. Подобная ситуация называется мнимым разделением. Глобальная виртуальная общая память из 16 страниц Память Рис. 8.38. Виртуальное адресное пространство из 16 страниц, распределенных между четырьмя узлами мультикомпыютера: исходное состояние (а); состояние после обращения процессора 0 к странице 10 (б); состояние после обращения процессора 1 к странице 10, предназначенной только для чтения (в) Проблему мнимого разделения можно решать по-разному. Например, можно отказаться от секвенцизльной состоятельности в пользу свободной состоятельности [91 В случае свободной состоятельности страницы, которые потенциально пригодны для записи, могут одновременно присутствовать на нескольких узлах, но перед записью процесс должен совершить операцию асцв( ге, чтобы сообщить Мупьтикомпьютеры 693 о своем намерении.
В этот момент все копии, кроме последней, объявляются недействительными, и до выполнения операции ге1еазе никаких копий создавать нельзя. После выполнения операции ге1еазе страница вновь становится общедоступной. Во втором варианте оптимизации предполагается, что изначально все страницы отображаются на память в режиме только чтения. Когда запись в страницу производится впервые, система создает копию страницы, называемую двойником. Затем исходная страница отображается на память в формате, пригодном для чтения и записи, после чего последующие записи могут производиться без задержек.
Если на удаленном узле происходит ошибка отсутствия страницы, что означает необходимость передачи туда модифицированной страницы, сначала выполняется пословное сравнение текущей страницы с ее двойником. После этого на удаленный узел передаются только те слова, которые были модифицированы, а не вся страница, что сокращает размер сообщений.
После возникновения ошибки отсутствия страницы нужно определить, где ее искать. Здесь возможны разные подходы, в том числе использовать каталоги, как в Х1)МА- и СОМА-машинах. Многие решения, применяемые в ?ЭБМ, пригодны и для Х?1МА- и СОМА-машин, поскольку ПБМ вЂ” это программная реализация таких машин, в которой каждая страница трактуется как строка каша. ПБМ по-прежнему остается ареной активных исследований. Большой интерес представляют системы САБНМЕКЕ 1117, 196], СКЕ 1104], БЬаз?а 1182] и Тгеас?- шаг?гз 19, 130]. Бпла Системы ПБМ со страничной организацией памяти (такие как 1Ъ'У и Тгеайпаг?гз) используют диспетчера памяти, чтобы аппаратно перехватывать доступ к отсутствующим страницам.
Хотя подготовка и пересылка только различающихся слов вместо всей страницы положительно сказывается на производительности, страницы остаются неудобными объектами совместного использования, поэтому применяются и другие подходы. Один из таких подходов реализован в система ?лпое, в которой процессы на разных машинах получают в свое распоряжение высокоструктурированную распределенную общую память 137]. Доступ к этой памяти осуществляется с помощью минимального набора примитивов, которые можно включать в существующие языки (например, в С или РОСТКАХ), в результате формируются так называемые параллельные языки — в данном случае это С-?лпоа и РОСТКАХ-?аида. В основе системы ?зпба лежит понятие абстрактного пространства кортежей, которое глобально по отношению ко всей системе и доступно всем процессам этой системы.
Пространство кортежей похоже на глобальную общую память, только с определенной внутренней структурой. Каждый из кортежей в пространстве кортежей состоит из одного или нескольких полей. В С-?1пг?а поля могут содержать целые, длинные целые и числа с плавающей точкой, а также сложные типы данных, например массивы (в том числе символьные строки) и структуры (но не другие кортежи).
В листинге 8.1. приведено 3 примера кортежей. 694 Глава 8. Параллельные компьютерные архитектуры Листинг 8.1. Кортежи в Е)лг)в СЬЬс". 2, 5) Г"паапх-1", 1, 5, 3.)а) Стаю 1у", ")а а)а1ег", Саго)уп. Е1апог) С кортежами можно выполнять 4 операции. Первая из них, оцЬ, вводит кортеж в пространство кортежей. Например: оогыаЬс". 2. 5): Эта операция вводит кортеж ("аЬс", 2, 5) в пространство кортежей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
