Массив процессорных элементов

Рис. 10.1. Матричный процессор

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

Для выполнения таких расчетов необходимо, чтобы каждый элемент матрич­ного процессора обеспечивал обмен данными с соседними элементами через по­казанные на рисунке соединения. Каждый элемент должен иметь несколько реги­стров и небольшой объем локальной памяти для хранения данных. Кроме того, важно наличие у элемента так называемого сетевого регистра, служащего для об­мена данными с соседними элементами. Центральный процессор направляет всем элементам команду пересылки значений сетевых регистров на один уровень вверх, вниз, вправо или влево. Каждый элемент должен содержать АЛУ для вы­полнения арифметических команд, получаемых от центрального процессора. Ор­ганизовав итеративный цикл, с помощью этих базовых средств команды элемен­там можно передавать многократно. При этом необходимо, чтобы управляющий процессор определял момент, когда каждый процессорный элемент вычислит тем­пературу в определенной точке с указанной точностью. С этой целью по достиже­нии заданного значения внутренний бит состояния каждого из элементов должен устанавливаться в 1. Соединения между элементами позволяют контроллеру уста­навливать все биты состояния в 1, что равнозначно завершению операции.

При разработке матричных процессоров возникает вопрос: что эффективнее ис­пользовать — несколько мощных процессоров или большое количество очень простых процессоров. Примером реализации первого подхода может служить суперкомпь­ютер ILLIAC-IV. В его состав входят 64 процессора, обрабатывающих 46-разряд­ные числа. Примером реализации второго подхода является применение матричных процессоров, разработанных в конце 1980-х годов. В системе СМ-2 производства корпорации Thinking Machines можно было установить до 65536 процессоров, но разрядность каждого из них равнялась одному биту. В системе Maspar MP-1216 допускалась установка 16384 процессоров разрядностью 4. Системы Cambridge Parallel Processing Gamma II Plus могли содержать до 4096 процессоров, обрабаты­вающих данные длиной в 1 байт или 1 бит. Разработчики этих систем полагали, что в SIMD-архитектуре наличие высокого уровня параллелизма эффективнее ис­пользования небольшого количества мощных процессоров.

Сфера применения матричных процессоров является достаточно узкой. В пер­вую очередь они предназначены для решения вычислительных задач, связанных с обработкой матриц и векторов. Напомним, что для решения подобных задач подходят и суперкомпьютеры с векторной архитектурой. Главным отличием мат­ричных процессоров от векторных систем является то, что при работе со вторыми высокая производительность достигается за счет интенсивной конвейеризации, а при использовании первых — за счет максимальной степени параллелизма, являющегося результатом параллельной работы компьютерных модулей. Но ни матричные, ни векторные компьютеры не могут значительно ускорить обычные вычисления, поэтому они не пользуются коммерческим успехом.

 

10.3. Архитектура мультипроцессорных систем общего назначения

Описанные в предыдущем разделе матричные системы предназначены для вы­полнения вычислений с ярко выраженным параллелизмом данных. Для других задач, где нет столь явно выраженного параллелизма данных, гораздо лучше под­ходит архитектура MIMD, в которой множество процессоров могут независимо и параллельно выполнять разные подпрограммы.

На рис. 10.2, 10.3 и 10.4 продемонстрированы три возможных способа реализации мультипроцессорной системы типа MIMD. Самая простая система представлена на рис. 10.2. Она состоит из n процессоров, k модулей памяти и коммуникацион­ной сети, связывающей процессоры и память. Сеть может стать причиной значи­тельной задержки при обращении процессора к памяти. Система, в которой такая задержка одинакова для всех операций доступа к памяти, называется мультипро­цессорной системой с однородным доступом к общей памяти (Uniform Memory Access, UMA) или системой с общей памятью. Поскольку процессоры выполняют команды с огромной скоростью, слишком большие задержки на выборку из памяти команд и данных для них не приемлемы. Однако коммуникационные сети с малым временем задержки имеют очень сложную структуру и высокую стоимость.

Модули памяти

Рис. 10.2. Мультипроцессорная система типа UMA

Достичь высокого быстродействия всех процессоров можно путем непосред­ственного соединения с ними модулей памяти. Архитектура такой системы пока­зана на рис. 10.3. Каждый процессор имеет доступ не только к собственной ло­кальной памяти, но и к памяти других процессоров сети. Но поскольку при обращении к памяти других процессоров запросы проходят через сеть, они вы­полняются дольше, чем обращения к локальной памяти. Системы этого типа на­зываются мультипроцессорными системами с неоднородным доступом к памя­ти (Non-Uniform Memory Access, NUMA).

