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

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

Разбить на страницы
Показывать лекцию целиком

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    В этом смысле привлекает внимание трансформация интересов "отца суперкомпьютеров" С.Крея, который признал определяющую роль принципа 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) следует через "окно просмотра" так, что для планирования оптимальной загрузки процессоров диспетчер может анализировать некоторое множество этих макроинструкций и из них выбирать вариант назначения их на процессоры для выполнения. Каждая макроинструкция может интерпретироваться и как процедура, где можно выделить имя $$\theta _{\mu }$$, множество $$\{ \alpha _{\mu }\}$$ входных параметров, множество $$\{ \beta _{\mu }\}$$ выходных параметров. На рис. 2.6 отображено "окно просмотра", через которое следует поток макроинструкций.

    (рис 2.6) Обработка "окна просмотра"

    Составим по его содержимому соответствующую матрицу следования размерности m x m:$${ S=||\alpha_{\mu \nu}||^m_I= \begin{pmatrix} \alpha_{11} \alpha_{12} \ldots \alpha_{1m}\\ \hdotsfor{4}\\ \alpha_{m1} \alpha_{m2} \ldots \alpha_{mm} \end{pmatrix} } \\ \\ { \alpha_{\mu \nu}= \left\{ \begin{aligned} 1,\ \text{если} \ \varepsilon_{\mu \nu}\ne \oslash,\\ 0,\ \text{в противном случае};\\ \end{aligned} \right. } \\ \\ { \varepsilon_{\mu \nu}=(\{\alpha_\mu\}\cap\{\beta_\nu\})\cup(\{\beta_\mu\}\cap\{\alpha_\nu\}\cup\{\beta_\nu\})\ \text{для всех}\ \nu < \mu. }$$

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

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

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

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

    1. Рассмотрим задачу умножения матриц $$A\times B=C$$:$${ \begin{pmatrix} a_{11}\ldots a_{1m} \\ \hdotsfor{3}\\ a_{m1}\ldots a_{mm} \end{pmatrix} \times \begin{pmatrix} b_{11}\ldots b_{1m} \\ \hdotsfor{3}\\ b_{m1}\ldots b_{mm} \end{pmatrix} = \begin{pmatrix} c_{11}\ldots c_{1m} \\ \hdotsfor{3}\\ c_{m1}\ldots c_{mm} \end{pmatrix} } \\ \\ { c_{ij}=\sum^m_{k=1}a_{ik}b_{kj}.$$

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

    $$\centering \smallskip \tabcolsep=4pt {\small \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|} \hline c_{11} c_{12} \ldots c_{1m} c_{21} \ldots c_{2m} c_{31} \ldots c_{mm}\\ \hline d_1 d_2 \ldots d_m d_{m+1} \ldots d_{2m} d_{2m+1} \ldots d_{m^2}\\ \hline \end{tabular} $$

    Пусть ВС содержит 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) Схема программной синхронизации при выполнении операции "свёртки"

    Страницы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    В этом смысле привлекает внимание трансформация интересов "отца суперкомпьютеров" С.Крея, который признал определяющую роль принципа 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) следует через "окно просмотра" так, что для планирования оптимальной загрузки процессоров диспетчер может анализировать некоторое множество этих макроинструкций и из них выбирать вариант назначения их на процессоры для выполнения. Каждая макроинструкция может интерпретироваться и как процедура, где можно выделить имя $$\theta _{\mu }$$, множество $$\{ \alpha _{\mu }\}$$ входных параметров, множество $$\{ \beta _{\mu }\}$$ выходных параметров. На рис. 2.6 отображено "окно просмотра", через которое следует поток макроинструкций.

    (рис 2.6) Обработка "окна просмотра"

    Составим по его содержимому соответствующую матрицу следования размерности m x m:$${ S=||\alpha_{\mu \nu}||^m_I= \begin{pmatrix} \alpha_{11} \alpha_{12} \ldots \alpha_{1m}\\ \hdotsfor{4}\\ \alpha_{m1} \alpha_{m2} \ldots \alpha_{mm} \end{pmatrix} } \\ \\ { \alpha_{\mu \nu}= \left\{ \begin{aligned} 1,\ \text{если} \ \varepsilon_{\mu \nu}\ne \oslash,\\ 0,\ \text{в противном случае};\\ \end{aligned} \right. } \\ \\ { \varepsilon_{\mu \nu}=(\{\alpha_\mu\}\cap\{\beta_\nu\})\cup(\{\beta_\mu\}\cap\{\alpha_\nu\}\cup\{\beta_\nu\})\ \text{для всех}\ \nu < \mu. }$$

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

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

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

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

    1. Рассмотрим задачу умножения матриц $$A\times B=C$$:$${ \begin{pmatrix} a_{11}\ldots a_{1m} \\ \hdotsfor{3}\\ a_{m1}\ldots a_{mm} \end{pmatrix} \times \begin{pmatrix} b_{11}\ldots b_{1m} \\ \hdotsfor{3}\\ b_{m1}\ldots b_{mm} \end{pmatrix} = \begin{pmatrix} c_{11}\ldots c_{1m} \\ \hdotsfor{3}\\ c_{m1}\ldots c_{mm} \end{pmatrix} } \\ \\ { c_{ij}=\sum^m_{k=1}a_{ik}b_{kj}.$$

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

    $$\centering \smallskip \tabcolsep=4pt {\small \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|} \hline c_{11} c_{12} \ldots c_{1m} c_{21} \ldots c_{2m} c_{31} \ldots c_{mm}\\ \hline d_1 d_2 \ldots d_m d_{m+1} \ldots d_{2m} d_{2m+1} \ldots d_{m^2}\\ \hline \end{tabular} $$

    Пусть ВС содержит 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) Схема программной синхронизации при выполнении операции "свёртки"

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^