Многопроцессорные системы
9.1. Общие требования, предъявляемые к МПС

Отношение стоимость / производительность. Появление любого нового направления в вычислительной технике определя-ется требованиями компьютерного рынка. Поэтому у разработчиков компьютеров нет одной единственной цели. Большая универсальная вычислительная машина (мейнфрейм) или суперкомпью-тер стоят дорого. Для достижения поставленных целей при проектировании высокопроизводительных конструкций приходится иг-норировать стоимостные характеристики.
Суперкомпьютеры фирмы Cray Research и высокопроизводительные мейнфреймы компании IBM относятся именно к этой категории компьютеров. Другим крайним примером может служить низкостоимостная кон-струкция, где производительность принесена в жертву для дости-жения низкой стоимости. К этому направлению относятся персо-нальные компьютеры различных клонов IBM PC. Между этими двумя крайними направлениями находятся конструкции, основан-ные на отношении стоимость/ производительность, в которых раз-работчики находят баланс между стоимостными параметрами и производительностью. Типичными примерами такого рода ком-пьютеров являются миникомпьютеры и рабочие станции.
Для сравнения различных компьютеров между собой обычно используются стандартные методики измерения произво-дительности. Эти методики позволяют разработчикам и пользова-телям использовать полученные в результате испытаний количест-венные показатели для оценки тех или иных технических решений, и в конце концов именно производительность и стоимость дают пользователю рациональную основу для решения вопроса, какой компьютер выбрать.
Надежность и отказоустойчивость. Важнейшей ха-рактеристикой вычислительных систем является надежность. По-вышение надежности основано на принципе предотвращения не-исправностей путем снижения интенсивности отказов и сбоев за счет применения электронных схем и компонентов с высокой и сверхвысокой степенью интеграции, снижения уровня помех, об-легченных режимов работы схем, обеспечение тепловых режимов их работы, а также за счет совершенствования методов сборки аппаратуры.
Отказоустойчивость - это такое свойство вычислительной системы, которое обеспечивает ей, как логической машине, воз-можность продолжения действий, заданных программой, после возникновения неисправностей. Введение отказоустойчивости требует избыточного аппаратного и программного обеспечения. Направления, связанные с предотвращением неисправностей и с отказоустойчивостью, - основные в проблеме надежности. Кон-цепции параллельности и отказоустойчивости вычислительных систем естественным образом связаны между собой, поскольку в обоих случаях требуются дополнительные функциональные ком-поненты. Поэтому, собственно, на параллельных вычислительных системах достигается как наиболее высокая производительность, так и, во многих случаях, очень высокая надежность. Имеющиеся ресурсы избыточности в параллельных системах могут гибко ис-пользоваться как для повышения производительности, так и для повышения надежности. Структура многопроцессорных и много-машинных систем приспособлена к автоматической реконфигура-ции и обеспечивает возможность продолжения работы системы после возникновения неисправностей.
Следует помнить, что понятие надежности включает не только аппаратные средства, но и программное обеспечение. Главной целью повышения надежности систем является целост-ность хранимых в них данных.
Масштабируемость. Масштабируемость представляет собой возможность наращивания числа и мощности процессоров, объемов оперативной и внешней памяти и других ресурсов вычислительной системы. Масштабируемость должна обеспечи-ваться архитектурой и конструкцией компьютера, а также соот-ветствующими средствами программного обеспечения.
Добавление каждого нового процессора в действительно масштабируемой системе должно давать прогнозируемое увеличе-ние производительности и пропускной способности при приемле-мых затратах. Одной из основных задач при построении масшта-бируемых систем является минимизация стоимости расширения компьютера и упрощение планирования. В идеале добавление процессоров к системе должно приводить к линейному росту ее производительности. Однако это не всегда так. Потери производи-тельности могут возникать, например, при недостаточной пропу-скной способности шин из-за возрастания трафика между процес-сорами и основной памятью, а также между памятью и устройст-вами ввода/вывода. В действительности реальное увеличение про-изводительности трудно оценить заранее, поскольку оно в значи-тельной степени зависит от динамики поведения прикладных задач.
Возможность масштабирования системы определяется не только архитектурой аппаратных средств, но зависит от заложен-ных свойств программного обеспечения. Масштабируемость про-граммного обеспечения затрагивает все его уровни от простых ме-ханизмов передачи сообщений до работы с такими сложными объ-ектами как мониторы транзакций и вся среда прикладной системы. В частности, программное обеспечение должно минимизировать трафик межпроцессорного обмена, который может препятствовать линейному росту производительности системы. Аппаратные сред-ства (процессоры, шины и устройства ввода/вывода) являются только частью масштабируемой архитектуры, на которой про-граммное обеспечение может обеспечить предсказуемый рост производительности. Важно понимать, что простой переход, на-пример, на более мощный процессор может привести к перегрузке других компонентов системы. Это означает, что действительно масштабируемая система должна быть сбалансирована по всем па-раметрам.
Совместимость и мобильность программного обеспе-чения. Концепция программной совместимости впервые в ши-роких масштабах была применена разработчиками системы IBM/360. Основная задача при проектировании всего ряда моде-лей этой системы заключалась в создании такой архитектуры, ко-торая была бы одинаковой с точки зрения пользователя для всех моделей системы независимо от цены и производительности ка-ждой из них. Огромные преимущества такого подхода, позво-ляющего сохранять существующий задел программного обеспе-чения при переходе на новые (как правило, более производитель-ные) модели были быстро оценены как производителями компь-ютеров, так и пользователями и начиная с этого времени практи-чески все фирмы-поставщики компьютерного оборудования взя-ли на вооружение эти принципы, поставляя серии совместимых компьютеров. Следует заметить однако, что со временем даже самая передовая архитектура неизбежно устаревает и возникает потребность внесения радикальных изменений архитектуру и способы организации вычислительных систем.
В настоящее время одним из наиболее важных факторов, определяющих современные тенденции в развитии информацион-ных технологий, является ориентация компаний-поставщиков компьютерного оборудования на рынок прикладных программных средств. Это объясняется прежде всего тем, что для конечного пользователя в конце концов важно программное обеспечение, по-зволяющее решить его задачи, а не выбор той или иной аппаратной платформы. Переход от однородных сетей программно со-вместимых компьютеров к построению неоднородных сетей, включающих компьютеры разных фирм-производителей, в корне изменил и точку зрения на саму сеть: из сравнительно простого средства обмена информацией она превратилась в средство инте-грации отдельных ресурсов - мощную распределенную вычисли-тельную систему, каждый элемент которой (сервер или рабочая станция) лучше всего соответствует требованиям конкретной при-кладной задачи.
Этот переход выдвинул ряд новых требований. Прежде всего такая вычислительная среда должна позволять гибко менять количество и состав аппаратных средств и программного обеспе-чения в соответствии с меняющимися требованиями решаемых за-дач. Во-вторых, она должна обеспечивать возможность запуска одних и тех же программных систем на различных аппаратных платформах, т.е. обеспечивать мобильность программного обеспе-чения. В третьих, эта среда должна гарантировать возможность применения одних и тех же человеко-машинных интерфейсов на всех компьютерах, входящих в неоднородную сеть. В условиях жесткой конкуренции производителей аппаратных платформ и программного обеспечения сформировалась концепция открытых систем, представляющая собой совокупность стандартов на раз-личные компоненты вычислительной среды, предназначенных для обеспечения мобильности программных средств в рамках неодно-родной, распределенной вычислительной системы.
Одним из вариантов моделей открытой среды является мо-дель OSE (Open System Environment), предложенная комитетом IEEE POSIX. На основе этой модели национальный институт стан-дартов и технологии США выпустил документ "Application Portability Profile (APP). The U.S. Government's Open System Environment Profile OSE/1 Version 2.0", который определяет реко-мендуемые для федеральных учреждений США спецификации в области информационных технологий, обеспечивающие мобиль-ность системного и прикладного программного обеспечения. Все ведущие производители компьютеров и программного обеспече-ния в США в настоящее время придерживаются требований этого документа.

