41120

Параллельные вычислительные системы

Лекция

Информатика, кибернетика и программирование

К распараллеливанию прибегают при проектировании отдельных устройств ЭВМ устройств управления буферов команд каналов обращения к памяти и модулей памяти многофункциональных арифметическологических устройств АЛУ повсеместно применяемых конвейеров и т. Сложилось представление о двух основных уровнях на которых в ВС применяются практические методы распараллеливания: на уровне программ процессов процедур первый уровень распараллеливания; на уровне команд и операций второй уровень распараллеливания. Уровень команд и операций...

Русский

2013-10-22

467 KB

70 чел.

Параллельные вычислительные системы

Предисловие

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

Какова же цель распараллеливания?

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

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

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

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

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


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

Два уровня распараллеливания

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

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

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

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

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

Важным революционизирующим моментом стал переход на микропроцессорную элементно-конструкторскую базу, обусловившую построение мультимикропроцессорных ВС.

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

  •  на уровне программ, процессов, процедур (первый уровень распараллеливания);
  •  на уровне команд и операций (второй уровень распараллеливания).

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

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

Различают два способа реализации такой загрузки: динамический и статический.

Динамическая загрузка осуществляется аппаратурой в процессе выполнения программы. Она использует упрощенные алгоритмы распараллеливания.

Статическая загрузка предусматривается при трансляции программы. Транслятор оптимизирует использование оборудования, также решая задачи распараллеливания. Это выражается в формировании "длинных" командных слов, задающих работы устройствам АЛУ в каждом машинном такте.

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

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

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

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

В ЭВМ классической архитектуры ведется последовательная обработка команд и данных. Команды поступают одна за другой (за исключением точек ветвления программы), и для них из ОЗУ или регистров так же последовательно поступают операнды. Одной команде (операции) соответствует один необходимый ей набор операндов (как правило, два для бинарных операций). Этот тип архитектуры — " один поток команд — один поток данных", ОКОД (SISD - "Single Instruction, Single Data") условно изображен на рис. 1.1.


Рис. 1.1.  ВС типа ОКОД (SISD)

Тип ОКМД — "один поток команд — много потоков данных" (SIMD — "Single Instruction — Multiplе Data") охватывает ВС, в которых одной командой обрабатывается набор данных, множество данных, вектор, и вырабатывается множество результатов. Это векторные и матричные системы, в которых по одной команде выполняется одна и та же операция над всеми элементами массива — вектора или матрицы, распределенными между процессорными (обрабатывающими) элементами ПЭ или процессорами. Принцип обработки показан на рис. 1.2.


Рис. 1.2.  ВС типа ОКМД (SIMD)

Отечественные векторные ВС — ПС-2000, ПС-2100. Допускают организацию матричной обработки. Классический пример матричной архитектуры — ILLIAC-1V (США).

К типу МКОД — "много потоков команд — один поток данных" (MISD — "Multiple Instruction — Single Data") принято относить векторный конвейер (обычно в составе ВС, чтобы подчеркнуть основной используемый принцип вычислений), например, в составе ВС Crey -1, "Электроника ССБИС". На векторном конвейере производится последовательная обработка одного потока данных многими обрабатывающими устройствами (ступенями, станциями) конвейера.

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

Принцип обработки показан на рис. 1.3.


Рис. 1.3.  ВС типа МКОД (MISD)

Тип МКМД — "много потоков команд — много потоков данных" (MIMD — "Multiple Instruction — Multiple Data") cоответствует более полному и независимому распараллеливанию. К этому типу относятся, например, все многопроцессорные вычислительные комплексы (МВК) семейства "Эльбрус".

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

Немного истории. Первую ЭВМ создал в 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.4.


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

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

{код операции, операнд 1, ..., операнд L,

адрес результата 1, ..., адрес результата M}

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

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

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

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

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

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


Рис. 1.5.  ВС с общей (а) и распределённой (б) памятью

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

