Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS
А.М.Федотов

Словарь-справочник по информатике (онтология информатики)

Вычислительные системы с программируемой структурой

Вычислительные системы с программируемой структурой полностью основываются на модели коллектива вычислителей и являются композицией взаимосвязанных элементарных машин (ЭМ). Каждая ЭМ в своем составе обязательно имеет локальный коммутатор (ЛК), процессор и память; может иметь также внешние устройства. Локальная память ЭМ предназначается для хранения и части данных, и, главное, ветви параллельной программы. Архитектура ВС с программируемой структурой относится к типу MIMD.
Такие ВС прежде всего ориентированы на распределенную обработку информации; они эффективны и при конвейерной, и при матричной обработке. При распределенном способе обработки данных на ВС полностью используются возможности MIMD-архитектуры. При конвейерном и матричном способах обработки данных архитектура MIMD виртуально трансформируется соответственно в архитектуру MISD и SIMD. Системы с программируемой структурой рассчитываются на работу во всех основных режимах: решения сложной задачи, обработки наборов задач, обслуживания потоков задач, реализации функций вычислительной сети.
Концепция ВС с программируемой структурой была сформулирована в Сибирском отделении АН СССР, первая система («Минск-222») была построена в 1965-1966 гг.
Примеры систем: «Минск-222», МИНИМАКС, СУММА, МИКРОС, МВС.


Этапы исследований

Работы в области высокопроизводительных средств обработки информации выполнялись в Институте математики (ИМ) СО АН СССР в 1960-х годах под руководством специалиста по вычислительной технике Э.В. Евреинова (1928, профессор с 1972 г.). Первая работа сотрудников ИМ СО АН СССР [2] о возможности построения ВС высокой производительности опередила американские публикации в данной области примерно на 6 месяцев. В середине 1960-х годов вышла в свет монография [3], обобщающая первые результаты работ ИМ СО АН СССР по функциональным структурам ВС и параллельному программированию. Во второй половине 1960-х годов были созданы и первые ВС [4]: «Минск-222» (1965-1966) и управляющая ВС для автоматизации научных исследований (1964-1967). К началу 1970-х годов завершилось формирование концепции ВС с программируемой структурой, как средств обработки информации, основанных на модели коллектива вычислителей. Первоначальное название рассматриваемых средств - «Однородные вычислительные системы» [2]; в конце 1970-х годов закрепляется название «ВС с программируемой структурой» (см. [4], стр. 26), так как оно точнее отражает архитектурные возможности систем - коллективов вычислителей. «Однородные ВС» и «ВС с программируемой структурой» следует рассматривать как синонимические термины.
Начиная с 70-х годов XX в. теоретические и проектные работы в Сибирском отделении АН СССР (ныне СО РАН) по ВС с программируемой структурой велись под руководством одного из разработчиков первой ВС с программируемой структурой «Минск-222» В.Г. Хорошевского (1940; д-р техн. наук с 1974 г., чл.-кор. РАН с 2000 г.).

Работы по ВС из академической сферы распространяются в промышленность, под руководством Хорошевского создается ряд систем: МИНИМАКС (1975), СУММА (1976), МИКРОС-1 (1986), МИКРОС-2 (1992), МИКРОС-Т (1996). Выходит в свет большое число публикаций как сотрудников СО АН СССР (СО РАН), так и других организаций [1, 2, 3, 4, 5, 6].
В 90-х годах XX в. активизируются работы по построению отечественных промышленных ВС с массовым параллелизмом. Работы по созданию систем семейства МВС (генераций МВС-100 и МВС-1000) выполнены в кооперации научно-исследовательских институтов РАН и промышленности.
Вычислительные масштабируемые системы генерации МВС-100 эксплуатируются с 1992 г. Количество процессоров в различных конфигурациях составляет от 4 до 128; производительность конфигураций ВС - от 400 MFLOPS до 10 GFLOPS. Системы генерации МВС-1000 поставляются с 1998 г.; их большемасштабные конфигурации ВС позволяют достичь производительности 10...103 GFLOPS.
Вычислительные системы с программируемой структурой - это распределенные средства обработки информации. В таких ВС нет единого функционально и конструктивно реализованного устройства: все компоненты (устройство управления, процессор и память) являются распределенными. Тип архитектуры ВС - MIMD; в системах заложена возможность программной перенастройки архитектуры MIMD в архитектуры MISD или SIMD.
Основной функционально-структурной единицей вычислительных ресурсов в системах рассматриваемого класса является элементарная машина (ЭМ). Допускается конфигурирование ВС с произвольным числом ЭМ. Следовательно, ВС с программируемой структурой относятся к масштабируемым средствам обработки информации и допускают формирование конфигураций с массовым параллелизмом.
Вычислительные системы с программируемой структурой сочетают в себе достоинства универсальных и специализированных средств обработки информации, в них допускается автоматическое формирование виртуальных проблемно-ориентированных конфигураций. В таких ВС с достаточной полнотой воплощены перспективные архитектурные принципы, системы основаны на модели коллектива вычислителей, обладают большими потенциальными возможностями по обеспеченно высоких значений показателей эффективности функционирования.


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