9.2. Классификация систем параллельной обработки данных
На протяжении всей истории развития вычислительной техники делались попытки найти какую-то общую классифика-цию, под которую подпадали бы все возможные направления раз-вития компьютерных архитектур. Ни одна из таких классификаций не могла охватить все разнообразие разрабатываемых архитектур-ных решений и не выдерживала испытания временем. Тем не ме-нее в научный оборот попали и широко используются ряд терми-нов, которые полезно знать не только разработчикам, но и пользо-вателям компьютеров.
Любая вычислительная система (будь то супер-ЭВМ или персональный компьютер) достигает своей наивысшей производи-тельности благодаря использованию высокоскоростных элементов и параллельному выполнению большого числа операций. Именно возможность параллельной работы различных устройств системы (работы с перекрытием) является основой ускорения основных операций.
Параллельные ЭВМ часто подразделяются по классифика-ции Флинна на машины типа SIMD и MIMD. Как и любая другая, приведенная выше классификация несовершенна: существуют машины прямо в нее не попадающие, имеются также важные при-знаки, которые в этой классификации не учтены. В частности, к машинам типа SIMD часто относят векторные процессоры, хотя их высокая производительность зависит от другой формы паралле-лизма - конвейерной организации машины. Многопроцессорные векторные системы, типа Cray Y-MP, состоят из нескольких век-торных процессоров и поэтому могут быть названы MSIMD (Multiple SIMD).
Классификация Флинна не делает различия по другим важ-ным для вычислительных моделей характеристикам, например, по уровню "зернистости" параллельных вычислений и методам син-хронизации.
Можно выделить четыре основных типа архитектуры сис-тем параллельной обработки:
- конвейерная и векторная обработка. Основу конвей-ерной обработки составляет раздельное выполнение некоторой операции в несколько этапов (за несколько ступеней) с передачей данных одного этапа следующему. Производительность при этом возрастает благодаря тому, что одновременно на различных сту-пенях конвейера выполняются несколько операций.
Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых операндов соответствует максимальной производительности конвейера. Если происходит задержка, то параллельно будет выполняться меньше операций и суммарная производительность снизится. Векторные операции обеспечивают идеальную возможность полной загрузки вычислительного конвейера.
При выполнении векторной команды одна и та же операция применяется ко всем элементам вектора (или чаще всего к соот-ветствующим элементам пары векторов). Для настройки конвейера на выполнение конкретной операции может потребоваться неко-торое установочное время, однако затем операнды могут посту-пать в конвейер с максимальной скоростью, допускаемой возмож-ностями памяти. При этом не возникает пауз ни в связи с выбор-кой новой команды, ни в связи с определением ветви вычислений при условном переходе. Таким образом, главный принцип вычис-лений на векторной машине состоит в выполнении некоторой эле-ментарной операции или комбинации из нескольких элементарных операций, которые должны повторно применяться к некоторому блоку данных. Таким операциям в исходной программе соответст-вуют небольшие компактные циклы.
- системы типа SIMD. Машины типа SIMD состоят из большого числа идентичных процессорных элементов, имеющих собственную память. Все процессорные элементы в такой машине выполняют одну и ту же программу. Очевидно, что такая машина, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же рабо-ту. Модель вычислений для машины SIMD очень похожа на мо-дель вычислений для векторного процессора: одиночная операция выполняется над большим блоком данных.
В отличие от ограниченного конвейерного функциони-рования векторного процессора, матричный процессор (синоним для большинства SIMD-машин) может быть значительно более гибким. Обрабатывающие элементы таких процессоров - это уни-версальные программируемые ЭВМ, так что задача, решаемая па-раллельно, может быть достаточно сложной и содержать ветвле-ния. Обычное проявление этой вычислительной модели в исход-ной программе примерно такое же, как и в случае векторных опе-раций: циклы на элементах массива, в которых значения, выраба-тываемые на одной итерации цикла, не используются на другой итерации цикла.
Модели вычислений на векторных и матричных ЭВМ на-столько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.
- системы типа MIMD. Термин "мультипроцессор" покры-вает большинство машин типа MIMD и (подобно тому, как термин "матричный процессор" применяется к машинам типа SIMD) часто используется в качестве синонима для машин типа MIMD. В муль-типроцессорной системе каждый процессорный элемент (ПЭ) вы-полняет свою программу достаточно независимо от других про-цессорных элементов.
Процессорные элементы, конечно, должны как-то связы-ваться друг с другом, что делает необходимым более подробную классификацию машин типа MIMD. В мультипроцессорах с общей памятью (сильносвязанных мультипроцессорах) имеется память данных и команд, доступная всем ПЭ. С общей памятью ПЭ свя-зываются с помощью общей шины или сети обмена. В противопо-ложность этому варианту в слабосвязанных многопроцессорных системах (машинах с локальной памятью) вся память делится ме-жду процессорными элементами и каждый блок памяти доступен только связанному с ним процессору. Сеть обмена связывает про-цессорные элементы друг с другом.
Базовой моделью вычислений на MIMD-мультипроцессоре является совокупность независимых процессов, эпизодически об-ращающихся к разделяемым данным. Существует большое коли-чество вариантов этой модели. На одном конце спектра - модель распределенных вычислений, в которой программа делится на довольно большое число параллельных задач, состоящих из мно-жества подпрограмм. На другом конце спектра - модель потоко-вых вычислений, в которых каждая операция в программе может рассматриваться как отдельный процесс. Такая операция ждет своих входных данных (операндов), которые должны быть пере-даны ей другими процессами. По их получении операция выпол-няется, и полученное значение передается тем процессам, которые в нем нуждаются. В потоковых моделях вычислений с большим и средним уровнем гранулярности, процессы содержат большое число операций и выполняются в потоковой манере.
- многопроцессорные системы с SIMD-процессорами. Многие современные супер-ЭВМ представляют собой многопро-цессорные системы, в которых в качестве процессоров использу-ются векторные процессоры или процессоры типа SIMD. Такие системы относятся к машинам класса MSIMD.
Языки программирования и соответствующие компиляторы для машин типа MSIMD обычно обеспечивают языковые конст-рукции, которые позволяют программисту описывать "крупнозер-нистый" параллелизм. В пределах каждой задачи компилятор ав-томатически векторизует подходящие циклы. Машины типа MSIMD, как можно себе представить, дают возможность исполь-зовать лучший из этих двух принципов декомпозиции: векторные операции ("мелкозернистый" параллелизм) для тех частей про-граммы, которые подходят для этого, и гибкие возможности MIMD-архитектуры для других частей программы.
Многопроцессорные системы за годы развития вычисли-тельной техники претерпели ряд этапов своего развития. Истори-чески первой стала осваиваться технология SIMD. Однако в на-стоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факто-рами:
- архитектура MIMD дает большую гибкость: при наличии адекватной поддержки со стороны аппаратных средств и про-граммного обеспечения MIMD может работать как однопользова-тельская система, обеспечивая высокопроизводительную обработ-ку данных для одной прикладной задачи, как многопрограммная машина, выполняющая множество задач параллельно, и как не-которая комбинация этих возможностей.
- архитектура MIMD может использовать все преимущества современной микропроцессорной технологии на основе строгого учета соотношения стоимость/производительность. В действи-тельности практически все современные многопроцессорные сис-темы строятся на тех же микропроцессорах, которые можно найти в персональных компьютерах, рабочих станциях и небольших од-нопроцессорных серверах.
Одной из отличительных особенностей многопроцессорной вычислительной системы является сеть обмена, с помощью кото-рой процессоры соединяются друг с другом или с памятью. Мо-дель обмена настолько важна для многопроцессорной системы, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, соответствующим решаемым задачам. Существуют две основные модели межпроцессорного обмена: одна основана на передаче со-общений, другая - на использовании общей памяти.
В многопроцессорной системе с общей памятью один про-цессор осуществляет запись в конкретную ячейку, а другой про-цессор производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом "почтового ящика".
В архитектурах с локальной памятью непосредственное разделение памяти невозможно. Вместо этого процессоры полу-чают доступ к совместно используемым данным посредством пе-редачи сообщений по сети обмена. Эффективность схемы комму-никаций зависит от протоколов обмена, основных сетей обмена и пропускной способности памяти и каналов обмена.
Часто, и притом необосновано, в машинах с общей памятью и векторных машинах затраты на обмен не учитываются, так как проблемы обмена в значительной степени скрыты от программи-ста. Однако накладные расходы на обмен в этих машинах имеются и определяются конфликтами шин, памяти и процессоров. Чем больше процессоров добавляется в систему, тем больше процессов соперничают при использовании одних и тех же данных и шины, что приводит к состоянию насыщения. Модель системы с об-щей памятью очень удобна для программирования и иногда рас-сматривается как высокоуровневое средство оценки влияния об-мена на работу системы, даже если основная система в действи-тельности реализована с применением локальной памяти и прин-ципа передачи сообщений.
В сетях с коммутацией каналов и в сетях с коммутацией па-кетов по мере возрастания требований к обмену следует учитывать возможность перегрузки сети. Здесь межпроцессорный обмен свя-зывает сетевые ресурсы: каналы, процессоры, буферы сообщений. Объем передаваемой информации может быть сокращен за счет тщательной функциональной декомпозиции задачи и тщательного диспетчирования выполняемых функций.
Таким образом, существующие MIMD-машины распадают-ся на два основных класса в зависимости от количества объеди-няемых процессоров, которое определяет и способ организации памяти и методику их межсоединений.
К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обыч-но менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизо-ванную общую память и объединить процессоры и память с по-мощью одной шины. При наличии у процессоров кэш-памяти дос-таточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от не-скольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис. 66.
Вторую группу машин составляют крупномасштабные сис-темы с распределенной памятью. Для того чтобы поддерживать большое количество процессоров приходится распределять основ-ную память между ними, в противном случае полосы пропускания памяти просто может не хватить для удовлетворения запросов, по-ступающих от очень большого числа процессоров. Естественно при таком подходе также требуется реализовать связь процес-соров между собой. На рис. 67 показана структура такой системы.

