БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
УДК 681.3
Вальчевская Гаянэ Юрьевна
МЕТОДЫ И АЛГОРИТМЫ СИНХРОНИЗАЦИИ ПРОЦЕССОРОВ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ ТОПОЛОГИИ «ОБЩАЯ ШИНА»
Специальность 05.13.13 – Вычислительные машины, комплексы, системы и сети
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
Минск 2000
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы диссертации
Желание повысить производительность многопроцессорной системы путем увеличения числа процессоров с целью распараллеливания процесса ведет к резкому росту накладных расходов системы, связанных с увеличением количества взаимодействий. Моделирование поведения многопроцессорных систем показало, что повышение их производительности сдерживается малоэффективными механизмами управления параллельно функционирующими процессорами и, прежде всего, средствами синхронизации. Известные в настоящее время методы и алгоритмы синхронизации М.Тауба, М.Маханька, Р.Мэннера и др. не могут быть использованы при выполнении вычислительных процессов, требующих реализации различных базовых примитивов синхронизации: барьеров, уведомлений, взаимных исключений.
Диссертация посвящена решению проблемы скоростной синхронизации, позволяющей сократить время выполнения параллельного процесса в многопроцессорных системах топологии «общая шина». Сложность данной проблемы обусловлена тем, что логика синхронизации должна одновременно удовлетворять ряду принципиально важных требований: обеспечивать симметричность как относительно процессоров и реализуемых ими задач, так и системных ресурсов, что гарантирует их равнодоступность; учитывать невозможность установить ограничения производительности процессоров или предположить, что их скорости постоянны во времени; не приводить к блокировке процессоров при рассинхронизации любого из них; учитывать, что не существует таких ограничений по скорости процессоров или задержек ожидания, при которых решение вопроса о пользовании общим разделяемым ресурсом откладывается на неопределенное время; обеспечивать реализацию всех базовых примитивов синхронизации при минимальных накладных расходах на организацию вычислительного процесса.
В основе предлагаемого подхода к решению проблемы скоростной синхронизации лежит идея разработки метода синхронизации, позволяющего реализовать в динамике работы любой из перечисленных примитивов, используя одни и те же программно-технические средства. Для этого требуются оригинальные протоколы синхронизации, а для определения оптимальных параметров синхронизации и характеристик многопроцессорных систем, таких как число процессоров, индивидуальные оптимальные задержки установки сигнала синхронизации окончания совместных инструкций (СИ), минимальное время реализации параллельного процесса, необходима разработка: математической модели анализа производительности многопроцессорной системы, учитывающей зависимость накладных расходов как от числа одновременно выполняемых задач, так и от числа процессоров, и алгоритма расчета оптимальных коэффициентов синхронизации.
Для достижения целей диссертации наряду с разработанными автором теоретическими положениями были всесторонне исследованы наиболее оригинальные идеи в области синхронизации, в частности, методы скоростной организации доступа процессоров к критическому интервалу (методы поиска максимального числа в неупорядоченном наборе чисел, распределенных по процессорам), методы программно-аппаратной синхронизации, обеспечивающие скоростную реализацию барьеров и уведомлений. Для расчета и минимизации времени синхронизации была применена система параллельной обработки dsPLAY.
Связь работы с крупными научными программами, темами
Результаты, полученные в диссертации, были использованы при выполнении ряда республиканских и международных научно-технических проектов.
- Разработать нейрокомпьютер (рабочую станцию) для решения прикладных задач параллельной обработки информации сложной структуры. Период выполнения - 1992-1994 гг. Раздел 01.03.03 республиканской научно-технической программы ”Информатика”.
- Разработка многопроцессорных архитектур для обработки и распознавания изображений. Период выполнения - 1994-1995 гг. Раздел 1.13.12 программы фундаментальных исследований “Проблемы искусственного интеллекта”.
- Разработка методов и средств скоростной параллельной обработки информации с использованием нейроархитектур в системах и образцах вооружений и военной техники для принятия решений в режиме, критическом по времени, обработки и распознавания видео изображений, радиоакустических сигналов. НИР Шифр “Район АН” № 02.03.05 НТК МО Республики Беларусь. Период выполнения - 1992-1994 гг.
- Исследование и разработка алгоритмов обнаружения и классификации полутоновых объектов на сложном фоне. НИР Шифр “Ракита – 2” № 02.01.02 НТК МО Республики Беларусь. Период выполнения - 1993-1994 гг.
- Параллельные логические процессоры для многопроцессорных систем. Период выполнения - 1991-1993 гг. и 1994-1996 гг., № Ma 1150/8-1 и 438 113/117/0, Немецкое Исследовательское Общество (DFG).
- Параллельные логические процессоры для реализации логических операций в многопроцессорных системах. Период выполнения - 1993-1995 гг., № 436 WER 113-1-0, Немецкое Исследовательское Общество (DFG).
- Европейская научно-технологическая сеть передачи информации. Период выполнения - 1995-1996 гг., № INTAS-E96-08, Брюссель, ЕС.
- Демонстрация скоростной параллельной архитектуры для обработки изображений. Период выполнения - 1994-1995 гг., № INTAS-93-1050, Брюссель, ЕС.
- Разработка научно-исследовательской компьютерной сети НАН Беларуси. Период выполнения - 1994-1995 гг., № 450/BYE/09/9508004, ЮНЕСКО, Париж.
- Разработать сетевую инфраструктуру учреждений Академии наук РБ с обеспечением доступа к глобальным компьютерным сетям. Период выполнения - 1996-1998, из состава отдельных проектов НИОКР ГКНТ РБ.
- Создать региональный узел республиканской научно-исследовательской компьютерной сети и подключить его к Интернет. Период выполнения - 1996-1998, из состава отдельных проектов НИОКР ГКНТ РБ.
- Разработка технорабочего проекта, монтаж и ввод в эксплуатацию автоматизированной системы стендовых испытаний корпуса ускоренных испытаний ПО “Минский тракторный завод”. Период выполнения - 1998-2001.
Цель и задачи исследования
Целью настоящей диссертации является разработка методов синхронизации в многопроцессорных системах топологии “общая шина” и создание на их основе эффективных протоколов статической и динамической синхронизации, позволяющих уменьшить накладные расходы на организацию взаимодействий процессоров.
Для достижения поставленной цели решаются следующие задачи:
- Разработать математическую модель анализа производительности многопроцессорной системы топологии «общая шина», учитывающую различные виды зависимости накладных расходов от количества процессоров и количества, выполняемых ими задач и определить оптимальное количество одновременно выполняемых задач и количество процессоров, реализующих вычислительный процесс за минимальное время.
- Разработать методику расчета минимальной верхней границы времени синхронизации в многопроцессорной системе топологии “общая шина”.
- Разработать метод статической синхронизации процессоров в многопроцессорной системе топологии “общая шина” без адресного обмена данными на основе функционально-полного семейства протоколов статической синхронизации, обеспечивающих синхронизацию при различных требованиях к завершению локальных действий процессоров и наличии априорных знаний о характере вычислительного процесса.
- Разработать протокол динамической синхронизации процессоров в многопроцессорной системе, обеспечивающий корректную синхронизацию при отсутствии адресного обмена данными и априорных знаний о характере вычислительного процесса.
- Разработать на основе предложенной математической модели алгоритм и программное обеспечение для расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение.
Объект и предмет исследования
Объектом исследования являются программно-аппаратные средства синхронизации в многопроцессорных системах топологии “общая шина”.
Гипотеза
Предполагается существование единого протокола синхронизации, реализующего любой из базовых примитивов в многопроцессорной системе в динамике ее работы.
Методология и методы проведенного исследования
В диссертации применялись методы математического моделирования, оптимизации, булевой алгебры, комбинаторного анализа, вариационного исчисления, а также методы синхронизации.
Научная новизна и значимость полученных результатов
- Разработана математическая модель анализа производительности многопроцессорной системы, отличающаяся от известных моделей тем, что она учитывает различные виды зависимости роста накладных расходов от увеличения количества процессоров и количества выполняемых задач. Это позволило аналитически определить для каждого вида зависимости верхнюю границу количества задач и оптимальное количество процессоров, реализующих вычислительный процесс за минимальное время в многопроцессорной системе.
- Предложена методика расчета минимальной верхней границы длительности синхронизации с использованием примитива взаимное исключение в многопроцессорной системе топологии “общая шина”, учитывающая технические характеристики процессоров, линий синхронизации и обмена данными, а также реализации протоколов синхронизации.
- Предложен метод статической синхронизации процессоров многопроцессорной системы топологии “общая шина” на основе разработанного функционально-полного семейства протоколов статической синхронизации. Метод обеспечивает синхронизацию процессоров без изменения количества линий синхронизации при увеличении числа процессоров, а также без адресного обмена данными и, в отличие от известных, позволяет реализовать вычислительный процесс, использующий различные базовые примитивы синхронизации. При этом время реализации протокола синхронизации не зависит от количества процессоров.
- Предложен протокол динамической синхронизации процессоров в многопроцессорной системе топологии “общая шина”, обеспечивающий корректную синхронизацию процессоров в отсутствии адресного обмена данными и априорных знаний о характере вычислительного процесса. Протокол позволяет завершать совместные инструкции как по окончании выполнения всеми процессорами локальных действий, так и по инициативе любого из процессоров и реализовать базовые примитивы синхронизации.
- Разработан алгоритм расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение.
Практическая значимость полученных результатов
Результаты научных исследований автора внедрены:
1) в центральном управляющем комплексе научно-информационной компьютерной сети НАН Беларуси BASNET. Комплекс создан в рамках ОНТП “Создать региональный узел республиканской научно-исследовательской компьютерной сети и подключить его к Интернет” (договор 7/96 с Фондом информатизации РБ) и ОНТП “Создать республиканский узел (WWW-сервер) о научных организациях и разработках в республике” (договор 8/96 с Фондом информатизации РБ), выполненных по Постановлению Совета Министров Республики Беларусь № 1677 от 18.12.1997 г. Комплекс внедрен в НАН Беларуси, и вошел в перечень важнейших научно-исследовательских разработок Национальной академии наук Беларуси, предлагаемых к использованию в области строительства, связи, транспорта и энергетики в 1997 г.;
2) в Институте технической кибернетики НАН Беларуси в аппаратно-программной многопроцессорной системе NERV для решения прикладных задач параллельной обработки информации сложной структуры, разработанной в рамках выполнения работ по НТП “Информатика”, задание 01.03.03.01 “Разработать нейрокомпьютер (рабочую станцию) для решения прикладных задач параллельной обработки информации сложной структуры” (период выполнения 1992-1995 гг.). Использование результатов моделирования взаимодействий процессоров, функционирующих в системе NERV, обеспечило двукратное сокращение времени синхронизации при восьми одновременно функционирующих процессорах, а также линейный рост производительности при увеличении количества процессоров.
3) в Фонде социальной защиты населения Министерства социальной защиты населения Республики Беларусь в корпоративной информационной системе по сбору страховых взносов и выплате пособий. Опытная эксплуатация в Фонде показала, что за счет разработанных аппаратно-программных средств удалось повысить надежность функционирования систем Фонда и примерно в 2 раза увеличить их производительность.
4) на ПО МТЗ при создании автоматизированной системы стендовых испытаний корпуса ускоренных испытаний. Использование предложенных методов и алгоритмов синхронизации в распределенной автоматизированной системе испытаний позволяет обеспечить оптимальную загрузку средств вычислительной техники при выполнении задач обмена информацией в реальном масштабе времени и повысить производительность распределенной вычислительной системы в 2,2 раза при решении задач обработки результатов испытаний узлов и агрегатов трактора.
Результаты диссертационной работы вошли в перечень основных результатов фундаментальных исследований Национальной академии наук Беларуси за 1995 г., а также использовались при выполнении международного проекта Немецкого исследовательского общества и НАН Беларуси по созданию параллельных логических процессоров для реализации логических операций в многопроцессорных системах (438 113/117/0 и Ma 1150/8-1).
Разработанный программно-технический комплекс демонстрировался на Международном салоне “Наука – Машиностроение – Рынок’97” в рамках Программы Президента Российской Федерации “Россия: человек, семья, общество, государство” ВВЦ, г. Москва, 1997 г., а также на выставке, посвященной 70-летию образования НАН Беларуси, Минск, 1999 г.
Результаты работы были отмечены дипломом за лучший результат по итогам работы Отделения ФМИ НАН Беларуси за 1997 год.
Целесообразным является использование результатов диссертации при выполнении российско-белорусского проекта СКИБР по разработке высокопроизводительной системы параллельной обработки информации.
Основные положения диссертации, выносимые на защиту
- Математическая модель анализа производительности многопроцессорной системы топологии «общая шина».
- Методика расчета минимальной верхней границы времени синхронизации в многопроцессорной системе топологии “общая шина”.
- Метод статической синхронизации процессоров в многопроцессорной системе топологии “общая шина” без адресного обмена данными.
- Протокол динамической синхронизации процессоров в многопроцессорной системе.
- Алгоритм и программное обеспечение для расчета оптимальных коэффициентов синхронизации с использованием примитива взаимное исключение.
Личный вклад соискателя
Основные положения, выносимые на защиту, получены лично автором, в том числе разработаны: математическая модель анализа производительности и методика расчета длительности синхронизации с использованием примитива взаимное исключение в многопроцессорной системе топологии ”общая шина”, метод статической синхронизации и протокол динамической синхронизации процессоров, реализующие базовые примитивы синхронизации: барьер, уведомление и взаимное исключение, а также алгоритм расчета оптимальных коэффициентов синхронизации процессоров с использованием примитива взаимное исключение в многопроцессорной системе. Научный руководитель принимал участие в постановке задач, определении и предварительном анализе возможных путей их решения, разработке архитектуры системы dsPLAY. Р. Хаузер (ФРГ), К.-Х. Ноффц (ФРГ), А.В. Шаренков, Н.Н. Легонин принимали участие в разработке системного и прикладного программного обеспечения для системы dsPLAY и системы NERV. К.-Х. Ноффц, Р. Хаузер (ФРГ) и В.В. Анищенко принимали участие в разработке технических узлов и функциональных схем dsPLAY и NERV. М.М. Маханек и Р. Мэннер разработали алгоритмы аппаратной синхронизации с использованием примитива уведомление. М.М. Маханек и В.Е. Чернявский разработали функциональные схемы конкретных узлов систем арбитража.
Апробация результатов диссертации
Основные научные положения и результаты диссертации доложены на:
Республиканской конференции ”Актуальные проблемы информатики: математическое, программное и информационное обеспечение”.- Минск.- 1990.
Международном симпозиуме “Разработка высокопроизводительных параллельных архитектур.- Минск.- 1992.
Международной конференции “Автоматизация проектирования дискретных систем” (CAD DD'95).- Минск.- 1995.
Международной научно-технической конференции “Моделирование интеллектуальных процессов проектирования и производства”, Минск, 1996.
Международном совещании “Создание интеррегиональной компьютерной сети по вопросам торговли (ICTIN)”, ЦМТ.- Женева.- 1997.
IV Всероссийской конференции “Нейрокомпьютеры и их применение”, Москва.- 1998.
Опубликованность результатов
По материалам диссертации опубликовано 14 печатных работ, в том числе 3 статьи в научном журнале, 2 статьи в сборнике, 5 тезисов докладов и выступлений на конференциях, 4 препринта. Всего 174 страницы опубликованных материалов.
Cтруктура и объем диссертации
Диссертация изложена на 106 страницах. Она содержит общую характеристику работы (9 стр.), 4 главы (86 стр., в том числе иллюстрации и таблицы – 19 стр.; 14 рисунков, 21 таблица), заключение (1 стр.), приложение (4 стр.), список использованных источников 89 наименований (7 стр.).
ОСНОВНОЕ СОДЕРЖАНИЕ
Во введении дана краткая оценка работ в рассматриваемой области, обоснована актуальность исследуемой в диссертационной работе проблемы, сформулированы цель и задачи, которые решаются для достижения поставленной цели.
В первой главе проведен анализ современного состояния предметной области, существующих методов синхронизации многопроцессорных систем для синхронных и асинхронных шин, использующих централизованный и распределенный механизмы синхронизации. В результате проведенного анализа известных систем синхронизации установлено, что уменьшение накладных расходов системы, связанных с организацией функционирования процессоров при выполнении взаимодействующих задач, может быть достигнуто за счет динамической реализации базовых примитивов синхронизации, совокупность которых гарантирует корректное завершение любого параллельного процесса: взаимное исключение - только одному процессору в момент времени разрешается войти в критическую секцию с возможностью доступа к разделяемым ресурсам; барьер - некоторые процессоры вынуждены ждать в определенной точке своей задачи до тех пор, пока остальные процессоры не завершат локальные вычисления; уведомление - один из процессоров сообщает остальным, что он прошел определенную точку в задаче, что позволяет остальным процессорам скорректировать свои действия.
Установлено, что одной из сложнейших проблем создания многопроцессорных систем топологии “общая шина” является синхронизация процессоров при выполнении процесса, состоящего из взаимосвязанных задач, поскольку производительность системы ограничена не только по числу вычислительных инструкций, но и по числу синхронизаций, выполняемых в единицу времени.
Диссертация развивает исследования в области разработки систем синхронизации. На основе проведенного автором анализа показано, что до сих пор не решена проблема одновременной аппаратной реализации всех трех базовых примитивов синхронизации с тем, чтобы обеспечить линейный рост производительности многопроцессорных систем при наращивании числа процессоров.
Во второй главе на основе классических результатов Индихиа, Стоуна и Хай-Ченга разрабатывается и исследуется математическая модель анализа производительности многопроцессорной системы, учитывающая три вида роста накладных расходов в зависимости от увеличения числа процессоров и одновременно выполняемых задач: квадратичный, линейный и отсутствие роста. Модель позволяет установить оптимальное количество задач и оптимальное количество процессоров, выполняющих вычислительный процесс за минимальное время.
Пусть E – количество процессоров в системе, M – количество одновременно реализуемых задач, R – среднее время реализации задачи процессором, С1, С2, С3 - среднее время взаимодействия двух задач, выполняемых различными процессорами для трех случаев зависимости накладных расходов от увеличения числа задач: квадратичного, линейного и отсутствия зависимости соответственно.
1) В случае квадратичного роста условие 
является необходимым для повышения производительности системы при распараллеливании процесса. Установлено, что коэффициент k роста производительности многопроцессорной системы 
. Если Е невелико, т.е., если 
>>
, то k ~ E. При увеличении числа процессоров kMax
.
2) В случае линейного роста условие 
при 
является необходимым для повышения производительности системы при распараллеливании процесса, и 
при EM. Система более эффективна по сравнению с системой, имеющей квадратичную зависимость накладных расходов, если 
.
3) В случае, когда накладные расходы не изменяются, условие
(1)
является необходимым для повышения производительности системы при распараллеливании процесса, и 
. Система более эффективна по сравнению с системой, имеющей линейную зависимость накладных расходов, если 
.
Из математической модели следуют выводы: во втором и третьем случаях при выполнении соответствующих необходимых условий система позволяет теоретически неограниченно наращивать производительность за счет увеличения числа M задач и числа E процессоров. С ростом M и E наступает такой момент, когда система третьего вида превзойдет все другие по производительности. Поэтому для достижения максимальной производительности надо не только уменьшать время С1, а найти такой механизм синхронизации, время реализации которого не зависит от E и М или имеет, по меньшей мере, линейную зависимость. При этом время С3 синхронизации процессоров должно быть минимизировано, с тем чтобы удовлетворять условию (1). Для этого предлагается методика определения минимальной верхней границы времени синхронизации с использованием примитива взаимное исключение.
Время реализации примитива взаимное исключение определяется как
С(Z)= 
+t(Z)+tpr + lin , (2)
где N - разрядность двоичных слов приоритетов; i - время распространения сигнала по линии арбитража Li, i=1,…,N; t(Z) - время выполнения распределенных локальных частей СИ арбитража на множестве процессоров Z={1,…,E}; - число шагов в протоколе синхронизации; tpr - время реализации процессором одного шага протокола; - количество переключений сигналов на линиях P, Q, R синхронизации при реализации протокола синхронизации, lin - время распространения сигналов по линиям P, Q, R.
Для определения
tpr, , разработаны и реализованы в системе параллельной обработки dsPLAY протоколы синхронизации, время выполнения которых не зависит от Е;
t(Z) решена задача минимизации с помощью разработанного алгоритма и ПО;
i и lin проведены эксперименты в dsPLAY: = ts+2.2ER1CD, где ts - время переключения выходного транзистора, CD – межэлектродная емкость, R1 – сопротивление нагрузочного резистора.
Для обеспечения корректного окончания СИ арбитража задержка установки сигнала синхронизации
Max {t(j,Z), jZ} jZcjj +(Z), 0<j<, (3)
где t(j,Z) - задержка j-м процессорным элементом (ПЭ) установки индивидуального сигнала синхронизации окончания СИ арбитража; j - временной такт, специфицируемый для j-го ПЭ (0<j<); jj,i - время срабатывания i-го узла j-го ПЭ; cj=i=1,...,Nj,idj,i - количество интервалов времени j, вносимых j-м ПЭ в общее время выполнения арбитража. dj,i=1, если j j,i=Maxj’Z{j j,i}, иначе dj,i=0. jZdj,i=1, (Z)= Max{aj,1+i=2,…,N(aj,i-1aj,i), jZ}, Aj=‹aj,1,…,aj,N› - двоичное слово приоритета, назначенное j – му ПЭ, j=1,…,E.
Условие (3) эквивалентно
, (4)
где nj=
- коэффициент синхронизации j-го ПЭ.
Задача отыскания минимального значения С(Z) сводится к нахождению tpr, , lin, сj и решению задачи определения коэффициентов nj: jZnjmin при условиях (4).
В третьей главе предлагается метод статической синхронизации процессоров и протокол динамической синхронизации. Метод статической синхронизации включает: семейство из шести базовых протоколов статической синхронизации (Табл. 1-6); графовую модель зависимости базовых протоколов синхронизации (Рис. 2); алгоритм формирования протокола статической синхронизации процессоров, реализующего любую последовательность базовых протоколов и гарантирующего корректное выполнение вычислительного процесса.
Для разработки базовых протоколов синхронизации предложено классифицировать СИ по типу их окончания. К СИ 1-го типа относятся инструкции, окончание которых инициируется всеми процессорами (барьер, взаимное исключение). К СИ 2-го типа - инструкции, окончание которых инициируется любым процессором, если им получен результат СИ, или если действия остальных процессоров уже не могут повлиять на этот результат (уведомление).
Семейство из шести базовых протоколов статической синхронизации
Таблица 1
Базовый протокол #1
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 1-го типа. | 0 | 0 | 1 | ||
| 2 | Начало СИ первого типа. Процессор kZ1, начинающий СИ, устанавливает qk=1, вызывая переключение Q в 1. | 0 | 1 | 1 | 1 | 1 |
| 3 | Все остальные процессоры jZ1 распознают Q=1 и также начинают СИ первого типа. Они устанавливают qj=1. | 0 | 1 | 1 | 2 | |
| 4 | Процессор sZ1, имеющий минимальное время t(s,Z), завершает первую СИ. Он устанавливает rs=0. | 0 | 1 | 1 | 3 | |
| 5 | Остальные процессоры jZ1 завершают СИ 1-го типа: rj=0, вызывая R=0. Исходное состояние для СИ (1-го или 2-го типа). | 0 | 1 | 0 | 4 | 2 |
Таблица 2
Базовый протокол #2
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 2-го типа. | 0 | 0 | 1 | ||
| 2 | Начало СИ второго типа. Процессор kZ1, начинающий СИ, устанавливает qk=1, вызывая переключение Q в 1. | 0 | 1 | 1 | 1 | 1 |
| 3 | Остальные процессоры jZ1 распознают Q=1 и начинают СИ, устанавливая qj=1. | 0 | 1 | 1 | 2 | |
| 4 | Процессор sZ1 определяет, что остальные процессоры не смогут повлиять на результат СИ 2-го типа. Для ее окончания он устанавливает ps=1, вызывая P=1. | 1 | 1 | 1 | 3 | 2 |
| 5 | Остальные процессоры jZ1 распознают окончание СИ второго типа согласно P=1. Они устанавливают pj=1. | 1 | 1 | 1 | 4 | |
| 6 | Все процессоры jZ1 устанавливают rj=0, вызывая R=0. | 1 | 1 | 0 | 5 | 3 |
| 7 | Все процессоры jZ1 в ответ на R=0 устанавливают qj=0, что влечет Q=0. Исходное состояние для СИ (1-го или 2-го типа). | 1 | 0 | 0 | 6 | 4 |
Таблица 3
Базовый протокол #3
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 1-го типа. | 0 | 1 | 0 | ||
| 2 | Начало СИ первого типа. Процессор kZ2, начинающий СИ, устанавливает pk=1, вызывая переключение P в 1. | 1 | 1 | 0 | 1 | 1 |
| 3 | Все остальные процессоры jZ2 распознают P=1 и также начинают СИ. Они устанавливают pj=1. | 1 | 1 | 0 | 2 | |
| 4 | Процессор sZ2, имеющий минимальное время t(s,Z), завершает СИ. Он устанавливает qs=0. | 1 | 1 | 0 | 3 | |
| 5 | Остальные процессоры jZ2 завершают СИ 1-го типа: qj=0, вызывая Q в 0. Исходное состояние для СИ (1-го или 2-го типа). | 1 | 0 | 0 | 4 | 2 |
Таблица 4
Базовый протокол #4
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 2-го типа. | 0 | 1 | 0 | ||
| 2 | Начало СИ второго типа. Процессор kZ3, начинающий СИ, устанавливает pk=1, вызывая переключение P в 1. | 1 | 1 | 0 | 1 | 1 |
| 3 | Все остальные процессоры jZ3 распознают P=1 и начинают СИ второго типа, устанавливая pj=1. | 1 | 1 | 0 | 2 | |
| 4 | Процессор sZ3 определяет, что остальные процессоры не смогут повлиять на результат СИ второго типа. Для ее окончания он устанавливает rs=1, вызывая переключение R в 1. | 1 | 1 | 1 | 3 | 2 |
Продолжение табл.4
| 5 | Остальные процессоры jZ3 распознают окончание СИ второго типа согласно R=1. Они устанавливают rj=1. | 1 | 1 | 1 | 4 | |
| 6 | Все процессоры jZ3 устанавливают qj=0, вызывая Q=0. | 1 | 0 | 1 | 5 | 3 |
| 7 | Все процессоры jZ3 в ответ на Q=0 устанавливают ps=0, что влечет P=0. Исходное состояние для СИ (1-го или 2-го типа). | 0 | 0 | 1 | 6 | 4 |
Таблица 5
Базовый протокол #5
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 1-го типа. | 1 | 0 | 0 | ||
| 2 | Начало СИ первого типа. Процессор kZ3, начинающий СИ, устанавливает rk=1, вызывая переключение R в 1. | 1 | 0 | 1 | 1 | 1 |
| 3 | Все остальные процессоры jZ3 распознают R=1 и также начинают СИ. Они устанавливают rj=1. | 1 | 0 | 1 | 2 | |
| 4 | Процессор sZ3, имеющий минимальное время t(s,Z), завершает СИ. Он устанавливает ps=0. | 1 | 0 | 1 | 3 | |
| 5 | Остальные процессоры jZ3 завершают СИ 1-го типа: pj=0, вызывая P=0. Исходное состояние для СИ (1-го или 2-го типа). | 0 | 0 | 1 | 3 | 2 |
Таблица 6
Базовый протокол #6
| # | Шаги базового протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для СИ 2-го типа. | 1 | 0 | 0 | ||
| 2 | Начало СИ второго типа. Процессор kZ2, начинающий СИ, устанавливает rk=1, вызывая переключение R в 1. | 1 | 0 | 1 | 1 | 1 |
| 3 | Все остальные процессоры jZ2 распознают R=1 и начинают СИ, устанавливая rj=1. | 1 | 0 | 1 | 2 | |
| 4 | Процессор sZ2 определяет, что остальные процессоры не смогут повлиять на результат СИ. Для ее окончания он устанавливает qs=1, вызывая переключение Q в 1. | 1 | 1 | 1 | 3 | 2 |
| 5 | Остальные процессоры jZ2 распознают окончание СИ второго типа согласно Q=1. Они устанавливают qj=1. | 1 | 1 | 1 | 4 | |
| 6 | Все процессоры jZ1 устанавливают pj=0, вызывая P=0. | 0 | 1 | 1 | 5 | 3 |
| 7 | Все процессоры jZ2 в ответ на P=0 устанавливают rk=0, что влечет R=0. Исходное состояние для СИ (1-го или 2-го типа). | 0 | 1 | 0 | 6 | 4 |
Граф на рис. 2 является объединением графов, представленных на рис. 1 и описанных в табл. 1-6. Вершинам приписаны начальные и конечные состояния линий синхронизации P, Q, R, а ориентированным дугам – переходы из начальных состояний в конечные, т.е. базовые протоколы синхронизации. Направленные дуги графа помечаются цифрой, соответствующей номеру базового протокола. Транзитивное замыкание графа является полносвязным, и для каждой пары вершин существует не менее двух путей, связывающих их. Это гарантирует отсутствие тупиков у графа (рис. 2) и обеспечивает функциональную полноту базовых протоколов синхронизации.
На основе графовой модели зависимости исходного состояния сигналов на линиях синхронизации P, Q, R от типа СИ (рис. 1) предложен алгоритм формирования протокола статической синхронизации процессоров.
Рис. 1. Графовая модель зависимости исходного
состояния сигналов на линиях синхронизации P
, Q, R от типа СИРазработан протокол динамической синхронизации процессоров (табл. 7), обеспечивающий корректную синхронизацию в отсутствии адресного обмена данными и априорных знаний о характере вычислительного процесса. В отличие от известных протокол позволяет без увеличения количества линий синхронизации завершать СИ как по окончании всеми процессорами локальных действий, так и по инициативе любого из них, т.е. процессор может как задерживать на требуемое время окончание совместной инструкции, так и форсировать ее окончание.
В четвертой главе предложен алгоритм и программное обеспечение для расчета оптимальных коэффициентов синхронизации. Коэффициенты nj не могут быть определены аналитическим путем из-за большого количества граничных условий типа (4), так как процессорам заведомо неизвестно, кто из них примет участие в СИ арбитража. Суть предложенного алгоритма заключается в следующем.
Формируется множество слов приоритетов Bi(n,N)={Aj, j=1,…,s=0,...,nCsN}, где CsN – число сочетаний из N по s, слова классифицируются по глубине (Aj), Aj Bi(n,N), рассчитываются максимальное max(Bi(n,N)) и среднее значение глубины слов приоритетов 
, где hi - количество слов фиксированной глубины i=0,…,max(Bi(n,N)) в множестве, а BinN - мощность множества.
Таблица 7
Протокол динамической синхронизации процессоров
| # | Шаги протокола синхронизации | P | Q | R | ||
| 1 | Исходное состояние для начала первой СИ. | 1 | 0 | 0 | ||
| 2 | Начало СИ. Процессор kZ, начинающий первую СИ, устанавливает qk=1, вызывая переключение Q в 1. | 1 | 1 | 0 | 1 | 1 |
| 3 | Остальные процессоры jZ распознают Q=1 и также начинают СИ. Они устанавливают qj=1. | 1 | 1 | 0 | 2 | |
| 4 | Некоторые процессоры jZ1 могут заканчивать выполнение индивидуальных частей СИ. Они устанавливают pj=0. | 1 | 1 | 0 | 3 | |
| 5 | Если процессор kZ определяет, что остальные процессоры не смогут повлиять на результат СИ, он, удерживая pk=1, устанавливает rk=1, вызывая R=1. Переход к выполнению шага 7а. | 1 | 1 | 1 | 3 | 2 |
| 6a | Иначе все процессоры sZ заканчивают выполнение индивидуальных частей СИ (первого типа). Они устанавливают pj=0. | 0 | 1 | 0 | 3 | 2 |
| 6а | Для поддержки протокола синхронизации процессоры jZ устанавливают rj=1. | 0 | 1 | 1 | 4 | 3 |
| 6b | Для поддержки протокола синхронизации процессоры jZ устанавливают qj=0. | 0 | 0 | 1 | 5 | 4 |
| 6c | Для поддержки протокола синхронизации процессоры jZ устанавливают pj=0. Переход к выполнению шага 8. | 1 | 0 | 1 | 6 | 5 |
| 7a | Все остальные процессоры jZ распознают окончание СИ (второго типа) согласно P=1. Они устанавливают rj=1. | 1 | 1 | 1 | 4 | |
| 7b | Для поддержки протокола синхронизации процессоры jZ устанавливают pj=1. | 1 | 1 | 1 | 5 | |
| 7c | Для поддержки протокола синхронизации процессоры jZ1 устанавливают qj=0. | 1 | 0 | 1 | 6 | 3 |
| 8 | Для поддержки протокола синхронизации процессоры jZ устанавливают rj=0. Исходное состояние для начала второй СИ. | 1 | 0 | 0 | 7 | 4,6 |