Рис. 10.3. Мультипроцессорная система типа NUMA

В схемах, приведенных на рис. 10.2 и 10.3, используется глобальная память, к ка­ждому из модулей которой может обратиться любой из процессоров. На рис. 10.4 де­монстрируется схема иной организации системы, характеризующаяся тем, что все модули памяти являются собственностью непосредственно соединенных с ними процессоров. Ни один из процессоров не может обратиться к удаленной па­мяти без взаимодействия с удаленным процессором, которому она принадлежит. Взаимодействие между этими двумя процессорами осуществляется в форме об­мена сообщениями. Системы такого типа называются системами с распределен­ной памятью и высокоскоростным протоколом передачи сообщений.

Рис. 10.4. Мультипроцессорная система с распределенной памятью

До сих пор в этом разделе в качестве основных функциональных устройств мультипроцессорной системы рассматривались процессоры и модули памяти. Мы не обсуждали модули ввода-вывода, хотя любая мультипроцессорная систе­ма обязательно должна иметь эффективные инструменты такого рода. Существу­ют разные средства, предназначенные для ввода и вывода информации. Отдель­ные модули ввода-вывода могут быть соединены прямо с коммуникационной сетью, обеспечивая стандартные интерфейсы ввода-вывода, о которых рассказы­валось в главе 4. Кроме того, некоторые функции ввода-вывода могут быть интег­рированы прямо в процессорные модули.

Высокоуровневое представление возможных способов организации мульти­процессоров показано на рис. 10.2, 10.3 и 10.4. Производительность и стоимость подоб­ных систем в значительной степени зависит от того, как реализованы их схемы. В следующих двух разделах речь пойдет о наиболее популярных схемах органи­зации сетей обмена и о структуре иерархии памяти.

10.4. Коммуникационные сети

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

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

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

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

Общая шина

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

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

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

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

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

Сети с координатной коммутацией

На рис. 10.5 показана сеть с коммутируемыми соединениями. Эта схема, разрабо­танная для телефонных сетей, называется координатным коммутатором (cros­sbar switch). Для наглядности все ключи на рисунке изображены в виде механи­ческих выключателей, но на самом деле это, конечно же, электронные ключи. В приведенной схеме любой модуль, Q _i,может быть соединен с другим модулем, Q _j путем замыкания соответствующего ключа. Сети, в которых существует прямое соединение между любой парой узлов, именуются полносвязными. В полносвязной сети может выполняться множество параллельных операций передачи. Если n уз­лов должны переслать данные n другим узлам, все эти операции могут быть вы­полнены одновременно. Сеть, в которой операции передачи никогда не блокиру­ются из-за отсутствия свободного пути, называется сетью без блокировок.

На рис. 10.5 в каждой точке пересечения соединений показан единственный ключ. Однако в реальном мультипроцессоре используются более сложные соеди­нения, и поэтому в каждой точке располагается целый набор ключей. В сети, со­единяющей n модулей, число точек пересечения равняется n², поэтому с увеличе­нием количества модулей возрастает и общее число ключей. В результате сеть получается громоздкой и дорогостоящей. По этой причине координатная комму­тация обычно применяется для сетей с небольшим количеством узлов.

 

Рис. 10.5. Сеть с координатной коммутацией

Многоступенчатые сети

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

Каждый прямоугольник на рис. 10.6 представляет собой переключатель 2х2, который может соединить любой из входов с любым из выходов. Кроме того, если оба входа должны быть соединены с разными выходами, он может соединить их как прямо, так и накрест. Если два входа запросили один и тот же выход, может быть удовлетворен только один запрос. Второй запрос блокируется, пока пере­ключатель не освободится. Можно показать, что сеть с s ступенями может ис­пользоваться для соединения 2^s модулей. В этом случае существует только один путь от модуля Q _j, к модулю Q _j. Таким образом, сеть обеспечивает соединение ме­жду двумя произвольными модулями. Однако она не в состоянии одновременно обслуживать большое количество запросов. Например, соединение между точками Q ₀ и Q ₄ может быть установлено одновременно с соединением между точ­ками Q ₁ и Q ₅.

 

Рис. 10.6. Многоступенчатая сеть типа shuffle

Многоступенчатая сеть дешевле сети с координатной коммутацией. Для со­единения n узлов по схеме, показанной на рис. 10.6, необходимо s =log₂n ступе­ней с n/2 переключателями на каждой.