Рис. 66

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

Рис. 67

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

9.3. Модели связи и архитектуры памяти
Как уже было отмечено, любая крупномасштабная много-процессорная система должна использовать множество устройств памяти, которые физически распределяются вместе с процессора-ми. Имеется две альтернативных организации адресации этих уст-ройств памяти и связанных с этим два альтернативных метода для передачи данных между процессорами. Физически отдельные уст-ройства памяти могут адресоваться как логически единое адресное пространство, что означает, что любой процессор может выпол-нять обращения к любым ячейкам памяти, предполагая, что он имеет соответствующие права доступа. Такие машины называются машинами с распределенной разделяемой (общей) памятью (DSM - distributed shared memory), масштабируемые архитектуры с раз-деляемой памятью, а иногда NUMA's - Non-Uniform Memory Access, поскольку время доступа зависит от расположения ячейки в памяти.
В альтернативном случае, адресное пространство состоит из отдельных адресных пространств, которые логически не связа-ны и доступ к которым не может быть осуществлен аппаратно другим процессором. В таком примере каждый модуль процессор-память представляет собой отдельный компьютер, поэтому такие системы называются многомашинными (multicomputers).
С каждой из этих организаций адресного пространства свя-зан свой механизм обмена. Для машины с единым адресным про-странством это адресное пространство может быть использовано для обмена данными посредством операций загрузки и записи. По-этому эти машины и получили название машин с разделяемой (общей) памятью. Для машин с множеством адресных пространств обмен данными должен использовать другой механизм: передачу сообщений между процессорами; поэтому эти машины часто на-зывают машинами с передачей сообщений.
Каждый из этих механизмов обмена имеет свои преимуще-ства. Для обмена в общей памяти это включает:
- совместимость с хорошо понятными используемыми как в однопроцессорных, так и маломасштабных многопроцессорных системах, механизмами, которые используют для обмена об-щую память.
- простота программирования, когда модели обмена между процессорами сложные или динамически меняются во время вы-полнения. Подобные преимущества упрощают конструирование компилятора.
- более низкая задержка обмена и лучшее использование полосы пропускания при обмене малыми порциями данных.
- возможность использования аппаратно управляемого кэширования для снижения частоты удаленного обмена, допус-кающая кэширование всех данных как разделяемых, так и нераз-деляемых.
Основные преимущества обмена с помощью передачи со-общений являются:
- аппаратура может быть более простой, особенно по срав-нению с моделью разделяемой памяти, которая поддерживает масштабируемую когерентность кэш-памяти.
- модели обмена понятны, принуждают программистов (или компиляторы) уделять внимание обмену, который обычно имеет высокую, связанную с ним стоимость.
Конечно, требуемая модель обмена может быть надстроена над аппаратной моделью, которая использует любой из этих меха-низмов. Поддержка передачи сообщений над разделяемой памя-тью, естественно, намного проще, если предположить, что маши-ны имеют адекватные полосы пропускания. Основные трудности возникают при работе с сообщениями, которые могут быть непра-вильно выровнены и сообщениями произвольной длины в системе памяти, которая обычно ориентирована на передачу выровненных блоков данных, организованных как блоки кэш-памяти. Эти труд-ности можно преодолеть либо с небольшими потерями производи-тельности программным способом, либо существенно без потерь при использовании небольшой аппаратной поддержки.
Построение механизмов реализации разделяемой памяти над механизмом передачи сообщений намного сложнее. Без пред-полагаемой поддержки со стороны аппаратуры все обращения к разделяемой памяти потребуют привлечения операционной систе-мы как для обеспечения преобразования адресов и защиты памяти, так и для преобразования обращений к памяти в посылку и прием сообщений. Поскольку операции загрузки и записи обычно работают с небольшим объемом данных, то большие накладные расходы по поддержанию такого обмена делают невозможной чисто программную реализацию.
При оценке любого механизма обмена критичными являют-ся три характеристики производительности:
1. Полоса пропускания: в идеале полоса пропускания меха-низма обмена будет ограничена полосами пропускания процессо-ра, памяти и системы межсоединений, а не какими-либо аспектами механизма обмена. Связанные с механизмом обмена накладные расходы (например, длина межпроцессорной связи) прямо воздей-ствуют на полосу пропускания.
2. Задержка: в идеале задержка должна быть настолько мала, насколько это возможно. Для ее определения критичны на-кладные расходы аппаратуры и программного обеспечения, свя-занные с инициированием и завершением обмена.
3. Упрятывание задержки: насколько хорошо механизм скрывает задержку путем перекрытия обмена с вычислениями или с другими обменами.
Каждый из этих параметров производительности воздейст-вует на характеристики обмена. В частности, задержка и полоса пропускания могут меняться в зависимости от размера элемента данных. В общем случае, механизм, который одинаково хорошо работает как с небольшими, так и с большими объемами данных будет более гибким и эффективным.
Таким образом, отличия разных машин с распределенной памятью определяются моделью памяти и механизмом обмена. Исторически машины с распределенной памятью первоначально были построены с использованием механизма передачи сообще-ний, поскольку это было очевидно проще и многие разработчики и исследователи не верили, что единое адресное пространство мож-но построить и в машинах с распределенной памятью. С недавнего времени модели обмена с общей памятью действительно начали поддерживаться практически в каждой разработанной машине (ха-рактерным примером могут служить системы с симметричной мультипроцессорной обработкой). Хотя машины с централизованной общей памятью, по-строенные на базе общей шины все еще доминируют в терминах размера компьютерного рынка, долговременные технические тен-денции направлены на использование преимуществ распределен-ной памяти даже в машинах умеренного размера. Как мы увидим, возможно наиболее важным вопросом, который встает при созда-нии машин с распределенной памятью, является вопрос о кэширо-вании и когерентности кэш-памяти.

