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

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

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

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

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

Курск – 2014

Работа выполнена в Юго-Западном государственном университете

Научный руководитель:        доктор технических наук, профессор

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

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

       Заслуженный деятель науки РФ

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

       

       

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

       

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

Защита состоится 19 декабря 2014 г. в 14:00 на заседании диссертационного совета  Д 212.105.02 при Юго-Западном государственном университете Курск, (конференц-зал).

С диссертацией можно ознакомиться в библиотеке ЮЗГУ и на официальном сайте университета swsu. ru.

Автореферат разослан «___»____________2014 г.

Ученый секретарь совета Д 212.105.02        ______________ Евгений Анатольевич Титенко

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

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

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

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

Вопросами организации межпроцессорного взаимодействия в параллельных системах занимались многие отечественные и зарубежные ученые, в частности, , Вл. В. Воеводин, , E. D. Brooks, D. K. Panda, J. Wu, M. O’Keefe, W. E. Cohen и др. За последние три десятилетия было разработано широкое многообразие методов, процедур и средств барьерной синхронизации, используемых на различных уровнях параллелизма и ориентированных на параллельные вычислительные системы разных архитектурных классов. Для систем рассматриваемого класса наиболее перспективны аппаратно-ориентированные методы распределенной барьерной синхронизации, обладающие наилучшими скоростными характеристиками и адаптированные к СБИС-реализации. Однако известные аппаратно-ориентированные методы характеризуются недостаточной гибкостью, накладывая жесткие ограничения на конфигурацию барьерных групп и/или количество барьеров в приложении, которые вступают в противоречие с действующими стандартами параллельного программирования (в частности, MPI 3.0) и не позволяют эффективно использовать эти методы на практике.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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