Другое, противоположное воплощение принципа МИМД — масспроцессорные или высокопараллельные архитектуры, объединяющие сотни — тысячи — десятки тысяч процессоров.

В современных супер-ЭВМ наметилась тенденция объединения двух принципов: общей (распределяемой) и распределенной (локальной) оперативной памяти (ЛОП). Такая структура используется в проекте МВК "Эльбрус-3" и "Эльбрус-3М" (рис. 1.6).


Рис. 1.6.  Схема ВС с модулями локальной памяти

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

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

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


Рис. 1.7.  Схема ВС с общей шиной

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

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

Матричный коммутатор можно представить (прямоугольной) сеткой шин. К одному концу каждой подсоединен источник-потребитель информации (рис. 1.8). Точки пересечения — узлы этой сетки — представляют собой управляющие ключи, которые соединяют или разъединяют соответствующие шины, устанавливая или прекращая связь между модулями. Реализуется связь "каждый с каждым". Одновременно могут связываться многие (до n/2 ) пары модулей.


Рис. 1.8.  Матричные коммутаторы: а) — перекрёстная коммутация процессоров, б) — коммутация процессоров и модулей памяти

На рис. 1.8а — перекрестная связь между процессорами в ВС с распределенной памятью, на рис. 1.8б — между n процессорами и m модулями ОП.

"Исторические" модели

Векторная ВС ПС-2000

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

Схема ВС приведена на рис. 1.9.


Рис. 1.9.  Схема ВС ПС-2000

Основу ПС-2000 составляет параллельный процессор с общим потоком команд ППС-2000, содержащий до 64 ПЭ.

Отмечая типичные архитектурные особенности моделей, иллюстрируя их на архитектурах ВС, ставших классическими, уделим второстепенное внимание быстро устаревающим характеристикам этих ВС. Однако отметим, что ПЭ ППС-2000 — 24-разрядный микропроцессор с производительностью 3 млн оп./с, а это было значительным достижением в начале 1980-х годов.

Соседние ПЭ связаны регулярными каналами РК для оперативного обмена данными. В связи с проблемной ориентированностью ВС это обеспечивает быстрый обмен при обработке "соседними" ПЭ "соседних" же элементов поверхностей, конечно же, информационно взаимосвязанных. Связь с помощью РК — циклическая, в частности, ПЭ1 с помощью РК связан с ПЭ64. Т.е. при "прокатывании" 64 ПЭ по длинной последовательности обрабатываемых элементов поверхности ПЭ1 и ПЭ64 являются "соседними": после элемента поверхности, обрабатываемого ПЭ64, следует элемент поверхности, обрабатываемый ПЭ1. Затем пошли дальше, превратив векторную ППС-2000 в матричную ВС.

Ввели сегментирование множества процессоров (процессоров решающего поля ). 64 ПЭ разбиваются или на 8 сегментов по 8 ПЭ, или на 4 сегмента по 16 ПЭ, или на 2 сегмента по 32 ПЭ. Это осуществляется, прежде всего, за счет установления связи с помощью РК между первым и последним ПЭ каждого сегмента. Тогда при обработке поверхности ПЭ "прокатываются" циклически не только по "длинному" вектору, но и, при сегментировании, по матричным элементам поверхности, как будет показано далее.

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

ППС-2000 имеет распределенную память.

В ППС-2000 предусмотрена двухуровневая схема управления: на уровне микрокоманд и команд. Память для их хранения — в УУ. На микрокомандном уровне пишутся отдельные фрагменты задачи — подпрограммы процедур, на командном — последовательность обращения к этим подпрограммам.

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

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

Возможна и динамическая загрузка микропрограмм в память ППС-2000.

Матричные ВС

Матричная ВС также является типичным представителем ОКМД, расширением принципа векторных ВС.