9.4. Многопроцессорные системы с общей памятью
Требования, предъявляемые современными процессорами к полосе пропускания памяти можно существенно сократить путем применения больших многоуровневых кэшей. Тогда, если эти тре-бования снижаются, то несколько процессоров смогут разделять доступ к одной и той же памяти. Начиная с 1980 года эта идея, подкрепленная широким распространением микропроцессоров, стимулировала многих разработчиков на создание небольших мультипроцессоров, в которых несколько процессоров разделяют одну физическую память, соединенную с ними с помощью разде-ляемой шины.
Из-за малого размера процессоров и заметного сокращения требуемой полосы пропускания шины, достигнутого за счет воз-можности реализации достаточно большой кэш-памяти, такие ма-шины стали исключительно эффективными по стоимости. В пер-вых разработках подобного рода машин удавалось разместить весь процессор и кэш на одной плате, которая затем вставлялась в зад-нюю панель, с помощью которой реализовывалась шинная архи-тектура. Современные конструкции позволяют разместить до че-тырех процессоров на одной плате. В такой машине кэши могут содержать как разделяемые, так и частные данные. Частные дан-ные - это данные, которые используются одним процессором, в то время как разделяемые данные используются многими процессо-рами, по существу обеспечивая обмен между ними. Когда кэширу-ется элемент частных данных, их значение переносится в кэш для сокращения среднего времени доступа, а также требуемой полосы пропускания.
Поскольку никакой другой процессор не использует эти данные, этот процесс идентичен процессу для однопроцессорной машины с кэш-памятью. Если кэшируются разделяемые данные, то разделяемое значение реплицируется и может содержаться в нескольких кэшах. Кроме сокращения задержки доступа и требуе-мой полосы пропускания такая репликация данных способствует также общему сокращению количества обменов. Однако кэширо-вание разделяемых данных вызывает новую проблему: когерент-ность кэш-памяти.
Мультипроцессорная когерентность кэш-памяти. Про-блема, о которой идет речь, возникает из-за того, что значение элемента данных в памяти, хранящееся в двух разных процессо-рах, доступно этим процессорам только через их индивидуальные кэши. На рис. 68 показан простой пример, иллюстрирующий эту проблему.
Проблема когерентности памяти для мультипроцессоров и устройств ввода/вывода имеет много аспектов. Обычно в малых мультипроцессорах используется аппаратный механизм, называе-мый протоколом, позволяющий решить эту проблему. Такие про-токолы называются протоколами когерентности кэш-памяти.
Существуют два класса таких протоколов:
1. Протоколы на основе справочника (directory based). Ин-формация о состоянии блока физической памяти содержится толь-ко в одном месте, называемом справочником (физически справоч-ник может быть распределен по узлам системы). Этот подход бу-дет рассмотрен в разд. 10.3.
2. Протоколы наблюдения (snooping). Каждый кэш, кото-рый содержит копию данных некоторого блока физической памя-ти, имеет также соответствующую копию служебной информации о его состоянии. Централизованная система записей отсутствует.
Обычно кэши расположены на общей (разделяемой) шине и контроллеры всех кэшей наблюдают за шиной (просматривают ее) для определения того, не содержат ли они копию соответствующе-го блока.

