Классификация архитектур вычислительных систем

Содержание

Введение……………………………………………………………………………….2

1. Классификация архитектур вычислительных систем……………………….6

1.1 "Фон-Неймановские" и "не-Фон-Неймановские" архитектуры…………….6

1.2 Классификация параллельных ВС…………………………………………....8

1.3 Системы с общей и распределенной памятью………………………….…..13

1.4 Способы межмодульного соединения (комплексирования)…………….....14

2. Микропроцессорные системы и способы распараллеливания………….....15

2.1 Мультимикропроцессорные вычислительные системы……………………15

2.2 Направление "мини-супер" для персональных компьютеров……………..18

3. Распараллеливание в ВС на уровне исполнительных устройств…………21

3.1 Конвейеры операций…………………………………………………………….21

3.2 Векторные конвейеры. "Зацепление" векторов………………………….....22

3.3 Выполнение операций на стеке……………………………………………...24

4. Вычислительные системы нетрадиционной архитектуры………………...26

4.1 Однородные вычислительные структуры (среды)…………………………26

4.2 Ассоциативные вычисления и ВС…………………………………………...29

4.3 ВС Connection Machine……………………………………………………….33

4.4 Нейронные сети и нейрокомпьютеры……………………………………….35

5. Системы с массовым параллелизмом (МРР)………………………………....38

Список литературы…………………………………………………………………41

Введение

 

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

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

Можно представить следующие направления развития параллельных технологий.

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

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

Параллельные алгоритмы являются естественным результатом оптимального решения задач распараллеливания. Применение многопроцессорных вычислительных систем, а, в особенности, бурно развивающиеся сетевые технологии для решения задач высокой сложности - оптимизационных, моделирования — стимулировали критический подход к тем методам вычислений, которые были разработаны для математика-вычислителя, крутящего ручку арифмометра. Изменился критерий оптимизации вычислительного процесса: не количество выполняемых операций стало определяющим, а "длина критического пути". Указанное направление также рассматривается в книге.

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

Необходимый объем предварительных знаний базируется на стандартах курсов по информатике и основам ЭВМ.

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

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

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

Приоритет в создании ВС на общей памяти принадлежит С. Крею, признанному "отцу супер-ЭВМ", главному конструктору системы CDC 6600, разработанной в 1963 году. Однако условия соперничества и сокрытия информации определили независимость отечественных разработок.

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

Если несколько процессоров составляют ВС, то важной характеристикой ее эффективности (основные составляющие эффективности — производительность, надежность, стоимость) при специализированном использовании (например, в составе автоматизированной системы управления, АСУ) является коэффициент полезной загрузки k₃. Для его определения находят коэффициенты загрузки процессоров:

где T_i, i = 1, ..., n, — суммарное время занятости каждого процессора решением задачи на всем отрезке полного решения задачи, длиной T_реш (рис.1). Тогда

Если P₀ — производительность одного процессора, то реальная производительность P_BC ВС, состоящей из n процессоров, при решении данной задачи (!) находится:

где P₀ определяется классом решаемых задач.

 

Рис. 1. Диаграмма параллельного выполнения информационно взаимосвязанных работ в ВС

 

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

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

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

Рис.2. Затраты производительности при обслуживании нескольких объектов

 

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

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

Однако ВС способна не только делиться своими методами с управлением и планированием. Закономерно и обратное влияние: задачи предъявляют требования к архитектуре ВС, обеспечивающие их эффективное решение.

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

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

 

Классификация архитектур вычислительных систем

 

1.1 "Фон-Неймановские" и "не-Фон-Неймановские" архитектуры

История. Первую ЭВМ создал в 1939 г. в США профессор Джон Атанасов, болгарин, со своим аспирантом К.Берри. Две малые ЭВМ, созданные ими в период 1937 — 1942 гг., были прототипами большой ЭВМ АВС для решения систем линейных уравнений, которая в 1942 г. доводилась по устройствам ввода-вывода и должна была войти в строй в 1943 г., но призыв Атанасова в армию в 1942 г. воспрепятствовал этому. Проект электронной ЭВМ Эниак (Electronics Numerical Integrator and Computer) был сделан в 1942 г. Д.Моучли и Д.Эккертом и осуществлен в 1945 г. в Муровской электротехнической лаборатории Пенсильванского университета. В 1946 г. Эниак был публично продемонстрирован в работе. В нем впервые были применены триггеры. Рождение Эниак считают началом компьютерной эры, посвящая ему научные симпозиумы и другие торжественные мероприятия. (Международный симпозиум, посвященный 50-летию первой ЭВМ, был проведен и в Москве в июне 1996 г.)

Однако еще в начале 40-х годов XX века Атанасов поделился с Моучли информацией о принципах, заложенных в ЭВМ АВС. Хотя Моучли впоследствии утверждал, что он не воспользовался этой информацией в патенте на Эниак, суд не согласился с этим. Вернувшись из армии после войны, Атанасов узнал, что более мощная ЭВМ Эниак уже создана, и потерял интерес к этой теме, не поинтересовавшись, насколько Эниак похож на его ЭВМ АВС.

Известный английский математик Алан Тьюринг был не только теоретиком по информации и теории алгоритмов, автором теоретического автомата "машины Тьюринга", но и талантливым инженером, создавшим в начале 1940-х годов первую работающую специализированную ЭВМ. Эта ЭВМ под названием "Колосс" была сконструирована и сделана им совместно с Х.А.Ньюменом в Блетчи (Англия) и начала работать в 1943 г. Сообщения о ней своевременно не публиковались, т.к. она использовалась для расшифровки секретных германских кодов во время войны.

Основные архитектурно-функциональные принципы построения ЦВМ были разработаны и опубликованы в 1946 г. венгерским математиком и физиком Джоном фон Нейманом и его коллегами Г.Голдстайном и А.Берксом в ставшем классическим отчете "Предварительное обсуждение логического конструирования электронного вычислительного устройства". Основополагающими принципами ЭВМ на основании этого отчета являются: 1) принцип программного управления выполнением программы, и 2) принцип хранимой в памяти программы. Они легли в основу понятия фон-Неймановской архитектуры, широко использующей счетчик команд.

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

Альтернативной архитектурой является "не-фон-Неймановская" архитектура, допускающая одновременный анализ более одной команды. Поиски ее обусловлены необходимостью распараллеливания выполнения программы между несколькими исполнительными устройствами — процессорами. Счетчик команд при этом не нужен. Порядок выполнения команд определяется наличием исходной информации для выполнения каждой из них. Если несколько команд готовы к выполнению, то принципиально возможно их назначение для выполнения таким же количеством свободных процессоров. Говорят, что такие ВС управляются потоком данных (data flow).Общая схема потоковых ВС представлена на рис. 1.1.1

 

Рис. 1.1.1 "Идеальная" потоковая ВС

 

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

{код операции, операнд 1, ..., операнд L,адрес результата 1, ..., адрес результата M}

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

Селекторная и распределительная сети образуют коммуникационную сеть ВС.

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

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