Классическим примером, прототипом и эталоном стала ВС ILLIAC 1V, разработанная в 1971 г. в Иллинойском университете и в начале 1972 г. установленная в Эймском научно-исследовательском центре NASA (Калифорния).

Одна последовательность команд программы управляет работой множества 64 ПЭ, одновременно выполняющих одну и ту же операцию над данными, которые могут быть различными и хранятся в ОП каждого ПЭ. (Производительность — до 200 млн. оп./с)

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


Рис. 1.10.  Схема обмена в матричной ВС

УУ — фактически простая вычислительная машина небольшой производительности и может выполнять операции над скалярами одновременно с выполнением матрицей ПЭ операций над векторами или матрицами. Посылает команды в независимые ПЭ и передает адреса в их ОП.

К центральной части подключена система ввода-вывода с управляющей машиной В-6500, устройство управления вводом-выводом, файловые диски, буферная память и коммутатор ввода-вывода. Операционная система, ассемблеры и трансляторы размещаются в памяти В-6500.

Почему же ВС — матричная?

ПЭ образуют матрицу, в которой информация от одного ПЭ к другому может быть передана через сеть пересылок данных при помощи специальных команд обмена. Регистры пересылок (рис. 1.11) каждого i -го ПЭ связаны высокоскоростными линиями обмена с регистрами пересылок ближайшего левого ( i-1 -го) и ближайшего правого ( i+1 )-го ПЭ, а также с регистрами пересылок ПЭ, отстоящего влево на 8 позиций от данного ( i-8 )-й и отстоящего вправо на 8 позиций от данного ( i+8 )-й, при этом нумерация ПЭ рассматривается как циклическая с переходом от 63 к 0 (нумерация возрастает по mod 64 ) слева направо и от 0 к 63 справа налево.


Рис. 1.11.  Конфигурация "быстрых" связей в ВС ILLIAC-4

Расстояния между ПЭ в сети пересылок и соответствующие пути передачи информации задаются комбинациями из (-1, +1, -8, +8).

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

Доступ к ОП имеют АУ соответствующего ПЭ, УУ системы и подсистема ввода-вывода. Управление доступом и разрешение конфликтов при доступе к ОП осуществляет УУ системы.

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

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


Рис. 1.12.  Решение задачи методом "сеток"

Кратко рассмотрим план решения подобной задачи на матричной ВС.

Пусть необходимо решить уравнение с частных производных

на области B:

Граничные условия:

f(0,y)= f1(y),

f(A,y)= f2(y),

f(x,0)= f3(x),

f(x,B)= f4(x).

Частные производные можно выразить через конечные разности несколькими способами, например:

Подставив полученные выражения в уравнение, получим основное рекуррентное соотношение для нахождения значения функции через ее значения в соседних четырех узлах:

fi, j = 0,5 fi+1, j + 0,5 fi-1, j - 0,25 hx2/hy(fi, j+1 - fi, j-1).

Распараллеливание вычислений и "прокатывание" матрицей ПЭ области B — многократные, до получения необходимой точности — очевидны.

А именно: первоначально в одном цикле итерации 64 ПЭ по выведенной формуле рассчитывают 8 x 8 узловых значений функции близ вершины координат, "цепляя" при этом граничные значения. Затем производится смещение вправо на следующую группу узловых значений функции. По окончании обработки по горизонтали производится смещение по вертикали и т.д. При следующей итерации процесс повторяется. От итерации к итерации распространяется влияние граничных условий на рассчитываемые значения функции. Процесс сходится для определения значений функции-решения в узлах сетки с требуемой точностью.

