Файл: Мультипроцессоры (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МУЛЬТИ ПРОФЕССОРОВ И ИХ ИСПОЛЬЗОВАНИЯ).pdf

Опишем подробнее основные положения архитектуры Data Flow. Язык машины потока данных существенно отличается от языка классической машины по всем перечисленным позициям. Основной лексической единицей языка машины потока данных является пакет. Структура пакета приведена на рис. 22.

Рис. 22 Структура Data Flow пакета

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

Перечисленные качественные характеристики архитектурной идеи, лежащей в основе проекта Data flow, воспринимаются как более предпочтительные для построения систем с массовым параллелизмом. Однако до настоящего времени неизвестно ни одного варианта их промышленной реализации - проект Data flow не выходит из стадии исследования и разработки. Наш опыт модельных испытаний системы с элементами Data flow, описанный в первой части настоящей статьи даёт тот же результат быстрого прекращения роста производительности на уровне 3-х кратного ускорения при 6 процессорах. Для того, что бы нащупать путь выхода из этого тупика необходимо понять, что объединяет оба проекта, несмотря на обозначенные нами существенные их различия. Общим для классической архитектуры и для проекта Data flow является принцип опережающей разметки трассы процесса. В обоих случаях знаковая система, лежащая в основе архитектуры, является средством создания символьной копии процесса. В классической машине символьная копия процесса существует в виде последовательности команд, а в архитектуре Data flow в виде потокового графа. В классической архитектуре команды считываются синхронно по одной в порядке следования в записи, а в Data flow активируются асинхронно группами в соответствии с логикой спуска по готовности данных. Но и в том и в другом случае активированные команды и пакеты не являются реальными агентами осуществления процессов обработки и вычислений, это только ссылки на данные и на функции. В след за активацией фрагментов трассы процесса разворачиваются потоки обеспечивающих событий, необходимых для поиска, доступа в память, чтения и транспорта данных к местам локализации функций обработки, а за тем по транспорту и размещению в памяти результатов обработки. Основным источником многочисленных накладных потерь являются работы по обслуживанию трассы процесса. Причём, запись трассы в виде потокового графа в Data flow в отличии от линейной последовательности в классической машине, порождает более сложные и объёмные работы по её обслуживанию. Проблема многократного использования стереотипных фрагментов трассы при линейной последовательной записи требует выделения двух точек записи – начала и конца процедуры. Для многократного повторного использования фрагмента потокового графа необходимо обозначить множество входных и выходных полюсов, привязанных к соответствующим вершинам графа. Далее необходимо организовать очереди фишек на входных полюсах, а сами фишки разметить по принадлежности к поколениям данных, возникающим в потоке обработки. Эта проблема получила название задачи раскраски фишек. А затем решать проблему синхронизации потоков фишек на всех входных полюсах процедуры. И всё это ещё не процесс вычислений – это только работы по обслуживанию записи трассы процесса. И это далеко не единственная проблема проекта, но она позволяет понять, почему проект Data flow до сих пор остаётся проектом.

Поищем аналогии в другой области. Похожая ситуация имела место на начальном этапе разработки проекта глобальной сети связи в конце 60-х годов [30]. Географически распределённые сети связи континентального и межконтинентального масштаба управлялись централизованно через центры коммутации. Сети функционировали на базе технологии коммутации цепей. Для осуществления сеанса связи через центры коммутации прокладывался маршрут, который монополизировал дорогостоящие магистральные ресурсы на время сеанса для пары абонентов. Для быстрого обслуживания плотных потоков требований на соединение приходилось наращивать число параллельно работающих каналов. Когда проектировщики задумались о построении глобальной единой автоматизированной системы связи (ЕАСС) и стали подсчитывать необходимые объёмы капитальных вложений оказалось, что проект по стоимости неподъёмный для самых богатых стран и их совместных усилий. Тогда инженеры связисты сделали экспертные оценки эффективности использования магистралей связи. Оказалось, что эффективность их загрузки чудовищно низкая и лежит в пределах нескольких процентов. Существовала проблема выбора - или строить и вводить в эксплуатацию гигантские объёмы новых магистралей или решить системную проблему и поискать более продуктивные технологии связи с лучшими показателями эффективности. Результат нам известен - была создана технология коммутации пакетов, современная глобальная паутина есть ни что иное как сеть пакетной коммутации [31].

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

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

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

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

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

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

2.3 Архитектура самоопределяемых данных и принципы распределенного управления

Идея построения архитектуры самоопределяемых данных имеет определённую предысторию, некоторые её фрагменты изложены в ряде публикаций и патентов прошедших лет [17],[32], [33].

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

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

Рис.23 Формат самоопределяемого операнда

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

Рассмотрим логику взаимодействия самоопределяемых операндов проиллюстрированную на рис. 24.

Рис. 24 Схема взаимодействия самоопределяемых операндов

В нижней части схемы изображены два операнда, предназначенные для выполнения заданной бинарной операции. Операция селекции может осуществляться аппаратурой или программно и смысл селекции состоит в том, что селектор отбирает пары операндов по кодовым состояниям полей селекции. На выходе селектора формируется блок, называемый парой. Пара состоит из двух информационных полей A₁ и A₂ , предназначенных для выполнения бинарной операции. К паре пристыковывается теговое сопровождение одного из операндов, второй тег после селекции отбрасывается. Отселектированная пара направляется в канал обработки, который состоит их двух секций – арифметического блока и преобразователя теговых кодов. Арифметический блок это стандартное арифметико-логическое устройство (АЛУ), которое управляется кодом операции из тегового сопровождения пары. Секция преобразования тегов содержит для каждого тегового поля свой унарный функциональный преобразователь. В результате прохождения через канал обработки образуется новый операнд A₃ с новым теговым сопровождением.

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

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

Рис. 25 Схема взаимодействия упрощённых самоопределяемых операндов