Передача запроса по сети выполняется следующим образом. Источник на­правляет в сеть двоичную последовательность, представляющую адрес приемни­ка. Эта последовательность передается по сети, и на каждой ступени анализиру­ется очередной ее бит, который определяет состояние переключателя. В нашем примере на ступени 1 используется старший бит, на ступени 2 — средний бит, а на ступени 3 — последний, младший бит. Когда запрос поступает на один из входов переключателя, он маршрутизируется к верхнему выходу, если управляющий бит имеет значение 0, или к нижнему выходу в противном случае. Обратите внима­ние на пример, приведенный на рис. 10.6, где жирной линией показан маршрут следования по сети запроса от источника Q ₅ приемнику Q ₃. Этот маршрут опре­деляется двоичной последовательностью 011, составляющей адрес приемника.

Сети с топологией гиперкуба

Во всех трех описанных выше коммутационных схемах передача запросов между двумя модулями происходит с некоторой задержкой. Эти схемы могут использо­ваться для реализации мультипроцессоров типа UMA. Далее мы рассмотрим то­пологии, подходящие только для мультипроцессоров типа NUMA. Первая и наи­более популярная сеть этого типа, соединяющая 2ⁿ узлов, имеет топологию n-мерного куба, называемую гиперкубом (hypercube). Помимо коммуникацион­ных схем каждый узел обычно содержит процессор и модуль памяти, а также не­которые средства ввода-вывода.

На рис. 10.7 изображен трехмерный гиперкуб. Здесь кружочками обозначены коммуникационные схемы узлов. Соединяемые узлами функциональные устрой­ства на рисунке не показаны. Ребра куба представляют собой двунаправленные связи между соседними узлами. В n-мерном гиперкубе каждый узел непосредст­венно связан с n соседними узлами. Двоичные адреса узлам удобнее назначать та­ким образом, чтобы адреса двух соседних узлов отличались единственным битом, как на рис. 10.7.

Маршрутизация сообщений в гиперкубе выполняется очень просто. Передача сообщения от процессора в узле N_i процессору узла N_j происходит следующим образом. Сначала двоичные адреса источника i и приемника j сравниваются, на­чиная с младшего бита и заканчивая старшим. Предположим, что они отличаются разрядом р. Далее узел N_i передает сообщение своему соседу, адрес которого, k, отличается от i в разряде p. Узел N _k пересылает сообщение своему соседу, исполь­зуя ту же схему сравнения адресов. После каждой передачи от одного узла к дру­гому сообщение приближается к узлу-приемнику N _j. Например, для передачи сообщения от узла N₂ к узлу N₅ требуются 3 пересылки, осуществляемые через узлы N₃ и n₁. Причем именно это количество пересылок соответствует макси­мальному расстоянию, проходимому сообщением в n-мерном гиперкубе.

Рис. 10.7. Сеть в виде трехмерного гиперкуба

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

Сети с топологией гиперкуба используются во множестве систем.

Сети с ячеистой топологией

Одним из самых удобных способов соединения большого количества узлов явля­ется ячеистая сеть (mesh network). Пример ячеистой сети с 16 узлами приведен на рис. 10.8. Соединения между ее узлами являются двунаправленными. Такие сети завоевали популярность в начале 1990-х годов и стали быстро вытеснять ги­перкубические структуры в архитектуре крупных мультипроцессорных систем.

Рис. 10.8. Двухмерная ячеистая сеть

Маршрутизация в ячеистой сети может осуществляться несколькими спосо­бами. Один из простейших и наиболее эффективных способов выбора пути меж­ду источником N _i и приемником N _j, заключается в том, что сначала выполняется передача данных в горизонтальном направлении от узла N _i к узлу N _j. По достиже­нии столбца, в котором расположен узел N _j, пересылка производится по вертика­ли. Широко известными примерами мультипроцессорных систем с ячеистой то­пологией являются компьютер Paragon компании Intel и экспериментальные системы Dash и Flash, разработанные в Стэндфордском университете, а также система Alewife, созданная в Массачуссетском технологическом институте.

Если соединить между собой узлы, находящиеся на противоположных сторо­нах (рис. 10.8), получится сеть, состоящая из набора двунаправленных горизон­тальных колец, соединенных с такими же вертикальными кольцами. В подобных сетях, то есть имеющих тороидальную топологию (torus), значительно сокраща­ется среднее время передачи информации, правда, они сложнее и дороже. Сеть такого типа используется в системах АР3000 компании Fujitsu.

