Ответы 190 страниц (1184228), страница 20
Текст из файла (страница 20)
Хотя MPI предлагает большой набор средств, все же, как уже отмечалось, для прикладных программистов более предпочтительными являются системы, основанные на расширении языков.
Расширения Фортрана для рассматриваемой архитектуры реализованы, например, в языке Fortran Suprenum [14]. В этом языке используется аппарат динамического создания задач и асинхронная модель передачи сообщений. Языковые средства обеспечивают более высокий уровень программирования, так в операторах передачи сообщений можно указывать произвольный список передаваемых данных, аналогичный списку ввода/вывода Фортрана, что гораздо удобнее, чем средства, имеющиеся в системах, основанных на библиотечном подходе, в которых требуется, чтобы либо все передаваемые данные находились в непрерывной области памяти, длина которой часто указывается в байтах, либо (как в MPI) необходимо предварительно объединить эти данные в структуру.
Разработка Fortran Suprenum легла в основу проекта европейского стандарта, который разработан в Германии в рамках общеевропейского проекта ESPRIT [15]. Языковые расширения в данном проекте ориентированы на Фортран 90. Для того, чтобы вводимые расширения были машинно-независимыми, предлагается модель абстрактной машины - GENESIS.
Согласно этой модели, прикладная программа содержит одну начальную задачу и может содержать другие задачи. Несколько задач могут выполняться параллельно на разных процессорах, однако число задач не ограничивается числом процессоров. Каждая задача имеет уникальное имя. Модель предполагает динамическое создание задач; однажды созданная задача размещается в локальной памяти статически. Задача использует только локальную область памяти без разделения данных с другими задачами. Выполнение программы начинается с выполнения начальной задачи. Она создает другие задачи, которые, в свою очередь, могут также создавать новые задачи.
Обмен информацией между задачами осуществляется с помощью передачи сообщений. Предусмотрено три способа передачи сообщений: синхронный, асинхронный и передача без ожидания.
В язык введен новый тип данных (имена задач), дополнительный вид программных единиц (программные единицы-задачи), новые операторы, включая операторы передачи сообщений SEND и RECEIVE, расширен набор стандартных процедур.
Группы, контексты, коммуникаторы.
Группа - упорядоченное (от 0 до ранга группы) множество идентификаторов процессов (т.е. процессов). Группы служат для указания адресата при посылке сообщений (процесс-адресат специфицируется своим номером в группе), определяют исполнителей коллективных операций. Являются мощным средством функционального распараллеливания - позволяют разделить группу процессов на несколько подгрупп, каждая из которых должна выполнять свою параллельную процедуру. При этом существенно упрощается проблема адресации при использовании параллельных процедур.
Контекст - область “видимости” для сообщений, аналогичное области видимости переменных в случае вложенных вызовов процедур. Сообщения, посланные в некотором контексте, могут быть приняты только в этом же контексте. Контексты - также важные средства поддержки параллельных процедур.
Коммуникаторы - позволяют ограничить область видимости (жизни, определения) сообщений рамками некоторой группы процессов, т.е. могут рассматриваться как пара - группа и контекст. Кроме того, они служат и для целей оптимизации, храня необходимые для этого дополнительные объекты. Имеются предопределенные коммуникаторы (точнее, создаваемые при инициализации MPI-системы):
MPI_COMM_ALL - все процессы
MPI_COMM_PEER - все, кроме главного процесса.
(6) Операции над группами (локальные, без обмена сообщениями).
Для поддержки пользовательских серверов имеется коллективная операция разбиения группы на подгруппы по ключам, которые указывает каждый процесс группы. Для поддержки связывания с серверами, имеются средства построения коммуникатора по некоторому имени, известному и серверу и клиентам.
(7) Точечные коммуникации.
Основные операции - send, receive Операции могут быть блокирующими и неблокирующими.
Параметры статических коммутационных сетей.
Основные характеристики для анализа топологической структуры
При анализе топологической структуры любой мультипроцессорной системы часто используют ряд характеристик, определяющих количественную меру топологии системы. Целесообразность определения таких характеристик обоснована на необходимости оценки качества системы и ее элементов с позиций общего системного подхода. Ниже приведены некоторые наиболее важные из них.
1. Сложность, определяется как число узлов и связей, составляющих топологию структуры. В случае необходимости выделяются элементы, соответствующие изолированным, висячим и тупиковым вершинам графа. Изолированные вершины неинцидентны ни одному из ребер графа, висячие — соответствуют вершинам, которые нельзя попасть ни из одной другой вершины графа, тупиковые — вершинам, из которых нельзя попасть в другие вершины графа. Наличие в графе изолированных вершин обычно свидетельствует об ошибках, допущенных при формировании или описании структуры, поскольку вся система — всегда целостный объект.
Исследуя граф структуры, следует убедиться в том, что все висячие и тупиковые вершины в нем правильно интерпретированы. Исследование числа и особенностей связей между элементами структуры направлено, прежде всего, на выявление в соответствующем графе контуров и сильно связанных подграфов.
2. Иерархичность — проявляется в структуре связей между элементами. Данная характеристика позволяет распределить элементы топологии в порядке их значимости и дает возможность провести классификацию топологий. Значимость элемента определяется его расположением и связями в графе по отношению к другим элементам, составляющим граф. Для ориентированного графа ранг элемента позволяет высказать такое весьма правдоподобное допущение: чем выше ранг элемента, тем сильнее он влияет на остальные элементы и тем тяжелее будут последствия его отказа. Возможно узкое понимание ранга как числа связей данного элемента с другими [23].
3. Диаметр структуры — соответствует метрической характеристике, введенной на графе для определения кратчайшего пути между наиболее удаленными вершинами. В ряде случаев разработчики структур оперируют понятием среднего диаметра, имеющим большую системную значимость. По значению диаметра (среднего диаметра) можно косвенно судить о ряде предельных параметров системы, в частности о ее надежности, длительности задержек сообщений, инерционности, количестве разделяющих вершин и ребер.
4. Связность — способность противостоять разбиению, разделению топологии на независимые части. Данная количественная характеристика позволяет выявить наличие обрывов в топологии, «мосты», и т. д. В теории графов существует несколько определений связности, обусловленных различными критериями. Расчет этих характеристик позволяет оценить топологию структуры с разных точек зрения.
5. Плотность — число вершин топологического графа структуры, обладающего заданными диаметром и степенями вершин. На практике эта характеристика применяется только к графам, все узлы которых имеют одинаковую степень.
6. Адаптируемость — приспособленность топологии системы к внешним условиям, позволяющая оптимальным образом достичь цели функционирования.
7. Надежность — способность топологии системы обеспечить функционирование системы в течение заданного промежутка времени. Надежность является одной из важнейших многопараметрических характеристик структуры и определяется как надежностью элементов, так и схемой объединения элементов. Существующие показатели надежности подразделяются на детерминированные и вероятностные.
9. Живучесть — оценивает сохранение частей топологии структуры, обеспечивающих выполнение поставленной задачи. Живучесть имеет тесную функциональную связь с показателями надежности топологии.
10. Параллельность — позволяет обеспечить одновременное функционирование элементов структуры с целью повышения производительности системы.
11. Наращиваемость — способность топологии некоторой структуры к развитию, достигаемая (без нарушения процесса выполнения основных функций) изменением числа вершин и (или) ребер.
12. Топологическая избыточность — отражает превышение общего числа связей над минимально необходимым. Данная топологическая характеристика используется для косвенной оценки экономичности и надежности исследуемых систем.
13. Стоимость — характеристика, оценивающая стоимость реализации структуры. Наилучшей топологической структурой считается та, которая либо наиболее эффективна при заданной стоимости, либо обладает заданными параметрами при минимальной стоимости. Стоимость топологических элементов предполагается не зависящей от времени, протяженности.
Топологии линейки, решетки, пирамиды.
Линейка ( linear array or farm ) – представляет собой линейный массив процессоров (рис.1).
Система, в которой каждый процессор имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);
Шина.
Шинные топологии традиционно используются для организации взаимодействия в вычислительных системах. Одномерная шина применяется во многих SMP-конфигурациях для соединения процессоров, памяти и подсистемы ввода/вывода. Основными ее достоинствами являются простота построения и малая задержка при передачи сообщения (за счет того, что все узлы находятся на расстоянии 1 друг от друга). Основными минусами шин является то, что ее пропускная способность делится между всеми узлами.
Рис. 15: Шины: а) одномерная; б) иерархическая.
Иерархическая шина ялвяется двумерной структурой, в которой множество локальных шин объединены глобальной шиной (или несколькими шинами). Эта схема лучше одномерной шины, если удается сделать большую часть пересылок локальными. Если же этого добиться невозможно и имеются множественные пересылки между локальными сегментами, то такая организация оказывается даже хуже одномерной шины.
6.2 Полносвязная сеть.
Такая сеть предусматривает соединение узлов по принципу „каждый с каждым“. Такая топология обеспечивает минимальную задержку при обращении к произвольному узлу. К сожалению, число связей равно [((n-1)n)/2], где n - количество узлов, то есть наблюдается квадратичный рост числа связей при увеличении числа узлов. Это делает стоимость связей неприемлемо большой, а так как обеспечивать настолько быстрое взаимодействие обычно не надо, то эта схема не используется совсем или используется для систем с числом узлов менее 4.
Рис. 16: Полносвязная схема.
6.3 Решетка.
Эта топология представляется наиболее естественной для соединения равноправных узлов. Но при этом максимальное расстояние между узлами будет равно 2Цn-2, что уже для случая с 16-тью узлами даст расстояние 6. Таким образом, подобное объединение однородных узлов не является достаточно компактным.
Тем не менее, подобная организация иногда применяется. Например, так могут быть связаны обрабатывающие элементы векторного процессора, хотя обычно при этом и узлы, и связи получаются неоднородными.
Рис. 17: Решетка.
Иногда решетка образуется двумя наборами шин - горизонтальным и вертикальным. В этом случае каждый процессор имеет два порта. Необходимо обеспечивать схемы маршрутизации для сообщений, которые идут в другие столбец и/или строку.
6.4 Деревья.
Деревья являются довольно популярным способом оргинцизации коммуникационной системы из-за своей иерархичности. При этом обеспечивается довольно малый диаметр сети. Наиболее часто применяется бинарное дерево (рис. ).
Однако простое дерево имеет узкое место. Им являются два узла - потомки корня. Сам корень должен только пересылать пакеты из левого поддерева в правое, а эти два узла должны осуществлять маршрутизацию для сообщений всего своего поддерева, анализируя адреса получателей данных.
Рис. 18: Бинарное дерево.
Чтобы избавиться от этой проблемы прибегают к схеме X-дерева (рис. , рис. ). В этом дереве вычислительные узлы находятся в листьях дерева, и организованные дополнительные связи, позволяющие листьям организовывать передачу данных внутри подддерева, не затрагивая более высокие уровни дерева.
Возможно, Х-дерево и есть пирамида…(примечание А.Е)