Неоднородность ЭВМ

Фиксированность структуры ЭВМ

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

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

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

Модель коллектива вычислителей

Коллектив аппаратурно-программных вычислителей суть вычислительная система (ВС). Архитектура ВС основывается на структурной и функциональной имитации коллектива (ансамбля) людей-вычислителей.

Каноническую основу конструкции вычислительной системы и ее функционирования составляет модель коллектива вычислителей. Эта модель представляется парой:

S = <H, A>

где H и A – описание конструкции (или просто: конструкция) и алгоритм работы коллектива вычислителей.

Конструкция коллектива вычислителей описывается в виде:

H = <C, G>

где C={c_i} – множество вычислителей с_i (i =0..N-1), N – мощность множества C, G – описание макроструктуры коллектива вычислителей, т.е. структуры сети связей между вычислителями c_i (или структура коллектива). Конструкция коллектива вычислителей есть отражение следующих основополагающих архитектурных принципов:

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

2. программируемости структуры (настраиваемости структуры G сети связей между вычислителями, достигаемой программными средствами);

3. однородности конструкции H (однородности вычислителей c_i и структуры G)

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

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

Структура коллектива вычислителей

Структура коллектива вычислителей представляется графом G, вершинам (узлам) которого сопоставлены вычислители c_i, а ребрам – линии связи между ними. Проблема выбора (синтеза) структур вычислительных систем не является тривиальной. В самом деле, универсальное решение – структура в виде полного графа, однако такие структуры практически реализуемы при небольшом числе вычислителей. Для достижения производительности ВС в диапазоне 10⁹ – 10¹⁵ оп/с при существующих интегральных технологиях требуется число вычислителей порядка 10⁰ – 10⁶. Следовательно, структуры последних систем не могут быть организованы по типу полного графа хотя бы из-за ограничений на число выводов с корпусов интегральных схем. Какие же структуры сети связей между вычислителями используются при формировании ВС?

Простейшие структуры ВС – нульмерные, одномерные и двумерные. Увеличение размерности структуры повышает структурную надёжность ВС. В самом деле, двумерные структуры предоставляют каждому вычислителю непосредственную связь с четырьмя соседними. В качестве примеров двумерных структур может служить «решетка» (точнее 2D-решетка) и тop (2D-тор). Следовательно, в системах с двумерной структурой при отказах некоторых вычислителей и (или) связей между ними сохраняется возможность организации связных подмножеств исправных вычислителей.

В n -мерных структурах каждый вычислитель связан с 2n соседними вычислителями. Ясно, что имеются технико-экономические и технологические ограничения в наращивании размерности структуры ВС.

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

n = log₂N,

где N – количество вершин, а n – число ребер, выходящих из каждой вершины; n – называют также размерностью гиперкуба. Итак, каждый вычислитель в гиперкубической ВС имеет связь ровно с n другими вычислителями. На рис. представлены одно-, дву-, трех- и четырехмерный гиперкубы. Гиперкуб размерности n называют также nD -кубом, где D означает размерность (Dimension).

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

Если вершины гиперкуба пронумеровать от 0 до n-1 в двоичной системе счисления так, что каждый разряд соответствует одному из n -направлений, то это будет булев n -мерный куб.

Гиперкуб N=16, n=4 является также двумерным тором.

Алгоритм работы коллектива вычислителей

Алгоритм A работы коллектива S обеспечивает согласованную работу всех вычислителей c_i и сети связей между ними (структуры G) в процессе решения общей задачи. Данный алгоритм может быть представлен в виде суперпозиции:

где

D - исходный массив данных, подлежащих обработке в процессе решения задачи,

D_i – индивидуальный массив данных для вычислителя c_i из C, причем в общем случае

P – параллельная программа решения общей задачи,

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

Ясно, что решение общей задачи осуществляется по некоторому параллельному алгоритму, и именно он кладется в основу параллельной программы. Распределенные по вычислителям данные и параллельная программа инициируют работу алгоритма A и определяют функционирование конструкции H коллектива вычислителей до конца решения задачи.

Эквивалентное представление алгоритма работы коллектива вычислителей есть композиция

где (A_i*A_i’) осуществляет функционирование вычислителя c_i среди других вычислителей множества C, A_i и A_i’ – соответственно алгоритм автономной работы c_i и алгоритм реализации взаимодействий с вычислителями c_j = C\c_i. Последний алгоритм является суперпозицией

A_i’(P(G))

в которой G – описание структуры коллектива C вычислителей, P_i’ – программа для установления связей и выполнения взаимодействий между вычислителем c_i и другими вычислителями подмножества C\c_i. Программа P_i’ является, как правило, частью ветви P_i параллельной программы.

Многообразие архитектурных реализаций модели коллектива вычислителей (многообразие типов вычислительных систем) является следствием разницы в способах воплощения совокупности алгоритмов { A_i’ } i=0..N-1, задания { P_i } и выбора структуры G, а также разнообразия в правилах композиции алгоритмов.

Аппаратурные средства, с помощью которых реализуется совокупность алгоритмов A₀’,A₁’…,A_i’,…A_N-1’ и которые вместе с сетью связей составляют среду для осуществления взаимодействий между вычислителями коллектива, называются коммутатором. От способа реализации коммутатора во многом зависит эффективность ВС параллельного действия. Коммутатор настолько же необходим при создании ВС, насколько нужны процессор и оперативная память для построения ЭВМ.

При полном воплощении принципа однородности имеют место отношения эквивалентности:

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

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

Литература:

Хорошевский, В. Архитектура вычислительных систем / В.Г. Хорошевский. Москва: МГТУ им. Баумана, 2008. - 520 с.

Лекция 6. Вычислительные системы

Принципы технической реализации модели коллектива вычислителей

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

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

Модульность вычислительной системы обеспечивает:

1. возможность использования любого модуля заданного типа для выполнения любого соответствующего ему задания пользователя;

2. простоту замены одного модуля на другой однотипный;

3. масштабируемость, т.е. возможность увеличения или уменьшения количества модулей без коренной реконфигурации связей между остальными модулями;

4. открытость системы для модернизации, исключающую ее моральное старение.

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

Близкодействие – принцип построения вычислительных систем, обусловливающий такую организацию информационных взаимодействий между модулями–вычислителями, при которой каждый из них может непосредственно (без “посредников”) обмениваться информацией с весьма ограниченной частью модулей-вычислителей. Следовательно, структура ВС позволяет осуществлять информационные взаимодействия между удаленными вершинами-вычислителями лишь с помощью промежуточных вершин-вычислителей, передающих информацию от “точки к точке” (point-to-point). Удаленными считаются все те вершины в структуре ВС, расстояние между которыми более 1 (число ребер между которыми более единицы).

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

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

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

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

Децентрализованное управление системой (в отличие от централизованного) позволяет:

1. достичь живучести ВС, т. е. ее способности продолжать работу при отказах модулей (в том числе и тех, которые предназначены для принятия решений);

2. избежать очередей при обслуживании “заявок” на управление.

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

Архитектурные свойства вычислительных систем

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

Масштабируемость (Scalability) вычислительных систем

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

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

Универсальность ВС. Вычислительные системы алгоритмически и структурно универсальны.

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

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

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

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

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