Как обычную, так и тороидальную ячеистую схему можно реализовать в виде трехмерной сети с соединениями между соседними узлами в направлениях Х, Y и Z. Трехмерная тороидальная сеть используется, в частности, в мультипроцессо­ре Cray T3E.

Сети с древовидной топологией

Еще одной популярной топологией сети обмена является иерархически структури­рованная сеть в виде дерева. На рис. 10.9, а показано дерево, соединяющее 16 моду­лей. Каждый родительский узел этого дерева позволяет соединять по два дочер­них узла за раз. Узлы промежуточных уровней, такие как узел А, могут соединять один из дочерних узлов с родительским. Таким образом осуществляется взаимо­действие между двумя удаленными узлами. Через один узел дерева не может од­новременно проходить несколько соединений.

Древовидная сеть хорошо подходит для случаев, когда через корневой узел се­ти проходит небольшой трафик. Если же трафик возрастает, производительность сети резко снижается, поскольку корневой узел становится ее узким местом. Для повышения пропускной способности сети с древовидной структурой можно уве­личить количество соединений на верхних уровнях иерархии. В результате полу­чается толстое дерево (fat tree), где каждый узел имеет более одного родитель­ского узла. Пример сети с топологией толстого дерева показан на рис. 10.9, б. Здесь каждый узел имеет два родительских узла. Подобная сеть использовалась в системе СМ-5 производства Thinking Machines Corporation.

а

б

Рис. 10.9. Древовидные сети: дерево с четырьмя ветвями (а); толстое дерево (б)

Сеть с кольцевой топологией

Одной из простейших сетевых топологий является кольцевое соединение всех узлов системы (рис. 10.10, а). Главное преимущество такой структуры состоит в простоте ее реализации. Соединения в кольце могут быть достаточно широкими, благодаря чему по ним можно параллельно передавать целый пакет. А вот слиш­ком длинные кольца не эффективны, поскольку среднее время передачи инфор­мации между двумя узлами получается слишком большим.

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

а

б

Рис. 10.10. Сеть с кольцевой топологией: одно кольцо (а); иерархия колец (б)

Сети смешанной топологии

Мы рассмотрели несколько сетевых топологий и попытались описать достоинст­ва и недостатки каждой из них. Разработчики мультипроцессорных систем стара­ются добиться максимальной производительности за приемлемую стоимость. Поэтому во многих коммерческих системах используются смешанные тополо­гии — их разработчики постарались соединить достоинства нескольких тополо­гий в единой системе. Например, отличным способом объединения нескольких процессоров является комбинация шинной топологии и топологии с координат­ной коммутацией. Часто встречаются процессорные кластеры, обычно содержа­щие от 2 до 8 процессоров, соединенные шиной или координатным коммутато­ром. Такие кластеры выступают в роли узлов сети, объединенных в большую систему с помощью подходящей топологии. В системе AV25000 производства Data General используются кластерные узлы, процессоры которых связаны об­щей шиной. В единую сеть эти узлы соединяются по кольцевой схеме. В системе Exemplar V2600 производства Hewlett-Packard узлы тоже соединены при помо­щи кольцевой сети, а процессоры в каждом из них объединены между собой по­средством координатного коммутатора. В системе AlphaServer SC производства Compaq узлы сети соединяются в толстое дерево, а процессоры внутри узлов со­единены путем координатной коммутации.

Симметричные мультипроцессорные системы

Рассмотрим мультипроцессорную систему, в которой все процессоры имеют оди­наковые возможности доступа к модулям памяти и устройствам ввода-вывода, так что с точки зрения операционной системы процессоры являются абсолютно идентичными. Если любой из процессоров может выполнять и ядро операцион­ной системы, и пользовательские программы, система называется симметричной мультипроцессорной системой (Symmetric Multiprocessor, SMP). В такой системе любой процессор может обрабатывать внешние прерывания и инициировать опе­рацию ввода-вывода для любого устройства ввода-вывода.

Симметричные мультипроцессорные системы обычно реализуются на основе шинной сети или сети с координатной коммутацией. Они часто используются в ка­честве узлов более крупных мультипроцессорных систем. Например, узлы SMP входят в состав описанных выше мультипроцессоров Exemplar V2600 и Alpha­Server SC.

10.5. Организация памяти в мультипроцессорных системах

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

Рис. 10.11. Процессорный узел в мультипроцессорной системе, показанной на рис. 10.2

