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

МИНИСТЕРСТВО ПУТЕЙ СООБЩЕНИЯ РФ

^МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ С" ПУТЕЙ СООБЩЕНИЯ _(МИИТ)_>

V

На правах рукописи

Желенков Борис Владимирович

УДК 681.3.02

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ БРМО-ТЕХНОЛОГИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ВЫСОКОЙ СЛОЖНОСТИ

05.13.05 - Элементы и устройства вычислительной техники и систем

управления.

- АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва 1998

Работа выполнена в Московском государственном университете путей сообщения (МИИТ)

Научный руководитель: доктор технических наук, профессор А. Б. БАРСКИЙ

Официальные оппоненты:

доктор технических наук, профессор А. В. Шилемко кандидатчехнических наук, доцент В. В. Шилов

Ведущее предприятие: Проектно-конструкторское техническое бюро АСУЖТ

Защита состоится 1998г. в ^ часов на заседании

диссертационного совета К 114.05.10 при Московском государственном университете путей сообщения (МИИТ) по адресу: 101475, Москва, А-55, ул. Образцова, 15, ауд.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан

Л/. 09 1998 года.

Отзыв на автореферат, заверенный печатью, просим направлять по адресу университета.

Ученый секретарь

диссертационного совета

доктор технических наук, профессор

Ю. А. Хохлов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Все существующие проекты содержат, ставшие традиционными, недостатки основными из которых являются:

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

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

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

В последнее десятилетие появился ряд работ, в которых теоретически обосновываются требования к архитектуре мультипроцессорных ВС на основе анализа массовых, типовых задач и эффективного способа их распараллеливания. Сделан вывод о том, что ВС, максимально приспособленная к обработке больших массивов данных обязательно должна "уметь" обрабатывать разные элементы массива по одной и той же программе, запущенной на разных процессорах. Такая технология обработки получила название SPMD-(Single Programm, Multiple Data) - технологии ( монопрограммная ВС).

Этими факторами обусловлена актуальность вопросов, рассматриваемых в настоящей работе.

Целью диссертационной работы является оценка реализуемости структурных и архитектурных принципов дешевой мультипроцессорной ВС SPMD-технологии с использованием концепций:

- архитектурной поддержки требований вычислительного процесса;

- общей/разделяемой памяти (Shared memory);

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

- использования существующей элементной базы.

Исходя из поставленной цели в работе решаются следующие задачи:

1. Обоснование применения БРМО-тсхнологии.

2. Обоснование возможности построения мультипроцессорной ВС технологии и вьфаботка структурной организации.

3. Обоснование системы коммутации и арбитража.

4. Обоснование системы синхронизации параллельных вычислительных процессов.

5. Анализ реализуемости способов распараллеливания и обоснование средств их поддержки.

6. Программа использования предложенной разработки.

На защиту выносятся: структура и взаимодействие устройств мультипроцессорной ВС для персонального компьютера; система коммутации; система синхронизации; средства поддержки распараллеливания с ВС.

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

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

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

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

Реализация результатов работы.

1. Результаты диссертационной работы впервые реализованы в 45 ЦНИИ МО РФ в НИР "Пролог-5" в виде предложений по выбору и оценке структурных и схемотехнических решений при построении перспективных мультимикропроцессорных вычислительных систем на основе 5РМО-технологии.

2. На базе проведенных исследований создается макет ВС БРМО-технологии.

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

Апробация работы. Основные результаты работы были доложены на II международной научно-технической конференции "Актуальные проблемы развития железнодорожного транспорта" (Москва, МИИТ 1996г), Военно-научной конференции " Совершенствование методологии вычислительных и программных комплексов и систем" ( Москва, 45 ЦНИИ МО РФ, 1997г), научно-методической конференции, посвященной пятилетней работе международного института "Проблемы и пути совершенствования многоуровневой подготовки специалистов в современных экономических

условиях" (Москва, МИИТ, 1997г), научной конференции "XXIV Гагаринские чтения. Всероссийская молодежная научная конференция" (Москва, 1998г)

Публикации. Непосредственно по теме диссертации опубликовано б печатных

работ.

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

Объем диссертации: 122 стр. текста, 22 стр. рисунков и таблиц, список литературы на 8 стр., приложения, включающие конкретные схемотехнические решения и материалы по внедрению результатов диссертации, на 16 стр.