Сосредоточенные и распределенные вычислительные системы

ВС с программируемой структурой являются распределенными средствами и в архитектурном, и в функциональном планах. В них любые ресурсы (процессоры, память и устройства управления, и системные устройства) представляются множествами соответствующих модулей. Тем не менее в классе систем с программируемой структурой выделяют (пространственно) сосредоточенные и распределенные ВС. Характерной особенностью сосредоточенных ВС является компактное пространственное размещение средств обработки и хранения информации, при котором нет необходимости использовать телекоммуникационные сети (существующие абонентские или специально разработанные сети передач данных). В сосредоточенных ВС нет линий связи, вносящих существенную задержку в работу ВС, нет жестких ограничений на топологию сети связи, на возможность параллельной передачи информации между функциональными модулями (процессорами, модулями памяти, ЭМ и др.). В таких ВС среднее время передачи слова между функциональными модулями соизмеримо со средним временем выполнения одной операции в процессоре.
К распределенным ВС относят макросистемы - системы сложной конфигурации, в которых в качестве функциональных элементов выступают пространственно-рассредоточенные вычислительные средства, основанные на моделях вычислителя и коллектива вычислителей, и сети связи, обеспечивающие взаимный теледоступ между средствами обработки информации.Распределенные ВС в общем случае предназначаются для реализации параллельных программ решения задач (произвольной сложности или с произвольным объемом вычислений, в монопрограммном и мультипрограммном режимах) на рассредоточенных в пространстве вычислительных ресурсах. Они должны быть приспособленными и для выполнения функций, присущих вычислительным сетям, и для реализации последовательных программ. В распределенных ВС допустимо централизованное и децентрализованное управление вычислительными процессами.
Любое функциональное взаимодействие между сосредоточенными ВС, составляющими распределенную систему, осуществляется через сеть связи. В сеть связи включаются каналы и системные устройства, распределенные по сосредоточенным ВС. В распределенных ВС нет принципиальных ограничений на физическую природу каналов; в них могут использоваться двухпроводные, коаксиальные и радиорелейные линии связи, средства коммуникации на основе волоконной оптики, микроволновой и спутниковой связи и др. На системное устройство возлагается выполнение функций, свойственных СУ для сосредоточенных ВС и устройствам связи для вычислительных сетей. В элементарные функции любого СУ входят: обмен информацией между сосредоточенной ВС и каналом, а также обеспечение транзитной передачи информации. В мощных распределенных ВС системное устройство может быть реализовано как параллельный сервер.
Предельным по простоте вариантом сосредоточенной ВС является ЭМ, следовательно, простейшим вариантом распределенной ВС является совокупность однотипных и регулярно соединенных ЭМ, использующая «длинные» программно-коммутируемые каналы межмашинной связи. В этом случае в состав ЭМ входят однотипные СУ.
Более развитым вариантом распределенных ВС являются системы, структура сети связи которых в целом является нерегулярной и которые компонуются из программно-совместимых ЭМ. В данном случае сеть связи организуется посредством программно-совместимых системных устройств. В топологическом плане такие ВС классифицируются как централизованные, децентрализованные, кольцевые и радиально-кольцевые системы. Топологическое изображение названных систем аналогично схемам, общепринятым для вычислительных сетей.
Распределенные системы, в которых выполняется условие программной совместимости ЭМ, относятся к гомогенным ВС. В теоретическом плане можно рассматривать и гетерогенные распределенные ВС, состоящие из программно-несовместимых ЭМ и сосредоточенных ВС и имеющие сеть связи с нерегулярной структурой. Однако реализация гетерогенных систем наталкивается на большие трудности, связанные прежде всего с организацией их эффективного функционирования.
В подкласс распределенных ВС входят вычислительные сети. Несмотря на внешнюю схожесть распределенных систем и сетей, существует принципиальное отличие в их функционировании. Вычислительные сети выполняют обработку потоков задач, как правило, представленных последовательными программами. В сетях параллельные программы также могут быть реализованы, если в их состав входят сосредоточенные ВС (например, в сети ARPA такой системой была ILLIAC-IV; в глобальной сети Internet функционирует большое разнообразие конвейерных, матричных, кластерных и мультипроцессорных ВС). Решение каждой задачи выполняется на отдельной ЭВМ или сосредоточенной ВС, совместное использование нескольких ЭВМ и (или) ВС для решения одной задачи не допускается. При обслуживании потоков задач в вычислительных сетях осуществляются распределение нагрузки на ресурсы, передача информации, распределение программ и данных, дистанционная обработка и т.п. В вычислительных сетях основным режимом является диалоговый, при котором взаимодействие происходит между двумя абонентами (пользователь - ЭВМ или ВС, пользователь - пользователь). Естественно, в сетях одновременно может происходить большое число диалогов. Работа вычислительной сети в этом отношении напоминает функционирование телефонной (проводной или сотовой) сети.
В распределенных ВС наряду с режимом работы, характерным для вычислительных сетей, реализуется также режим решения общей сложной задачи. Задача представляется параллельной программой, каждая макроветвь (или ветвь) которой реализуется на своей сосредоточенной ВС (или ЭМ). Для распределенных ВС при решении одной сложной задачи характерен режим группового обмена информацией между абонентами (машины - машины, машины - пользователь).
Таким образом, распределенные системы относятся к более общему классу средств обработки информации по сравнению с вычислительными сетями и качественно от них отличаются возможностью решения одной сложной задачи на распределенных вычислительных ресурсах.

