Метод и аппаратные средства барьерной синхронизации однокристальных матричных мультикомпьютеров на основе виртуально-многослойной конвейерной координирующей среды тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Бредихин, Руслан Владимирович

• Бредихин, Руслан Владимирович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Бредихин, Руслан Владимирович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. АРХИТЕКТУРА И КООРДИНАЦИОННЫЕ ПРОЦЕССЫ ОДНОКРИСТАЛЬНЫХ МАТРИЧНЫХ МУЛЬТИКОМПЬЮТЕРОВ

1.1. Особенности архитектуры однокристальных матричных мультикомпьютеров

1.2. Координационные процессы в мультикомпьютерах. Процедура барьерной синхронизации

1.3. Методы, процедуры и средства барьерной синхронизации 17 Выводы

2. ОРГАНИЗАЦИЯ БАРЬЕРНОЙ СИНХРОНИЗАЦИИ НА ОСНОВЕ ВИРТУАЛЬНО-МНОГОСЛОЙНОЙ КОНВЕЙЕРНОЙ

КООРДИНИРУЮЩЕЙ СРЕДЫ

2.1. Принципы организации виртуально-многослойной координирующей среды

2.2. Концептуальный базис разработанного метода барьерной синхронизации

2.3. Особенности разработанного метода барьерной синхронизации

2.3.1. Определение индикаторных функций и условий синхронизации

2.3.2. Определение топологии физических слоев координирующей среды

2.3.3. Определение логической конфигурации физических слоев координирующей среды

2.3.4. Виртуализация физических слоев координирующей среды

2.3.5. Определение логической конфигурации виртуальной координирующей среды

2.3.6. Организация тактовой синхронизации виртуальной координирующей среды

2.3.7. Инвариантность разработанного метода к конфигурации барьерных групп

Выводы

3. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ РАСПРЕДЕЛЕННОЙ КООРДИНИРУЮЩЕЙ СРЕДЫ С ВИРТУАЛЬНЫМИ КАНАЛАМИ

3.1. Синтез базовой схемы ячейки координирующей среды

3.2. Синтез схемы ячейки координирующей среды с виртуальными каналами

3.3. Синтез схемы ячейки координирующей среды с многоразрядными виртуальными каналами

3.4. Оценка аппаратной сложности ячейки координирующей среды и гибкости разработанных аппаратных средств 93 Выводы

4. ИССЛЕДОВАНИЕ ФУНКЦИОНИРОВАНИЯ РАЗРАБОТАННОЙ ЯЧЕЙКИ В СОСТАВЕ КООРДИНИРУЮЩЕЙ СРЕДЫ МАТРИЧНОГО МУЛЬТИКОМПЬЮТЕРА

4.1. Методика проведения исследований

4.2. Особенности используемого языка имитационного моделирования

4.3. Особенности используемых инструментальных средств имитационного моделирования

4.4. Результаты имитационного моделирования 110 Выводы ИЗ

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЕ 1 - Листинг управляющей подпрограммы, реализуемой обобщенными массовыми контроллерами при моделировании координирующей среды

ПРИЛОЖЕНИЕ 2 - Акты о внедрении результатов диссертации

Введение диссертации (часть автореферата) на тему «Метод и аппаратные средства барьерной синхронизации однокристальных матричных мультикомпьютеров на основе виртуально-многослойной конвейерной координирующей среды»

ВВЕДЕНИЕ

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

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

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

Вопросами организации межпроцессорного взаимодействия в параллельных системах занимались многие отечественные и зарубежные ученые, в частности, A.B. Каляев, И.В. Каляев, В.В. Воеводин, Вл.В. Воеводин, A.B. Корнеев, И.И. Левин, А.П. Типикин, И.В. Зотов, E.D. Brooks, D.K. Panda, J. Wu, M. O'Keefe, W.E. Cohen и др. За последние три десятилетия было разработано широкое многообразие методов, процедур и средств барьерной синхронизации, используемых на различных уровнях параллелизма и ориентированных на параллельные вычислительные системы разных архитектурных классов. Для си-

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

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

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

Объект исследования: аппаратные средства барьерной синхронизации в составе однокристальных матричных мультикомпьютеров (ОММК).

Предмет исследования: методы, процедуры и схемы устройств барьерной синхронизации параллельных процессов в ОММК.

Работа выполнена при поддержке Минобрнауки РФ в рамках гранта Президента РФ МД-2218.2011.8, а также в соответствии с планом НИР ЮЗГУ в 2009-2014 гг.

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

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

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

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

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

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

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

Результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

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

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

