Архитектура компьютерных сетей

Кэш уровня L2 объемом 384 Кбайт. Блоки кэша L2 объединены по два в кластеры, причем каждый кластер поддерживает работу с тремя процессорами и обеспечивает доступ ко всему адресного пространства основной памяти.

Адаптер переключения магистрали-BSN (bus-switching network adapter), который организует связь блоков кэша L2 с одним из четырех блоков главной памяти. В состав BSN входит и кэш уровня L3 объемом 2 Мбайт.

Одноплатный блок главной памяти объемом 8 Гбайт. В состав комплекса входят четыре таких блока, обеспечивая общий  объем главной памяти 32 Гбайт.

В этой структуре есть несколько особенностей, на которых стоит остановиться подробнее:

коммутируемая подсистема взаимосвязей;

совместно используемый кэш уровня L2;

кэш уровня L3.

У SMP-системах персонального пользования  и рабочих станциях общепринятой является структура с единой системной магистралью (см. рис. 2.3). Впоследствии в этом варианте магистраль может стать узким местом, препятствующим дальнейшему наращиванию системы - добавлению в нее новых компонентов. Проектировщики систем IBM S/390 попытались справиться с этой проблемой двумя способами. Во-первых, они разделили подсистему главной памяти на четыре одноплатных блоки, оснастив каждый из них собственным контроллером, который способен с высокой скоростью обрабатывать запросы к памяти. В результате суммарная пропускная способность канала доступа к памяти увеличилось в четыре раза. Во-вторых, связь между каждым процессором (фактически, между его кэшем уровня L2) и отдельным блоком памяти реализована не в форме магистрали общего пользования, а, скорее, в форме двухточечной соединения - каждый связь подключает группу из трех процессоров через кэш L2 до модуля BSN. В свою очередь, BSN выполняет функцию переключателя, объединяет пять каналов связи (четыре из кэшами L2 и один с блоком памяти) - связывает четыре физических каналы в одну логическую магистраль передачи данных. Таким образом, сигнал, поступающий по каждому из четырех каналов, подключенных к кэшей L2, дублируется по другим трем каналам, и тем самым обеспечивается информационная целостность кешив.Звернемо внимание на то, что хотя в системе есть четыре отдельных блока памяти, каждый процессор и каждый блок кэша L2 оснащен только двумя физическими портами, через которые они связываются с подсистемой главной памяти. Такое решение выбрано потому что каждый блок кэша L2 может хранить данные только с половины всего адресного пространства памяти. Для обслуживания запросов всего адресного пространства используется пара блоков кэша, и каждый процессор должен иметь доступ к обоих блоков в паре.

 

 

2. Классификация ВС

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

Можно привести следующую классификацию  архитектур параллельных ВС. 

 

 

Классы вычислительных систем 

 

Машины SIMD распались на две подгруппы. В первую подгруппу попадают многочисленные суперкомпьютеры и другие машины, которые оперируют векторами, выполняя одну и ту же операцию над каждым элементом вектора. Во вторую подгруппу попадают машины типа ILLIAC IV, в которых главный блок управления посылает команды нескольким независимым АЛУ. 

 

В нашей классификации категория MIMD распалась на мультипроцессоры (машины с памятью совместного использования) и мультикомпьютеры (машины с передачей  сообщений). Существует три типа мультипроцессоров. Они отличаются друг от друга по способу реализации памяти совместного использования. Они называются UMA (Uniform Memory Access — архитектура с однородным доступом к памяти), NUMA (NonUniform Memory Access — архитектура с неоднородным доступом к памяти) иСОМА (Cache Only Memory Access — архитектура с доступом только к кэш-памяти).

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

 

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

 

Во  вторую подкатегорию машин MIMD попадают мультикомпьютеры, которые в отличие от мультипроцессоров не имеют памяти совместного использования на архитектурном уровне. Другими словами, операционная система в процессоре мультикомпьютера не может получить доступ к памяти, относящейся к другому процессору, просто путем выполнения команды LOAD. Ему приходится отправлять сообщение и ждать ответа. Именно способность операционной системы считывать слово из отдаленного модуля памяти с помощью команды LOAD отличает мультипроцессоры от мультикомпьютеров. Как мы уже говорили, даже в мультикомпьютере пользовательские программы могут обращаться к другим модулям памяти с помощью команд LOAD и STORE, но эту иллюзию создает операционная система, а не аппаратное обеспечение. Разница незначительна, но очень важна. Так как мультикомпьютеры не имеют прямого доступа к отдаленным модулям памяти, они иногда называются машинами NORMA (NO Remote Memory Access — без доступа к отдаленным модулям памяти). 

 