Первой распределенной ВС с программируемой структурой была АСТРА [4].


Режимы функционирования вычислительной системы и способы обработки информации
Первый режим - монопрограммный, т.е. для решения задачи используются все ресурсы ВС. Задача представляется в виде параллельной программы, число ветвей в которой либо фиксировано, либо допускает варьирование в заданном диапазоне. В качестве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное количество ветвей в параллельной программе менее общего количества ЭМ в системе, то избыточные машины используются для повышения надежности функционирования ВС.
Второй и третий режимы функционирования ВС относятся к мультипрограммным. При работе ВС в этих режимах одновременно решается несколько задач, следовательно, ресурсы системы делятся между несколькими задачами.
При организации функционирования ВС в случае набора задач учитывается не только количество задач, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени решения и др. Алгоритмы организации функционирования ВС задают распределение задач по машинам и последовательность выполнения задач на каждой машине. В результате становится известным, в какой промежуток времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора. Этот режим, безусловно, является обобщением мультипрограммных режимов для ЭВМ, и он более сложный. В самом деле, при мультипрограммировании ресурсы ЭВМ (прежде всего процессор) делятся между несколькими последовательными программами. При обработке наборов параллельных задач ресурсы ВС (множество элементарных машин) также распределяются между задачами, однако в любой момент времени задачи решаются на непересекающихся подмножествах машин. Следовательно, мультипрограммные режимы работы ЭВМ реализуются путем разделения времени процессора, в то время как обработка наборов задач на ВС осуществляется посредством разделения «пространства» машин.
Третий режим - обслуживание потока задач на ВС - принципиально отличается от обработки задач набора: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключен. Для режима потока задач созданы методы и алгоритмы [4], обеспечивающие стохастически оптимальное функционирование ВС.
Различают распределенный, матричный и конвейерный способы обработки информации. Принципы, положенные в основу ВС с программируемой структурой, позволяют реализовать в них любой из этих способов обработки данных.
При распределенной обработке параллельные программы и данные рассредотачиваются по элементарным машинам ВС. Допустимо построение адаптирующихся параллельных программ, число ветвей в которых в процессе их реализации соответствует числу (работоспособных) ЭМ в системе. Способ распределенной обработки данных был теоретически и экспериментально исследован в широком диапазоне классов сложных задач.
Опыт применения методики крупноблочного распараллеливания при решении сложных задач на действующих ВС показал высокую эффективность параллельных программ для распределенной обработки информации.
В случае матричной обработки данных программа вычислений содержится в одной (управляющей) ЭМ, а данные однородно распределяются по всем машинам ВС (или подсистемы). Процесс решения задачи состоит из чередующихся процедур: рассылки команд из управляющей ЭМ остальным машинам и исполнения этих команд всеми машинами, но каждой над своими операндами.
Матричный способ в сравнении с распределенным дает экономию в использовании (распределенной по ЭМ) памяти ВС. Однако данному способу присущ недостаток, заключающийся в неоднородном использовании машин и, в частности, в неоднородной нагрузке на их память. Этого недостатка лишен обобщенный матричный способ обработки информации. При этом способе программа не целиком помещается в одной ЭМ, а предварительно сегментируется (не распараллеливается!) и затем посегментно размещается в памяти машин. Последовательность сегментов, составляющих программу, может быть размещена в памяти машин, например так, что номер распределенного в машину сегмента будет равен ее номеру. И для распределенного, и для матричного способов обработки информации характерно то, что в процессе решения задачи имеют место обмены данными между ЭМ системы.
При конвейерном способе обработки данных структура ВС предварительно настраивается так, что машины образуют конвейер (или «линейку», или «кольцо»). Затем осуществляются сегментирование программы и размещение в машинах ВС последовательности полученных сегментов в соответствии со структурой конвейера. Размещение данных может быть сосредоточенным (например, на внешней памяти одной ЭМ) или распределенным (по памятям всех машин конвейера). В процессе решения задачи данные проходят через последовательность машин, составляющих конвейер.
Таким образом, при распределенном способе обработки информации полностью используются возможности ВС с архитектурой MIMD. Матричный и конвейерный способы обработки информации обеспечивают частичное использование возможностей архитектуры ВС. Архитектура MIMD при первом способе трансформируется в архитектуру SIMD, а при втором - в архитектуру MISD.


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