Вернемся к отечественной разработке ПС-2000 (ПС-2100) — векторной ВС. В ней предусмотрена возможность сегментации процессоров, при которой последний процессор в сегменте связывается регулярным каналом (аналог высокоскоростной линии) с первым. Все 64 процессора могут составить один сегмент, могут быть сформированы два сегмента по 32 ПЭ, четыре по 16, 8 по 8 ПЭ. Итак, получается идеальная схема для "покрытия" двумерной подобласти обсчитываемой области. Правда, отсутствуют быстрые связи по вертикали, что должно быть возмещено хранением всей информации по столбцам в ОП каждого ПЭ. Зато, при смещении процессоров на смежную подобласть по горизонтали, последний ПЭ предыдущей подобласти остается "левым" для первого в новой подобласти. Т.е. при таком смещении сохраняется регулярность фактических связей между узлами сетки.

В ILLIAC-1V такая регулярность сохранялась бы, если бы существовали быстрые связи между ПЭ7 и ПЭ0, ПЭ15 и ПЭ8 и т.д., то есть циклически по строкам матрицы.

Как видим, такие связи учтены при более поздних разработках матричных ВС.

ВС Крей-1 ("Электроника ССБИС")

ВС Cray-1, несмотря на последующие разработки, остается эталоном типа МКОД. В России разработан аналог — векторно-конвейерная ЭВМ "Электроника ССБИС", отличающаяся некоторыми увеличенными параметрами комплектации. Структура ВС показана на рис. 1.13.


Рис. 1.13.  Схема ВС Cray-1

Предназначена для выполнения как векторных, так и скалярных операций, Имеет 64 буферных (выравнивающих) регистра для 24 -битовых адресов ( B -регистры), 64 буферных (выравнивающих) регистров для 64 -битовых слов данных ( T -регистры). B -регистры в свою очередь пополняют буфер для одной из основных групп регистров машины — 8 адресных регистров, а T -регистры — для группы 8 скалярных регистров. Адресные регистры используются и как индексные. Третья основная группа регистров — 8 векторных регистров по 64 64 -битовых слов. Регистр длины вектора определяет число операций, выполняемых по векторным командам, т.е. действительную длину вектора. Маска вектора определяет элементы, над которыми выполняется операция.

Буфер команд состоит из четырех ЗУ, каждое из которых — из 64 16 -разрядных регистров. Представляет 4 программы, выполняемые в мультипрограммном режиме. (В "Э-ССБИС" — 16 таких ЗУ.)

12 специализированных функциональных блоков-конвейеров (в "Э-ССБИС" 16 блоков) выполняют арифметические, логические операции и сдвиг. Уровней конвейера — от 2 до 14. Блоки являются независимыми. Несколько функциональных блоков могут работать одновременно. Возможно "зацепление" векторов при выполнении операций вида A x B + C, когда два или более конвейеров выстраиваются в один и результат с одного немедленно поступает как операнд на другой.

Таким образом, параллелизм в обработке данных организуется с помощью:

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

(Нас интересует архитектура, но не катастрофически стареющие характеристики. Однако для справки: такт машины 12{,}5 нс, цикл обращения к ОЗУ 50 нс, производительность считается: 38 млн. скалярных оп/с и 80 млн. векторных оп/с.)

МВК "Эльбрус-2"

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


Рис. 1.14.  Общая схема МВК "Эльбрус-2"

Производительность (информация имеет историческую ценность) в 10-процессорном варианте — до 120 млн. оп/с ( 12,5 млн оп/с на одном процессоре). Максимальный объем ОП — 16 млн 72 -разрядных слов ( 144 Мбайт), максимальная пропускная способность каналов ввода-вывода — 120 Мбайт/с. Эти характеристики позволили решить многие проблемы применения супер-ЭВМ, но сегодня не впечатляют.

Принципиальные предпосылки разработки:

  1.  Аппаратная поддержка ЯВУ.
  2.  Параллелизм на двух уровнях — мультипроцессорная обработка (распределение процессов между процессорами), конвейерная обработка команд и параллельная обработка данных в многофункциональном АЛУ ( 10 ИУ).

В МВК могут входить от 1 до 10 ЦП, от 1 до 32 модулей ОП и от 1 до 4 ПВВ.