СОДЕРЖАНИИ РАБОТЫ

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

Глава 1 имеет обзорный характер и, кроме того, в ней конкретизируются задачи исследования.

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

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

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

Распараллеливание может вьшолняться либо по информации, либо по управлению.

При распараллеливании по управлению, на ПЭ выполняются различные фраг-менты(команды) программы над различными данными. Такая система классифициру-

ется, как ВС типа МКМД (множественный поток команд, множественный поток данных или MIMD - Multiple Instraction, Multiple Data).

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

к,-

Расчет производительности производится по формуле:

ПвсгШзПо.

где По - производительность процессора при решении тестовой задачи.

Следовательно общее требование параллельной обработки -

К,-» шах

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

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

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

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

Такая технология обработки получила название SPMD-(Single Programm. Multiple Data) - технологии (монопрограммная ВС). IIa рис. 1 представлена оркшмза-ция распараллеливания по SPMD-техпологии по опорному массиву на N процессорных элементах (ПЭ).

При анализе такого способа распараллеливания К,-»max при п—>оо, где п -размер обрабатываемого массива

Рис 1. Организация распараллеливания по ЯК\Ш- технологии по опорному массиву на N ПЭ.

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

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

Рассматриваемая ниже ВС реализует принцип - "Одна программа - много потоков данных" (SPMD). Архитектурно поддерживаются требования вычислительного процесса.

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

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

Это необходимо, например, для выбора процессором "своего" элемента массива, переадресации с учётом числа процессоров, анализа выхода за границы массивов и т.д.

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

На рис. 2 представлена структурная схема ВС SPMD-технологии.

В состав ВС входят: N устройств обработки информации (ПЭ), действующих по принципу параллельного исполнения одной программы с многими данными, М модулей общей/разделяемой памяти команд и данных (ОГ1) (Shared memory), доступной для всех процессоров, коммутатор для осуществления связи ПЭ-+ОП, блок "СИНХ" для синхронизации асинхронной работы ПЭ, блок "АОН" для автоматиче-

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

Рис 2. Структура средства расширения ПК на базе 5Р.\ГО-те.\нологии.

Для обеспечения широкого фронта работ к моменту представления настоящей работы осуществляется практическая реализация макета ВС БРМО-технологии минимальной конфигурации.

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