Практическая значимость работы:

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

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

Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ЗАО «Открытые технологии 98» (г. Москва), в ООО «НПЦ «Иннотех» (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники ЮЗГУ в рамках дисциплин «Вычислительные системы повышенной надежности», «Отказоустойчивые многопроцессорные платформы», в курсовом и дипломном проектировании.

Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на Международной научно-технической конференции «Распознавание - 2013» (г. Курск, 2013 г.), на I Региональной научно-технической конференции «Информационные системы и технологии» (г. Курск, 2012 г.), а также на научных семинарах кафедры вычислительной техники ЮЗГУ (ранее КурскГТУ) с 2009 по 2014 г.

Публикации по теме диссертации. Результаты диссертационной работы отражены в 10 публикациях, в числе которых 5 статей, опубликованных в научных изданиях из Перечня ВАК РФ, а также 1 свидетельство о регистрации программы для ЭВМ.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах личный вклад соискателя сводится к следующему: в [5,6,12,53] разработаны основные положения и этапы аппаратно-ориентированного метода барьерной синхронизации на основе использования виртуально-многослойной координирующей среды; в [3,4,19] синтезированы функциональные схемы основных блоков, входящих в состав ячейки координирующей среды; в [13,17,40] исследовано функционирование разработанной ячейки виртуально-многослойной координирующей среды в составе матричного мультикомпьютера.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 141 страницу текста (с учетом приложений) и поясняется 30 рисунками и 5 таблицами; список литературы включает 106 наименований.

Области возможного использования. Результаты диссертационной работы могут найти применение при создании перспективных матричных СБИС-мультикомпьютеров, подобных однокристальным системам TILE-Gx, а также при построении крупномасштабных мультикомпьютеров (аналогичных выпускаемых фирмами Cray, IBM, HP), объединяющих тысячи - сотни тысяч идентичных процессорных узлов многомерной матричной коммуникационной средой, и локальных сетей ЭВМ, организованных в матричные структуры.

1. АРХИТЕКТУРА И КООРДИНАЦИОННЫЕ ПРОЦЕССЫ ОДНОКРИСТАЛЬНЫХ МАТРИЧНЫХ МУЛЬТИКОМПЬЮТЕРОВ

В данном разделе излагаются особенности архитектуры однокристальных матричных мультикомпьютеров (ОММК) на примере ряда современных СБИС-систем, рассматриваются координационные процессы, протекающие в ОММК, и в частности, барьерная синхронизация - одна из стандартных и наиболее распространенных форм коллективного координационного межпроцессорного взаимодействия в мультикомпьютерах, формулируется задача обеспечения барьерной синхронизации в ОММК, дается аналитический обзор методов, процедур и средств барьерной синхронизации с акцентом на распределенные аппаратные решения, обсуждаются их ограничения и формулируется цель диссертационного исследования. Основное содержание раздела опубликовано в работе [13].

1.1. Особенности архитектуры однокристальных матричных мультикомпьютеров

Современная технология производства сверхбольших интегральных схем (СБИС) позволяет выпускать микросхемы сверхвысокой степени интеграции, превышающей 2 млрд. транзисторов на кристалл, имеющие время переключения вентиля порядка 5 пс [105]. Наличие элементной базы подобного уровня дает возможность создания однокристальных мультикомпьютеров, объединяющих десятки мощных процессорных модулей, устройств ввода-вывода, контроллеров памяти [51, 52].

Спектр выпускаемых промышленностью СБИС-систем весьма широк и охватывает как довольно простые по современным меркам образцы (например, двухъядерные-четырехъядерные процессоры Intel [21] и AMD [37]), так и весьма сложные приборы, включающие до 100 процессорных модулей (муль-тикомпьютеры фирмы Tilera [96]). Сегодня многопроцессорные системы на кристалле представлены многими известными производителями. Кроме Intel, AMD, Tilera, к их числу относятся Oracle (8-ядерный процессор OpenSPARC Т1

[85]), Azul Systems (процессор Vega 3, содержащий 54 ядра [100]), IntellaSys (процессор SEAforth 40C18 с 40 ядрами [68]). Компания Intel также заявила о стремлении в недалекой перспективе наладить производство процессоров с большим числом ядер; на данный момент ею выпущен экспериментальный прототип 80-ядерного мультипроцессора Polaris [67] (однако следует отметить, что ядра этого процессора более простые, чем те, что используются в распространенных сегодня 2- и 4-ядерных процессорах).

Однокристальные системы, содержащие небольшое число процессоров (как правило, до 8), используют шинную топологическую структуру, которая обеспечивает достаточную пропускную способность [85]. В свою очередь, системы с большим числом процессоров строятся на основе двумерной матричной топологии и её модификаций (матрица колец, тор и т.п.) [97]. Межпроцессорные обмены данными в таких системах осуществляются через неблокирующие переключатели или сети с непосредственными связями и пакетной коммутацией, транслирующие данные в параллельном коде в формате многоразрядных слов. Двумерная матричная топология упрощает размещение процессорных модулей на кристалле, позволяя при этом эффективно отводить тепло. Однако, матрицы большей размерности (обладающие большей топологической плотностью) пока не получили распространения при производстве СБИС-систем ввиду технологических проблем отведения тепла от кристалла [93].

Типичными представителями однокристальных матричных мультиком-пьютеров являются СБИС-системы TILE фирмы Tilera [98]. Линейка СБИС-мультикомпьютеров TILE, выпускаемых в настоящее время, включает 72-ядерные системы TILE-Gx8072 (в конфигурации 9x8), 64-ядерные системы TILE64 и TILEPro64 (в конфигурации 8x8), 36-ядерные системы TILEPro36, TILE-Gx8036 (в конфигурации 6x6), 16-ядерные системы TILE-Gx8016 (в конфигурации 4x4), 9-ядерные системы TILE-Gx8009 (в конфигурации 3x3).

Структурная организация СБИС-системы TILE-Gx8036 представлена на рис. 1.1 [95].

Рис. 1.1. Структурная организация СБИС Т1ЬЕ-Сх8036

СБИС-система Т1ЬЕ-Сх8036 содержит 36 процессорных модулей (ПМ), взаимодействующих через матричную коммутационную среду ¡МеэЬ с конфигурацией 6 х 6 и функционирующих на частотах от 1 до 1.2 ГГц. Каждый ПМ включает 64-разрядный 3-конвейерный процессорный элемент (ПЭ), кэшпамять двух уровней (объемом соответственно 32 и 256 кбайт), а также неблокирующий переключатель для подключения к среде ¡МезИ. Каждый ПМ может независимо работать под управлением автономной ОС или функционировать во взаимосвязи с другими модулями под управлением мультипроцессорной ОС

SMP Linux. СБИС-матрица в целом дополнительно содержит кэш третьего уровня объемом 9 Мбайт.

Особый интерес представляет коммуникационная среда iMesh, объединяющая процессорные модули мультикомпьютера TILE-Gx8036. Она представляет собой суперпозицию из пяти независимо функционирующих высокоскоростных матричных сетей, имеющих суммарную пропускную способность 60 Тбит/сек. Передача данных в среде iMesh осуществляется параллельным кодом на базе метода cuthrough-маршрутизации, что позволяет снизить длительность каждого шага передачи до 1 такта.

Система TILE-Gx8036 объединяет широкий спектр контроллеров памяти и интерфейсов ввода-вывода. В их числе имеется два 72-разрядных контроллера синхронной динамической памяти DDR3, позволяющих подключать до 512 Гбайт оперативной памяти, 3 контроллера PCI Express (PCIE), 4 порта 12С, порт SPI, до 16 портов SGMII, 10 Gigabit Ethernet (XAUI), отладочный интерфейс периферийного сканирования JTAG. Также СБИС содержит встроенную аппаратуру шифрования и сжатия данных MiCA. Особенностью системы TILE-Gx8036 является поддержка технологии динамического распределенного кэша (Dynamic Distributed Cache - DDC), обеспечивающую когерентность кэшпамяти по всей матрице процессоров на аппаратном уровне. DDC позволяет использовать СБИС для реализации многопоточных приложений с разделяемой памятью, что превращает TILE-Gx8036 в мощный ccNUMA-мультипроцессор. Потребляемая мощность приборов TILE-Gx8036 составляет от 20 до 28 Вт.

Аналогичными по архитектуре являются и другие системы фирмы Tilera, в частности, СБИС Tile-Gx8016 и Tile-Gx8009.

1.2. Координационные процессы в мультикомпьютерах. Процедура барьерной синхронизации

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

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

Существует несколько видов межпроцессорного взаимодействия, относящихся к разным уровням архитектуры системы. В системах класса MIMD межпроцессорное взаимодействие преимущественно протекает на уровне процессов и/или потоков. Для обеспечения межпроцессорного обмена данными в ходе взаимодействия применяются как разделяемые коммуникационные среды (SGI Origin 3000, Sun Ultra Enterprise 10000), так и сети с непосредственными связями (Cray ХТ-5, IBM Blue Gene, TILE-Gx).

К числу важнейших коммуникационных процедур, выполняемых в ходе межпроцессорного взаимодействия в MIMD-системах, относится барьерная синхронизация. В её основе лежит понятие барьера [49]. Барьер можно рассматривать как логический разделитель в потоке управления параллельной программы, по достижении которого все (или некоторые) процессы (потоки) приостанавливают выполнение до тех пор, пока остальные процессы также не достигнут этого разделителя, с тем чтобы продолжить дальнейшее выполнение синхронно. Барьеры обычно используются с целью задания определенного порядка следования участков программного кода (ветвей параллельной программы) и не предусматривают передачи каких-либо данных для вычислений в процессорах. Различают глобальную и локальную барьерную синхронизацию. В первом случае в синхронизации участвуют все процессы параллельного приложения, выполняющиеся в системе в данный момент времени. Во втором случае участниками синхронизации является только часть процессов, образующих так называемую барьерную группу.

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

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

Барьерная синхронизация является не только одним из часто встречающихся видов межпроцессорного взаимодействия, но и считается базовой стандартной коммуникационной операцией параллельных программ, разрабатываемых в соответствии с современными стандартами параллельного программирования. Так, стандарт программирования мультикомпьютеров MPI содержит процедуру MPI_Barrier, которая обеспечивает синхронизацию группы параллельных процессов, объединённых так называемым коммуникатором (барьерной группы) [79]. Аналогичная процедура имеется и в другом широко распространенном стандарте ОрепМР, являющемся основой программирования мультипроцессоров (в ОрепМР синтаксически она оформляется в виде директивы и применяется к группе синхронизируемых потоков) [84].

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

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

CBS -> max; EBS < EBS; TBS < TBS, (1.1)

где Свз - гибкость метода (средств) синхронизации; Евз - структурная сложность средств синхронизации (Еш - предельно допустимое значение); Тв5 -среднее время синхронизации {ТВБ - предельно допустимое значение).

Важнейшей количественной характеристикой средств синхронизации является время Твз, определяемое как средний интервал между моментом достижения барьера последним синхронизируемым процессом и моментом запуска последнего процесса из барьерной группы. Гибкость Св8 представляет собой отношение числа допустимых вариантов размещения синхронизируемых процессов среди модулей мультикомпьютера к общему числу таких вариантов. Её максимальное значение - единица. Структурная сложность Евз определяет сложность физической реализации средств синхронизации и может включать объем программного кода, аппаратную сложность и т.п.

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

1.3. Методы, процедуры и средства барьерной синхронизации

За последние три десятилетия было разработано широкое многообразие методов, способов и средств барьерной синхронизации, используемых на различных уровнях параллелизма и ориентированных на параллельные вычислительные системы разных архитектурных классов. В зависимости от уровня реализации существующие решения можно разделить на три класса [15]: программные [22, 34, 35, 36, 54, 63, 64, 72, 75, 76, 80, 99, 103, 104], гибридные (программно-аппаратные) [23, 24, 30, 31, 32, 46, 50, 62, 65, 74, 77, 86, 88, 90, 92, 94, 102] и аппаратные [1, 8, 9, 10, 16, 25, 26, 27, 28, 29, 30, 33, 44, 45, 47, 48, 55, 56, 58, 59, 60, 61, 66, 69, 70, 71, 73, 78, 82, 83, 87, 89, 91, 101, 106]. Программные решения полностью базируются на использовании стандартного коммуникационного оборудования и протоколов и обычно представляются в виде набора специализированных системных утилит. Будучи весьма гибкими, масштабируемыми и простыми, программно реализованные процедуры барьерной синхронизации, как правило, на 1-3 порядка медленнее аппаратно реализованных процедур и поэтому не нашли применения в мультикомпьютерах. В связи с этим в дальнейшем мы исключаем из рассмотрения методы синхронизации, предполагающие чисто программное воплощение.

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

Список литературы диссертационного исследования кандидат наук Бредихин, Руслан Владимирович, 2014 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Аль-Хади, A.M. Распределенная процедура барьерной синхронизации с динамическим ограничением области распространения координирующих сигналов [Текст] / A.M. Аль-Хади, С. А. Муратов, И.В. Зотов // Телекоммуникации. 2011. №5. С. 2-7.

2. Баранов, С.И. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем [Текст] / С.И. Баранов, Л.И. Журавина, В.А. Песчанский // Автоматика и вычислительная техника. 1984. №5. С. 74-81.

3. Бредихин, Р.В. Об организации встроенного аппаратного взаимоконтроля в логических мультиконтроллерах [Текст] / Бредихин Р.В., Ньян Лин, Зотов И.В. // Изв. Йузов. Приборостроение. 2013. Т.56, №6. С. 44-49.

4. Бредихин, Р.В. Организация барьерной синхронизации в матричных мультикомпьютерах на основе виртуально-многослойной конвейерной координирующей среды [Текст] / Бредихин Р.В., Зотов И.В., Сухочев Ю.О. // Материалы Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации», Курск, 18-20 мая 2013 г.Курск: ЮЗГУ, 2013. С.

5. Бредихин, Р.В. Распределенная координирующая среда матричного мультиконтроллера с многослойными виртуальными каналами [Текст] / Бредихин Р.В., Леонов М.Е., Зотов И.В. // Материалы докладов I Региональной научно-технической конференции «Информационные системы и технологии», 16-19 октября 2012 г., Курск: ЮЗГУ. С. 197-199.

6. Бредихин, Р.В. Распределенная процедура циклической барьерной синхронизации для однокристальных матричных мультикомпьютеров [Текст] / Бредихин Р.В., Зотов И.В. // Известия ЮЗГУ. Серия Управление, вычислительная техника, информатика. Медицинское приборостроение. №2, часть 1, 2012. С. 48-54.

7. Воеводин, B.B. Параллельные вычисления [Текст] / В.В. Воеводин, Вл.В. Воеводин. СПБ.: БХВ-Петербург, 2002. 608 с.

8. Волобуев, C.B. Организация барьерной синхронизации в стандарте MPI с использованием распределенного многослойного параллельно-конвейерного синхронизатора [Текст] / Волобуев C.B., Зотов И.В. // Известия ЮЗГУ. Серия Управление, вычислительная техника, информатика. Медицинское приборостроение. 2011, №1. С. 41-44.

9. Волобуев, C.B. Процедура распределенной параллельно-конвейерной барьерной синхронизации, инвариантная к способу размещения синхронизируемых процессов [Текст] / Волобуев C.B., Зотов И.В. // Известия вузов. Приборостроение. 2010. Т.53, №10. С. 29-34.

Ю.Волобуев, C.B. Распределенный механизм барьерной синхронизации на основе параллельно-конвейерной координирующей среды [Текст] / C.B. Волобуев, И.В. Зотов // Информационно-измерительные и управляющие системы. 2010. №7. С. 35-39. .

П.Емельянов, С.Г. Архитектура параллельных логических мультиконтроллеров [Текст] / Емельянов С.Г., Зотов И.В., Титов B.C. // М.: Высшая школа, 2009. 233 с.

12.Зотов, И.В. Аппаратная реализация барьерной синхронизации в матричных мультикомпьютерах [Текст] / Зотов И.В., Бурмака A.A., Бредихин Р.В., Сухочев Ю.О. // Информационно-измерительные и управляющие системы. 2013. №8. С. 41-45.

13.Зотов, И.В. Аппаратно-ориентированные методы управления межпроцессорной координацией в параллельных системах с распределенной памятью [Текст] / Зотов И.В., Бобынцев Д.О., Бредихин Р.В., Ньян Лин // Известия ЮЗГУ. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». 2013. №1. С. 43-48.

14.Зотов, И.В. Визуальная среда для имитационного моделирования коммутаторов и коммуникационных сетей [Текст] / Зотов И.В. // Перспективы развития систем управления оружием: сборник докладов IV научно-

практической конференции, Курск, 19-20 сентября 2007 г. М.: Изд-во «Бедретдинов и Ко», 2007. С. 71-82.

15.Зотов, И.В. Методы распределенной барьерной синхронизации параллельных процессов в матричных СБИС-системах [Текст] / И.В. Зотов, C.B. Волобуев, A.M. Аль-Хади // Нейрокомпьютеры: разработка, применение. 2009. №12. С. 46-52.

16.3отов, И.В. Модель синхронизации параллельных управляющих процессов в микроконтроллерных сетях с матричной организацией [Текст] / И.В.Зотов // Автоматика и вычислительная техника. 2001. №3. С. 44-55.

17.3отов, И.В. Принципы организации встроенного аппаратного межмодульного взаимоконтроля в матричных логических мультиконтроллерах [Текст] / Зотов И.В., Бредихин Р.В., Лисицин Л.А., Ньян Лин // Известия ЮЗГУ. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». 2013. №1. С. 202-208.

18.Зотов, И.В. Теоретические основы синтеза схем быстродействующих устройств распределенной децентрализованной координации параллельных микропрограмм в мультиконтроллерах: дис. ...д-ра техн. наук: 05.13.05: защищена 07.12.06: утв. 15.03.07 / Зотов Игорь Валерьевич. Курск, 2007. 383 с.

19.Макаров, Д.И. Модель ячейки координирующей среды мультиконтроллера с интегрированными средствами аппаратного контроля модулей [Текст] / Макаров Д.И., Бредихин Р.В., Зотов И.В. // Материалы докладов I Региональной научно-технической конференции «Информационные системы и технологии», 16-19 октября 2012 г., Курск: ЮЗГУ. С. 56-59.

20.Наджаджра, М.Х. Использование аппарата Q-схем для моделирования алгоритмов маршрутизации [Текст] / М.Х. Наджаджра, Дж.Н. Абдель-Джалил, И.В. Зотов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы 7-й Международной научно-технической конференции, Курск, 4-7 октября 2005 г. - Курск: КурскГТУ, 2005. - С. 179-181.

21.Обзор продукции. Процессор Intel Хеоп серии 7500 [Электронный ресурс] // Корпорация Intel, 2010. URL: http://cache-www.intel.com/cd/00/00/45/27/452706_452706.pdf (дата обращения: 09.09.2013).

22.Патент №2005/0050374 А1 США, МКИ 8 G06F 12/00. Method for synchronizing processors in a multiprocessors system / T. Nakamura, N. Sukegawa (Япония). -№10/894064; заявлено 20.07.2004; опубл. 03.03.2005. 14 с.

23.Патент №2010/0095090 А1 США, МКИ 10 G06F 15/76, 9/02, 12/08. Barrier synchronization method, device and multi-core processor. / H. Unno, M. Ukai, M. Depetro (США). - №12/638746; заявлено 15.12.2009; опубл. 15.04.2010. 18 с.

24.Патент №2010/0124241 А1 США, МКИ 10 H04G 3/06. Barrier synchronization apparatus, barrier synchronization system and barrier synchronization method / S. Hiramoto, Y. Ajima, T. Inoue (Япония). - №12/582119; заявлено 20.10.2009; опубл. 20.05.2010. 39 с.

25.Патент №2116665 РФ, МКИ 6 G06F9/22. Модуль мультимикропро-граммной системы / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97102631/09; заявлено 18.02.97; опубл. 27.07.98, Бюл. №21. 21 с.

26.Патент №2152071 РФ, МКИ 7 G06F9/22, 9/28. Модуль системы микропрограммного управления / И.В.Зотов (РФ). - №99109080/09; заявлено 5.05.99; опубл. 27.06.2000, Бюл. №18. 20 с.

27.Патент №2168198 РФ, МКИ 7 G05B19/05, G06F9/28. Микроконтроллерная сеть / И.В.Зотов (РФ). - №99119676/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15. 21 с.

28.Патент №2280887 РФ, МКИ 8 G05B19/18, G06F9/28. Микроконтроллерная сеть / А.А. Иванов, Дж.Н. Абдель-Джалил, И.В. Зотов, С.В. Виноградов (РФ). - №2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21. 26 с.

29.Патент РФ №2450328, кл. G06F9/00. Логический мультиконтроллер с распределенным параллельно-конвейерным барьерным синхронизатором / А.М.А. Аль-Хади, С.В. Волобуев, И.В. Зотов, С.А. Муратов (РФ) / заявл. 15.12.2010; опубл. 10.05.2012.

30.Патент №5434995 США, МКИ 6 G06F15/16, 15/80. Barrier synchronization for distributed memory massively parallel processing systems / S.M.Oberlin, E.C.Fromm (США). -№165265; заявлено 10.12.93; опубл. 18.07.95. 25 с.

31.Патент №5721921 США, МКИ 6 G06F13/38, 15/16. Barrier and eureka synchronization architecture for multiprocessors / R.E. Kessler, S.M. Oberlin, G.M. Thorson (США). -№450251; заявлено 25.05.95; опубл. 24.02.98. 37 с.

32.Патент №6085303 США, МКИ 7 G06F15/16. Serialized race-free virtual barrier network / G.Thorson, R.S.Passint, S.L.Scott (США). - №972010; заявлено 17.11.97; опубл. 04.07.2000. 22 с.

33.Патент №6216174 В1 США, МКИ 7 G06F15/80. System and method for fast barrier synchronization / S.L. Scott, R.E. Kessler (США). - №09/162673; заявлено 29.09.98; опубл. 10.04.2001. 10 с.

34.Патент №6996812 В2 США, МКИ 8 G06F9/45. Software implementation of synchronous memory barrier / P.E. McKenney (США). - №09/884597; заявлено 18.06.2001; опубл. 7.02.2006. 11 с.

35.Патент №7512951 В1 США, МКИ 9 G06F9/46. Barrier synchronization object for multi-threaded application / R. Marejca (США). - №10/641172; заявлено 14.08.03; опубл. 31.03.09. 13 с.

36.Патент №7770170 В2 США, МКИ 10 G06F 9/45, 9/46, 17/30, 13/00. Blocking local sense synchronization barrier / J. Rector, J.D. Morrison, N.M. Clift и др. (США).-№11/180338; заявлено 12.07.2005; опубл. 03.08.2010. 16 с.

37.Процессоры AMD [Электронный ресурс] // Advanced Micro Devices, Inc. URL: http://www.amd.com/ru/products/Pages/processors.aspx (дата обращения: 09.09.2013).

38.Свидетельство о регистрации программы для ЭВМ №2006610308. Библиотека классов для имитационного моделирования коммуникационных сетей / Э.И.Ватутин, И.В.Зотов (РФ). - М.: РосПатент; заявлено 22.10.2005; дата регистрации 16.01.2006.

39.Свидетельство о регистрации программы для ЭВМ №2007611310. Визуальная среда имитационного моделирования VisualQChart / И.В. Зотов [и др.]. Заявл. 13.02.07; дата регистрации 27.03.07.

40.Свидетельство об официальной регистрации программы для ЭВМ №2011612774 / Бредихин Р.В. и др. заявл. 14.02.2011; per. 06.04.2011.

41.Советов, Б.Я. Моделирование систем: учеб. Пособие [Текст] / Б.Я. Советов, С.А. Яковлев. М.: Высшая школа, 2005. 343 с.

42.Сусин, П.В. Коммутатор с распределенными выходными очередями для параллельных систем логического управления: дис...канд. техн. наук: 05.13.05: защищена 20.06.2003: утв. 14.11.2003 / Сусин Павел Викторович. -Курск, 2003.-220 с.

43.Угрюмов, Е.П. Цифровая схемотехника [Текст] / Е.П. Угрюмов. СПб.: БХВ-Петербург, 2004. 800 с.

44.Abellan, J.L. Efficient and scalable barrier synchronization for many-core CMPs [Текст] / J.L. Abellan, J. Fernandez, M.E. Acacio // Proceedings of the 7th ACM international conference on Computing frontiers, Bertinoro, Italy, 2010. pp. 7374.

45.Abellan, J.L. Efficient Hardware Barrier Synchronization in Many-Core CMPs [Текст] / J.L. Abellan, J. Fernandez, M.E. Acacio // IEEE Transactions on Parallel and Distributed Systems, 2012. vol. 23, no. 8, pp. 1453-1466.

46.Amin, P. Bridging Interference Barriers in Self-Organized Synchronization [Текст] / P. Amin, V.P.K. Ganesan, O. Tirkkonen // Proc. IEEE Sixth International Conference on Self-Adaptive and Self-Organizing Systems, 2012. pp. 109-118.

47.Anderson, J. R. Simulation and Analysis of Barrier Synchronization Methods [Текст] / J. R. Anderson // Technical Report No: HPPC-95-04, University of Minnesota, 1995. 42 p.

48.Ashraf, A.-K. Distributed barrier synchronization procedure with the dynamic limitation of the coordinating signal propagation area [Текст] / Ashraf A.K., Zotov I.V., Hazem A.M., Skopin D.E. // International Review on Computers and Software (I.RE.CO.S.), Vol.7, No 3, May 2012. pp. 991-995.

49.Axelrod, T.S. Effects of Synchronization Barriers on Multiprocessor Performance [Текст] // Parallel Computing, 1986. no. 3, pp. 129-140.

50.Bai, S. Barrier synchronization for CELL multi-processor architecture [Текст] / S. Bai, Q. Zhou, R. Zhou, L. Li // Proc. 1st IEEE Int'l Conf. Ubi-Media Computing, 2008. pp. 155-158.

51.Benini, L. Networks on chips: a paradigm [Текст] / L. Benini, G. De Micheli // IEEE Transactions on Computers, 2002. Vol. 35, no. 1. pp. 70-78.

52.Bjerregaard, T. A survey of research and practices of network-on-chip [Текст] / Т. Bjerregaard, S. Mahadevan // ACM Computing Surveys, 2006. Vol. 38, no 1. pp. 1-51.

53.Bredikhin, R.V. A distributed parallel pipelined hardware-level barrier synchronization method for mesh-connected multicomputers / Igor V. Zotov, Ruslan V. Bredikhin, Evgeni A. Titenko // International Review on Computers and Software (I.RE.CO.S.), Vol.8, No 9, September 2013. PP. 2254-2261.

54.Brooks, E.D. The Butterfly Barrier [Текст] / E.D. Brooks // International Journal of Parallel Programming. 1986. vol.15, no. 4. pp. 295-307.

55.Chen, X. DSBS: Distributed and Scalable Barrier Synchronization in Many-Core Network-on-Chips [Текст] / X. Chen, Sh. Chen // IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, 2011. pp.1030-1037.

56.Cohen, W.E. An optical bus-based distributed dynamic barrier mechanism [Текст] / W.E. Cohen, D.W. Hyde, R.K. Gaede // IEEE Trans. Comput., 2000. vol. 49, no. 12, pp. 1354-1365.

5 7. Connection machine CM-5 technical summary / Thinking Machines Corp. 1992. Nov.

58.Delgado, M., A distributed barrier synchronization solution in hardware for 2D-mesh multicomputers [Текст] / M. Delgado, S. Kofuji // Proc. 3rd Intl Conf. High Performance Computing, Dec. 19-22 1996. IEEE: 1996. pp. 368-373.

59.Dietz, H.G. A fine-grain parallel architecture based on barrier synchronization [Текст] / H. G. Dietz, R. Hoare, T. Mattox // Intl. Conf. Parallel Processing, 1996. vol. 1. pp. 247-250.

60.Dietz, H.G. PAPERS: Purdue's adapter for parallel execution and rapid synchronization [Текст] / H. G. Dietz, T. Muhammad [et al.] // Technical Report TREE 94-11, March 1994 / School of Electrical Engineering. Purdue University, 1994.

61.Feldmann, A. Subset barrier synchronization on a private-memory parallel system [Текст] / A. Feldmann, T. Gross, D. O'Hallaron и др. // Proc. ACM Symp. Parallel Algor. Architect. (SPAA92), San Diego, 29 June - 1 July 1992. ACM, 1992. pp. 209-218.

62.Forsell, M. Efficient barrier synchronization mechanism for emulated shared memory NOCs [Текст] / M. Forsell // Proc. Int'l Symp. System-on-Chip, 2004. pp. 33-36.

63.Goodman, J.R. Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors [Текст] / J.R. Goodman, M.K. Vernon, P.J. Woest // ACM SIGARCH Computer Architecture News. 1989. vol. 17, no.2. pp. 64-75.

64.Hengsen, D. Two Algorithms for Barrier Synchronization [Текст] / D. Hengsen, R. Finkel, U. Manber // International Journal of Parallel Programming. 1988. vol.17, no. l.pp. 1-17.

65.Hindam, T. Connecting the distributed hardware agents for barrier synchronization operation [Текст] / Т. Hindam // Proc. Int'l Conf. Electrical, Electronic and Computer Engineering, 2004. pp. 261-264.

66.Ноаге, R. Bitwise aggregate networks [Текст] / R. Hoare, H. Dietz [et al.] // 8th IEEE Symp. Parallel Distrib. Processing, Oct. 23-26 1996. IEEE: 1996, P. 306313.

67.1ntel 80-Core Teraflop Research Chip [Электронный ресурс] http://www.youtube.com/watch?v=TAKGOUvtzpE (дата обращения: 09.09.2013).

68.IntellaSys SEAforth 40C18 [Электронный ресурс] // URL: http://www.intellasys.net/index.php ? option=com_content&task=view&id=60& Itemid=75 (дата обращения: 09.09.2013).

69Johnson, D. Low-cost, high-performance barrier synchronization on networks of workstation [Текст] / D. Johnson, D. Lilja, J. Reidl и др. // Journal of Parallel and Distributed Computing. 1997. vol. 40. pp. 131-137.

70. Johnson, D. A distributed hardware mechanism for process synchronization on shared-bus multiprocessors [Текст] / D. Johnson, D. Lilja, J. Riedl // Proc. Intl Conf. Parallel Processing (ICPP-94), August 15-19, 1994. / North Carolina State University. NC, CRC Press: 1994. Vol.2 (Software), pp.268-275.

71.Johnson, T.A. Cyclical cascade chains: a dynamic barrier synchronization mechanism for multiprocessor systems [Текст] / T.A.Johnson, R.R.Hoare // Proc. IEEE Workshop Mass. Paral. Processing, Intl Paral. Distrib. Processing Symp. (IPDPS-01), San Francisco, 23-27 April 2001. - Los Alamitos: IEEE Computer Society, 2001. pp. 2061-2068.

72.Jung, I. Two-phase barrier: a synchronization primitive for improving the processor utilization [Текст] / I. Jung, J. Hyun, J. Lee, J. Ma // Int J. Parallel Progr. 2001, vol. 29, no. 6. pp. 607-627.

73.Kessler, R.E. Cray T3D: A new dimension for Cray Research [Текст] / R. E. Kessler, J. L. Schwarzmeier // Proc. 38th IEEE Int. Computer Conf., 1993. pp. 176-182.

74.Kini, S.P. Fast and scalable barrier using RDMA and multicast mechanisms for Infiniband-based clusters [Текст] / S.P. Kini, J. Liu, J. Wu, P. Wyckoff, D.K. Panda // Proc. 10th European PVM/MPI Users' Group Conf., 2003. pp. 369-378.

75.Marr, S. Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-Grained Parallelism [Текст] / S.Marr, S.Verhaegen, B. De Fraine, Th. D'Hondt, W. De Meuter // Proc. IEEE 12th International Conference on High Performance Computing and Communications, 2010. pp.130-137.

76.Mee, W.J. Synchronization techniques for distributed systems: an overview / W.J. Mee, G.S. Hura//Microelectron. Reliab. 1992. vol.32, no. 1/2. pp. 175-197.

77.Moh, S. Four-ary tree-based barrier synchronization for 2D meshes without nonmember involvement [Текст ] / S.Moh, C.Yu, B.Lee и др. // IEEE Trans. Com-put. 2001. vol.50, no. 8. pp. 811-823.

78.Monchiero, M. Efficient synchronization for embedded on-chip multiprocessors / M. Monchiero, G. Palermo, C. Silvano, O. Villa // IEEE Transactions on very large scale integration (VLSI) systems. October 2006. vol. 14, №10. pp. 1049-1062.

79.MPI: A Message-Passing Interface Standard, Version 3.0 [Электронный ресурс] / Message Passing Interface Forum, September 2012, URL: http://www.mpi-forum.org/docs/mpi-3.0/mpi30-report.pdf (дата обращения: 09.09.2013).

80.Nikolopoulos, D.S. Quantitative Architectural Evaluation of Synchronization Algorithms and Disciplines on ccNUMA Systems: The Case of the SGI 0rigin2000 [Текст] / D.S. Nikolopoulos, T.S. Papatheodorou // 13th International conference on Supercomputing, 20-25 June 1999. pp. 319-328.

81.0'Boyle, M. Compile time barrier synchronization minimization [Текст] / M.O'Boyle, E.Stohr // IEEE Trans. Parallel Distrib. Systems. 2002. vol.13, no. 6. pp. 529-543.

82.0'Keefe, M. Hardware barrier synchronization: Dynamic barrier MIMD (DBM) [Текст] /М. O'Keefe, H. Dietz // ICPP Proceedings, 1990. vol. 1. pp. 43-46.

83.0'Keefe, M. Hardware barrier synchronization: Static barrier MIMD (SBM) [Текст] / M. O'Keefe, H. Dietz // ICPP Proceedings, 1990. vol. 1. pp. 35-42.

84.0penMP Application Program Interface, Version 4.0 [Электронный ресурс] / OpenMP Architecture Review Board July 2013, URL: http://www.openmp.0rg/mp-documents/OpenMP4.O.O.pdf (дата обращения: 09.09.2013).

85.0penSPARC T1 Overview [Электронный ресурс] // Oracle Technology Network, 2013. URL: http://www.oracle.com/technetwork/systems/opensparc/ opensparc-tl-page-1444609.html (дата обращения: 09.09.2013).

86.Panda, D.K. Fast Barrier Synchronization in Wormhole k-ary n-cube Networks [Текст] / D.K. Panda // Proc. First IEEE Symp. High-Performance Computer Architecture, 1995. pp. 200-209.

87.Ramakrishnan, V. Efficient techniques for nested and disjoint barrier synchronization [Текст] / V. Ramakrishnan, I.D. Scherson, R. Subramanian // J. Paral. Distrib. Comput., 1999. vol. 58, no. 8, pp. 333-356.

88. Sampson, J. Exploiting fine-grained data parallelism with chip multiprocessors and fast barriers [Текст] / J. Sampson, R. González, J.-F. Collard, N.P. Jouppi, M. Schlansker, B. Calder // Proc. 39th Annual IEEE/ACM Int'l. Symp. Microarchitecture, 2006. pp. 235-246.

89.Sampson, J. Fast synchronization for chip multiprocessors [Текст] / J.Sampson, R.González, J.-F.Collard и др. // SIGARCH Computer Architecture News. 2005. vol.33, no. 4. pp. 64-69.

90.Sartori, J. Low-overhead, high-speed multi-core barrier synchronization [Текст] / J. Sartori, R. Kumar // High Performance Embedded Architectures and Compilers, Lecture Notes in Computer Science, 2010. vol. №5952. pp. 18-34.

91.Shang, S.S. Distributed hardwired barrier synchronization for scalable multiprocessor clusters [Текст] /S.S. Shang, K. Hwang // IEEE Transactions on Parallel and Distributed Systems. 1995. Vol.6, no.6. pp. 591-605.

92.Sivaram, R. A reliable hardware barrier synchronization scheme [Текст] / R.Sivaram, C.B.Stunkel, D.K.Panda// Proc. 11 Intl Parallel Processing Symp. (IPPS-97), Geneva, 1-5 April 1997. - Los Alamitos: IEEE Computer Society, 1997. pp. 274-280.

93.Sun, C. Three-dimensional multiprocessor system-on-chip thermal optimization [Текст] / С. Sun, L. Chang, R.P. Dick // 5th IEEE/ACM international conference on hardware/software codesign and system synthesis. 30 September -3 October, 2007. pp. 117-122.

94.Sun, Y. Barrier synchronization on wormhole-routed networks [Текст] / Y. Sun, P.Y.S. Cheung, X. Lin // IEEE Trans. Parallel Distrib. Systems., 2001. vol. 12, no. 6, pp. 583-597.

95.TILE-Gx8036™ Overview [Электронный ресурс] // Tilera Corporation, 2012. URL: http://www.tilera.com/sites/default/files/productbriefs/TILE-Gx8036_PB033-02_web.pdf (дата обращения: 09.09.2013).

96.TILE-Gx8072™ Overview [Электронный ресурс] // Tilera Corporation, 2013. URL: http://www.tilera.com/sites/default/files/productbriefs/TILE-Gx8072_PB041-02.pdf (дата обращения: 09.09.2013).

97.TILEPro64™ Overview [Электронный ресурс] // Tilera Corporation, 2011. URL: http://www.tilera.com/sites/default/files/productbriefs/ TILEPro64_Processor_PB019_v4.pdf (дата обращения: 09.09.2013).

98.Tilera products [Электронный ресурс] // Tilera Corporation, 2013. URL: http://www.tilera.com/products/processors (дата обращения: 09.09.2013).

99.Tzeng, N.-F. Distributed Shared Memory Systems with Improved Barrier Synchronization and Data Transfer [Текст] / N.-F. Tzeng, A. Kongmunvattana // Proceedings of the 11th International conference on Supercomputing, Vienna, Austria, 1997. pp. 148-155.

100. Vega 3 Processor [Электронный ресурс] // Azul Systems, 2010. URL: http://www.azulsystems.com/products/vega/processor (дата обращения: 09.09.2013).

101. Volobuev, S.V. A distributed parallel pipelined barrier synchronizer for N-dimensional mesh-connected multiprocessor systems. [Текст] / Volobuev S.V., Zotov I.V., Al-Hadi A.M. // Proc. 7th Intl Conf. on Information and Telecommunication Technologies in Intelligent Systems, Lugano, Schweiz, July 0309 2010. pp. 89-94.

102. Yang, J.S. Designing tree-based barrier synchronization on 2D mesh networks [Текст] /J.S. Yang, C.T. King // IEEE Trans. Parallel Distrib. Systems, 1998. vol. 9, no. 6, pp. 526-533.

103. Yew, P.C. Distributing Hot Spot Addressing in Large Scale Multiprocessors [Текст] / P.C. Yew, N.F. Tzeng, D.H. Lawrie // IEEE Transactions on Computers, 1987. vol.36, no. 4. pp. 388-395.

104. Zhang, L. Highly Efficient Synchronization Based on Active Memory Operations [Текст] / L. Zhang, Z. Fang, J. B. Carter // 18th International Parallel and Distributed Processing Symposium, 2004. pp. 58-68.

105. Zhongfeng, Wang. VLSI [Текст] / InTech, 2010. 464 p.

106. Zotov, I.V. Distributed Virtual Bit-Slice Synchronizer: A Scalable Hardware Barrier Mechanism for n-Dimensional Meshes [Текст] / I.V. Zotov // IEEE Trans. Comput. 2010. vol.59, no. 9. pp. 1187-1199.

ПРИЛОЖЕЬШЕ 1 - Листинг управляющей подпрограммы, реализуемой обобщенными массовыми контроллерами при моделировании координирующей среды.

/* получение id управляема клапанов */ static int ids[9]; unsigned short i, k, 1, row, col, group_id, process_no; GA.TESTATESMAP_ITERATOR it = GateStateSMap.beginO ;

for ( i = 0; it != GateStatesMap.endO; ++it, ++i ) ids[i] = it->first; static int idJJCIn, id_LCIn, id_UCOut, id_LCOut, id_UCOff, id_LCOff, id_CFIn, id_CPOut, id_CFOff; static string gate_name; for ( i = 0; i < 9; ++i ) { gate_name = GETNAMEBYID( CQChart::gate, ids[i] ); switch( gate_name[0] ) { case 'C1 :

if ( gate_name[3] = 'f' ) id_CTOff = ids[i]; else

if ( gate_name[3] = 'n' ) id_CFIn = ids[i]; else id_CFOut = ids[i]; break; case 'L' :

if ( gate_name[8] = 'f' ) id_LCOff = ids[i]; else

if ( gate_name[8] = 'n1 ) id_LCIn = ids[i]; else id_LCOut = ids[i]; break; case 'U' :

if ( gate_name[8] = 'f' ) id_UCOff = ids[i]; else

if ( gate_name[8] = 'n' ) id_UCIn = ids[i];

else id_UCOut = ids[i];

break;

}

}

/* сброс состояния управляемых клапанов */ GateStatesMap[idJJCIn] = 0; GateStatesMap[id_LCIn] = 0; GateStatesMap[idJJCOut] = 0; GateStatesMap[id_LCOut] = 0; GateStatesMap[idJJCOff] = 1; GateStatesMap[id_LCX)ff] = 1; GateStatesMap[id_CFIn] = 0; GateStatesMap[id_CPOut] = 0; GateStatesMap[id_CPOff] = 1;

/* вычисление адреса текущего мэдуля в матрице [row: col] */ static const unsigned short maxrowcount = 32 /* 4, 8, 16, 32, 64 */, maxcolcount = maxrowcount;

string tmp_str = AssocControllers[0]-XSetName().copy();

char * ptr = const_cast<char *>( strrchr( tmp_str. c_str (), ) );

col = atoi ( ++ptr ) ;

*—ptr = ' \0' ;

ptr = const_cast<char *>( strrchr( tinp_str.c_str (), ) ); row = atoi( ++ptr ) ;

/* имитация подачи фиктивного импульса от мэдуля верхней строки */ if ( row = 1 ) {

if ( GETSTATEBYNAME( AssocControllers[0]->GetName() ) - empty )

{

GateStatesMap[id_UCIn] = 1; GateStatesMap[id_UCOff] = 0;

}

}

/* имитация подачи фиктивного импульса от модуля левого столбца */ if ( col = 1 && row != 1 ) {

if ( GETSTATEBYNAME ( AssocControllers [1] ->GetName () ) = empty )

{

GateStatesMap[idJLCIn] = 1; GateStatesMap[id_LCOff] = 0;

}

}

/* имитация подачи волны импульсов правым нижним модулем */ if ( row = maxrowcount && col = maxcolcount ) { GateStatesMap [idJJCIn] = 1; GateStatesMap[idJJCOff] = 0; GateStatesMap[id_LCIn] = 1; GateStatesMap[id_LCOff] = 0;

}

/* проверка поступления волны импульсов от соседей */ bool pulse_wave_here = false;

if ( GETSTATEBYNAME ( AssocControllers [0]->GetName() ) == busy && GETSTATEBYNAME ( AssocControllers [1] ->GetName () ) = busy ) pulse_wave_here = true; /* определение нового состояния клапанов Up(Lo)ClockOutGt */ if ( pulse_wave_here ) {

GateStatesMap[idJJCOut] = 1; GateStatesMap[id_LCOut] = 1;

}

/* структуры и типы данных, доступные всей матрице модулей */ typedef unsigned char mtype; // unsigned short при m - 16, unsigned int при m = 32 typedef unsigned char ptype;

static const ptype p = 8; //8, 16, 32 - глубина виртуализации static const mtype m = 8; // 8, 16, 32 - число параллельных слоев // среднее время пребывания задачи в системе (в тактах) static const unsigned short aver_task_exec_time = 2000; // средняя продолжительность существования барьерной группы

static const unsigned short aver_group_duration = aver_task_exec_time / 5; // среднее время мэжду моментами инстанцирования барьерных групп

static const unsigned short aver_group_creation = aver_task_exec_time / 100; // предельные значения мощности барьерной группы static const unsigned short min_group_card = 2, max_group_card = maxrowcount * maxcolcount; // среднее время мэжду смежными барьерами одной группы

static const unsigned short aver_interbarrier_time = aver_group_duration / 40; // период следования импульсов волны синхронизации static unsigned short pulse_wave_period = 11; // минимальное время существования барьерной группы в системе static unsigned short min_group_duration = maxrowcount * maxcolcount; static mtype completion_latch[maxrowcount][maxcolcount][p]; // защелки static mtype participation_latch[maxrowcount][maxcolcount][p]; // защелки static ptype counter[maxrowcount][maxcolcount]; // счетчики каналов static ptype capacity_register; // общий регистр Capacity Register // матрицы регистров Virtual Slice Register и Physical Slice Register static ptype virtual_slice_register[maxrowcount][maxcolcount]; static mtype physical_slice_register[maxrowcount][maxcolcount]; // матрица триггеров

static bool CF[maxrowcount][maxcolcount]; // максимальный номер занятого виртуального канала

static unsigned short max_alloc;

// статус виртуальных каналов распределенного синхронизатора static mtype channel_status[p];

// время существования барьерных групп и занятости каналов static unsigned short channel_timer [p*m]; // матрица номеров импульсов волны синхронизации //static unsigned short pulse_wave [maxrowcount] [maxcolcount]; // остаток времени пребывания процессов в межбарьерных секциях static unsigned short interbarrier_timer[maxrowcount] [maxcolcount]; // множество существующих барьерных групп (группы представляются // номэрами назначенных им каналов синхронизации) static vectorCunsigned short> existing_groups;

// множество барьерных групп, участвующих в синхронизации в данный момэнт

static vector<unsigned short> synchronized_groups;

// множество процессов, участвующих в синхронизации в данный момент

// (процессы задаются сквозными номерами согласно размещению в матрице)

static vectorCunsigned short> synchronized_processes;

// массив множеств процессов, принадлежащих барьерным группам

static vector< vectorCunsigned short> > group_members;

// массив для учета фактического времени синхронизации барьерных групп

static vectorCunsigned int> real_synch_time;

// массив для разрешения учета времени синхронизации барьерных групп static vectorCbool> synch_time_enabled;

// способ размещения синхронизируеьых групп процессов в матрице процессоров static short group_allocation [maxrowcount] [maxcolcount]; /* инициализация структур данных */ static bool first_call = true; static FILE * ieee_log_file = NULL;

if ( first_call ) { first_call = false;

capacity_register = 0x1; // первоначально существует барьерная группа

channel_status[0] = 0x1; // MPI_CCMM_WORLD, отображенная на канал 0

existing_groups.push_back(0) ;

real_synch_time.push_back(0);

synch_time_enabled.push_back(false);

// номера процессов глобальной группы

vectorCunsigned short> global_group_members;

for ( i = 1; i <= maxrowcount * maxcolcount; ++i )

global_group_members. push_back (i);

group_members.push_back( global_group_members );

max_alloc = 0; // один канал всегда считается занятым

for ( k = 0; к с maxrowcount; ++k )

for ( 1=0; 1С maxcolcount; ++1 ) { for ( ptype q = 1; q С p; ++q ) participation_latch[k] [1] [q] = Oxff; // Oxffff при m = 16, Oxffffffff при m = 32 // помечаем, что все процессоры принадлежат группе MPI_CCMM_WORLD

participation_latch [k] [1] [0] = Oxfe; // Oxfffe при m = 16, Oxfffffffe при

32

// сброс размещения синхронизируемых групп процессов group_allocation[k][1] = -1;

// -1 означает, что процесс не входит в синхронизируемые группы // задание времени до следующего барьера int random__value; do {

random_value = rand();

if ( random_value <= 0 ) continue;

interbarrier_timer[k][1] =

-aver_interbarrier_time * log(double(random_value)/RAND_MAX);

interbarrier_timer[k] [1] += pulse_wave_period; }

while ( random value <= 0 ||

interbarrier_timer[k][1] < pulse_wave_period ); // если длительность процесса меньше pulse_wave_period,

// среда мэжет работать некорректно }

}

if ( pulse_wave_here ) {

/* счет прошедших волн импульсов синхронизации */ //++pulse_wave[row-l][col-1]; /* определение состояния элемента И б */ ptype q = counter[row-1][col-1];

bool AND6 = CF[row-l] [col-1] && q = virtual_slice_register[row-1] [col-1]; /* вычисление набора флагов участия/завершения PCF */ mtype PCF = participation_latch[row-1][col-1][q] |

( AND6 ? physical_slice_register[row-1][col-1] : 0 ); /* вычисление набора флагов состояния барьера BF на выходе элемента И 1 */ mtype BF = 0;

if ( row != 1 && col != 1 )

BF = completion_latch[row-2][col-1][q] & completion_latch[row-1][col-2][q] & PCF; else

if ( row = 1 && col != 1 )

BF = completion_latch[row-1][col-2][q] & PCF; else

if ( row != 1 && col = 1 )

BF = completion_latch[row-2][col-1][q] & PCF; else // row = 1 && col = 1

BF = ~completion_latch[maxrowcount-l][maxcolcount-1][q] & PCF; /* модификация q-го регистра защелки completion_latch */ mtype old_completion_latch = completion_latch[row-1][col-1][q];

completion_latch [row-1] [col-1] [q] = BF; // значение q выходит за границу диапазона

/* определение нового состояния клапана CFOutGt */ if ( ( old_completion_latch & ~BF &

( AND6 ? physical_slice_register[row-1][col-1] : 0x0 ) ) != 0 ) {

// разрешаем активизацию данного процесса GateStatesMap[id_CFOut] = 1; CF[row-1][col-1] = false;

/* поиск канала, на который отображена группа данного процесса */ process_no = col + (row - 1) * maxcolcount;

vectorCunsigned short>::iterator sg_it = synchronized_groups.begin(); while ( sg_it != synchronized_groups.end() ) { if ( find( group_members[*sg_it].begin(), group_members[*sg_it].end(),

process_no ) != group_members[*sg_it].end() ) {

/* удаление группы из числа синхронизируемых */ synchronized_groups.erase( remove( synchronized_groups.begin(), synchronized_groups.end(), *sg_it ), synchronized_groups.end() );

break; }

++sg_it; }

/* проверяем завершение активизации всех процессов данной группы */ group_id = group_allocation[row-1][col-1]; bool activation_completed = true; for ( k = 0; k < maxrowcount; ++k )

for ( 1=0; 1 < maxcolcount; ++1 ) {

if ( group_id != group_allocation[k][1] ) continue;

if ( CF[k][1] ) {

activation_conpleted = false;

break; }

}

if ( activation_completed ) {

// все процессы активизированы - время синхронизации подсчитано

for ( к = 0; к < maxrowcount; ++к )

for ( 1=0; 1 < maxcolcount; ++1 )

if ( group_id = group_allocation[k][1] )

group_allocation[k][1] = -1;

static unsigned_int64 sum_real_synch_time = 0;

static unsigned count = 0;

sum_real_synch_time += real_synch_time[group_id]; ++count;

double aver_real_synch_time = sum_real_synch_time / (double)count; ///

ieee_log_file = fopen("ieee.log", "a+t"); fprintf( ieee_log_file,

"Average real synch time: %.101f\n", aver_real_synch_time );

fclose( ieee_log_file );

///

real_synch_time[group_id] = 0;

synch_time_enabled[group_id] = false; }

// помечаем, что этот процесс можно включить в другие // группы синхронизируемых процессов synchronized_processes.erase( remove( synchronizedjprocesses.begin(), synchronized_processes.end(), process_no ), synchronized_processes.end() );

// задание для данного процесса времени до следующего барьера int random_value; do {

random_value = rand();

if ( randam_value <= 0 ) continue;

interbarrier_timer[row-l][col-1] =

-aver_interbarrier_time * log(double(random_value)/RAND_MAX);

interbarrier_timer[row-1][col-1] += pulse_wave_period; }

while ( random_value <= 0 ||

interbarrier_timer[row-1][col-1] < pulse_wave_period ); // если длительность процесса меньше pulse_wave_period,

// среда мажет работать некорректно }

}

static unsigned short period = maxrowcount * maxcolcount; if ( —period = 0 ) {

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

period = maxrowcount * maxcolcount; /* инстанцирование очередной барьерной группы */

static unsigned short group_creation_timer = 0x0; if ( group_creation__timer = 1 ) {

// поиск первого виртуального слоя со свободными каналами ptype q = 0;

for ( ; q < p; ++q ) if ( channel_status[q] != Oxff ) break if ( q >= p ) throw exception ( ) ; // превышен предел числа // поиск первого свободного канала в найденном слое

mtype s = Oxl;

unsigned char bit_index = 0; while ( ( s & channel_status[q] ) != 0 ) { s «= 1;

++bit_index; }

// захват нового виртуального слоя if ( channel_status[q] = 0 ) ++capacity_register; // пометка занятости захваченного канала channel_status[q] |= s; group_id = q*m + bit_index; // включение созданной группы в множество существующих групп existing_groups.push_back(group_id); // определение максимального номера занятого канала

if ( group_id > max_alloc ) { real_synch_time.push_back(0); synch_time_enabled.push_back(false);

max_alloc = group_id; }

// задание времени существования данной группы int random_value; do {

random_value = rand();

if ( random_value <= 0 ) continue;

channel_timer[group_id] =

-aver_group_duration * log( double(random_value) /

RAND_MAX ) ;

// исключение нереально короткого времени существования групп

channel_timer[group_id] += min_group_duration; }

while ( random_value <= 0 | | channel_timer [group_id] < min_group_duration ) ;

// определение подмножества процессоров группы vectorCunsigned short> this_group_members; // вначале включаем в группу все процессы unsigned short left_count = max_group_card; for ( unsigned short i = 1; i <= left_count; ++i ) this_group_members.push_back(i);

unsigned short card = min_group_card + random ( max_group_card/4 - 1 ); // удаляем процессы, не включаемые в группу do {

if ( left_count - card ) break; this_group_members.erase(

this_group_members.begin() + random( this_group_members.size() ) ) ;

left_count—; } while ( true );

// модификация содержимого защелок participation_latch

unsigned short rnd_row, rnd_col; vector<unsigned short>::iterator gm_it = this_group_members.begin(); while ( gm_it != this_group_members.end() ) { rnd_row = (*gm_it - 1) / maxcolcount +1; md_col = *gm_it - maxcolcount * (rnd_row - 1); participation_latch[rnd_row-l][rnd_col-l][q] &= ~s;

++gm_it; }

// включение членов группы в массив

if ( group_id >= (unsigned short)group_members.size() ) group_members.push_back( this_group_members );

else group_members[group_id] = this_group_members; }