Рис. 68

В мультипроцессорных системах, использующих мик-ропроцессоры с кэш-памятью, подсоединенные к централизован-ной общей памяти, протоколы наблюдения приобрели популяр-ность, поскольку для опроса состояния кэшей они могут использо-вать заранее существующее физическое соединение - шину памя-ти.
Неформально, проблема когерентности памяти состоит в необходимости гарантировать, что любое считывание элемента данных возвращает последнее по времени записанное в него зна-чение. Это определение не совсем корректно, поскольку невоз-можно требовать, чтобы операция считывания мгновенно видела значение, записанное в этот элемент данных некоторым другим процессором. Если, например, операция записи на одном процес-соре предшествует операции чтения той же ячейки на другом про-цессоре в пределах очень короткого интервала времени, то невоз-можно гарантировать, что чтение вернет записанное значение дан-ных, поскольку в этот момент времени записываемые данные мо-гут даже не покинуть процессор.
Вопрос о том, когда точно записываемое значение должно быть доступно процессору, выполняющему чтение, определяется выбранной моделью согласованного (непротиворечивого) состоя-ния памяти и связан с реализацией синхронизации параллельных вычислений. Поэтому с целью упрощения предположим, что мы требуем только, чтобы записанное операцией записи значение бы-ло доступно операции чтения, возникшей немного позже записи и что операции записи данного процессора всегда видны в порядке их выполнения.
С этим простым определением согласованного состояния памяти мы можем гарантировать когерентность путем обеспече-ния двух свойств:
1. Операция чтения ячейки памяти одним процессором, ко-торая следует за операцией записи в ту же ячейку памяти другим процессором, получит записанное значение, если операции чтения и записи достаточно отделены друг от друга по времени.
2. Операции записи в одну и ту же ячейку памяти выполня-ются строго последовательно (иногда говорят, что они сериализо-ваны): это означает, что две подряд идущие операции записи в одну и ту же ячейку памяти будут наблюдаться другими процес-сорами именно в том порядке, в котором они появляются в про-грамме процессора, выполняющего эти операции записи.
Первое свойство очевидно связано с определением коге-рентного (согласованного) состояния памяти: если бы процессор всегда бы считывал только старое значение данных, мы сказали бы, что память некогерентна.
Необходимость строго последовательного выполнения опе-раций записи является более тонким, но также очень важным свойством. Представим себе, что строго последовательное выпол-нение операций записи не соблюдается. Тогда процессор P1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор P2. Строго последовательное выполнение операций за-писи гарантирует два важных следствия для этой последователь-ности операций записи. Во-первых, оно гарантирует, что каждый процессор в машине в некоторый момент времени будет наблю-дать запись, выполняемую процессором P2. Если последователь-ность операций записи не соблюдается, то может возникнуть си-туация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессора P2, а затем операцию записи процес-сора P1, и будет хранить это записанное P1 значение неограничен-но долго.
Более тонкая проблема возникает с поддержанием разумной модели порядка выполнения программ и когерентности памяти для пользователя: представьте, что третий процессор постоянно читает ту же самую ячейку памяти, в которую записывают процес-соры P1 и P2; он должен наблюдать сначала значение, записанное P1, а затем значение, записанное P2. Возможно, он никогда не сможет увидеть значения, записанного P1, поскольку запись от P2 возникла раньше чтения. Если он даже видит значение, записанное P1, он должен видеть значение, записанное P2, при последующем чтении.
Подобным образом любой другой процессор, который мо-жет наблюдать за значениями, записываемыми как P1, так и P2, должен наблюдать идентичное поведение. Простейший способ до-биться таких свойств заключается в строгом соблюдении порядка операций записи, чтобы все записи в одну и ту же ячейку могли наблюдаться в том же самом порядке. Это свойство называется последовательным выполнением (сериализацией) операций записи (write serialization). Вопрос о том, когда процессор должен увидеть значение, записанное другим процессором достаточно сложен и имеет заметное воздействие на производительность, особенно в больших машинах.
Альтернативные протоколы. Имеются две методики под-держания описанной выше когерентности. Один из методов за-ключается в том, чтобы гарантировать, что процессор должен по-лучить исключительные права доступа к элементу данных перед выполнением записи в этот элемент данных. Этот тип протоколов называется протоколом записи с аннулированием (write ivalidate protocol), поскольку при выполнении записи он аннулирует другие копии. Это наиболее часто используемый протокол как в схемах на основе справочников, так и в схемах наблюдения. Исключи-тельное право доступа гарантирует, что во время выполнения за-писи не существует никаких других копий элемента данных, в ко-торые можно писать или из которых можно читать: все другие кэ-шированные копии элемента данных аннулированы.
Чтобы увидеть, как такой протокол обеспечивает когерент-ность, рассмотрим операцию записи, вслед за которой следует операция чтения другим процессором. Поскольку запись требует исключительного права доступа, любая копия, поддерживаемая читающим процессором, должна быть аннулирована (в соответст-вии с названием протокола).
Таким образом, когда возникает операция чтения, произой-дет промах кэш-памяти, который вынуждает выполнить выборку новой копии данных. Для выполнения операции записи мы можем потребовать, чтобы процессор имел достоверную (valid) копию данных в своей кэш-памяти прежде, чем выполнять в нее запись.
Таким образом, если оба процессора попытаются записать в один и тот же элемент данных одновременно, один из них выигра-ет состязание у второго (мы вскоре увидим, как принять решение, кто из них выиграет) и вызывает аннулирование его копии. Другой процессор для завершения своей операции записи должен сначала получить новую копию данных, которая теперь уже должна со-держать обновленное значение.
Альтернативой протоколу записи с аннулированием яв-ляется обновление всех копий элемента данных в случае записи в этот элемент данных. Этот тип протокола называется протоколом записи с обновлением (write update protocol) или протоколом запи-си с трансляцией (write broadcast protocol). Обычно в этом прото-коле для снижения требований к полосе пропускания полезно от-слеживать, является ли слово в кэш-памяти разделяемым объек-том, или нет, а именно, содержится ли оно в других кэшах. Если нет, то нет никакой необходимости обновлять другой кэш или транслировать в него обновленные данные.
Разница в производительности между протоколами записи с обновлением и с аннулированием определяется тремя характери-стиками:
1. Несколько последовательных операций записи в одно и то же слово, не перемежающихся операциями чтения, требуют не-скольких операций трансляции при использовании протокола за-писи с обновлением, но только одной начальной операции анну-лирования при использовании протокола записи с аннулировани-ем.
2. При наличии многословных блоков в кэш-памяти каждое слово, записываемое в блок кэша, требует трансляции при исполь-зовании протокола записи с обновлением, в то время как только первая запись в любое слово блока нуждается в генерации опера-ции аннулирования при использовании протокола записи с анну-лированием. Протокол записи с аннулированием работает на уровне блоков кэш-памяти, в то время как протокол записи с об-новлением должен работать на уровне отдельных слов (или бай-тов, если выполняется запись байта).
3. Задержка между записью слова в одном процессоре и чтением записанного значения другим процессором обычно мень-ше при использовании схемы записи с обновлением, поскольку за-писанные данные немедленно транслируются в процессор, выпол-няющий чтение (предполагается, что этот процессор имеет копию данных). Для сравнения, при использовании протокола записи с аннулированием в процессоре, выполняющим чтение, сначала произойдет аннулирование его копии, затем будет производиться чтение данных и его приостановка до тех пор, пока обновлен-ная копия блока не станет доступной и не вернется в процессор.
Эти две схемы во многом похожи на схемы работы кэш-памяти со сквозной записью и с записью с обратным копировани-ем. Также как и схема задержанной записи с обратным копирова-нием требует меньшей полосы пропускания памяти, так как она использует преимущества операций над целым блоком, протокол записи с аннулированием обычно требует менее тяжелого трафи-ка, чем протокол записи с обновлением, поскольку несколько за-писей в один и тот же блок кэш-памяти не требуют трансляции каждой записи. При сквозной записи память обновляется почти мгновенно после записи (возможно с некоторой задержкой в бу-фере записи). Подобным образом при использовании протокола записи с обновлением другие копии обновляются так быстро, на-сколько это возможно. Наиболее важное отличие в производи-тельности протоколов записи с аннулированием и с обновлением связано с характеристиками прикладных программ и с выбором размера блока.
Основы реализации. Ключевым моментом реализации в многопроцессорных системах с небольшим числом процессоров как схемы записи с аннулированием, так и схемы записи с обнов-лением данных, является использование для выполнения этих опе-раций механизма шины. Для выполнения операции обновления или аннулирования процессор просто захватывает шину и транс-лирует по ней адрес, по которому должно производиться обновле-ние или аннулирование данных.
Все процессоры непрерывно наблюдают за шиной, контро-лируя появляющиеся на ней адреса. Процессоры проверяют не на-ходится ли в их кэш-памяти адрес, появившийся на шине. Если это так, то соответствующие данные в кэше либо аннулируются, либо обновляются в зависимости от используемого протокола. После-довательный порядок обращений, присущий шине, обеспечивает также строго последовательное выполнение операций записи, по-скольку когда два процессора конкурируют за выполнение записи в одну и ту же ячейку, один из них должен получить доступ к ши-не раньше другого.
Один процессор, получив доступ к шине, вызовет необ-ходимость обновления или аннулирования копий в других процес-сорах. В любом случае, все записи будут выполняться строго по-следовательно. Один из выводов, который следует сделать из ана-лиза этой схемы, заключается в том, что запись в разделяемый элемент данных не может закончиться до тех пор, пока она не за-хватит доступ к шине.
В дополнение к аннулированию или обновлению соответст-вующих копий блока кэш-памяти, в который производилась за-пись, мы должны также разместить элемент данных, если при за-писи происходит промах кэш-памяти. В кэш-памяти со сквозной записью последнее значение элемента данных найти легко, по-скольку все записываемые данные всегда посылаются также и в память, из которой последнее записанное значение элемента дан-ных может быть выбрано (наличие буферов записи может привес-ти к некоторому усложнению).
Однако для кэш-памяти с обратным копированием задача нахождения последнего значения элемента данных сложнее, по-скольку это значение скорее всего находится в кэш, а не в памяти. В этом случае используется та же самая схема наблюдения, что и при записи: каждый процессор наблюдает и контролирует адреса, помещаемые на шину. Если процессор обнаруживает, что он имеет модифицированную ("грязную") копию блока кэш-памяти, то именно он должен обеспечить пересылку этого блока в ответ на запрос чтения и вызвать отмену обращения к основной памяти. Поскольку кэш с обратным копированием предъявляют меньшие требования к полосе пропускания памяти, они намного предпочти-тельнее в мультипроцессорах, несмотря на некоторое увеличение сложности. Поэтому далее мы рассмотрим вопросы реализации кэш-памяти с обратным копированием.
Для реализации процесса наблюдения могут быть исполь-зованы обычные теги кэш. Более того, упоминавшийся ранее бит достоверности (valid bit), позволяет легко реализовать аннулиро-вание. Промахи операций чтения, вызванные либо аннулировани-ем, либо каким-нибудь другим событием, также не сложны для понимания, поскольку они просто основаны на возможности на-блюдения. Для операций записи мы хотели бы также знать, имеются ли другие кэшированные копии блока, поскольку в случае отсутствия таких копий, запись можно не посылать на шину, что сокращает время на выполнение записи, а также требуемую поло-су пропускания.
Чтобы отследить, является ли блок разделяемым, мы можем ввести дополнительный бит состояния (shared), связанный с каж-дым блоком, точно также как это делалось для битов достоверно-сти (valid) и модификации (modified или dirty) блока. Добавив бит состояния, определяющий является ли блок разделяемым, мы мо-жем решить вопрос о том, должна ли запись генерировать опера-цию аннулирования в протоколе с аннулированием, или операцию трансляции при использовании протокола с обновлением. Если происходит запись в блок, находящийся в состоянии "разделяе-мый" при использовании протокола записи с аннулированием, кэш формирует на шине операцию аннулирования и помечает блок как частный (private). Никаких последующих операций аннулирования этого блока данный процессор посылать больше не будет. Процес-сор с исключительной (exclusive) копией блока кэш-памяти обыч-но называется "владельцем" (owner) блока кэш-памяти.
При использовании протокола записи с обновлением, если блок находится в состоянии "разделяемый", то каждая запись в этот блок должна транслироваться. В случае протокола с аннули-рованием, когда посылается операция аннулирования, состояние блока меняется с "разделяемый" на "неразделяемый" (или "част-ный"). Позже, если другой процессор запросит этот блок, состоя-ние снова должно измениться на "разделяемый". Поскольку наш наблюдающий кэш видит также все промахи, он знает, когда этот блок кэша запрашивается другим процессором, и его состояние должно стать "разделяемый".
Поскольку любая транзакция на шине контролирует адрес-ные теги кэша, потенциально это может приводить к конфликтам с обращениями к кэшу со стороны процессора. Число таких потен-циальных конфликтов можно снизить применением одного из двух методов: дублированием тегов, или использованием много-уровневых кэшей с "охватом" (inclusion), в которых уровни, нахо-дящиеся ближе к процессору являются поднабором уровней, нахо-дящихся дальше от него. Если теги дублируются, то обращения процессора и наблюдение за шиной могут выполняться парал-лельно. Конечно, если при обращении процессора происходит промах, он должен будет выполнять арбитраж с механизмом на-блюдения для обновления обоих наборов тегов.
Точно также, если механизм наблюдения за шиной находит совпадающий тег, ему будет нужно проводить арбитраж и обра-щаться к обоим наборам тегов кэш (для выполнения аннулирова-ния или обновления бита "разделяемый"), возможно также и к массиву данных в кэше, для нахождения копии блока. Таким обра-зом, при использовании схемы дублирования тегов процессор должен приостановиться только в том случае, если он выполняет обращение к кэш в тот же самый момент времени, когда механизм наблюдения обнаружил копию в кэш. Более того, активность ме-ханизма наблюдения задерживается только тогда, когда кэш име-ет дело с промахом.
Если процессор использует многоуровневый кэш со свойст-вами охвата, тогда каждая строка в основном кэш имеется и во вторичном кэш. Таким образом, активность по наблюдению может быть связана с кэш второго уровня, в то время как большинство активностей процессора могут быть связаны с первичным кэш. Ес-ли механизм наблюдения получает попадание во вторичный кэш, тогда он должен выполнять арбитраж за первичный кэш, чтобы обновить состояние и возможно найти данные, что обычно будет приводить к приостановке процессора. Такое решение было при-нято во многих современных системах, поскольку многоуровне-вый кэш позволяет существенно снизить требований к полосе пропускания. Иногда может быть даже полезно дублировать теги во вторичном кэш, чтобы еще больше сократить количество кон-фликтов между активностями процессора и механизма наблюдения.
В реальных системах существует много вариаций схем ко-герентности кэш, в зависимости от того используется ли схема на основе аннулирования или обновления, построена ли кэш-память на принципах сквозной или обратной записи, когда происходит обновление, а также имеет ли место состояние "владения" и как оно реализуется. В таблице 8 представлены несколько протоколов
290 с наблюдением и некоторые машины, которые используют эти протоколы.

9.5. Многопроцессорные системы с локальной памятью
Существуют два различных способа построения крупно-масштабных систем с распределенной (локальной) памятью. Про-стейший способ заключается в том, чтобы исключить аппаратные механизмы, обеспечивающие когерентность кэш-памяти, и сосре-доточить внимание на создании масштабируемой системы памяти.
Наиболее известным примером такой системы является компьютер T3D компании Cray Research. В этих машинах память распределяется между узлами (процессорными элементами) и все узлы соединяются между собой посредством того или иного типа Машины с архитектурой, подобной Cray T3D, называют
процессорами (машинами) с массовым параллелизмом (MPP - Massively Parallel Processor). К машинам с массовым параллелизмом предъявляются взаимно исключающие требования. Чем
больше объем устройства, тем большее число процессоров можно расположить в нем, тем длиннее каналы передачи управления и данных, а значит и меньше тактовая частота. Происшедшее возрастание нормы массивности для больших машин до 512 и даже 64К процессоров обусловлено не ростом размеров машины, а повышением степени интеграции схем, позволившей за последние
годы резко повысить плотность размещения элементов в устройствах. Топология сети обмена между процессорами в такого рода системах может быть различной. В таблице 9 приведены характеристики сети обмена для некоторых коммерческих MPP сети. Доступ к памяти может быть локальным или удаленным. Специальные контроллеры, размещаемые в узлах сети, могут на основе анализа адреса обращения принять решение о том, нахо-дятся ли требуемые данные в локальной памяти данного узла, или размещаются в памяти удаленного узла. В последнем случае кон-троллеру удаленной памяти посылается сообщение для обращения к требуемым данным.
Чтобы обойти проблемы когерентности, разделяемые (об-щие) данные не кэшируются. Конечно, с помощью программного обеспечения можно реализовать некоторую схему кэширования разделяемых данных путем их копирования из общего адресного пространства в локальную память конкретного узла. В этом случае когерентностью памяти также будет управлять программное обес-печение. Преимуществом такого подхода является практически минимальная необходимая поддержка со стороны аппаратуры, хо-тя наличие, например, таких возможностей как блочное (группо-вое) копирование данных было бы весьма полезным. Недостатком такой организации является то, что механизмы программной под-держки когерентности подобного рода кэш-памяти компилятором весьма ограничены. Существующая в настоящее время методика в основном подходит для программ с хорошо структурированным параллелизмом на уровне программного цикла.

Таблица 9

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

Рис. 69