Введение к работе
Актуальность темы исследования. Научно-технический прогресс требует неуклонного роста производительности многопроцессорных вычислительных систем, что обусловлено необходимостью быстрого решения сложных задач в заданном интервале времени. Наиболее распространённые многопроцессорные кластерные системы, каждый узел которых построен по фон-неймановской архитектуре, удовлетворяют этим требованиям на задачах, не требующих большого числа информационных обменов. Однако при решении на кластерных системах сильносвязанных задач, в которых число информационных обменов сопоставимо с числом выполняемых операций, время, затрачиваемое на организацию процесса параллельных вычислений, оказывается сравнимым с временем, затрачиваемым на непосредственные вычисления. В связи с этим для многопроцессорных кластерных систем с увеличением числа процессоров наблюдается либо выход на фиксированный уровень, либо падение производительности.
Альтернативой кластерным системам являются активно развиваемые в настоящее время реконфигурируемые вычислительные системы (РВС), построенные на программируемых логических интегральных схемах (ПЛИС). Благодаря возможности программирования на современных ПЛИС сложных функций, РВС с успехом применяются для решения сильносвязанных задач различных проблемных областей науки и техники, демонстрируя при этом линейный рост производительности при увеличении аппаратного ресурса. Это достигается за счет того, что в РВС каждый функциональный блок активно используется при решении задачи и при этом аппаратно реализуется множество каналов связи, что решает проблему информационных обменов.
При решении задач на РВС, в основном, используется структурная организация вычислений, при которой через аппаратно реализуемую вычислительную структуру, соответствующую информационному графу задачи, проходят информационные потоки. Такой подход обеспечивает обработку и передачу данных в едином темпе в вычислительной структуре, что и обуславливает эффективность решения задач. Однако структурная организация вычислений зачастую требует больших аппаратных затрат на реализацию информационного графа задачи. Одной их важнейших характеристик вычислительной структуры, определяющей требуемый объём аппаратного ресурса РВС, является интенсивность потоков данных (произведение числа информационных каналов на скорость передачи данных) между функционально законченными подграфами информационного графа задачи.
В настоящее время на РВС эффективно решаются задачи, для которых интенсивность потока данных практически одинакова в вычислительной структуре задачи. Это обуславливается тем, что в данном случае можно легко масштабировать вычислительную структуру решаемой задачи и, как следствие, реализовать ее на имеющемся ресурсе реконфигурируемой вычислительной системы. В то же время существует большой класс задач, в которых интенсивность потоков данных в разных местах вычислительной структуры отличается более чем на два десятичных порядка. Задачи, в которых интенсивность потоков данных в разных местах вычислительной структуры отличается на 3-4 десятичных порядка, будем называть задачами с существенно переменной интенсивностью потоков данных. К числу таких задач относятся, в частности, задачи транскодирования видеоизображений, молекулярного конструирования лекарств, автоматизированного размещения элементов, трассировки электрических соединений устройств электронной техники и мониторинга компьютерных сетей. Вычислительную структуру таких задач масштабировать практически невозможно, поэтому структурная реализация информационного графа такой задачи может потребовать ресурса большего, чем весь аппаратный ресурс имеющейся РВС. Если аппаратного ресурса не хватает, то необходимо от структурной реализации задачи переходить к мультипроцедурной (когда каждый процессор работает по своей независимой программе). Однако мультипроцедурная реализация, характерная для кластерных систем, неэффективна для РВС. Переход к мультипроцедурной реализации приведет к падению реальной производительности более чем на два десятичных порядка.
В этой связи целесообразна такая редукция вычислительной структуры информационного графа задачи, которая позволила бы реализовать ее аппаратно на имеющемся ресурсе РВС. В настоящее время формализованных методов синтеза параллельно-конвейерных программ для РВС на основе редукции вычислительных структур для решения задач с существенно переменной интенсивностью потоков данных не существует. Более того, напрямую сокращать затраты на реализацию вычислительной структуры возможно только для ограниченного класса решаемых задач за счет масштабирования по числу базовых подграфов. Поэтому более перспективной является редукция производительности РВС, приводящая, в свою очередь, к снижению аппаратных затрат. Это обусловлено тем, что редуцировать производительность можно по большему числу параметров, таких как число базовых подграфов, число операций базового подграфа, разрядность обрабатываемых операндов, тактовая частота и скважность. Здесь и далее под редукцией производительности будем понимать сокращение параметров производительности вычислительной структуры, приводящее к снижению аппаратных затрат.
Таким образом, актуально создание новых методов синтеза параллельно-конвейерных программ на основе редукции производительности вычислительной структуры, обеспечивающих решение задач с существенно переменной интенсивностью потоков данных на РВС в условиях ограниченного аппаратного ресурса при заданном уровне реальной производительности.
Объектом исследования являются методы синтеза параллельно-конвейерных программ для решения сильносвязанных задач на реконфигурируемых вычислительных системах.
Целью диссертации является сокращение аппаратных затрат, требуемых для реализации вычислительных структур, полученных в результате синтеза параллельно-конвейерных программ для РВС.
Научная задача, решаемая в диссертации, - создание методов синтеза параллельно-конвейерных программ для решения задач с существенно переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах в условиях ограниченного аппаратного ресурса при заданном уровне реальной производительности.
Для достижения поставленной цели решены следующие задачи исследования:
- проведен анализ методов синтеза параллельно-конвейерных программ для решения задач на реконфигурируемых вычислительных системах;
- разработаны правила синтеза параллельно-конвейерных программ на основе редукции производительности вычислительной структуры информационного графа задачи с существенно-переменной интенсивностью потоков данных и доказано, что их применение обеспечивает сокращение требуемых аппаратных затрат РВС;
- разработана методика синтеза параллельно-конвейерных программ на основе многокритериальной редукции производительности вычислительной структуры информационного графа задачи с существенно-переменной интенсивностью потоков данных, отвечающая предложенным правилам;
- на основании разработанной методики впервые созданы параллельно-конвейерный алгоритм и прикладная программа решения задачи молекулярного докинга с существенно переменной интенсивностью потоков данных на РВС и оценена эффективность полученного решения.
Методы исследований. При проведении теоретических исследований были использованы основы теории графов, теории множеств, методы структурной и структурно-процедурной организации вычислений. Практические исследования проведены на действующих многопроцессорных вычислительных системах и реконфигурируемых вычислительных системах.
Достоверность и обоснованность полученных научных результатов подтверждены корректностью исходных постановок, непротиворечивостью математических выкладок, а также вычислительными экспериментами на ряде реконфигурируемых вычислительных систем и кластерных МВС. Результаты диссертации докладывались и обсуждались на российских и международных научных конференциях и семинарах, где соискатель выступал с докладами по данной проблематике и получил положительные отзывы научной общественности.
Научная новизна диссертации состоит в том, что в ней:
- разработаны правила синтеза параллельно-конвейерных программ, которые в отличие от известных основаны на редукции производительности вычислительной структуры информационного графа задачи и обеспечивают принципиальную возможность решения на РВС задач с существенно переменной интенсивностью потоков данных;
- формализованы методы синтеза параллельно-конвейерных программ, которые в отличие от известных основаны на однокритериальной редукции производительности по числу операций базового подграфа и по разрядности обрабатываемых операндов вычислительной структуры информационного графа задачи;
- разработан новый метод синтеза параллельно-конвейерных программ, который в отличие от известных основан на редукции производительности по тактовой частоте и скважности и обеспечивает сбалансированную по производительности реализацию подзадач в едином вычислительном контуре;
- разработана новая методика синтеза параллельно-конвейерных программ, которая в отличие от известных основана на многокритериальной редукции производительности вычислительной структуры информационного графа задачи и позволяет решать на РВС задачи с существенно-переменной интенсивностью потоков данных в едином вычислительном контуре.
- на основе многокритериальной редукции производительности впервые разработан параллельно-конвейерный алгоритм решения на РВС задачи молекулярного докинга со структурной организацией вычислений.
Положения, выдвигаемые для защиты:
- при структурной организации вычислений, если производительность вычислительных структур всех подзадач информационного графа задачи сбалансирована (обеспечивается единый темп прохождения данных между вычислительными структурами подзадач), то после корректных редукционных преобразований производительность вычислительных структур всех подзадач также будет сбалансирована;
- при структурной организации вычислений, если редукция производительности вычислительной структуры подзадачи по каждому параметру (число базовых подграфов подзадачи, число операций базового подграфа, разрядность обрабатываемых операндов, тактовая частота работы вычислительной структуры подзадачи, скважность потока данных на входе подзадачи базового подграфа) приводит к корректным преобразованиям задачи, то и редукция производительности вычислительной структуры по произвольной композиции этих параметров приведет к корректным преобразованиям задачи.
Результаты, выдвигаемые для защиты:
- правила синтеза параллельно-конвейерных программ на основе редукции производительности вычислительной структуры информационного графа задачи с существенно переменной интенсивностью потоков данных;
- метод синтеза параллельно-конвейерных программ на основе редукции производительности по тактовой частоте и скважности;
- методика синтеза параллельно-конвейерных программ на основе многокритериальной редукции производительности вычислительной структуры информационного графа задачи с существенно-переменной интенсивностью потоков данных;
- параллельно-конвейерный алгоритм решения задачи молекулярного докинга на реконфигурируемых вычислительных системах со структурной организацией вычислений.
Практическая ценность работы. Использование предлагаемых методов позволяет сократить требуемые аппаратные затраты РВС при решении задач с существенно переменной интенсивностью потоков данных и, как следствие, расширить класс решаемых на РВС задач. Созданная методика синтеза параллельно-конвейерных программ на основе многокритериальной редукции позволяет создавать такие параллельно-конвейерные программы для задач с существенно переменной интенсивностью потоков данных, которые работают значительно быстрее, чем параллельные программы на кластерных МВС, в частности, параллельно-конвейерная программа задачи молекулярного докинга на одной плате РВС выполняется в 50 раз быстрее по сравнению с кластерной МВС, содержащей 32 процессорных узла.
Реализация и внедрение результатов работы. Результаты диссертации использовались при выполнении ряда НИОКР. Наиболее важными из них являются:
- НИР «Исследование и разработка методов и средств технологии суперкомпьютерного молекулярного моделирования на базе реконфигурируемых вычислительных систем» (шифр 2008-04-1.4-15-05-001, 2009), №ГР01200853499;
- ОКР «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» по государственному контракту № 02.524.12.4002 на выполнение опытно-конструкторских работ, шифр «Большая медведица», №ГР 01.2.007 05707;
- НИР «Принципы и методы программирования реконфигурируемых многопроцессорных вычислительных систем» № ГР0120.085.00115, Ростов-на-Дону, ЮНЦ РАН, 2008-2009;
- НИР «Разработка научно-технических основ создания многопроцессорных вычислительных систем сверх-петафлопсной производительности и подготовка кадров высшей квалификации в области распределенных вычислений» (шифр 2009-1.1-215-002-013, 2010), №ГР 01200958384;
- ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой элементной базы», шифр «Медведь», выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг.» по госконтракту №02.447.11.1007, №ГР0122.0510630;
- НИР «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем» (шифр «Маска», 2011), №ГР01201153442.
Результаты диссертации внедрены в НИВЦ МГУ (г. Москва), НИИ МВС ЮФУ (г. Таганрог), в.ч. 26165 (г. Москва), НИЦ ФГУП «18 ЦНИИ» МО РФ (г. Курск).
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях: на научно-практической конференции молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (University of Amsterdam, г. Амстердам, Нидерланды, 2012); на седьмой международной научной молодежной школе «Высокопроизводительные вычислительные системы» (Таганрог, 2010); на шестой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2010); на пятой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2009); на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы (МВУС-2009)» (Таганрог, 2009); на международной молодежной научно-технической конференции и пятой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2008)» (Таганрог, 2008); на международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008)» (пос. Кацивели, АР Крым, Украина, 2008); на третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2007);.
Личный вклад автора. Все научные результаты диссертации получены автором лично.
Публикации. По результатам диссертации опубликовано 19 работ, из них 5 статей, из которых 4 статьи опубликованы в ведущих рецензируемых научных журналах и изданиях, входящих в Перечень ВАК РФ, 7 материалов докладов на международных и российских научно-технических конференциях, 1 свидетельство об официальной регистрации программ для ЭВМ, 6 отчетов о НИОКР.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка использованных источников и пяти приложений. Работа содержит 165 страниц основного текста, 91 рисунок, список используемой литературы из 90 источников, 22 страницы приложений.