/* счет времени между моментами создания барьерных групп */

if ( —group_creation_timer = 0 I I group_creation_timer = Oxffff )

{

int random_value; do {

random_value = rand();

if ( random_value <= 0 ) continue;

group_creation_timer -

-aver_group_creation * log(double

(random_value)/RAND_MAX); }

while ( random_value <= 0 I I group_creation_timer = 0 );

}

/* счет времэни существования барьерных групп */

for ( group_id =1; group_id <= max_alloc; ++group_id )

if ( channel_timer [group_id] > 0 ) —channel_timer[group_id] ; /* формирование множества синхронизируемых групп */ unsigned short next_synch_group = random ( max_alloc + 1 ) ; if ( next_synch_group != 0 && channel_timer [next_synch_group] > 0 ) // группа существует в системе if ( find ( synchronized_groups.begin(), synchronized_groups.end(),

next_synch_group ) = synchronized_groups.end() ) { // группа не входит в число синхронизируемых групп // проверка наличия в группе синхронизируемых процессов bool has_synch_processes = false; vectorCunsigned short>: .'iterator sg_it = group_members[next_synch_group].begin() ;

while ( sg_it != group_members[next_synch_group].end() ) {

if ( find( synchronized_processes.begin(), synchronized__processes. end (), *sg_it ) != synchronized_processes.end() ) { //в группе есть уже синхронизируемый процесс has_synch_processes = true;

break; }

k = (*sg_it - 1) / maxcolcount + 1; 1 = *sg_it - maxcolcount * (k - 1); if ( CF[k-l][1-1] )

{ // в группе есть еще не активизированный процесс has_synch_processes = true;

break; }

++sg_it; }

if ( !has_synch_processes ) {

// группа не содержит синхронизируемых процессов // включаем ее в число синхронизируемых групп synchronized_groups.push_back( next_synch_group ); // добавляем ее процессы в множество синхронизируемых процессов sg_it = group_members[next_synch_group].begin();

while ( sg_it != group_members[next_synch_group].end() ) {

synchronized_processes.push_back( *sg_it ); k - (*sg_it - 1) / maxcolcount +1; 1 = *sg_it - maxcolcount * (k - 1); group_allocation[k-l][1-1] = next_synch_group;

++sg_it; }

} }