1. Вычислительные системы с программируемой структурой - гибкий класс средств обработки информации с архитектурой MIMD. Архитектура таких систем не имеет принципиальных ограничений на пути ко все более полному воплощению в реализациях принципов модели коллектива вычислителей как на макроуровне (на уровне системы в целом), так и на микроуровне (на уровне одной ЭМ). Концепция ВС с программируемой структурой свидетельствует о революционном отходе от классической архитектуры ЭВМ фон Неймана.
2. Накоплен опыт создания ВС с программируемой структурой («Минск-222», МИНИМАКС, СУММА, МИКРОС-1, МИКРОС-2, МИКРОС-Т, МВС-100, МВС-1000 и др.). Реализованы мультитранспьютерные живучие ВС с программируемой структурой МИКРОС-Т и МВС-100 и высокопроизводительные системы МВС-1000; распределенные децентрализованные ОС, инвариантные к структуре сети межмашинных связей и количеству ЭМ; языки параллельного программирования; комплексы отказоустойчивых прикладных параллельных программ.
Результаты многолетней эксплуатации созданных систем показывают высокую эффективность архитектурных решений, присущих концепции ВС с программируемой структурой. Эта концепция позволяет в условиях современных ограничений в производстве средств микропроцессорной техники (в технологии БИС) строить промышленные ВС, множество конфигураций которых составляют семейства (ряды) совместимых экономичных моделей для широкого диапазона по производительности, надежности и живучести. Примером служит ВС МИКРОС, подход в реализации которой допускает формирование требуемых сосредоточенных и распределенных моделей из серийных средств микропроцессорной техники и обеспечивает на многие годы возможность эволюционного совершенствования системы в соответствии с развитием технологии БИС.
3. Вычислительные системы с программируемой структурой - это коллектив ЭМ, количество которых и структура сети связей между которыми допускают варьирования в широких пределах. Рост производительности таких ВС обеспечивается увеличением количества ЭМ и расширением конфигураций каждой из них.

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

    Литература
  1. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.
  2. Евреинов Э.В., Косарев Ю.Г. О возможности построения вычислительных систем высокой производительности. Новосибирск: Изд-во СО АН СССР, 1962.
  3. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966.
  4. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. Новосибирск: Наука, 1978.
  5. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985.
  6. Хорошевский ВТ. Инженерный анализ функционирования вычислительных машин и систем. М.: Радио и связь, 1987.

Ключевые термины, связанные с термином "Вычислительные системы с программируемой структурой":

  1. «Минск-222»
  2. АСТРА
  3. МВС
  4. МИКРОС
  5. МИНИМАКС
  6. Модель коллектива вычислителей
  7. СУММА

Литература

Дополнительная:

  1. Хорошевский В.Г. Архитектура вычислительных систем: Учеб. пособие. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. - 520 с.
  2. Э.В. Евреинов, Ю.Г. Косарев Однородные универсальные вычислительные системы высокой производительности. // Новосибирск: Наука, 1966.

Ссылки на персон:

  1. Хорошевский Виктор Гаврилович

Ключевые термины (головные):  Модель коллектива вычислителей;   MIMD-архитектура;   «Минск-222»;   МИНИМАКС;   СУММА;   МИКРОС;   МВС;   АСТРА;

Контекстный поиск: Задайте образец для поиска:
|Головная| |Преподавание| | Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотов Анатолий Михайлович 		[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 1998-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.
    Дата последней модификации: 09.12.2013