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

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

Иллюстрации

Показать все

Реферат

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

Основой построения ЭВМ являются принцип программного управления (Чарльз Бэб-бидж - 1861 г.) и принцип хранимой в памяти программы (Джон фон-Нейман - 1942 г.). Известны [1-3] два основных способа организации вычислений: выполнение команд программы в том порядке, в котором они размещены в памяти, начиная с первой, и выполнение команд программы по готовности данных.

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

Достоинствами, определившими широкую распространенность ВС controlflow-архитектуры, являются: близость используемых при программировании алгоритмических языков к естественному языку описания алгоритмов решаемых задач (математическому, в частности); глубокая теоретическая проработка процессов алгоритмизации, программирования и проектирования технических средств; наличие проверенного многолетней практикой использования системного программного обеспечения, включая средства оптимизации структур исполняемых программ; относительные простота конструкции технических средств и низкая стоимость.

Недостатками ВС controlflow-архитектуры являются: последовательное выполнение команд программы, большое количество тактов обращения к памяти в цикле работы центрального процессора, что канал «процессор - память» делает «узким местом», ограничивающим быстродействие ВС [1, 7, 14].

Второй способ известен как управление потоком данных (англ. data flow). Основными причинами появления ВС dataflow-архитектуры явились настоятельная необходимость в существенном увеличении производительности и наличие в структуре ВС controlflow-архитектуры «узкого места», препятствующего ее увеличению. Существенными признаками ВС dataflow-архитектуры являются ассоциативная память, отсутствие счетчика адреса команды и описание алгоритма решаемой задачи ярусно-параллельной формой помеченного ориентированного графа потока данных, в вершины которого отображаются операции, а в дуги - отношения между ними по данным и логическим условиям выполнения [4].

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

Попытки увеличения быстродействия ВС controlflow-архитектуры и ее модификаций базировались на совершенствовании элементной и компонентной базы, наращивании тактовой частоты, конвейеризации вычислительного процесса, мультипрограммировании, мультипроцессировании, адаптации систем команд к изобразительным возможностям алгоритмических языков и структурам исполняемых программ, буферизации канала «процессор - память» (кэшировании), адаптации структур программ к многопроцессорной центральной части ВС (мультискалярная архитектура) и топологии центральной части многопроцессорной ВС к структуре исполняемых программ (реконфигурируемые многопроцессорные ВС), выявлении и реализации скрытого параллелизма последовательных программ (суперскалярная, WLIV- и EPIC-архитектуры), увеличении числа одновременного обрабатываемых потоков (мульти- и гипертредовая архитектуры) [5-10].

Основными причинами неполного извлечения из конвейеров команд их потенциальных возможностей явились наличие разгона и выбега, зависимость команд программы по данным и управлению, а также неверные предсказания переходов [6-8, 11, 12].

Быстродействие ВС суперскалярной архитектуры ограничили: малый размер «окна исполнения», неверные предсказания переходов, квадратичный рост сложности ядра, с увеличением числа функциональных устройств в составе центральной части, повышение нагрузки на канал «процессор-память» и переменная степень скрытого параллелизма последовательных программ [7, 12].

«Обозреть» всю программу планировалось при создании мультискалярной архитектуры. Однако при статическом исследовании транслятором программного кода размер окна исполнения фактически определили команды перехода. Функциональные устройства превратились в полнокровные процессоры, а параллелизм уровня команд остался не востребованным [7]. Возросли сложность трансляции и реализуемого операционной системой управления параллельными (последовательными взаимодействующими) процессами, что отрицательно сказалось на цене.

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

Мультипроцессирование [4, 5, 8] потенциально позволяет не только покрыть все виды параллелизма (от параллелизма независимых задач до параллелизма данных), но и повысить надежность функционирования центральной части ЭВМ за счет выявления отказавших процессорных элементов (ПЭ) и перераспределения их вычислительной нагрузки между исправными ПЭ. Коммуникации между ПЭ строили и продолжают строить по ортогональному принципу (матрица, куб, гиперкуб, тор), что позволяет эффективно реализовать лишь параллелизм слабо зависимых ветвей и параллелизм данных. Эффективно реализовать параллелизм уровня команд в этих топологиях не удается ввиду отсутствия в них диагональных связей [12-14]. В этих условиях, с точки зрения эффективного использования основных вычислительных ресурсов, возможность воссоздания в гиперкубе практически любой топологии [7] выглядит мало привлекательной.

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

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

