Методы и средства решения задач линейной алгебры на вы-сокопроизводительных реконфигурируемых вычислительных системах Пелипец Андрей Владимирович

Введение к работе

Актуальность темы исследования. В настоящее время неуклонно растет потребность в высокопроизводительных расчетах, что обусловлено появлением новых вычислительных задач большой сложности. Ответом суперкомпьютерной отрасли на эти вызовы стал рост производительности вычислительных систем, но этот процесс уже долгое время носит экстенсивный характер, что в итоге приводит к его замедлению. Согласно данным мирового рейтинга TOP500 с 1994 по 2008 год рост средней производительности всех систем в списке составлял 90% в год, а к настоящему времени этот показатель понизился до 55% в год.

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

суперкомпьютеров, но не улучшает положение дел с падением роста производительности.

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

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

В настоящее время динамично развиваются реконфигурируемые

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

Использование реконфигурируемых вычислительных систем имеет

обоснованные перспективы, поскольку технологическое и архитектурное развитие ПЛИС на протяжении всего времени демонстрирует устойчивый рост таких показателей, как доступный пользователю объем программируемой логики,

количество внутрикристальной памяти и трассировочных ресурсов, тактовую частоту.

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

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

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

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

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

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

высокопроизводительных вычислительных систем.

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

реконфигурируемых вычислительных систем.

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

эффективностью, близкой к максимальной.

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

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

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

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

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

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

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

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

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

Научная новизна диссертации заключается в том, что в ней разработаны:

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

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

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

Положения, выдвигаемые на защиту:

1) стандартные методы и средства решения задач линейной алгебры на
высокопроизводительных системах не позволяют получить эффективность, близкую
к максимальной, при увеличении вычислительных ресурсов системы;

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

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

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

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

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

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

Разработанное программное обеспечение позволило при увеличении вычислительного ресурса системы получить эффективность 0,8-0,99 в решении систем линейных уравнений прямыми и итерационными методами. При этом эффективность РВС в решении данных задач превысила кластерные системы на 11-67 %.

Реализация и внедрение результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, среди которых можно выделить следующие:

– «Исследование возможности создания программируемого блока обработки сигналов из состава прибора 46 серийного образца изделия «Л-01», отчет о НИР, № гос. рег. 01201360203, Таганрог, НИИ МВС ЮФУ, шифр «Лира», 2013;

– «Разработка и исследование методов синтеза прикладных программ для реконфигурируемых вычислительных систем на основе перспективных ПЛИС сверхвысокой степени интеграции», отчет о НИР, № гос. рег. 114061040060, Таганрог, НИИ МВС ЮФУ шифр "Шкала", 2014;

– «Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа», отчет о НИР, № гос. рег. 140912-077192, Таганрог, НИИ МВС ЮФУ, шифр "Русалка", 2014;

– «Процессор многоканальной обработки данных», пояснительная записка, БУКЛ.466535.285 ПЗ. - Ч.1-4, Таганрог, НИИ МВС ЮФУ, шифр "Сокол РТИ", 2014;

– «Разработка методов и программных средств синтеза вычислительных
структур для оперативного решения вычислительно-трудоемких задач на
реконфигурируемых вычислительных системах различных архитектур и

конфигураций», отчет о НИР, № гос. рег. 01201460286, Таганрог, НИИ МВС ЮФУ, шифр "Синтезатор", 2016;

Созданные методы и программные средства внедрены в следующих организациях: НИИ МВС ЮФУ (г. Таганрог), ООО «НИЦ СЭ и НК» (г. Таганрог), ЮНЦ РАН (г. Ростов-на-Дону).

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: X, XII, XIII Ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; 6-й Всероссийской мультиконференции по проблемам управления (МКПУ-2013), с. Дивноморское, Геленджик, 2013 г.; 8-й Всероссийской мультиконференции по проблемам управления (МКПУ-2015), с. Дивноморское, Геленджик, 2015 г.; 4-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2016)», с. Дивноморское, Геленджик, 2016 г.

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

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

научных журналах, входящих в Перечень ВАК. Результаты работы также отражены в 5 отчетах о НИОКР.

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

Диссертация соответствует п. 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», технические науки.