/* уничтожение барьерных групп и освобождение каналов */ if ( max_alloc > 0 ) {

for ( group_id = 1; group_id <= max_alloc; ++group_id ) if ( channel_timer [group_id] = 0 ) { // обнуление статуса канала ptype q = group_id / m;

unsigned char bit_index = group_id % m + 1; mtype s = 0x1;

while ( —bit_index ) s «= 1; if ( ( channel_status[q] & s ) != 0 ) { // проверяем не является ли эта группа синхронизируемой if ( find( synchronized_groups.begin(), synchronized_groups.end(), group_id ) = synchronized_groups. end () ) { // не является - уничтожить группу можно // освобождаем канал синхронизации channel_status[q] &= ~s; // освобождение виртуального слоя if ( channel_status [q] = 0 ) —capacity_register; // проверка не освобождается ли канал с максимальным номером if ( group_id = max_alloc ) —max_alloc; // удаление группы из множества существующих барьерных групп group_members[group_id].clear(); existing_groups.erase(

find( existing_groups.begin(), existing_groups.end(), group_id ) ) ;

// переустановка защелок participation_latch

for ( k = 1; k <= maxrowcount; ++k ) for ( 1=1; 1 <= maxcolcount; ++1 ) if ( (participation_latch[k-l][1-1][q] & s) = 0 )

{

// установка group_id-ro разряда защелки participation_latch participation_latch[k-l][1-1][q] |= s;

} } }

} // channel_timer[group_id]" != 0 } // itiax_alloc = 0