Мульти- или гипертредовая, т.е. многопотоковые, архитектуры по сути [7] являются альтернативой кэшированию. Их особенностью является введение в состав центрального процессора n блоков регистров, закрепление их за тредами (подпроцессами) и циклическое переключение процессора с блока на блок. Если время обращения к основной памяти не превышает (n-1) тактов, то проблема «узкого места» успешно решается. Однако и этот способ не идеален. Переключение процессора на новый тред предполагает преемственность состояний. Традиционные запоминание старого и восстановление нового состояния процессора - неприемлемы. Поэтому каждый блок регистров должен иметь довольно емкую служебную часть, хранящую слово состояния процессора в предыдущем шаге реализации закрепленного за ним подпроцесса.

При всем различии подходов к созданию мультитредовых микропроцессоров [7], общим для них является введение множества устройств выборки команд, каждое из которых организует «окно исполнения» для одного подпроцесса. В рамках одного подпроцесса выполняется предсказание переходов, переименование регистров и динамическая подготовка команд к исполнению. Тем самым, общее число находящихся в обработке команд значительно превышает размер окна исполнения однопотокового процессора, с одной стороны, и тактовая частота не лимитируется размером окна исполнения - с другой. Выявление подпроцессов может производиться компилятором на уровне входной (на языке высокого уровня) или выходной (исполняемой) программы. Однако компиляторы не всегда могут разрешить проблемы зависимостей между подпроцессами на уровне регистров и ячеек памяти, проявляющимися в ходе исполнения. Для этого в микропроцессор вводится специальная аппаратура условного исполнения, предусматривающая возврат с отбрасыванием наработанных результатов при обнаружении нарушения зависимостей между подпроцессами по данным.

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

В итоге мульти- или гипертредовые микропроцессоры, наряду с сокращением разрыва между скоростью обработки и временем доступа во внекристальную память, призваны уменьшить простои центрального процессора в ожидании команд или данных. Однако практика показала, что введение двух тредов отнюдь не удваивает производительности. Дополнительная регистровая память и таблицы страниц (англ. аббревиатура TLB), как критические ресурсы, порождают дополнительные «промахи», «лишние» откачки и подкачки блоков, что приводит к неявному увеличению времени переключения процессора с блока на блок [11].

В итоге, несмотря на разработку новых (нефоннеймановских) архитектур и очевидный прогресс в области технологии производства микропроцессоров, ни одно новшество, в том числе параллелизм и многоядерность не дало прироста производительности, пропорционального потребляемой энергии и затрачиваемым системным ресурсам [11].

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

Известна параллельная вычислительная система с программируемой архитектурой (см. патент RU 2202123 С2, МПК⁷ G06F 15/16, опубл. 10.04.2003), включающая N параллельных процессоров, каждый их которых содержит матрицу процессорных элементов (ПЭ), управляющий процессор, системную шину, служебное ОЗУ и буферное ОЗУ. При этом каждый параллельный процессор дополнительно содержит один или более сетевых адаптеров, первая группа входов-выходов каждого сетевого адаптера соединена с системной шиной параллельного процессора, которому принадлежит данный сетевой адаптер, а вторая группа входов-выходов каждого сетевого адаптера соединена с одной из коммуникационных сред. Дополнительно к перечисленному в ВС введены один или более вычислительных узлов, каждый из которых содержит последовательный процессор, системную шину и один или более сетевых адаптеров. При этом группа входов-выходов последовательного процессора соединена с системной шиной, с которой также соединена первая группа входов-выходов каждого сетевого адаптера, а вторая группа входов-выходов каждого сетевого адаптера соединена с одной из коммуникационных сред.