Каждый ПВВ имеет 40 каналов связи: 8 быстрых (аналог селекторных) каналов (БК) для магнитных барабанов и дисков и 32 стандартных (СК) для прочих устройств ввода-вывода.

Работа с удаленными объектами по линиям связи осуществляется с помощью процессоров передачи данных (их — до 16 ), которые являются самостоятельными модулями с собственной системой команд и внутренней памятью.

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

ЦП МВК "Эльбрус" имеет безадресную систему команд, основанную на ПОЛИЗ и выполняемую на стеке. Обрабатывает числовые данные в 32 разряда (полслова), 64 разряда (слово), 128 разрядов (двойное слово). Нечисловая информация может быть представлена в виде битовых, цифровых или байтовых наборов. Каждое слово сопровождается 6 -разрядным тегом, определяющим его тип. Два разряда используются в аппаратном контроле.

Проект МВК "Эльбрус-3"

Так как ассемблерный язык исключен из интерфейса пользователя, то аппаратная реализация (она отражена в системе команд — в машинном языке) МВК "Эльбрус-3" значительно отличается от "Эльбрус-2". Структура МВК представлена на рис. 1.15.


Рис. 1.15.  Общая схема МВК "Эльбрус-3"

Здесь ООП — общая оперативная память ( 8 секций (блоков) по 4 модуля; модуль — 32 Мбайт); МКТ — модульные комплексы телеобработки (аналог ППД — в "Эльбрус-2"); ЛОП — локальная оперативная память, 416 Мбайт.

Принципы, лежащие в основе разработки:

  1.  Программная совместимость на уровне ЯВУ (Эль-76 — ЯВУ-ассемблер) с другими моделями "Эльбрус".
  2.  Теговая архитектура.
  3.  Дальнейшее развитие многопроцессорности на общей ОП, что повышает производительность и структурную надежность. Пиковая производительность одного (из 16 ) процессора достигает 700 млн. оп/с при такте машины 10 нс.
  4.  Архитектура с длинным командным словом обеспечивает микрораспараллеливание между 7 ИУ АЛУ на уровне операций ( 2 ИУ сложения, 2 — умножения, одно — деления, 2 — логических), а также параллельное обращение по 8 каналам в ЛОП или ОП.
  5.  Семь конвейерных и независимых ИУ обеспечивают загрузку процессора работами в каждый такт.
  6.  Управление машиной позволяет контролировать каждый такт. Т.е. "длинная" команда выдается каждый такт, непосредственно запуская устройства без дополнительного динамического аппаратного планирования их загрузки.
  7.  Оптимизация распределения ресурсов возлагается на высокооптимизирующий транслятор с ЯВУ Эль-76 и с других языков высокого уровня.
  8.  Функционально разделенное СОЗУ снижает конфликты при обращении и отражает типы хранимых данных. Оно состоит из ассоциативного буфера команд в 2 тыс. слов, буфера стека в 1 тыс. слов для хранения верхних уровней локальных данных выполняемых процедур, буфера массивов в 512 слов и ассоциативной памяти глобалов (общих данных процедур) в 512 слов.

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

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

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

Все сказанное выше подтверждает перспективность структурных решений при проектировании многопроцессорного комплекса "Эльбрус-3" и его микропроцессорного развития "Эльбрус-3М", "Эльбрус-2К". Таким образом, структура "длинного командного слова" (архитектура VLIW, лежащая в основе EPIC ) попадает в разряд классических.

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

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

Такими решениями являются следующие.

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

Например, на одном кристалле MVP (Multimedia Video Processor) семейства TMS 320 C80 (фирма Texas Instrument ) расположены 4 32 -разрядных цифровых сигнальных процессора ( DSP — Digital Signal Processor) с фиксированной запятой ( ADSP-0ADSP-3 ). Их особенность — высокая степень конвейеризации и до 64 бит длина командного слова для параллельного выполнения нескольких операций. Система команд содержит команды над битовыми полями и структурами данных, несущими графическую информацию. Такая специализация обусловила понятие — DSP-архитектура.

Процессоры работают независимо. Т.е. ВС — типа MIMD — (Multiple-Instruction, Multiple-Data). Программируются отдельно на ассемблере или ЯВУ. Данными обмениваются через общую внутрикристальную память.

Каждый из ADSP содержит КЭШ-память команд ( 2 Кбайта), и через матричный коммутатор Crossbar получает доступ к 32 из имеющихся 50 Кбайт быстродействующей статической внутренней памяти. Память расслоенная — поделена на сегменты. Если два и более процессора в одном цикле попытаются обратиться к одному сегменту, аппаратная система управления доступом с циклическим изменением приоритета ( round robin prioritization ) позволит сделать это только одному процессору.

32 -разрядное АЛУ ADSP может работать как два 16 - или четыре 8 -разрядных АЛУ. Этого достаточно для обработки видеоизображений. Специальные блоки ускоряют обработку графики. Блоки генерации адресов формируют кольцевые (бесконечные) буферы. Аппаратно поддержаны три вложенных цикла.

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

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

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

Преследуя многофункциональность средств обмена, не обязательно требовать их размещения на одном кристалле с центральным процессором. Так, фирма Analog Devices предлагает микропроцессоры ADSP-21060/62 SHARC ("АКУЛА") для цифровой обработки сигналов, специально предназначенные для комплексирования.

Средства комплексирования "АКУЛЫ":

  •  магистраль для подключения 6 "АКУЛ" и одного ХОСТ-процессора (управляющего, с привилегированным доступом к магистрали, а также к памяти каждого процессора — через специальный порт);
    •  сигнальные регистры в составе каждого процессора, непосредственно связанные (одной ножкой) с каждым из других процессоров — для контроля их состояния;
    •  ЛИНКи — каждый процессор имеет 6 выходов (ЛИНКов) для непосредственной связи "процессор - процессор".
  1.  Общее адресное пространство комплексируемых микропроцессоров "АКУЛА" обеспечивает псевдообщую память и исключает необходимость программной организации обмена данными. Если адрес физически принадлежит ОП другого процессора, то обмен организуется автоматически, без вмешательства пользователя (т.е. программно не предусматривается).
  2.  Межпроцессорный (магистральный) обмен инициируется в том случае, если адрес считывания или записи принадлежит адресному пространству другого процессора (единичный обмен). Аналогично возникают групповые пересылки данных с использованием "чужого" адресного пространства.

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

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

Микропроцессор утверждается в роли основы элементно-конструкторской базы ВС, и это поняли ведущие разработчики.

В этом смысле привлекает внимание трансформация интересов "отца суперкомпьютеров" С.Крея, который признал определяющую роль принципа MIMD при построении ВС Cray Superserver 6400 System ( CS640 ), выпускаемой корпорацией Cray Research в сотрудничестве с компанией SUN Microsystems (сотрудничество с фирмой SUN ныне характерно и для ведущих российских разработчиков).

Система предполагает наращиваемую конфигурацию от 4 до 64 процессоров SuperSPARC. Принято компромиссное решение на основе классической схемы разделения (общей) ОП при многопроцессорной обработке и распределенной памяти при параллельной обработке массивов. Чтобы работать с частично распределенной памятью в ОЗУ, ВС имеет в любой конфигурации 4 шины. Шина использует сетевую технологию "коммутации пакетов". Это позволяет находить путь обмена единицами информации в соответствии с занятостью или освобождением шин.

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

Направление "мини-супер" призвано поддержать персональный компьютер

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

Супер-ЭВМ уникальна, мало тиражируема, цена ее высока.

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

Тогда целесообразно поставить следующую проблему.

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

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

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

Общая схема такой установки показана на рис. 2.1. Выбраны конкретные значения параметров.