/* счет фактического времени синхронизации барьерных групп */ i = 0;

while ( i < (unsigned short) synch_time_enabled. size () ) {

if ( synch_time_enabled[i] ) ++real_synch_time[i] ;

++i; }

gotoxy( 1, 5 );

printf( "MaxAlloc: %u", max_alloc ); gotoxy( 1, б );

printf( "Capacity register: %u", capacity_register );

gotoxy( 1, 7 );

printf( "Channel status: " );

clreol();

for ( short g = p - 1; g >= 0; —g ) { printf( "%X", (channel_status[g] & OxfO) »4 ); printf( "%X", channel_status[g] &■ OxOf );

}

gotoxy( 1, 8 );

printf( "Synchronized groups: " ); clreol();

for ( short g = 0; g < (short) synchronized_groups.size (); ++g ) { printf( "%u ", synchronized_groups[g] );

}

gotoxy( 1, 9 ) ;

printf( "Existing groups: " ); clreol();

for ( short g = 0; g < (short)existing_groups.size{); ++g ) { printf( "%u ", existing_groups[g] );

}

} // period != 0

/* счет продолжительности межбарьерных секций синхронизируеь/ых процессов process_no = col + (row - 1) * maxcolcount; if ( find( synchronized_processes.begin(), synchronized_processes.end(),

process_no ) != synchronized_processes. end () ) {

bool old_CF = CFtrow-1] [col-1];

if ( interbarrier_timer[row-l][col-1] = 0 )

/* индикация завершения процесса */