Этот аналог имеет следующие недостатки:

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

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

Известна также мультипроцессорная система (см. патент RU 2450339 С2, кл. G06F 15/16, опубл. 10.05.2012 Бюл. №13), содержащая множество параллельных процессоров в одном чипе, компьютерную память, расположенную в этом чипе и доступную каждому из упомянутых процессоров, а разрядность этой шины не превышает разрядности одной строки памяти. При этом каждый из этих процессоров выполнен с возможностью обработки набора команд, оптимизированного для параллельной обработки на уровне потоков, который может быть расширен командами оптимизации выполнения последовательностей команд в процессоре. Кроме этого каждый процессор содержит локальную кэш-память, выделенную каждому из, по меньшей мере, трех конкретных регистров в данном процессоре: регистру команды, регистру операнда и регистру результата. Предложен вариант мультипроцессорной системы, содержащей множество параллельных процессоров, связанных с внешним контроллером памяти и внешним процессором и внедренных в кристалл динамической оперативной памяти (DRAM). Предложен также способ параллельной обработки на уровне потоков системой, содержащей главный процессор и компьютерную память в одном чипе, и множество параллельных процессоров, предназначенных для обработки одного потока с использованием минимального набора команд.

Этот аналог имеет следующие недостатки:

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

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

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

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

- применение в операционных устройствах накапливающих сумматоров, требующих последовательной подачи на вход кодов операндов [], не способствует повышению быстродействия процессоров,

- изобретение не использует параллелизма уровня команд, реализация которого вносит наибольший вклад в повышение производительности.

