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

Можно выделить четыре типа архитектуры систем параллельной обработки.

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

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

2. Машины типа SIMD. Эти машины состоят из большого числа идентичных процессорных элементов, имеющих собственную память; все процессорные элементы в машине выполняют одну и ту же программу. Очевидно, что такая машина, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же работу. Модель вычислений для машины БІМБ очень похожа на модель вычислений для векторного процессора: одиночная операция выполняется над большим блоком данных.

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

Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.

3. Машины типа ЫТЫВ. Термином мультипроцессор называют большинство машин типа MIMD, и он часто используется в качестве синонима для машин типа MIMD (подобно тому, как термин "матричный процессор" применяется к машинам типа SIMD). В мультипроцессорной системе каждый процессорный элемент выполняет свою программу достаточно независимо от других процессорных элементов. Процессорные элементы, конечно, должны как-то связываться друг с другом, что делает необходимым более подробную классификацию машин типа М1МБ. В мультипроцессорах с общей памятью (сильносвязанных мультипроцессорах) имеется память данных и команд, доступная всём процессорным элементам. С общей памятью процессорные элементы связываются с помощью общей шины или сети обмена. В противоположность этому варианту в слабосвязанных многопроцессорных системах (машинах с локальной памятью) вся память делится между процессорными элементами, и каждый блок памяти доступен только связанному с ним процессору. Сеть обмена связывает процессорные элементы друг с другом.

Базовой моделью вычислений на М1МО-мультипроцессоре является совокупность независимых процессов, эпизодически обращающихся к разделяемым данным. Существует большое количество вариантов этой модели. На одном конце спектра - модель распределенных вычислений, в которой программа делится на довольно большое число параллельных задач, состоящих из множества подпрограмм. На другом конце спектра - модель потоковых вычислений, в которых каждая операция в программе может рассматриваться как отдельный процесс. Такая операция ждет своих входных данных (операндов), которые должны быть переданы ей другими процессами. По их получении операция выполняется, и полученное значение передается тем процессам, которые в нем нуждаются. В потоковых моделях вычислений с большим и средним уровнем гранулярности процессы содержат большое число операций и выполняются в потоковой манере.

4. Многопроцессорные машины с Б1МО-процессорами. Многие современные суперЭВМ представляют собой многопроцессорные системы, в которых в качестве процессоров используются векторные процессоры, или процессоры типа 81МБ. Такие машины относятся к машинам класса М81МБ.

Многопроцессорные системы за годы развития вычислительной техники прошли ряд этапов. Исторически первым стало освоение технологии БШБ. Однако в настоящее время наметился устойчивый интерес к архитектурам М1МБ. Этот интерес главным образом определяется двумя факторами:

• архитектура М1МБ обеспечивает большую гибкость - при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения МИУГО может работать как однопользовательская система. В результате достигается высокая производительность обработки данных для одной прикладной задачи, выполняется множество задач параллельно, как на многопрограммной машине;

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

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

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

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

Таким образом, существующие MIMD-машины распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти, и методику их соединений.

Многопроцессорные системы с общей памятью. К этой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку при этом имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Архитектура подобной системы представлена на рис. 4.14.

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

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

В такой машине кэш-память может содержать как разделяемые, так и частные данные. Частные данные - это данные, которые используются одним процессором, в то время как разделяемые данные используются многими процессорами, по существу обеспечивая обмен между ними. Когда кэшируется элемент частных данных, их значение переносится в кэш-память для сокращения среднего времени доступа, а также для уменьшения требуемой полосы пропускания. Поскольку никакой другой процессор не использует частные данные, этот процесс идентичен процессу для однопроцессорной машины с кэш-памятью. Если кэшируются разделяемые данные, то разделяемое значение реплицируется (от лат. replicare - обращать назад, отражать) и может содержаться не в одной кэш-памяти, а в нескольких. Кроме сокращения задержки доступа и уменьшения требуемой полосы пропускания такая репликация данных способствует также общему сокращению количества обменов. Однако кэширование разделяемых данных создает новую проблему - когерентность (от лат. cohaerentia - сцепление, связь) кэш-памяти.

Мультипроцессорная когерентность кэш-памяти возникает из-за того, что значение элемента данных в памяти, хранящееся в двух разных процессорах, доступно этим процессорам только через их индивидуальные кэш-модули.

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

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

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

• Первое условие, очевидно, связано с определением когерентного (согласованного) состояния памяти: если бы процессор всегда считывал только старое значение данных, мы сказали бы, что память некогерентна.

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

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

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

Рис. 4.15. Типовая архитектура мультипроцессорной системы с распределенной памятью ров, которые удается поддерживать на одной разделяемой шине и общей памяти.

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

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

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

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

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

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

⇐Классификация архитектур выислительных систем | Информационные системы и технологии в зкономике | Концепция выислительных систем с управлением потоком данных⇒