В мультипроцессорных системах типа NUMA (рис. 10.3) каждый узел содер­жит процессор и модуль памяти. Наиболее естественный способ реализации та­кого узла показан на рис. 10.12. Для подобных систем удобно использовать гло­бальное адресное пространство. И снова каждый процессор может обратиться к любому модулю памяти, хотя на доступ к локальным модулям памяти глобаль­ного адресного пространства уходит меньше времени, чем на доступ к удаленным модулям.

В системе с распределенной памятью (рис. 10.4) процессоры могут обращать­ся напрямую только к своей локальной памяти. Поэтому каждый модуль памяти составляет локальное адресное пространство одного процессора; глобального ад­ресного пространства нет вообще. Любое взаимодействие между программами или процессами, выполняющимися на разных процессорах, осуществляется при помощи сообщений, передаваемых между процессорами. При таком виде взаимо­действия каждый процессор рассматривает коммуникационную сеть как устрой­ство ввода-вывода. В таком случае каждый узел системы можно рассматривать как отдельный компьютер. Поэтому системы подобного типа также называются мультикомпьютерными. Данная архитектура представляет собой простейший способ соединения множества компьютеров в большую систему. Взаимодействие между задачами, выполняющимися на разных компьютерах, осуществляется довольно медленно, поскольку для обмена сообщениями требуется программное обеспече­ние. Этот тип систем рассматривается в разделе 10.7.

Рис. 10.12. Структура узла мультипроцессора, изображенного на рис. 10.3

 

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

10.6. Программный параллелизм и общие переменные

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

Кроме того, программу легко разделить на параллельно выполняемые задачи при использовании языка высокого уровня, позволяющего программисту явно выделить отдельные задачи. Такая конструкция часто называется PAR-сегментом. Она показана на рис. 10.13. Между управляющими командами PARBEGIN и PAREND находится список процедур, от Proc1 до ProcК, которые могут выпол­няться параллельно. Рассмотрим порядок реализации этой программы. После за­вершения сегмента программы, предшествующего команде PARBEGIN, может немедленно начаться выполнение любой из К параллельных процедур или же всех этих процедур, что зависит от количества свободных процессоров. Последо­вательность их запуска может быть любой. Выполнение части программы, сле­дующей за командой PAREND, разрешается только после завершения выполне­ния всех или К параллельных процедур.

PARBEGIN

Proc1;

Proc2;

….. PAR-сегмент

ProcК;

PAREND

…..

Рис. 10.13. Программная конструкция для параллельного выполнения

 

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

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

10.6.1. Доступ к общим переменным

Предположим, что мы определили две задачи, которые могут параллельно вы­полняться мультипроцессорной системой. Эти задачи почти полностью незави­симы, но время от времени они считывают и модифицируют некоторую общую переменную, хранящуюся в глобальной памяти. Пусть, например, общая пере­менная SUM представляет баланс некоторого счета. Этот счет должен обновлять­ся несколькими задачами, выполняющимися разными процессорами. Каждая за­дача производит с переменной SUM следующие действия: считывает ее текущее значение, выполняет некоторую операцию с его использованием, а результат со­храняет в переменной SUM. Нетрудно представить себе, какие ошибки могут воз­никнуть, если такие операции с переменой SUM будут осуществляться задачами Т1 и Т2, выполняющимися в параллельном режиме процессорами Р1 и Р2. Пред­положим, что обе задачи, Т1 и Т2, считывают текущее значение переменной SUM, скажем 17, и каждая по отдельности его модифицирует. Задача Т1 прибавляет к не­му 5, получая 22, а задача Т2 вычитает из него 7, результатом чего является число 10. Затем каждая из задач заносит в переменную SUM свой результат — сначала это действие выполняет задача Т2, затем задача Т1. Теперь в переменной SUM хранится число 22, что является ошибкой, так как на самом деле в этой перемен­ной должно находиться значение l5 (17 +5-7), которое получится при строго последовательном проведении изменений.

Для того чтобы обеспечить правильную работу с переменной SUM, каждая задача должна получать к ней монопольный доступ на все время выполнения последовательности операций чтения, модификации и записи. С этой целью мо­жет быть задействована глобальная переменная блокировки LOCK и машинная команда Test and Set. Переменная LOCK может принимать значение 0 или 1. Мы используем ее для того, чтобы гарантировать, что никакие две задачи не смогут одновременно получить доступ к переменной SUM. Последовательность команд, для выполнения которой требуется монопольный доступ к некоторой перемен­ной, называется критической секцией прог

Поделиться:

Воспользуйтесь поиском по сайту: