1.5.Параллелизм уровня потоков и уровня заданий
Параллелизм уровня потоков и уровня заданий применяется в процессорах класса MIMD.
MIMD (англ. Multiple Instruction stream, Multiple Data stream – Множественный поток Команд, Множественный поток Данных) – концепция архитектуры компьютера, используемая для достижения параллелизма вычислений. Машины имеют несколько процессоров, которые функционируют асинхронно и независимо. В любой момент, различные процессоры могут выполнять различные команды над различными частями данных. MIMD-архитектуры могут быть использованы в целом ряде областей, таких как системы автоматизированного проектирования / автоматизированное производство, моделирование, а также коммуникатор связей (communication switches). MIMD машины могут быть либо с общей памятью, либо с распределяемой памятью. Эта классификация основана на том как MIMD-процессоры получают доступ к памяти. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.
Обработка разделена на несколько потоков, каждый с собственным аппаратным состоянием процессора, в рамках единственного определённого программным обеспечением процесса или в пределах множественных процессов. Поскольку система имеет несколько потоков, ожидающих выполнения (системные или пользовательские потоки), эта архитектура эффективно использует аппаратные ресурсы.
В MIMD могут возникнуть проблемы взаимной блокировки и состязания за обладание ресурсами, так как потоки, пытаясь получить доступ к ресурсам, могут столкнуться непредсказуемым способом. MIMD требует специального кодирования в операционной системе компьютера, но не требует изменений в прикладных программах, кроме случаев когда программы сами используют множественные потоки (MIMD прозрачен для однопоточных программ под управлением большинства операционных систем, если программы сами не отказываются от управления со стороны ОС). И системное и пользовательское программное обеспечение, возможно, должны использовать программные конструкции, такие как семафоры, чтобы препятствовать тому, чтобы один поток вмешался в другой, в случае если они содержат ссылку на одни и те же данные. Такое действие увеличивает сложность кода, снижает производительность и значительно увеличивают количество необходимого тестирования, хотя обычно не настолько чтобы свести на нет преимущества многопроцессорной обработки.
Подобные конфликты могут возникнуть на аппаратном уровне между процессорами, и должен обычно решаться аппаратными средствами, или с комбинацией программного обеспечения и оборудования.
1.5.1.Архитектура SPMD
Анализ задач, требующих вмешательства супер-ЭВМ, показывает, что все такие задачи – так называемые задачи "большой размерности", которые сводятся к обработке больших массивов данных. Их сложность может быть как полиномиальной, так и экспоненциальной. В сведении к обработке больших массивов данных кроется серьезное обобщение. Действительно, очевидность такого положения демонстрируется не только на традиционных задачах – векторных, матричных (обработки сигналов и изображений, картографии, геодезии и др.), конечно-разностных (во всем диапазоне сводимых к ним), моделирования поведения среды. Она проявляется на задачах, моделирующих многоканальный доступ к данным, на задачах одновременного управления множеством объектов, использования общих баз данных (в серверах), баз знаний, обработки нейросетей. Она же подтверждается на тех задачах, для которых сегодня считается трудным определение целесообразной стратегии распараллеливания. Это задачи оптимального планирования и исследования операций, по сложности известные как NP-сложные задачи, подкласс задач экспоненциальной сложности. Большая часть таких задач решается методом "ветвей и границ", т.е. перебором вариантов. Можно считать, что каждый вариант условно (да и фактически) определяет элемент некоторого динамически развиваемого массива. Значит, в распределении вариантов при решении таких задач – путь к реализации второго способа распараллеливания.
Здесь нет возврата к традиционным векторным машинам. Обработка разных элементов одного массива, к которой сводится задача, должна быть в целом асинхронной, по разным ветвям одного, а если надо, – по разным алгоритмам. Именно последнее замечание свидетельствует о возможности реализации и первого способа распараллеливания. Вместе с тем, необходимо обеспечить возможность синхронизации ВС при обработке общих данных или другой реализации частично упорядоченных работ.
Для решения отдельной задачи за минимальное время традиционные симметричные ВС требуют формирования в очереди к процессору большого числа, в общем случае взаимосвязанных, процессов отдельных программ, выполняющихся под управлением операционной системы. С увеличением числа процессоров в ВС растет сложность программирования. Число процессов ограничено особенностями алгоритмов, отраженными в его информационно-логической граф-схеме. Не все возможности распараллеливания могут быть использованы, так как накладные расходы на организацию вычислений при высокой детализации работ, порождающих отдельные процессы, становятся неимоверно высоки.
Значительный вес обрабатываемой информации, организованной в массивы, определил применение векторных ВС с синхронно работающими процессорами при выполнении общей команды. Этот способ обработки расширил возможность распараллеливания по данным, но ограничил ее локальным применением, хотя и такое применение оказывается достаточно эффективным для построения специализированных систем. При этом обработка однородных данных по разным ветвям алгоритма затруднена.
Ряд архитектур ВС основан на совмещении указанных способов параллельной обработки. Векторные процессоры включаются в ВС как операционные функциональные устройства, выполняющие специальные команды в программе. Соответствующее этому преобразование алгоритмов решения широкого круга задач превратилось в самостоятельную проблему (проблему векторизации задач), что не исключает поиска других архитектурных решений.
Известен достаточный опыт экспериментального программирования задач повышенной сложности на основе подобной технологии.
Из сказанного выше следует вывод: необходимо на основе симметричной ВС построить ВС, в наибольшей степени приспособленную к распределению элементов больших массивов для обработки разными процессорами по идентичным алгоритмам. Обработка должна в общем случае производиться по разным ветвям. Должна быть синхронизация обращений к общим данным. Выполнение разных ветвей одной программы делает возможным выполнение разных программ разными процессорами. Тип таких ВС получил название SPMD: "Single Program – Multiplе Data" ( SPMD-технология ).
Тогда можно представить абстрактно общую архитектуру многопроцессорной ВС, соответствующую современным представлениям о параллельном вычислительном процессе.
Отметим лишь некоторые черты такой архитектуры, которые должны быть обязательно восполнены при реализации – с помощью процедур ОС или микропрограммно – в системе команд процессора на симметричной ВС.
"Идеальная" структура ВС SPMD-технологии приведена на рис.1.10. Программа находится в памяти команд (ПК), откуда сегментами считывается в буферы команд БКi процессоров Пi, i = 0, ..., N-1. БКi – активное устройство, способное считывать следующий сегмент программы на фоне выполнения предыдущего по входящей в сегмент команде.
Рис. 1.10. Структура ВС
Память процессора ППi содержит область для хранения стеков вычислительного процесса, в том числе – стеков подпрограмм и вложенных циклов. В других областях этой памяти хранятся модификаторы, дескрипторы массивов и локальные величины. Через коммутатор К процессоры связаны с оперативной памятью данных (ОПД), состоящей из P модулей Sp, p = 0, ..., P-1, с независимым доступом. Модули объединены в блоки, внутри каждого из которых адресация осуществляется по принципу интерливинга. Память закрытых адресов (ПЗА) служит для синхронизации вычислений методом управления потоком данных: считывание по отмеченным в нем адресам ОПД (и, следовательно, вычислительный процесс) задерживается до выполнения записи по этим адресам. Конфликт при одновременной попытке двух и более процессоров закрыть один адрес разрешается в пользу одного процессора, а попытка повторного закрытия адреса воспринимается как попытка считывания по нему. Блок C предназначен для синхронизации Пi в необходимых случаях – для одновременного начала выполнения программы с некоторой команды.
Микропрограммирование, как и расширение набора операций на основе более простых, позволяет создать достаточно широкий набор сложных операций, определяющих систему команд ВС, ее машинный язык.
|