Мультикомпьютеры можно разделить на две категории. Первая категория содержит процессоры МРР (Massively Parallel Processors — процессоры с массовым параллелизмом) — дорогостоящие суперкомпьютеры, которые состоят из большого количества процессоров, связанных высокоскоростной коммуникационной сетью. В качестве примеров можно назвать Cray T3E и IBM SP/2. 

 

Вторая  категория мультикомпьютеров включает рабочие станции, которые связываются  с помощью уже имеющейся технологии соединения. Эти примитивные машины называются NOW (Network of Workstations — сеть рабочих станций) и COW(ClusterofWorkstattions — кластер рабочих станций). 

 

 

 

Параллельные алгоритмы. Параллельная программа. Локальное и глобальное распараллеливание. 

 

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

 

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

Методы  и алгоритмы обработки информации, решения задач, как правило, – последовательные. Процесс “приспособления” методов к реализации на коллективе вычислителей или процесс “расщепления” последовательных алгоритмов решения сложных задач называется  распараллеливанием (Paralleling or Multisequencing). 

 

Теоретическая и практическая деятельность по созданию параллельных алгоритмов и программ обработки информации называется параллельным программированием (Parallel or Concurrent Programming). Качество параллельного алгоритма (или его эффективность) определяется методикой распараллеливания сложных задач. 

 

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

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

 

 

Схемы параллельных алгоритмов 

 

Одним из конструктивных приемов крупноблочного распараллеливания сложных задач  является

распараллеливание по циклам

. Прием позволяет представить  процесс решения задачи в виде параллельных ветвей, полученных расщеплением цикла на части, число которых в пределе равно числу повторений цикла. На входе и выходе из цикла процесс вычислений – последовательный; доля последовательных участков в общем времени решения задачи незначительна. 

 

Как правило, последовательные участки  имеют место в начале и конце  параллельной программы. На начальном  участке осуществляется инициирование  программы и ввод исходных данных, а на конечном – вывод результатов (запись в архивные файлы). При достаточно полном воплощении принципов модели коллектива вычислителей допустимы реализации в системе параллельных ввода и вывода информации.

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

 

Модель вычислений в виде графа «операции-операнды» 

 

Для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач может быть использована модель в виде графа «операции-операнды».

Принимается:

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

 

 

Представим  множество операций, выполняемых  в исследуемом алгоритме решения  вычислительной задачи, и существующие между операциями информационные зависимости  в виде ациклического ориентированного графа G=(V,R).

Где V={1..|V|} есть множество вершин графа, представляющих выполняемые операции алгоритма, R есть множество дуг графа (при этом дуга r=(i, j) принадлежит графу только, если операция jиспользует результат выполнения операции i).

Разные  схемы вычислений обладают различными возможностями для распараллеливания  и тем самым при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для  параллельного исполнения вычислительной схемы алгоритма. 

 

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

 

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

H_p={(i, P_i, t_i):i∈V}

в котором для каждой операции i∈V указывается номер используемого для выполнения операции процессора P_i, и время начала выполнения операции t_i. Для того, чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества H_p.

1) один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени,

2) к назначаемому моменту выполнения  операции все необходимые данные  уже должны быть вычислены. 

 

Время T_p выполнения параллельного алгоритма зависит от выбранного расписания и вычислительной схемы алгоритма. Рассмотрим основные показатели производительности параллельных алгоритмов. 

 

Показатели эффективности параллельных вычислений: ускорение, эффективность, масштабируемость 

 

Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной S_p(n)=T₁(n)/T_p(n)

т.е. как отношение времени решения  задач на скалярной ЭВМ к времени  выполнения параллельного алгоритма (величинаnиспользуется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).  

 

Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением E_p(n)=T₁(n)/(pT_p(n))=S_p(n)/p (величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально используются для решения задачи).