Рис. 2.1.  Схема ВС для персонального компьютера

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

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

Семафорный механизм может быть эффективно реализован с помощью механизма закрытия адресов (памяти закрытых адресов).

Тогда, в общем случае применения семафоров, должны быть введены команды следующего вида.

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

Записать по семафору ( Зап(С) А ). Запись по адресу производится аналогично предыдущей команде.

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

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

  •  ожидается присвоение данному предикату значения 1 (в режиме "жужжания");
  •  пропускается выполнение данной команды.

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

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

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

Возможно использование простейших коммутаторов для обмена ПЭ с модулями памяти.

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

Произведем некоторые обобщения.

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

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

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

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

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

Все модели семейства МВК "Эльбрус" предполагают наличие в составе АЛУ процессора нескольких исполнительных устройств (ИУ), специализированных по типам операций. Тогда в целом для ВС можно сказать, что вычислительный ресурс второго уровня является распределенным и неоднородным (рис. 2.2).


Рис. 2.2.  ВС с распределённым решающим полем

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

Так, в МВК "Эльбрус-2" применена динамическая загрузка ИУ в процессе выполнения последовательности безадресных команд программы, которую подробно рассмотрим в лекции 3. Обобщенный алгоритм такой загрузки основан на промежуточном переводе безадресных команд в трехадресные. Появление адресов аргументов и результатов в каждой команде позволяет на основе совместного анализа нескольких команд, представленных в "окне просмотра", выявлять их частичную упорядоченность и выделять независимые команды для одновременного выполнения. Это — адресный метод распараллеливания, который рассматривался в архитектуре data flow. Команды проходят стадии обработки, как показано на рис. 2.3.


Рис. 2.3.  Схема оптимизатора-компоновщика "длинных" командных слов

Однако проект МВК "Эльбрус-3", породивший микропроцессорное воплощение — МВК "Эльбрус-3М", — основан на использовании идеи "длинного" командного слова и управления каждым тактом системы. Динамическое распределение работ между ИУ заменено статическим — предписанием каждому ИУ, что он должен начать делать в данном такте. В "длинном" командном слове, в соответствующих позициях, записаны инструкции каждому ИУ.

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

Способы распараллеливания

Различают два основных способа распараллеливания: по управлению и по информации.

Первый способ — представление алгоритма задачи в виде частично-упорядоченной последовательности выполняемых работ. Затем в результате диспетчирования реализуется оптимальный план выполнения работ в ВС при ограничениях на время выполнения всего алгоритма или за минимальное время.

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

Для исследования графа и диспетчирования используют матрицы следования S ; их дополняют столбцом T весов — получают расширенные матрицы следования S* (рис. 2.4).


Рис. 2.4.  Исходная информация для распараллеливания

Здесь предполагаем, что ВС — однородная, с общей (разделяемой) памятью, т.е. потерями времени на обмен между работами можно пренебречь.

Пусть ВС содержит два процессора (n = 2). Тогда в результате оптимального распределения получим план (рис. 2.5).


Рис. 2.5.  Временная диаграмма параллельного выполнения работ

План действительно совпадает с оптимальным, т.к. длина расписания T = 7, что совпадает с длиной критического пути в графе, Tкр = 7 (путь 1 -> 3 -> 4 ).

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

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

Обобщим эту задачу.

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


Рис. 2.6.  Обработка "окна просмотра"

Составим по его содержимому соответствующую матрицу следования размерности m x m:

По матрице следования S диспетчер производит назначение.

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

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

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

1. Рассмотрим задачу умножения матриц :

Развернем матрицу — результат — в линейный (одномерный) массив, переименуем ее элементы и заменим два индекса на один:

Пусть ВС содержит n процессоров. Выберем следующий план счета элементов матрицы C:

процессор 1 считает элементы d1, d1+n, d1+2n, ...

процессор 2 считает элементы d2, d2+n, d2+2n, ...

