автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы и алгоритмы синхронизации процессоров в многопроцессорных системах топологии "общая шина"

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

ГГК од

УДКб81-3 1 7 и 2300

Вальчевскап Гаянэ Юрьевна

МЕТОДЫ И АЛГОРИТМЫ СИНХРОНИЗАЦИИ ПРОЦЕССОРОВ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ ТОПОЛОГИИ «ОБЩАЯ ШИНА»

Специальность 05.13 Л 3 - Вычислителыгые машины, комплексы, системы и сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

Минск 2000

Работа выполнена в ордена Трудового Красного Знамени Институте технической кибернетики Национальной академии наук Беларуси

Научный руководитель:

д.т.н. М.М. Маханек

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

д.т.н., проф. А.А. Петровский к.т.н., доц. Г.И. Шпаковский

Оппонирующая организация:

Научно-исследовательский институт электронных вычислительных машин

Защита состоится 4 мая 2000 г. в 14°° часов на заседании совета по защите диссертаций Д 02.15.01 в Белорусском государственном университете информатики и радиоэлектроники по адресу: 220027, г. Минск, ул. П. Бровки, б, БГУИР, корп. 1, ауд. 232, тел. 2398989.

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

Автореферат разослан п3__"¿Ъ^/^у/^р 2000г.

Ученый секретарь совета по защите диссертаций,

д.т.н.

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

Актуальность темы диссертации

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

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

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

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

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

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

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

1. Разработать нейрокомпьютер (рабочую станцию) для решения прикладных задач параллельной обработки информации сложной структуры. Период выполнения - 1992-1994 гг. Раздел 01.03.03 республиканской научно-технической программы "Информатика".

2. Разработка многопроцессорных архитектур для обработки и распознавания изображений. Период выполнения - 1994-1995 гг. Раздел 1.13.12 программы фундаментальных исследований "Проблемы искусственного интеллекта".

3. Разработка методов и средств скоростной параллельной обработки информации с использованием нейроархитектур в системах и образцах вооружений и военной техники для принятия решений в режиме, критическом по времени, обработки и распознавания видео изображений, радиоакустических сигнаяоз. НИР Шифр "Район АН" № 02.03.05 НТК МО Республики Беларусь. Период выполнения - 1992-1994 гг.

4. Исследование и разработка алгоритмов обнаружения и классификации полутоновых объектов на сложном фоне. НИР Шифр "Ракита - 2" № 02.01.02 НТК МО Республики Беларусь. Период выполнения - 1993-1994 гг.

5. Параллельные логические процессоры для многопроцессорных систем. Период выполнения - 1991-1993 гг. и 1994-1996 гг., № Ма 1150/8-1 и 438 113/117/0, Немецкое Исследовательское Общество (DFG).

6. Параллельные логические процессоры для реализации логических операций в шюгопроцессорных системах. Период выполнения - 1993-1995 гг., № 436 WER 113-1-0, Немецкое Исследовательское Общество (DFG).

7. Европейская научно-технологическая сеть передачи информации. Период выполнения - 1995-1996 гг., № INTAS-E96-08, Брюссель, ЕС.

8. Демонстрация скоростной параллельной архитектуры для обработки изображений. Период выполнения - 1994-1995 гг., № INTAS-93-1050, Брюссель, ЕС.

9. Разработка научно-исследовательской компьютерной сети HAH Беларуси. Период выполнения - 1994-1995 гг., № 450/BYE/09/9508004, ЮНЕСКО, Париж.

10.Разработать сетевую инфраструктуру учреждений Академии наук РБ с обеспечением доступа к глобальным компьютерным сетям. Период выполнения -1996-1998, из состава отдельных проектов НИОКР ГКНТ РБ.

11. Создать региональный узел республиканской научно-исследовательской компьютерной сети и подключить его к Интернет. Период выполнения - 1996-1998, из состава отдельных проектов НИОКР ГКНТ РБ.

12. Разработка технорабочего проекта, монтаж и ввод в эксплуатацию автоматизированной системы стендовых испытаний корпуса ускоренных испытаний ПО "Минский тракторный завод". Период выполнения - 1998-2001.

Цель и задачи исследования

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

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

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

2. Разработать методику расчета минимальной верхней границы времени синхронизации в многопроцессорной системе тополопш "общая шина".

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

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

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

Объект и предмет исследования

Объектом исследования являются программно-аппаратные средства синхронизации в многопроцессорных системах топологии "общая шина".

Гипотеза

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

