СКИПОДы 2007 полная версия (1127795), страница 28
Текст из файла (страница 28)
Являются мощным средством функционального распараллеливания - позволяютразделить группу процессов на несколько подгрупп, каждая из которых должна выполнятьсвою параллельную процедуру. При этом существенно упрощается проблема адресации прииспользовании параллельных процедур.88Контекст - область “видимости” для сообщений, аналогичное области видимостипеременных в случае вложенных вызовов процедур. Сообщения, посланные в некоторомконтексте, могут быть приняты только в этом же контексте.
Контексты - также важныесредства поддержки параллельных процедур.Коммуникаторы - позволяют ограничить область видимости (жизни, определения)сообщений рамками некоторой группы процессов, т.е. могут рассматриваться как пара группа и контекст. Кроме того, они служат и для целей оптимизации, храня необходимыедля этого дополнительные объекты. Имеются предопределенные коммуникаторы (точнее,создаваемые при инициализации MPI-системы):MPI_COMM_ALL - все процессыMPI_COMM_PEER - все, кроме главного процесса.(6) Операции над группами (локальные, без обмена сообщениями).Для поддержки пользовательских серверов имеется коллективная операция разбиениягруппы на подгруппы по ключам, которые указывает каждый процесс группы.
Дляподдержки связывания с серверами, имеются средства построения коммуникатора понекоторому имени, известному и серверу и клиентам.(7) Точечные коммуникации.Основные операции - send,неблокирующими.receiveОперациимогутбытьблокирующимииПараметры статических коммутационных сетей.Основные характеристики для анализа топологической структурыПри анализе топологической структуры любой мультипроцессорной системы частоиспользуют ряд характеристик, определяющих количественную меру топологии системы.Целесообразность определения таких характеристик обоснована на необходимости оценкикачества системы и ее элементов с позиций общего системного подхода.
Ниже приведенынекоторые наиболее важные из них.1. Сложность, определяется как числоузлов и связей, составляющих топологиюструктуры. В случае необходимости выделяются элементы, соответствующиеизолированным, висячим и тупиковым вершинам графа. Изолированные вершинынеинцидентны ни одному из ребер графа, висячие — соответствуют вершинам, которыенельзя попасть ни из одной другой вершины графа, тупиковые — вершинам, из которыхнельзя попасть в другие вершины графа. Наличие в графе изолированных вершин обычносвидетельствует об ошибках, допущенных при формировании или описании структуры,поскольку вся система — всегда целостный объект.Исследуя граф структуры, следует убедиться в том, что все висячие и тупиковые вершины внем правильно интерпретированы.
Исследование числа и особенностей связей междуэлементами структуры направлено, прежде всего, на выявление в соответствующем графеконтуров и сильно связанных подграфов.2. Иерархичность — проявляется в структуре связей между элементами. Даннаяхарактеристика позволяет распределить элементы топологии в порядке их значимости идает возможность провести классификацию топологий. Значимость элемента определяетсяего расположением и связями в графе по отношению к другим элементам, составляющимграф.
Для ориентированного графа ранг элемента позволяет высказать такое весьмаправдоподобное допущение: чем выше ранг элемента, тем сильнее он влияет на остальные89элементы и тем тяжелее будут последствия его отказа. Возможно узкое понимание рангакак числа связей данного элемента с другими [23].3. Диаметр структуры — соответствует метрической характеристике, введенной на графедля определения кратчайшего пути между наиболее удаленными вершинами. В рядеслучаев разработчики структур оперируют понятием среднего диаметра, имеющимбольшую системную значимость.
По значению диаметра (среднего диаметра) можнокосвенно судить о ряде предельных параметров системы, в частности о ее надежности,длительности задержек сообщений, инерционности, количестве разделяющих вершин иребер.4. Связность — способность противостоять разбиению, разделению топологии нанезависимые части. Данная количественная характеристика позволяет выявить наличиеобрывов в топологии, «мосты», и т. д.
В теории графов существует несколько определенийсвязности, обусловленных различными критериями. Расчет этих характеристик позволяетоценить топологию структуры с разных точек зрения.5. Плотность — число вершин топологического графа структуры, обладающего заданнымидиаметром и степенями вершин. На практике эта характеристика применяется только кграфам, все узлы которых имеют одинаковую степень.6. Адаптируемость — приспособленность топологии системы к внешним условиям,позволяющая оптимальным образом достичь цели функционирования.7.
Надежность — способность топологии системы обеспечить функционирование системыв течение заданного промежутка времени. Надежность является одной из важнейшихмногопараметрических характеристик структуры и определяется как надежностьюэлементов, так и схемой объединения элементов. Существующие показатели надежностиподразделяются на детерминированные и вероятностные.9.
Живучесть — оценивает сохранение частей топологии структуры, обеспечивающихвыполнение поставленной задачи. Живучесть имеет тесную функциональную связь споказателями надежности топологии.10. Параллельность — позволяет обеспечить одновременное функционирование элементовструктуры с целью повышения производительности системы.11. Наращиваемость — способность топологии некоторой структуры к развитию,достигаемая (без нарушения процесса выполнения основных функций) изменением числавершин и (или) ребер.12. Топологическая избыточность — отражает превышение общего числа связей надминимально необходимым.
Данная топологическая характеристика используется длякосвенной оценки экономичности и надежности исследуемых систем.13. Стоимость — характеристика, оценивающая стоимость реализации структуры.Наилучшей топологической структурой считается та, которая либо наиболее эффективнапри заданной стоимости, либо обладает заданными параметрами при минимальнойстоимости. Стоимость топологических элементов предполагается не зависящей от времени,протяженности.90Топологии линейки, решетки, пирамиды.Линейка ( linear array or farm ) – представляет собой линейный массив процессоров (рис.1).Система, в которой каждый процессор имеет линии связи только с двумя соседними (спредыдущим и последующим) процессорами; такая схема является, с одной стороны,просто реализуемой, а с другой стороны, соответствует структуре передачи данных прирешении многих вычислительных задач (например, при организации конвейерныхвычислений);Шина.Шинные топологии традиционно используются для организации взаимодействия ввычислительных системах.
Одномерная шина применяется во многих SMP-конфигурацияхдля соединения процессоров, памяти и подсистемы ввода/вывода. Основными еедостоинствами являются простота построения и малая задержка при передачи сообщения(за счет того, что все узлы находятся на расстоянии 1 друг от друга). Основными минусамишин является то, что ее пропускная способность делится между всеми узлами.Рис.
15: Шины: а) одномерная; б) иерархическая.Иерархическая шина ялвяется двумерной структурой, в которой множество локальных шинобъединены глобальной шиной (или несколькими шинами). Эта схема лучше одномернойшины, если удается сделать большую часть пересылок локальными. Если же этого добитьсяневозможно и имеются множественные пересылки между локальными сегментами, то такаяорганизация оказывается даже хуже одномерной шины.6.2 Полносвязная сеть.Такая сеть предусматривает соединение узлов по принципу „каждый с каждым“.
Такаятопология обеспечивает минимальную задержку при обращении к произвольному узлу. Ксожалению, число связей равно [((n-1)n)/2], где n - количество узлов, то есть наблюдаетсяквадратичный рост числа связей при увеличении числа узлов. Это делает стоимость связейнеприемлемо большой, а так как обеспечивать настолько быстрое взаимодействие обычноне надо, то эта схема не используется совсем или используется для систем с числом узловменее 4.91Рис.
16: Полносвязная схема.6.3 Решетка.Эта топология представляется наиболее естественной для соединения равноправных узлов.Но при этом максимальное расстояние между узлами будет равно 2Цn-2, что уже для случаяс 16-тью узлами даст расстояние 6. Таким образом, подобное объединение однородныхузлов не является достаточно компактным.Тем не менее, подобная организация иногда применяется. Например, так могут бытьсвязаны обрабатывающие элементы векторного процессора, хотя обычно при этом и узлы, исвязи получаются неоднородными.Рис. 17: Решетка.Иногда решетка образуется двумя наборами шин - горизонтальным и вертикальным.
В этомслучае каждый процессор имеет два порта. Необходимо обеспечивать схемымаршрутизации для сообщений, которые идут в другие столбец и/или строку.6.4 Деревья.Деревья являются довольно популярным способом оргинцизации коммуникационнойсистемы из-за своей иерархичности. При этом обеспечивается довольно малый диаметрсети. Наиболее часто применяется бинарное дерево (рис. ).Однако простое дерево имеет узкое место.
Им являются два узла - потомки корня. Самкорень должен только пересылать пакеты из левого поддерева в правое, а эти два узладолжны осуществлять маршрутизацию для сообщений всего своего поддерева, анализируяадреса получателей данных.92Рис. 18: Бинарное дерево.Чтобы избавиться от этой проблемы прибегают к схеме X-дерева (рис. , рис. ). В этомдереве вычислительные узлы находятся в листьях дерева, и организованныедополнительные связи, позволяющие листьям организовывать передачу данных внутриподддерева, не затрагивая более высокие уровни дерева.Возможно, Х-дерево и есть пирамида…(примечание А.Е)Другой подход к решению той же проблемы прдоставляет „толстое дерево“ (рис.
). Этопрямой способ решения, при котором связи поддеревьев более высокого уровня обладаютболее высокой производительностью.Рис. 21: Толстое дерево (fat-tree).Топология гиперкуба.Для получения более компактной конфигурации необходимо решить задачу о нахождениифигуры, имеющей максимальный объем при минимальной площади поверхности. Втрехмерном пространстве таким свойством обладает шар. Но поскольку нам необходимопостроить узловую систему, вместо шара приходится использовать куб (если числопроцессоров равно 8) или гиперкуб, если число процессоров больше 8. Размерностьгиперкуба будет определяться в зависимости от числа процессоров, которые необходимосоединить. Так, для соединения 16 процессоров потребуется четырехмерный гиперкуб. Дляего построения следует взять обычный трехмерный куб, сдвинуть в нужном направлении и,соединив вершины, получить гиперкуб размером 4.93Рис.
4.4. Топология связи, 3-х мерный гиперкубАрхитектура гиперкуба является второй по эффективности, но самой наглядной.Используются и другие топологии сетей связи: трехмерный тор, "кольцо", "звезда" идругие.Рис. 4.5. Топология связи, 4-х мерный гиперкубГиперкуб — пространственное обобщение рассмотренной плоской решетки, где адресацияпроцессоров (и соответственно, блоков распределенной памяти) ставится в зависимость отструктуры связей между ними.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