........................................................................

процессор n считает элементы dn, d2n, d3n, ...

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

Здесь не потребовалась какая-либо синхронизация параллельного вычислительного процесса.

2. Рассмотрим задачу счета способом "пирамиды".

Эту задачу мы исследовали при рассмотрении ВС типа SPMD. Посмотрим еще раз, какая синхронизация нам здесь потребуется.

Пусть необходимо перемножить все элементы некоторого массива {a1,a2,... , a10}. Каждый элемент занимает одну ячейку памяти. Пусть число процессоров в ВС n=4. Чтобы распараллелить этот процесс, примем схему счета "пирамидой" (рис. 2.7).


Рис. 2.7.  Граф-схема выполнения операции "свёртки"

Количество уровней операций в ней ]log2 m[=]log210[=4 ( ]x[ — ближайшее целое, не меньшее x ).

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


Рис. 2.8.  Схема выполнения операции свёртки четырьмя процессорами

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

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

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

Здесь распараллеливание по данным смыкается с распараллеливанием по управлению.

Возможная схема общей для всех процессоров программы — на рис. 2.9. Она реализована в примере для ВС типа SPMD.


Рис. 2.9.  Схема программной синхронизации при выполнении операции "свёртки"


 

А также другие работы, которые могут Вас заинтересовать

63813. Организация скорой медицинской помощи 33 KB
  Организация скорой медицинской помощи Первые станции СМП появились в нач. Сейчас СМП претерпела изменения. СМП врачи скорой помощи. В крупных городах в 70 –е гг неотложную помощь и СМП объединили.
63814. Организация и управление лечебно-профилактической помощью сельскому населению 28 KB
  К функциям земского самоуправления относилась и организация мед. В 1936 году медицинская организация Лиги наций признала что наиболее удобной формой помощи сельскому населению является сельский врачебный участок.
63815. Фельдшерско-акушерский пункт 22 KB
  Санитарно – противоэпидемическая работа: а) организация прививок среди населения б) организация подворных обходов с целью выявления инфекционных больных) санитарный надзор за детскими, коммунальными, пищевыми объектам...
63816. Сельская участковая больница. Сельская врачебная амбулатория 29 KB
  В больнице 1 категории 6 отделений: терапевтическое хирургическое акушерско-гинекологическое педиатрическое инфекционное противотуберкулёзное. В каждой последующей категории на 1 отделение меньше.
63817. Центральная районная больница 31 KB
  Центральная районная больница ЦРБ Оказывает помощь жителям: жителям районного центра по участковому принципу проживающим на приписных участках по участковому принципу. Те населённые пункты которые находятся недалеко от ЦРБ и обслуживаются ею называются приписными участками проживающим в сельской местности...
63818. Областная больница, структура, задачи 24.5 KB
  ОБ является центром организационно методического руководства всех мед. учреждений области и базой специализированной помощи и специализации и повышения квалификации среднего и старшего мед. Имеет клинико экспертный отдел который проводит анализ оказанной помощи проводит экспертизу...
63819. Охрана материнства и детства — приоритетное направление здравоохранения 30 KB
  Показатели здоровья женщин и детей являются наиболее чувствительным индикатором социально-экономического развития общества. Деятельность государственной системы охраны материнства и детства направлена на реализацию комплекса социально-экономических и лечебно-профилактических мер...
63820. Родильный дом 30 KB
  Стационар родильного дома имеет следующие подразделения: 1 приемно-пропускной блок; 2 родовые отделения; 3 послеродовое физиологическое первое акушерское отделение 50 55 акушерских коек; 4 обсервационное второе акушерское отделение 20 25 акушерских коек...
63821. Женская консультация 28.5 KB
  Основными задачами женской консультации являются: проведение профилактических мероприятий направленных на предупреждение осложнений беременности родов послеродового периода гинекологических заболеваний; оказание лечебно-гинекологической помощи...