Методология и методы проведенного исследования

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

Научная новизна и значимость полученных результатов

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

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

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

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

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

5. Разработан алгоритм расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение.

Практическая значимость полученных результатов Результаты научных исследований автора внедрены:

1) в центральном управляющем комплексе научно-информационной компьютерной сети НАЛ Беларуси BASNET. Комплекс создан в рамках ОНТП "Создать региональный узел республиканской научно-исследовательской компьютерной сети и подключить его к Интернет" (договор 7/96 с Фондом информатизации РБ) и ОНТП "Создать республиканский узел (WWW-сервер) о научных организациях и

разработках в республике" (договор 8/96 с Фондом информатизации РБ), выполненных по Постановлению Совета Министров Республики Беларусь № 1677 от 18.12.1997 г. Комплекс внедрен в HAH Беларуси, и вошел в перечень важнейших научно-исследовательских разработок Национальной академии наук Беларуси, предлагаемых к использованию в области строительства, связи, транспорта и энергетики в 1997 г.;

2) в Институте технической кибернетики HAH Беларуси в аппаратно-программной многопроцессорной системе NERV для решения прикладных задач параллельной обработки информации сложной структуры, разработанной в рамках выполнения работ по HT1I "Информатика", задание 01.03.03.01 "Разработать нейрокомпьютер (рабочую станцию) для решения прикладных задач параллельной обработки информации сложной структуры" (период выполнения 1992-1995 гг.). Использование результатов моделирования взаимодействий процессоров, функционирующих в системе NERV, обеспечило двукратное сокращение времени синхронизации при восьми одновременно функционирующих процессорах, а также линейный рост производительности при увеличении количества процессоров.

3) в Фонде социальной защиты населения Министерства социальной защиты населе1шя Республики Беларусь в корпоративной информационной системе по сбору страховых взносов и выплате пособий. Опьггаая эксплуатация в Фонде показала, что за счет разработанных аппаратно-программных средств удалось позы-сить надежность функционирования систем Фонда и примерно в 2 раза увеличить их производительность.

4) на ПО МТЗ при создании автоматизированной системы стендовых испытаний корпуса ускоренных испытаний. Использование предложенных методов и алгоритмов синхронизации в распределенной автоматизированной системе испытаний позволяет обеспечить оптимальную загрузку средств вычислительной техники при выполнении задач обмена информацией в реальном масштабе времени и повысить производительность распределенной вычислительной системы в 2,2 раза при решении задач обработки результатов испытаний узлов и агрегатов трактора.

Результаты диссертационной работы вошли в перечень основных результатов фундаментальных исследований Национальной академии наук Беларуси за 1995 г., а также использовались при выполнении международного проекта Немецкого исследовательского общества и HAH Беларуси по созданию параллельных логических процессоров для реализации логических операций в многопроцессорных системах (438 113/117/0 и Ма 1150/8-1).

Разработанный программно-технический комплекс демонстрировался на Международном салоне "Наука - Машиностроение - Рынок'97" в рамках Программы Президента Российской Федерации "Россия: человек, семья, общество, государство" ВВЦ, г. Москва, 1997 г., а также на выставке, посвященной 70-летию образования HAH Беларуси, Минск, 1999 г.

Результаты работы были отмечены дипломом за лучший результат по итогам работы Отделения ФМИ HAH Беларуси за 1997 год.

Целесообразным является использование результатов диссертации при выполнении российско-белорусского проекта СКИБР по разработке высокопроизводительной системы параллельной обработки информации.

Основные положения диссертации, выносимые на защиту

1. Математическая модель анализа производительности многопроцессорной системе топологии «общая шина».

2. Методика расчета минимальной верхней границы времени синхронизации в многопроцессорной системе топологии "общая шина".

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

4. Протокол динамической синхронизации процессоров в многопроцессорной системе.

5. Алгоритм и программное обеспечение для расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение.

Личный вклад соискателя

Основные положения, выносимые на защиту, получены лично автором, в том числе разработаны: математическая модель анализа производительности и методика расчета длительности синхронизации с использованием примитива взаимное исключение в многопроцессорной системе топологии "общая шина", метод статической синхронизации и протокол динамической синхронизации процессоров, реализующие базовые примитивы синхронизации: барьер, уведомление и взаимное исключение, а также алгоритм расчета оптимальных коэффициентов синхронизации процессоров с использованием примитива взаимное исключение в многопроцессорной системе. Научный руководитель принимал участие в постановке задач, определении и предварительном анализе возможных путей их решения, разработке архитектуры системы dsPLAY. Р. Хаузер (ФРГ), К.-Х. Ноффц (ФРГ), A.B. Шаренков, H.H. Легонин принимали участие в разработке системного и прикладного программного обеспечения для системы dsPLAY и системы NERV. К.-Х. Ноффц, Р. Хаузер (ФРГ) и В.В. Анищенко принимали участие в разработке технических узлов и функциональных схем dsPLAY и NERV. М.М. Маханек и Р. Мэн-нер разработали алгоритмы аппаратной синхронизации с использованием примитива уведомление. М.М. Маханек и В.Е. Чернявский разработали функциональные схемы конкретных узлов систем арбитража. Апробация результатов диссертации

Основные научные положения и результаты диссертации доложены на:

Республиканской конференции "Актуальные проблемы информатики: математическое, программное и информационное обеспечение".- Минск.- 1990.

Международном симпозиуме "Разработка высокопроизводительных параллельных архитектур.- Минск.- 1992.

Международной конференции "Автоматизация проектирования дискретных систем" (CAD DD'95).- Минск.- 1995.

Международной научно-технической конференции "Моделирование интеллектуальных процессов проектирования и производства", Минск, 1996.

Международном совещании "Создание интеррегиональной компьютерной сети по вопросам торговли (1СТСЧ)" ЦМТ.- Женева.- 1997.

IV Всероссийской конференции "Нейрокомпьютеры и их примените", Москва.- 1998.

Опублнкованность результатов

По материалам диссертации опубликовано 14 печатных работ, в том числе 3 статьи в научном журнале, 2 статьи в сборнике, 5 тезисов докладов и выступлений на конференциях, 4 препринта. Всего 174 страницы опубликованных материалов.

Структура и объем диссертации

Диссертация изложена на 106 страницах. Она содержит общую характеристику работы (9 стр.), 4 главы (86 стр., в том числе иллюстрации и таблицы - 19 стр.; 14 рисунков, 21 таблица), заключение (1 стр.), приложение (4 стр.), список использованных источников 89 наименований (7 стр.).

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

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

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

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

Пусть Е - количество процессоров в системе, М - количество одновременно реализуемых задач, II - среднее время реализации задачи процессором, С1; С2, С3

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

211

1)В случае квадратичного роста условие Е£М<— является необходи-

С1

мым для повышения производительности системы при распараллеливании процесса. Установлено, что коэффициент к роста производительности многопроцес-

ЛЕ

сорной системы к =

Сх

И +М(Е-1)

. Если Е невелико, т.е., если —»-

^ 2

то к ~ Е. При увеличении числа процессоров к^ах<

СХ 2 И

С^М

2) В случае линейного роста условие Е > ^——^ при С2 < й. является необходимым для повышения производительности системы при распараллеливании

ИМ ^

процесса, и кмах = ——^ ^ 2 при Е->М. Система более эффективна по сравнению с системой, имеющей квадратичную зависимость накладных расходов,

1 2 2Е 2 '

3) В случае, когда накладные расходы не изменяются, условие

с, (.)

является необходимым для повышения производительности системы при распараллеливании процесса, и к^ах~Е. Система более эффективна по сравнению с системой, имеющей линейную зависимость накладных расходов, если С3 <. С2М.

Из математической модели следуют выводы: во втором и третьем случаях при выполнении соответствующих необходимых условий система позволяет теоретически неограниченно наращивать производительность за счет увеличения числа М задач и числа Е процессоров. С ростом М и Е наступает такой момент, когда система третьего вида превзойдет все другие по производительности. Поэтому для достижения максимальной производительности надо не только уменьшать время С|, а найгп такой механизм синхронизации, время реализация которого не зависит от Е и М или имеет, по меньшей мере, линейную зависимость. При этом время С3 синхронизации процессоров должно быть минимизировано, с тем

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

Время реализации примитива взаимное исключение определяется как

N

с(г>= 5> оИп , (2)

¡=1

где N - разрядность двоичных слов приоритетов; 61 - время распространения сигнала но линии арбитража Ц, ¡=1,...,1У; ^Х) - время выполнения распределенных локальных частей СИ арбитража на множестве процессоров 2>={1,...,Е}; г( -число шагов в протоколе синхронизации; - время реализации процессором одного шага протокола; V - количество переключений сигналов на линиях Р, <3, К синхронизации при реализации протокола синхронизации, 6цц - время распространения сигналов по линиям Р, О, К. Для определения

*рг> Л. v разработаны и реализованы в системе параллельной обработки (ЬРЕАУ протоколы синхронизации, время выполнения которых не зависит от Е; 1(2,) решена задача минимизации с помощью разработанного алгоритма и ПО; 0] и 0Ип проведены эксперименты в сЬРЬАУ: 0= где Ц - время пе-

реключения выходного транзистора, С]) - межэлектродная емкость, Н| - сопротивление нагрузочного резистора.

Для обеспечения корректного окончания СИ арбитража задержка установки сигнала "синхронизации

Мах{10'£),]е2};>^е2с^+ф(г)е, 0<^<оо, (3)

где - задержка ^м процессорным элементом (ПЭ) установки индивидуального сигнала синхронизации окончания СИ арбитража; ^ - временной такт, специфицируемый для .¡-го ПЭ (0<^<со); - время срабатывания ¡-го узла ]-го ПЭ;

^ - количество интервалов времени т^ вносимых ¿-м ПЭ в общее

время выполнения арбитража. ^ ¡=1, если Т| ^ ¡^Мах.^^}^' иначе <1^=0.

Ф(Х)= Max{ajJl+2.=2 ^(ajд.1Фaj ¡), jА]=<а];1,...,а]>к> - двоичное слово приоритета, назначенное ] - му ПЭ, ]=1,...,Е. Условие (3) эквивалентно

где - коэффициент синхронизации j-гo ПЭ.

Задача отыскания минимального значения C(Z) сводится к нахождению 1рГ 9, 61!п, Cj и решению задачи определения коэффициентов Dj: >П11П

при условиях (4).

В третьей главе предлагается метод статической синхронизации процессоров и протокол динамической синхронизации. Метод статической синхронизации включает: семейство из шести базовых протоколов статической синхронизации (Табл. 1-6); графовую модель зависимости базовых протоколов синхронизации (Рис. 2); алгоритм формирования протокола статической синхронизации процессоров, реализующего любую последовательность базовых протоколов и гарантирующего корректное выполните вычислительного процесса.

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

Семейство из шести базовых протоколов статической синхронизации

Таблица 1

Базовый протокол #1___„_„

# Шаги базового протокола синхронизации Р р 11 V

1 Исходное состояние для СИ 1-го типа. 0 0 1

2 Начало СИ первого типа. Процессор начинающий СИ, устанавливает дк=1, вызывая переключение <2 в 1. 0 1 1 1 1

3 Все остальные процессоры распознают 0=1 и также начинают СИ первого типа. Они устанавливают q:=l. 0 I 1 2

4 Процессор ьеХу, имеющий минимальное время завершает первую СИ. Он устанавливает г5=0. 0 I 1 3

5 Остальные процессоры jeZ^ завершают СИ 1-го типа: ^=0, вызывая Н=0. Исходное состояние для СИ (1-го или 2-го типа). 0 I 0 4 2

Таблица 2

Базовый протокол #2_

# Шаги базового протокола синхронизации Р 9 и л V

1 Исходное состояние для СИ 2-го типа. 0 0 1

2 Начало СИ второго типа. Процессор кеХ^, начинающий СИ, устанавливает вызывая переключение <2 в 1. 0 1 1 1 1

3 Остальные процессоры ¡еЪ^ распознают (2=1 и начинают СИ, устанавливая 0 1 1 2

4 Процессор определяет, что остальные процессоры не смогут повлиять на результат СИ 2-го типа. Для ее окончания он устанавливает р8=1, вызывая Р=1. 1 I 1 3 2

5 Остальные процессоры ¡еХ-^ распознают окончание СИ второго типа согласно Р=1. Они устанавливают р—1. I 1 I 4

6 Все процессоры устанавливают г;=0, вызывая ]*=(). 1 1 0 5 3

7 Все процессоры в ответ на И=0 устанавливают qj=0, что влечет 0=0. Исходное состояние для СИ (1-го или 2-го типа). 1 0 0 6 4

Таблица 3

Базовый протокол #3___г_г_т__

# Шаги базового протокола синхронизации Р 0 я л V

1 Исходное состояние для СИ 1-го типа. 0 1 0

2 Начало'СИ первого типа. Процессор начинающий СИ, устанавливает рк=1, вызывая переключение Р в 1. 1 1 0 1 1

3 Все остальные процессоры распознают Р=1 и также начинают СИ. Они устанавливают р)~1. 1 I 0 2

4 Процессор зеХ2, имеющий минимальное время завершает СИ. Он устанавливает 1 1 0 3

5 Остальные процессоры jeZ2 завершают СИ 1-го типа: вызывая 0 в 0. Исходное состояние для СИ (1-го или 2-го типа). 1 0 0 4 2

Таблица 4

Базовый протокол #4.......

# Шаги базового протокола синхронизации Р 0 И п V

1 Исходное состояние для СИ 2-го типа. 0 1 0

2 Начало СИ второго типа. Процессор кеХ^, начинающий СИ, устанавливает Р|с=1, вызывая переключение Р в 1. 1 I 0 1 1

3 Все остальные процессоры} распознают Р=1 и начинают СИ второго типа, устанавливая Р}=1. 1 I 0 2

4 Процессор яеЪ-^ определяет, что остальные процессоры не смогут повлиять на результат СИ второго типа. Для ее окончания он устанавливает г5=1, вызывая переключение К в 1. 1 I 1 3 2

_____Продолжение табл.4

5 Остальные процессоры ] eZз распознают окончание СИ второго типа согласно 11=1. Они устанавливают гр=1. 1 1 I 4

6 Все процессоры ] еЪт, устанавливают вызывая <2=0. I 0 I 5 3

7 Все процессоры ¡^'¿з в ответ на 0=0 устанавливают р5=0, что влечет Р=0. Исходное состояние для СИ (1-го или 2-го типа). 0 0 1 6 4

Таблица 5

Базовый протокол #5__

# Шаги базового протокола синхронизации Р к ч — V

1 Исходное состояние для СИ 1-го типа. 1 0 0

2 Начало СИ первого типа. Процессор ксХ-}, начинающий СИ, устанавливает ^=1, вызывая переключение К в 1. 1 0 1 1 1

3 Все остальные процессоры jeZз распознают 11=1 и также начинают СИ. Они устанавливают 1 0 I 2

4 Процессор имеющий минимальное время завершает СИ. Он устанавливает р5=0. 1 0 I 3

5 Остальные процессоры jeZз завершают СИ 1-го типа: р^О, вызывая Р=0. Исходное состояние для СИ (1-го или 2-го типа). 0 0 1 3 2

Таблица 6

Базовый протокол #6___

# Шаги базового протокола синхронизации Р <? и ц V

1 Исходное состояние для СИ 2-го типа. 1 0 0

2 Начало СИ второго типа. Процессор ке^, начинающий СИ, устанавливает 1^=1, вызывая переключение Л в 1. 1 0 1 1 1

з Все остальные процессоры )еХ2 распознают 11=1 и начинают СИ, устанавливая Г|=1. 1 0 I 2

4 Процессор эеХ2 определяет, что остальные процессоры не смогут повлиять на результат СИ. Для ее окончания он устанавливает вызывая переключение О в 1. 1 1 1 3 2

5 Остальные процессоры распознают окончание СИ второго типа согласно 0=1. Они устанавливают 1 1 I 4

6 Все процессорыустанавливают Р^О, вызывая Р=0. 0 I 1 5 3

7 Все процессоры '^Ъ^ в ответ на Р=0 устанавливают гк=0, что влечет 11=0. Исходное состояние для СИ (1-го или 2-го типа). 0 1 0 6 4

Граф на рис. 2 является объединением графов, представленных на рис. 1 и описанных в табл. 1-6. Вершинам приписаны начальные и конечные состояния линий синхронизации Р, (5, II, а ориентированным дугам - переходы из начальных состояний в конечные, т.е. базовые протоколы синхронизации. Направленные дуги графа помечаются цифрой, соответствующей номеру базового протокола.

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

На основе графовой модели зависимости, исходного состояния сигналов на линиях синхронизации Р, Я от типа СИ (рис. 1) предложен алгоритм формирования протокола статической синхронизации процессоров.

Начальное состояние

Начальное состояние

р<ЗН О О 1

1-ый тип СИ

010 100

0 1 о

2-ой тип СИ 1-ый тип СИ

юо [ оо:

2 -ой тип СИ

001 !

Табл.1 Табл.2 Конечные состояния

Табл. 3 Табл. 4 Конечные состояния

Начальное состояние

р (2 л 1 о о

1-ый тип СИ

Пси7 001 010

2-ой тип СИ

Табл. 5 Табл. 6

Конечные состояния

Рис. 1. Графовая модель зависимости исходного состояния сигналов на линиях синхронизации Р, О, II от типа СИ

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

В четвертой главе предложен алгоритм и программное обеспечение для

расчета оптимальных коэффициентов синхронизации. Коэффициенты П| не могут

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

Формируется множество слов приоритетов В1(п,Гч)={А^

1=1,...,ПС5 ). где С^ - число сочетаний из N по 5, слова класснфициру-ются по глубине ф(Aj), Aj е В1(пД), рассчитываются максимальное фша1(1М(пД))

А

и среднее значите глубины слов приоритетов фср (В|(п,1Чт)) = > —где -

1=0

количество слов фиксированной глубины ¡=0,...,фтах(В1(пД)) в множестве, а В1ПК - мощность множества.

Таблица 7

Протокол динамической синхронизации процессоров

а Шаги протокола синхронизации Р 9 к Г] V

1 Исходное состояние для начала первой СИ. 1 0 0

2 Начало СИ. Процессор к'ег, начинающий первую СИ, устанавливает 4^'=!, вызывая переключение О в 1. 1 1 0 1 1

3 Остальные процессоры ¡еХ распознают <2=1 и также начинают СИ. Они устанавливают Ч]=1. I 1 0 2

4 Некоторые процессоры ¡еХ^ могут заканчивать выполнение индивидуальных частей СИ. Они устанавливают р;=0. 1 1 0 3

5 Если процессор к"еХ определяет, что остальные процессоры не смогут повлиять на результат СИ, он, удерживая Рк'^1, устанавливает гк<«=1, вызывая 11=1. Переход к выполнению шага 7а. 1 1 1 3 2

6а Иначе все процессоры ьс-Х заканчивают выполнение индивидуальных частей СИ (первого типа). Они устанавливают Pj=0. 0 I 0 3 2

6а Для поддержки протокола синхронизации процессоры }еХ устанавливают 1^=1. 0 I 1 4 3

6Ь Для поддержки протокола синхронизации процессоры jeZ устанавливают 0 0 1 5 4

6с Для' поддержки протокола синхронизации процессоры ] еХ устанавливают Р]=0. Переход к выполнению шага 8. 1 0 I 6 5

7а Все остальные процессоры ] еХ распознают окончание СИ (второго типа) согласно Р=1. Они устанавливают Г|=1. 1 1 1 4

7Ь Для поддержки протокола синхронизации процессоры jeZ устанавливают Pj=l. 1 1 1 5

7с Для поддержки протокола синхронизации процессоры }еХ1 устанавливают qj=0. I 0 1 6 3

8 Для поддержки протокола синхронизации процессоры jeZ устанавливают Г|=0. Исходное состояние для начала второй СИ. 1 0 0 7 4,6

РОЯ

РСЖ

Рис. 2. Графовая модель взаимосвязи семейства базовых протоколов (БП) статической синхронизации

Исследуются СИ арбитража с различным числом слов

Уе{1,...,2_0 - дСр^} из множества В1(п,1Ч). Рассчитывается среднее значение глубины фср1у(ВКа,Г0) во всех возможных СИ арбитража с заданным У.

П У

С Л ))

1=1 ^ Ед

фер,у(В1(п,Г0) =------.

¡=1

Для В1(пДЧ) строится таблица формирования ограничений вида (4), на основании которой определяются оптимальные коэффициенты синхронизации ^. Используя эти коэффициенты и специфицируемые для системы характеристики tpP ®Ип> ®1> полученные экспериментально с помощью (18РЬАУ, определяется минимальное значение времени реализации примитива взаимное исключение (2).

В стандартных системах арбитража коэффициент синхронизации всегда не превышает разрядности N слов приоритетов: П|<14. Результаты диссертации показали, что среднее значение коэффициента г^ср может быть уменьшено за счет расширения диапазона допустимых значений, например, при П|<6 1^ср=4,44. Если п^8, ^<9, то П|Ср=4, =3.94 и =3.92 соответственно. Это позволяет увеличить скорость выполнения СИ арбитража более чем на 13% только за счет корректного определения коэффициентов синхронизации. При верификации с помощью системы с^РЬАУ компонентов, входящих в соотношение (2), согласование было в рам-

ках допустимой погрешности и в среднем составило около 4,6% для шестиразрядных слов. Также было экспериментально подтверждено, что значение Мах {((],?,), ¡еХ], где является верхней границей времени реализации СИ ар-

битража, что обеспечило корректность выполнения СИ синхронизации.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Разработана методика расчета минимальной верхней границы времени синхронизации в многопроцессорной системе топологии "общая шина" [2,11, 13].

3. Разработан метод статической синхронизации процессоров в многопроцессорной системе топологии "общая шина" без адресного обмена данными на основе функционально-полного семейства протоколов статической синхронизации, обеспечивающих синхронизацию при различных требованиях к завершению локальных действий процессоров и наличии априорных знаний о характере вычислительного процесса [1,2,11,13].

4. Разработан протокол динамической синхронизации процессоров в многопроцессорной системе, обеспечивающий корректную синхронизацию при отсутствии адресного обмена данными и априорных знаний о характере вычислительного процесса [1,13].

5. Разработан на основе предложенной математической модели алгоритм и программное обеспечение для расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение [3,5-8].

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Маханек М.М., Вальчевская Г.Ю., Мэннер Р. Синхронизация нараллльных операций в распределенных многопроцессорных системах // Известия АН Беларуси. Сер. физ.-тех. наук - N 2,- 1995.- С. 70-79.

2. Маханек М.М., Вальчевская Г.Ю., Мэннер Р. Минимизация верхней оценки продолжительности параллельной операции К Известия АН Беларуси. Сер. физ.-тех. наук.- 1995.- N 3.- С. 48-53.

3. Маханех М.М., Валъчезская Г.Ю. Перепрограммируемая система для моделирования параллельных логических операций // Известия АН Беларуси. Сер. физ.-тех. наук,- 1996.- N 4,- С. 58-63.

4. Маханек М.М., Вальчевская Г.Ю. Координационная деятельность по нейрокомпьютерам в Европейской программе развития информационных технологий // Разработка высокопроизводительных параллельных архитектур: Сб. ст.; Научн. редакторы М.М. Маханек, Р. Мэннер.- Минск: НТК АНБ.- 1992.- С. 6-23.

5. Вальчевская Г.Ю., Маханек М.М., Чернявский В.Е. Программное моделирование логических операций в распределешюм параллельном процессоре И Разработка высокопроизводительных параллельных архитектур: Сб. ст.; Научн. редакторы М.М. Маханек, Р. Мэннер.- Минск: ИТК АНБ., 1992,- С. 60-70.

6. Вальчевская Г.Ю. Диалоговая система проектирования распределенного процессора поиска экстремума // Автоматизация проектирования дискретных систем: Материалы международной конференции. Тезисы докладов. / Белгосуннверситет.-Мипск, 1995,- Том. 1,- С. 153.

7. Вальчевская Г.Ю., Маханек М.М. Перепрограммируемый комплекс dsPLAY для моделирования логических операций // Автоматизация проектирования дискретных систем: Материалы международной конференции. Тезисы докладов / Белгосуниверситет.- Минск, 1995.- Том. 1,- С. 28.

8. Г.Ю. Вальчевская. Комплекс для проектирования аппаратных средств синхронизации многопроцессорных систем // Международная научно-техническая кон-ференц. "Моделирование интеллектуальных процессов проектирования и производства".- Минск, 13-15 ноября, 1996.- С. 29.

9. Litoff J., Langolis G., Ilacqua J., Records H., Makhaniok M., Valtchevskaya G. Using technology to foster collaborative learning at a distance: the National Academy of Sciences of Belarus and Bryant College connection, ICTE Tampa, 17th International Conference on Technology and Education, Tampa, Florida.- 1999.- P. 105-109.

10. Makhaniok M., Valtchevskaia G., Manner R. Unified Research and Information Computer Network of the Republic of Belarus.- Conference on Computer Science and Information technologies (CSIT99), 1999, Yerevan, Armenia.- P. 421-424.

11. Маханек M.M., Вальчевская Г.Ю., P. Мэннер, K.-X. Ноффц. Синхронизация логических операций в однородных параллельных структурах.- Минск, 1993.- 58 с.-(Препринг N9 / ИТК АНБ).

12. Маханек М.М., Хаузер Р., Мэгагер Р., Вальчевская Г.Ю. Архитектура многопроцессорной системы для эффективной реализации генетических алгоритмов.-Минск, 1994.- 30 с. (Препринт/ Ин-т техн. кибернетики АНБ; N 6).

13.Makhaniok M., Valtchevskaia G., Manner R. Improved 3-Line Hardware Synchronization.- Minsk, 1996,15 p.- (Preprint N6/ITK ANB).

14. Вальчевская Г.Ю. Критерий эффективности распараллеливания задачи в асинхронных многопроцессорных системах,- Минск, 1998,- 12 е.- (Препринт N9 / ИТК АН БССР).

РЭЗЮМЕ дысертацы! Вальчэускай Гаянэ Юр'еуны "Метады I алгарытмы сшхрашзаць» працэсарау у шматпрацэсарных сктэмах тапалоги «а!ульная шына»"

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

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

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

На аснове прапанаванай матэматычнай мадэЛ1 анагпзу прадукцыйнасщ, якая адрозгаваецца ад вядомых тым, што яна умчвае тры выпада залежнасщ накладных выдаткау ад павел!чэння колькасвд выконваемых задач 1 працэсарау, выраша-на праблема распрацоуш пратаколау сшхрашзацьи, час рэалЬацьп язах не зале-жьщь ад лису працэсарау 1 задач. Распрацаваныя метад 1 пратаколы статычнай г дынам1чнай С1нхрашзацьп дазваляюць рэалЬаваць любую камбшацыю з базавай сукупнасщ прымггывау сшхрашзацьи: бар'ерау, паведамленняу \ узаемных вы-ключэнняу, што гарантуе карэктнае выкананне любога параллельнага прасзсу. 1стотным адрозненнем гэтых пратаколау з'яуляецца тое, што яны дазваляюць за-канчваць сумесную шструкцыю як пасля завяршэння усь\п працэсарам1 лакальных дзеяныяу, так 1 па шщыятыве любого з шх. Прапанавана методыка вызначэння працяглаац сумеснай шструкцьй 1 алгарытм знаходжання аптъшальных ка-эф'щыентау сшхрашзацьп.

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

РЕЗЮМЕ

диссертации Вальчевской Гаянэ Юрьевны "Методы и алгоритмы синхронизации процессоров в многопроцессорных системах топологии «общая шина»"

Ключевые слова: многопроцессорные системы, базовые примитивы и протоколы синхронизации, математическая модель анализа производительности, длительность синхронизации.

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

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

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

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

SUMMARY

of the dissertation thesis "The methods and algorithms of synchronization for multiprocessor system organization based on common bus " by Gajane Jurievna Valtchevskaia

Key words: multiprocessor systems, basic synchronization primitives, synchronization protocols, mathematical model for performance analysis, duration of synchronization.

The dissertation thesis is devoted to the problem of high-speed synchronization for bus-oriented multiprocessor systems. Its purpose is the development of methods for synchronization and utilization of efficient protocols on this basis, which allow reducing duration of parallel processes.

While fulfilling applied tasks with the usage of genetic and neurocomputing algorithms, the effectiveness of the system in general is determined by the number of simulating neurons or individuals in a population, that is by the number of processors. The specificity of these algorithms consists in the fact that for every instruction of synchronization a few simple computational instructions to be executed. For this system has the limitation both with performance of computational instructions and with the number of instructions of synchronization, the moment comes when with the growth of the number of processors the system begins to decline its performance.

On the basis of the offered mathematical model for performance analysis, differed from the known models by the investigation of three cases of dependence of overhead from the increase of the number of fulfilled tasks and processors, the problem of the development of synchronization protocols was settled as follows. The duration of the realization of protocols isn't depended on the number of processors and tasks.

Proposed method and protocols of the static and dynamic synchronization allow realizing any combination of basic totality of synchronization primitives: barrier, notification and mutual exclusion, which guarantee the correct execution of any parallel process. The essential advantage of these protocols is that they allow finishing any common instruction as after the fulfillment of the local actions by all processors, as after the initiative of any of them.

The methodology of determination of duration of common instruction and algorithm were developed to identify optimal synchronization parameters.

The result of the work was used while the fulfillment of the number of Republic and International projects for the development of a number of parallel distributed systems.

ВАЛЬЧЕВСКАЯ Гаянэ Юрьевна

МЕТОДЫ И АЛГОРИТМЫ СИНХРОНИЗАЦИИ ПРОЦЕССОРОВ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ ТОПОЛОГИИ «ОБЩАЯ ШИНА»

Специальность 05.13.13. - Вычислительные машины, комплексы, системы и сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 27. СЗ. .2000. Формат 60x84 1/16

Бумага ппсчая. Печать ризографическая. Усл. печ. л. 1,39. Уч.-изд. л. 1,0. Тираж 50 экз. Зак. 152.

Белорусский государственный университет информатики и радиоэлектроники Отпечатано в БГУИР. Лицензия ЛП № 156. 220027, Минск, П. Бровки, 6