г--¿Е/.■-*»«». (о

где: Т<;о[. - время решения тестовой задачи;

N - количество процессоров;

V - число команд в тестовой задаче;

(¡- время выполнения ¡-ой команды.

В общем виде, переобозначив значение Тш| с учетом тех факторов, от которых оно зависит, а также спустившись при разбиении программы на уровень отдельных команд, входящих в состав программы, и введя в рассмотрение частоту р, появления этих команд (т.е. в соответствии с пршшитюм применения смесей Гибсона), для некоторой представительной тестовой задачи можно записать:

Ти1(Х,У^,М) = + Г_(К.Л?.А/), (2)

где: Тсотр - время выполнения вычислительных операций;

Тсолич- время выполнения операций, связанных с обращением в ОП;

X - количество вычислительных операций;

У - количество операций, связанных с обращением в ОП;

М - количество модулей ОП; N - количество ПЭ.

На основании вышесказанного определим слагаемые в выражении 2. К

(3)

где: K/N - количество циклов выполнения программы; К - размер обрабатываемого массива;

ticomp - время выполнения i-й операции, измеряемое в машинных тактах (МТ).

f 17

к

L

1 +

1-

1—

M(X+Y)J J

\

N-1

J 3N 4

✓

-(4)

/V В1У

где: (сгш,т (МТ) - время, необходимое на арбитраж и на переключение ячеек коммутатора;

(МТ) - время выполнения операции записи; 12 (МТ) - время выполнения операции считывания;

1-(1-¥/(М(Х+У))Гч"1 - вероятность того, что к одному модулю ОП обратятся другие ПЭ;

V

(N-1)/(3N) - вероятность того, что адрес закрыт другим ПЭ. Вероятность того, что адрес будет закрыт, равна вероятности появления операции на запись в ОП. При обращении в ОП, ПЭ выполняет либо операцию считывания, либо операцию записи. Среднее соотношение количества обращений на считывание к обращениям на запись составляет 3/1(дашюе значение определено на основе экспериментального программирования).

(ti+3ti)/4 - вероятность выполнения операции на запись или считывание; BW-производительпость коммутатора (среднее число одновременно проводимых обменов ПЭ—>ОП).

В результате анализа выражений 3 и 4, можно сделать вывод, что на время выполнения программы, а следовательно, и на производительность ВС влияет Т1Ш11П,. Из выражения 4 следует, что Tcomm(Y, N, М) -> min при BW -> шах.

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

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

Существует четыре основных вида топологий коммутаторов мультипроцессорных систем.

Разделяемая шина (Shared bus) является менее сложной и наиболее популярной среди производителей (Multimax, Allianl). Разделяемая шина не позволяет производить более одной передачи "процессор-память" одновременно. При большом числе ПЭ значительно возрастает время ожидания шины.

Матричный К (Cross-bar) поддерживает все возможные связи между ПЭ и модулями ОП одновременно.

Многоуровневые сети (MINs) и многошинные (Multi-bus) по своей производительности и стоимости находятся между разделяемой шиной и матричным коммутатором. При этом коммутатор-разделяемая шина можно рассматривать как разновидность многошинного коммутатора.

н

За основной показатель производительности принимается ширина выборки па-мяти(BW-bandwidth). Он определяет число успешно выполненных операций (чте-1ше/запись) с памятью в одном цикле передачи. При этом анализируются конфликты при обращении к модулям ОП (когда два и более ПЭ пытаются обратиться к одному и тому же модулю ОП). Это обусловлено случайной природой возникновения запросов к памяти.

Для определения В\У был проведен поиск вероятностных аналитических моделей коммутаторов.

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

Стрекср предложил следующий вариант определения В\У для матричного коммутатора (МК): если ПЭ генерирует запрос с вероятностью Р, одинаковой ко веем модулям памяти, ширина выборки будет определяться следующим образом:

где: Р/М-вероятность того, что ПЭ обратится к конкретному модулю памяти;

(p/M)N -вероятность того, что все ПЭ обратятся к модулям памяти одновре-

Умножение на М дает размер ожидаемого числа различных модулей памяти, к которым осуществлен запрос.

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

менно;

(1-Р/М)*-всроятность того, что не будет ни одного обращения; 1-(1-Р/М)",)-вероятность того, что по крайней мере один запрос осуществится.

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

Ожидаемое число запросов, которое передается на Ь входов получается при N=3 = М=Ь =1. Деление этого числа на Ь дает вероятность запроса к любой из Ь линий. Так как выходы одного уровня являются входами другого, можно рекурсивно оценивать вероятность выхода любого уровня, начиная с первого. Если РО) - вероятность того, что существует запрос к выходам переключателя на ¡-ом уровне, тогда

( р ,У

П=1- для 1<Ч<=П. (6)

\ Ъ )

Вероятность выхода последнего уровня определяет ширину выборки дельта-

сети:

Ш = Р.Ь'- (7)

Этот аналитический прием использован в работе для оценки МУК с ячейками размерностью 2x2.

Для оценки многошинного коммутатора использован подход предложенный Бийаном.

Ширина выборки для системы размеренностью ГЧхМхВ (Ы - количество ПЭ, М - количество модулей памяти, В - количество шин) составит:

где: ^ = тт(_у,М);

Р- вероятность запроса; ( /V )- биномиальный коэффициент;

5(у,х) - число Стерлинга второго вида.

(9)

Моделирование проводилось для систем размерностью 4x4. Это обусловлено отказом от использования большого числа процессоров в системе, что компенсируется их производительностью.

При анализе многошинного коммутатора было рассмотрено три варианта связей: с одной шиной (МШК1), с двумя шинами (МШК2), с тремя шинами (МШКЗ).

Для получения сравнительного анализа по быстродействию трех основных систем коммутации (матричный коммутатор, многоуровневый коммутатор, многошинный коммутаюр) были разработаны имитационные модели в системе ОРБЯ. При этом мультипроцессорную ВС можно представить в виде замкнутой сети массового обслуживания (СМО).

В результате проведенных исследований было выполнено сравнение характеристик коммутаторов по четырем основным параметрам: производительность (сводится к ширине выборки- В\У), быстродействие ( сводится к оценке отношения времени ожидания выполнения заявок к памяти от вероятности их появления ), надежность. стоимость. Результаты приведены в таблице 1.

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

Таблица 1 Параметры оценки различных топологий коммутаторов.

№ Параметр оценки Топологии коммутаторов

МК МШК1 МИЖ2 МШКЗ МУК

1. Производительность (В\У) 1,69 1,43 1,59 1,67 1,57

2. Быстродействие (1) 13,04 63,50 24,88 15,37 18,37

3. Надежность (р- вероятность отказа; 1-р - вероятность безотказной работы) (1-Р)' (1-Р)4 (1-Р)4 (1-Р)4 (1-Р)4

4. Стоимость (стоимость арбитра = стоимости ячейки коммутатора =х) 24х 18х 26х 34х 24х

Таким образом, подставив в выражение 4 BVV для матричного коммутатора, получим оценку производительности разрабатываемой ВС. В качестве тестовой задачи предлагается использовать задачу умножения матриц. В результате была получена зависимость времени выполнения данной задачи от количества процессоров и модулей памяти (рис. 3). Из анализа этой зависимости видно, что насыщение системы происходит при количестве ПЭ>4, что подтверждает концепцию использования в системе до десяти ПЭ.

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

1хМ

2 3 4 5 6 7 8

ПЭ

Рис. 3. Зависимость времени выполнения тестовой задачи от количества Г7Э и модулей ОП в системе

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

IS

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

Б процессе работы, ПЭ для обращения к "своим" данным используют свой номер. Задание этого номера происходит в начальный момент времени и зависит от количества включенных ПЭ и их приоритетов. Для этого разработан блок автоматического определения номеров ПЭ (АОН). В основе работы этого блока, как и в основе работы арбитра, предлагается использовать принцип ситуационного управления. Разработана функциональная и принципиальная схема АОНа для реализации на существующей элементной базе.

Общая/разделяемая память разбита на М независимых модулей при общем адресном пространстве. Предложено организовать общую/разделяемую память как расширение оперативной памяти. Таким образом, адресное пространство оперативной памяти состоит из двух частей: область памяти, определяемая младшей частью адреса, доступная только тому ПЭ, в состав которого она входит; область памяти, определяемая старшей частью адреса доступная всем ПЭ в составе ВС.

Кроме этого, при использовании стандартных плат процессоров возникает проблема обеспечения когерентности КЭШ-памятей, находящихся на исходных платах. Для обеспечения корректного выполнения программ при выполнении записи в ОП одним из ПЭ, предлагается генерировать сигнал сброса КЭШ-памятей всех ПЭ одновременно, а при попытке считывания ПЭ из ОП по закрытому адресу (см. ниже) будет генерироваться сигнал сброса КЭШ-памяти только для данного ПЭ (назовем его -CACHE Reset Write, Read Closed - CACHE RWRC) или только для ПЭ, который пытается считать из ОП по закрытому адресу.

Каждый модуль ОП снабжен дополнительным блоком - память закрытых адресов (ПЗА). ПЗА также представляет собой ОЗУ, как и модуль памяти, который она сопровождает.

В 3-й главе решается задача выбора способа синхронизации по данным и решается проблема ограничения асинхронной работы процессоров.

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

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

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

Каждый модуль ОП предложено снабдить дополнительным блоком памяти, который хранит информацию о закрытых адресах данного модуля и номерах ПЭ, которые закрыли эти адреса. Такие блоки называются памятью закрытых адресов (ПЗА).

Занесение в ПЗА номера ПЭ, закрывшего адрес, достаточно для правильного (корректного) выполнения задачи. Используются специальные команды ЗАКР(А) и ОТКР(А).

Разработанная схема синхронизации соответствует синхронизации способом семафоров. Семафором здесь является содержимое ПЗА по адресу "А", а адрес - это номер семафора. Семафоры работают по протоколу продолжительного переобращения.

В диссертации приводятся алгоритмы, реализуемые в критических секциях при решении задач синхронизации:

- задача взаимного исключения;

- задача "поставщики-потребители";

- задача "читатели-писатели".

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

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

Для реализации ограничения асинхронности вводится команда "СИНХ". Механизм ее выполнения основывается на специальных аппаратных средствах (блок "СИНХ"), тесно связанных с программным обеспечением. Разработана функциональная и принципиальная схема блока "СИНХ".

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

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

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

Динамическое распараллеливание обеспечивается дескрипторами массивов, которые формируются автоматически при распараллеливании на уровне программ.

Приведенный ранее в ряде работ дескриптор массива, обеспечивает динамическое распределение данных между ПЭ. Он включает в себя восемь элементов.

Для облегчения обработки п-мерных массивов(п£1) предложено дополнительно ввести дескриптор размерностей массива.

Дескриптор должен содержать следующие элементы:

ПО - адрес первого параметра размерности массива;

Ш - количество параметров.

В результате получается следующий дескриптор:

БО- содержит адрес первого элемента массива.

01- содержит шаг переадресации И. Шаг переадресации зависит от того над какими элементами массива будет выполнено действие. Если это элементы разных мае-

сивов, то Ь=1. Если это элементы одного массива, то Ь может принимать значение 2 и более.

02- количество элементов (к-1).

03- адрес последнего элемента массива.

1)4- содержит значение N1), используемое для переадресации к "своему" следующему элементу массива с учетом числа ПЭ.

05- адрес аО+П^]Ч11=00-Н1^04 (¡-номер ПЭ, на котором обрабатывается данный дескриптор), используемый для автоматической переадресации при последовательном обращении к дескриптору с учетом начального обращения к "своему" элементу массива и с учетом последующего изменения адреса элемента на величину ЫЬ, хранимую в 04. При этом в начальный момент времени 05 содержит значение аО+Ш. При последующих обращениях к дескриптору 05 будет увеличиваться на величину, находящуюся в Э4.

06 - адрес первого параметра размерности массива;

07 - количество параметров.

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

Разрабомн обобщенный алгоритм формирования дескрипторов. Формирование дескрипторов массивов осуществляется на стадии компиляции в ПМ при анализе текущей команды программы.

ВЫВОДЫ, ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

В диссертации получены следующие основные теоретические и практические результаты:

1. На основе ВС типа MIMD, как наиболее приспособленной к параллельной обработке данных, организуется мультипроцессорная система, поддерживающая работу ПЭ как по одинаковым, так и по разным программам. Такая структура получила название SPMD (Single Programm- Multiple Data или Одна программа - Множественный поток данных). Использование в ее конструкции существующей элементной базы и типовых узлов обеспечивает низкую стоимость. Физически, такую систему наиболее целесообразно реализовать в виде мини супер-ЭВМ, как средство расширения возможностей ПК.

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

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

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

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах.

1. Желенков Б. В. Локально-асинхронная вычислительная система типа SPMD.-Тезисы докладов II международной научно-технической конференции "Актуальные проблемы развития железнодорожного транспорта", М.: МИИТ, 1996г., с. 62.

2. Барский А. Б., Желенков Б. В. 4 Учебно-экспернментальный супермакет ВС,-Военно-научная конференция, 4 Секция: " Совершенствование методологии вычислительных и 1грограммных комплексов и систем" - М.: 45 ЦНИИ МО РФ, 1997г., с38-39.

3. Барский А. Б., Желенков Б. В. Направление развития высокопроизводительных вычислительных систем - Заключительньт отчет по теме "Пролог-5", книга 1,

. раздел 1.3. М.: 45 ЦНИИ МО РФ, 1997г., с 55-67.

4. Желенков Б. В. Мультимикропроцессорная ВС для изучения процессов параллельной обработки данных,- Тезисы научно-методической конференции, посвященной пятилетней работе международного института "Проблемы и пути совершенствования многоуровневой подготовки специалистов в современных экономических условиях", М.: МИИТ, 1997г., с. 16.

5. Желенков Б. В Мультипроцессорная вычислительная система для решения задач управления - Тезисы научной конференции "XXIV Гагаринские чтения. Всероссийская молодежная научная конференция", М.: ЛАТМЭС, 1998г., с.41-42 .

6. Желенков Б. В. Новая технология построения вычислительных систем для решения сложных задач на железнодорожном транспорте,- "Транспорт, наука, техника, управление", 1998г., №4, с. 21-23.