Наиболее близким к заявляемому изобретению по технической сущности и достигаемому техническому результату является асинхронная синергическая вычислительная система (см. патент РФ №2198422 С2, кл.: G06F 9/28, G06F 11/14, G06F 15/76. Опубл. 10.02.2003.), содержащая N функциональных блоков, коммутатор "каждый с каждым", имеющий N информационных входов, 2N адресных входов и 2N информационных выходов. Каждый функциональный блок состоит из устройства управления, устройства памяти команд и операционного устройства, реализующего двуместные и одноместные операции, а также имеет два идентификационных входа аргументов, два входа признаков готовности аргументов, два информационных входа, идентификационный выход аргументов, два выхода признаков аргументов, два адресных выхода, идентификационный выход результата, выход признака результата, информационный выход, выход логического номера, N входов признаков разрешения выбора команд, выход признака разрешения выбора команд, а в коммутатор введены N идентификационных входов результатов, N входов признаков готовности результатов, N идентификационных входов аргументов, 2N входов признаков аргументов, N входов логических номеров, 2N идентификационных выходов аргументов, 2N выходов призраков готовности аргументов. Причем в k-м функциональном блоке (k=1,…,N) первый и второй идентификационные входы аргументов соединены, соответственно, с (2k-1)-м и 2k-м идентификационными выходами аргументов коммутатора, первый и второй входы признаков готовности аргументов соединены, соответственно, с (2k-1)-м и 2k-м выходами признаков готовности аргументов коммутатора, первый и второй информационные входы соединены, соответственно, с (2k-1)-м и 2k-м информационными выходами коммутатора, идентификационный выход аргумента соединен с k-м идентификационным входом аргументов коммутатоpa, первый и второй выходы признаков аргументов соединены, соответственно, с (2k-1)-м и 2k-м входами признаков аргументов коммутатора, первый и второй адресные выходы соединены, соответственно, с (2k-1)-м и 2k-м адресными входами коммутатора. Идентификационный выход результата соединен с k-м идентификационным входом результата коммутатора. Выход признака готовности результата соединен с k-м входом признака готовности результата коммутатора. Информационный выход соединен с k-м информационным входом коммутатора. Выход признака разрешения выбора команд соединен с k-м входом признаков разрешения выбора команд всех функциональных блоков. Кроме того: идентификационные входы аргументов, входы признаков готовности аргументов и информационные входы функционального блока являются соответствующими входами устройства управления, идентификационный выход аргументов, выходы признаков аргументов и адресные выходы функционального блока являются соответствующими выходами устройства управления, третий адресный выход устройства управления соединен с адресным входом устройства памяти команд, командный вход-выход устройства управления соединен с командным входом-выходом устройства памяти команд, идентификационный и управляющий выходы устройства управления соединены, соответственно, с идентификационным и управляющим входами операционного устройства, первый и второй информационные выходы устройства управления соединены, соответственно, с первым и вторым информационными входами операционного устройства, идентификационный выход результата; выход признака результата и информационный выход операционного устройства являются соответствующими выходами функционального блока, выход логического номера, N входов признаков разрешения выбора команд и выход признака разрешения выбора команд функционального блока являются соответствующими выходами и входами устройства управления. Причем устройство управления состоит из блока выбора команд, блока дешифрации команд, блока формирования исполняемой команды, блока управления исполнением команд, блока разрешения выбора команд, регистра информационной связности, имеющего размерность N разрядов, памяти занятых меток, памяти готовности аргументов, буферной памяти кода операции, буферной памяти первого аргумента, буферной памяти второго аргумента, имеющих размер L слов, а адресный выход блока выбора команд является третьим адресным выходом устройства управления, командный выход блока выбора команд является командным выходом устройства управления. Первый идентификационный выход блока выбора команд соединен с адресным входом чтения памяти занятых меток, вход признака занятости метки блока выбора команд соединен с информационным выходом памяти занятых меток, второй идентификационный выход блока выбора команд соединен с идентификационным входом блока дешифрации команд и адресным входом записи памяти занятых меток, выход признака занятости метки блока выбора команд соединен с информационным входом памяти занятых меток, управляющий вход блока выбора команд соединен с управляющим выходом блока дешифрации команд, информационный вход блока выбора команд соединен с третьим информационным выходом блока управления исполнением команд, выход признака разрешения выбора команд блока выбора команд является соответствующим выходом устройства управления. Командный вход блока дешифрации команд является командным входом устройства управления, идентификационный выход аргументов, выходы признаков аргументов, адресные выходы блока дешифрации команд являются соответствующими выходами устройства управления, информационно-управляющий выход блока дешифрации команд соединен с информационно-управляющим входом блока формирования исполняемой команды, идентификационные входы аргументов, входы признаков готовности аргументов и информационные входы которого являются соответствующими входами устройства управления. Первый идентификационный выход блока формирования исполняемой команды соединен с адресным входом памяти готовности аргументов, второй, третий и четвертый идентификационные выходы блока формирования исполняемой команды соединены, соответственно, с адресными входами записи буферной памяти кода операции, буферной памяти первого аргумента и буферной памяти второго аргумента, первый информационный вход-выход блока формирования исполняемой команды соединен с информационным входом-выходом памяти готовности аргументов, второй, третий и четвертый информационные выходы блока формирования исполняемой команды соединены, соответственно, с информационными входами записи буферной памяти кода операции, буферной памяти первого аргумента и буферной памяти второго аргумента, выход признака готовности команды блока формирования исполняемой команды соединен с входом признака готовности команды блока управления исполнением команды, пятый идентификационный выход блока формирования исполняемой команды соединен с идентификационным входом блока управления исполнением команды, первый, второй и третий идентификационные выходы которого соединены, соответственно, с адресными входами чтения буферной памяти кода операции, буферной памяти первого аргумента и буферной памяти второго аргумента, первый, второй и третий информационные входы блока управления исполнением команд соединены, соответственно, с информационными выходами чтения буферной памяти кода операции, буферной памяти первого аргумента и буферной памяти второго аргумента, выход логического номера блока управления исполнением команд является выходом устройства управления, четвертый идентификационный выход блока управления исполнением команд соединен с адресным входом записи памяти занятых меток, выход признака занятости метки блока управления исполнением команд соединен с информационным входом памяти занятых меток, выход установки информационной связности блока управления исполнением команд соединен с входом регистра информационной связности, пятый идентификационный выход блока управления исполнением команд является идентификационным выходом устройства управления, управляющий выход, первый и второй информационные выходы блока управления исполнением команд являются соответствующими выходами устройства управления, выход регистра информационной связности соединен с входом информационной связности блока разрешения выбора команд, выход признака разрешения которого соединен с входом признака разрешения блока выбора команд. N входов признаков разрешения выбора команд блока разрешения выбора команд являются соответствующими входами устройства управления. Коммутатор состоит из N узлов коммутации, каждый из которых включает N устройств выбора, содержащих регистр логического номера, имеющий размерность]Iog₂N[разрядов, блок формирования признаков выбора, память признаков выбора, имеющей размер L слов, два буферных блока FIFO-памяти, причем во всех узлах коммутации для k-го устройства выбора (k=1,…,N), k-й информационный вход коммутатора соединен с первыми информационными входами буферных блоков FIFO-памяти, k-й идентификационный вход результата соединен со вторыми информационными входами буферных блоков FIFO-памяти и адресным входом чтения памяти признаков выбора, k-й вход признака готовности результата соединен с сигнальным входом чтения памяти признаков выбора, а во всех устройствах выбора k-го узла коммутации (k=1,…,N) (2k-1)-й адресный вход коммутатора соединен с адресными входами первого аргумента блоков формирования признаков выбора, 2k-й адресный вход коммутатора соединен с адресными входами второго аргумента блоков формирования признаков выбора, (2k-1)-й вход признаков аргументов соединен с входами признака первого аргумента блоков формирования признаков, 2k-й вход признаков аргументов соединен с входами признака второго аргумента блоков формирования признаков, k-й вход логического номера соединен с входами регистров логического номера, k-й идентификационный вход аргумента соединен с адресными входами записи памятей признаков выбора, а также во всех устройствах выбора выход регистра логического номера соединен с входом логического номера блока формирования признаков выбора выход признака наличия аргументов блока формирования признаков выбора соединен с сигнальным входом записи памяти признаков выбора, выходы признаков первого и второго аргументов соединены, соответственно, с первым и вторым информационными входами памяти признаков выбора, первый информационный выход памяти признаков выбора соединен с сигнальным входом записи первого буферного блока FIFO-памяти, второй информационный выход памяти признаков выбора соединен с сигнальным входом записи второго буферного блока FIFO-памяти, кроме того, все первые буферные блоки FIFO-памяти k-го узла коммутации связаны последовательно сигнальным входом чтения в кольцо, а первые информационные выходы первых буферных блоков FIFO-памяти объединены и являются (2k-1)-м информационным выходом коммутатора, вторые информационные выходы первых буферных блоков FIFO-памяти объединены и являются (2k-1)-м идентификационным выходом аргументов коммутатора, выходы признаков готовности первых буферных блоков FIFO-памяти объединены и являются (2k-1)-м выходом признаков готовности аргументов коммутатора, все вторые буферные блоки FIFO-памяти k-го узла коммутации также связаны последовательно сигнальным входом чтения в кольцо, причем первые информационные выходы вторых буферных блоков FIFO-памяти объединены и являются 2k-м информационным выходом коммутатора, вторые информационные выходы вторых буферных блоков FIFO-памяти объединены и являются 2k-м идентификационным выходом аргументов коммутатора, выходы признаков готовности вторых буферных блоков FIFO-памяти объединены и являются 2k-м выходом признаков готовности аргументов коммутатора.

Синергическая вычислительная система принята за прототип заявляемого изобретения.

Общими с заявляемым изобретением признаками прототипа являются:

- наличие памяти команд,

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

- активизация операционных устройств готовностью данных.

Изобретение-прототип имеет следующие недостатки:

- необоснованная сложность организации вычислительного процесса,

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

Эти недостатки обусловлены следующими причинами.

Последовательное, поэлементное формирование из команд формата controlflow-архитектуры (см. фиг. 2 описания изобретения-прототипа) командных слов dataflow-архитектуры, с буферизацией каждого элемента, последовали: введение в процесс управления идентификаторов аргументов, признаков разрешения выбора команд, признаков (готовности аргументов SA₁ и SA₂, признаков готовности команд, признаков готовности результатов SR и логических номеров функциональных блоков, а в состав устройств управления каждого функционального блока - памяти команд, блока разрешения выбора команд, блока формирования исполняемой команды, памяти занятых меток, памяти готовности аргументов, буферной памяти кода операции, буферной памяти первого аргумента и буферной памяти второго аргумента, имеющих емкость L слов.

Реализация врожденного параллелизма управления потоком данных выполнена: введением в состав устройств управления каждого функционального блока регистра информационной связности; использованием в качестве коммуникационного устройства коммутатора «каждый с каждым», имеющего N×N=N² устройств выбора и 2N×N=2N² буферных блоков FIFO-памяти с двумя информационными входами каждый и, наконец, пятистадийной организацией цикла выполнения команд. При этом на первой стадии осуществляется выбор controlflow-команды, дешифрация кода операции, формирование памяти признаков выбора, формирование заготовки командного слова dataflow-архитектуры, включающее запись соответствующих признаков в память готовности аргументов и буферную память кода операции. На второй стадии производится прием результатов выполнения предшествующих операций и запись их в соответствующие буферные блоки FIFO-памяти в качестве аргументов для выполняемых операций. На третьей стадии производится считывание аргументов из FIFO-памяти и запись их в буферную память первого и второго аргументов. На четвертой стадии производится выбор подготовленных команд dataflow-архитектуры из буферной памяти кода операции, буферной памяти первого и второго аргументов и выдача их на исполнение. На пятой стадии выполняется операция. В результате сложность конструкции обрабатывающей части вычислительной системы оказалась пропорциональной количеству функциональных блоков N, что естественно, а сложность конструкции коммуникационной части - пропорциональной 2N². При этом, синхронизация только запуска команд (первая стадия циклов их выполнения) и асинхронное выполнение остальных стадий (в зависимости от готовности результатов, аргументов и командных слов) на фоне зависимости единовременной потребности в вычислительных и коммуникационных ресурсах от структуры ярусно-параллельной формы информационного графа исполняемой программы (в описании прототипа такие графы приводятся) эффективность загрузки функциональных блоков собственно вычислительной работой оставляет желать лучшего (выше по тексту работы, направленные лишь на формирование командных слов dataflow-архитектуры выделены косым шрифтом).

Известна [15-18] также потоковая модель последовательной программы в виде композиции двух линейно упорядоченных, помеченных, ориентированных графов, один из которых отображает логическую, а другой - информационную структуру программы. При этом термин «композиция» подчеркивает взаимно однозначное соответствие между парами вершин, одна из которых принадлежит графу переходов, отображающему логическую структуру программы, а другая - информационному графу, отображающему информационную структуру программы. Вершины графа переходов помечаются номерами операторов входной программы или адресами размещения в памяти команд исполняемой программы. Дуги графа переходов отображают порядок перехода между операторами входной программы или командами исполняемой программы. Дуги, отображающие передачи управления помечаются логическими условиями перехода по ним. Вершины информационного графа помечаются операциями, задаваемыми операторами входной программы или командами исполняемой программы, а дуги - результатами выполнения операции и порядком их участия в очередных операциях в качестве операндов.

Известны методы и алгоритмы эквивалентных преобразований потоковой модели, в том числе и распараллеливания, с временной сложностью O(n²), где n - количество операторов или команд в программе. При этом эквивалентность обеспечивается соответствием логических структур исходной (последовательной) и исполняемой (параллельной) программы на уровне линейных участков, разветвлений и циклов, а также сохранением информационных связей «результат - операнд» в пределах перечисленных элементов логической структуры и между ними [18, 19].

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

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

Поставленные задачи решены благодаря тому, что в ВС, содержащей N функциональных модулей (ФМ), имеющих два информационных входа, два входа признаков готовности, информационный выход и выход признака готовности результата и состоящих из устройств управления и операционных устройств, реализующих двуместные и одноместные операции, количество N ФМ четно, а из состава ВС удалены: коммутатор «каждой с каждым», буферная память кода операции, буферная память первого аргумента, буферная память второго аргумента, память готовности аргументов, память занятых меток, блок формирования исполняемой команды, блок разрешения выбора команд и регистр информационной связности. Устройства памяти команд выведены из состава ФМ в состав ВС с образованием двух устройств с расширенным интерфейсом, доступных со стороны N/2 ФМ каждое. В состав ВС дополнительно введены: локальная шина, системный контроллер, служебная память, память данных с расширенным интерфейсом и адаптер. В состав ФМ введены: коммутатор первого операнда, коммутатор второго операнда, выходной коммутатор, регистры первого и второго операндов, регистр результата операции. В состав устройств управления ФМ введены регистр команд и блок управления потоком данных. Интерфейс ФМ расширен введением четырех информационно-управляющих входов, информационного входа-выхода, информационно-управляющего выхода, управляющего входа-выхода и командного входа-выхода. При этом вход регистра команд соединен с командным входом-выходом ФМ, выходы адресной части регистра команд соединены с блоком управления потоком данных, два выхода которого соединены с адресными входами коммутаторов первого и второго операндов, третий выход соединен с информационным входом-выходом ФМ, четвертый выход соединен с управляющим входом-выходом ФМ, а пятый вход-выход соединен с блоком управления выполнением команд. Выход операционной части регистра команд соединен с входом блока управления выполнением команд, имеющим связи со всеми блоками, устройствами, узлами и коммуникациями интерфейса ФМ. Регистры операндов и регистр результата выполненной операции соединены с операционным устройством способом, известным из уровня техники. Коммутаторы первого и второго операндов имеют: по четыре входа, соединенных с информационно-управляющими входами ФМ; по одному входу, соединенному с информационным входом-выходом ФМ; по адресному входу, соединенному с соответствующим выходом блока управления потоком данных; по информационному выходу, соединенному с входом одноименного регистра операнда, и по выходу готовности, соединенному с соответствующим входом блока управления выполнением команд. Выходной коммутатор имеет: информационный вход, соединенный с выходом регистра результата; вход готовности результата, соединенный с одноименным выходом блока управления выполнением команд; адресный вход, соединенный с соответствующим выходом блока управления выполнением команд и два выхода, один из которых соединен с информационно-управляющим выходом ФМ, а другой - с информационным входом-выходом ФМ. Информационно-управляющие выходы ФМ соединены с информационно-управляющими входами других ФМ с образованием многоуровневой, однонаправленной, замкнутой, вычислительной сети, содержащей два, взаимодействующих по данным и их готовности кольца, количество ФМ в которой определяется из соотношения N>2Т_пк/Т_фм, где: Т_пк - длительность цикла обращения в память команд, а Т_фм - длительность цикла выполнения команды ФМ. Выход каждого ФМ соединяется: с первым информационно-управляющим входом следующего ФМ в своей цепи, с вторым информационно-управляющим входом ФМ, следующего через один ФМ в своей цепи, с третьим информационно-управляющим входом следующего ФМ в соседней цепи и с четвертым информационно-управляющим входом ФМ, следующего через один ФМ в соседней цепи. Все управляющие входы-выходы ФМ первого кольца соединены с одним входом-выходом системного контроллера, а все управляющие входы-выходы ФМ второго кольца - с другим входом-выходом системного контроллера. Все командные входы-выходы ФМ первого кольца соединены с входом-выходом первой памяти команд, а все командные входы-выходы ФМ второго кольца - с входом-выходом второй памяти команд; информационные входы-выходы ФМ первого кольца соединены с первым дополнительным портом памяти данных, а информационные входы-выходы ФМ второго кольца - со вторым дополнительным портом памяти данных. Локальная шина соединяет системный контроллер с первой и второй памятью команд, со служебной памятью, с памятью данных и адапте