CF[row-l][col-1] = true;

else —interbarrier_timer[row-1][col-1];

if ( !old_CF && CF[row-1][col-1] ) {

/* поиск канала, на который отображена группа данного процесса */ group_id = 0;

vector<unsigned short>::iterator

sg_it = synchronized_groups.begin();

while ( sg_it != synchronized_groups.end() ) {

if ( find( group_members[*sg_it].begin(),

group_members[*sg_it].end(),

process_no ) != group_members[*sg_it].end() ) {

group_id = *sg_it;

break; }

++sg_it; }

/* загрузка Physical Slice (m) Register и Virtual Slice (p) Register */ virtual_slice_register [row-1] [col-1] = group_id / m; unsigned char bit_index = group_id % m + 1; physical_slice_register[row-1][col-1] = 0x1;

while ( —bit_index ) physical_slice_register [row-1] [col-1] «= 1; /* проверка завершения всех процессов данной группы */ bool group_completed = true; unsigned short member; i = 0;

while ( i < (unsigned short)group_members[group_id].size() ) {

member = group_members [group__id] [i] ; k = (member - 1) / maxcolcount + 1; 1 = member - maxcolcount * (k - 1) ; if ( !CF[k-l][1-1] ) { group_completed = false;

break; }

++i; }

if ( group_cornpleted ) {

/* все процессы завершились - начинаем счет времени синхронизации */

synch_time_enabled[group_id] = true; }

/* определение нового состояния клапанов CFInGt и CFOffGt */ GateStatesMap[id_CFIn] = 1; GateStatesMap[id_CFOff] = 0; } // !(!old_CF && CF[row-l][col-1])

}

/* активизация очередного виртуального слоя в данном модуле if ( pulse_wave_here ) {

if ( counter[row-1][col-1] >= capacity_register - 1 ) counter[row-1][col-1] = 0;

else ++counter[row-1][col-1]; }

return (void)0;

УТВЕРЖДАЮ

проректор по научной работе Юго-Западного государственного университета

д.т.н., профе^^Кири^ек A.B.

АКТ

об использовании результатов диссертационной работы Бредихина Руслана Владимировича

Мы, нижеподписавшиеся, начальник учебно-методического управления, к.т.н., доцент Романченко A.C., и.о. декана факультета информатики и вычислительной техники, к.ф.-м.н., профессор Старков Ф.А., зав. кафедрой вычислительной техники, д.т.н., профессор Титов B.C., составили настоящий акт о том, что результаты работы Бредихина Руслана Владимировича внедрены в учебный процесс, а именно:

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

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

Начальник учебно-методического управления к.т.н., доцент

Романченко A.C.

И.о. декана факультета ИВТ к.ф.-м.н., профессор

Зав. каф. ВТ д.т.н., профессор

Старков Ф.А.

Титов B.C.

УТВЕРЖДАЮ

Директор

АКТ "" ег '

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

Комиссия в составе Гривачева A.B. - директора, Курочкина А.Г. -коммерческого директора и Добросердова О.Г. - технического директора констатирует, что диссертационная работа Бредихина Р.В., посвященная разработке метода и устройств барьерной синхронизации для матричных СБИС-мультикомпьютеров, представляет несомненный практический интерес для нашей организации. Основные выводы и результаты диссертации нашли практическое применение в деятельности ООО «НПЦ «Иннотех». В частности, при построении вычислительного кластера ООО «НПЦ «Иннотех» была использована идея введения виртуально-многослойной архитектуры, которая позволяли существенно снизить сложность коммуникационной среды при одновременном расширении ее функциональных возможностей. Также нашли применение программные средства имитационного моделирования, созданные при непосредственном участии соискателя. Большой интерес вызвала разработанная в диссертации структурно-функциональная организация ячейки барьерной синхронизации в составе координирующей среды, удовлетворяющая требованиям стандарта параллельного программирования MPI и применимая к мультикомпьютеров различной размерности.

Данный акт не является основанием для финансовых расчетов.

Технический директор

Коммерческий директор

УТВЕРЖДАЮ

Генеральный директор ЗАО «Открытые технологии 98» 115280, Россия, Москва, ул. Ленинская Слобода, д. 19, стр. 6, БЦ «Омега Плаза» Рыжов Николай Владимирович « » 2013 г.

АКТ

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