Geum.ru
Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

  Сорокин Дмитрий Анатольевич

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

Специальность 05.13.11 - Математическое и программное обеспечение  вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Таганрог - 2012

Работа выполнена на кафедре Интеллектуальных и многопроцессорных систем (ИМС) Технологического института Южного федерального университета в г. Таганроге (ТТИ ЮФУ) и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика А.В. Каляева федерального государственного автономного образовательного учреждения высшего профессионального образования Южный федеральный университет (НИИ многопроцессорных вычислительных систем ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ:        евин Илья Израилевич,

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

профессор, НИИ МВС ЮФУ

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:        Золотовский Виктор Евдокимович, доктор технических наук,

       профессор, ТТИ ЮФУ

Шиленков Максим Викторович, кандидат технических наук,

заместитель генерального директора ЗАО Эврика

(г. Санкт-Петербург)

       

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:        Федеральное государственное

  бюджетное учреждение науки

  Южный научный центр

  Российской академии наук

   (ЮНЦ РАН, г. Ростов-на-Дону)

Защита диссертации состоится л15 июня 2012 г. в 1420 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. И, комн. 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан  л____________________2012 г.

Просим Вас прислать отзыв, заверенный печатью учреждения, по адресу: 347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44, Технологический институт Южного федерального университета в г. Таганроге, Ученому секретарю диссертационного совета Д 212.208.24 Кухаренко Анатолию Павловичу.

Ученый секретарь

диссертационного совета

кандидат технических наук,

доцент        

А.П. Кухаренко

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

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

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

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

В настоящее время на РВС эффективно решаются задачи, для которых интенсивность потока данных практически одинакова в вычислительной структуре задачи. Это обуславливается тем, что в данном случае можно легко масштабировать вычислительную структуру решаемой задачи и, как следствие, реализовать ее на имеющемся ресурсе реконфигурируемой вычислительной системы. В то же время существует большой класс задач, в которых интенсивность потоков данных в разных местах вычислительной структуры отличается более чем на два десятичных порядка. Задачи, в которых интенсивность потоков данных в разных местах вычислительной структуры отличается на 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 страницы приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Базовый подграф задачи докинга, который мультиплицируется по данным и итерациям, представлен на рис. 1.

Рис.1. Базовый подграф задачи докинга

Конфигурация лиганда в трехмерном пространстве определяется кортежем параметров <i1,i2,Е,ik>. Параметры (i1,i2,i3) задают поступательное движение лиганда как целого, параметры (i4,i5,i6,i7) задают вращение лиганда как целого, а параметры (i8,i9,Е,ik) задают внутренние торсионные вращения частей лиганда.

Базовый подграф состоит из пяти подзадач. Подзадача P1 состоит из процедур Crossover и Mutate. Процедура Crossover формирует поток параметров <i1,i2,Е,ik> по алгоритму диффузионного кроссовера. Процедура Mutate состоит из трех независимых процедур: Mut_d - процедуры модификации параметров (i1,i2,i3); Mut_q - процедуры модификации параметров (i4,i5,i6,i7); Mut_ - процедуры модификации параметров (i8,i9,Е,ik).

Подзадача P2 состоит из процедур Rotate и Rotate_translate. Процедура Rotate выполняет пересчет декартовых координат атомов лиганда с учетом параметров (i8,i9,Е,ik). Процедура Rotate_translate выполняет пересчет декартовых координат атомов лиганда с учетом параметров (i1,i2,i3) и (i4,i5,i6,i7).

Подзадача P3 состоит из четырех процедур: E_tors - процедуры расчета энергии торсионного напряжения конформера; E_vdw - процедуры расчета энергии Ван-дер-Ваальсового взаимодействия между атомами лиганда; E_es - процедуры расчета энергии электростатического взаимодействия между атомами лиганда и E_grid - процедуры расчета энергии лиганда в поле протеина.

Подзадача P4 реализует расчет общей энергии связывания Eall комплекса лиганд-белок. Подзадача P5 реализует процедуру Matting pool selection - отбор b=MatingPoolSize лучших кортежей <i1,i2,Е,ik>, которым соответствуют минимальные значения энергий связывания Eall.

При переходе от подзадачи P1 к подзадаче P2 интенсивность потока данных увеличивается в n раз, при переходе от подзадачи P2 к подзадаче P3 интенсивность потока данных увеличивается еще в m раз. В подзадаче P4 интенсивность потока данных уменьшается в nm раз, а в подзадаче P5 уменьшается в k раз. Таким образом, при n=20 интенсивность потока данных меняется более чем в 400 раз, а при n=100 Ц  более чем в 10000 раз.

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

,

где N(p) - объем ресурса, затрачиваемый на реализацию базового подграфа p подзадачи Pi; fi - число базовых подграфов подзадачи Pi.

Если ресурса РВС достаточно (lаа1), то вычислительная структура будет содержать [l] базовых подграфов, которые совместно обходят информационный граф задачи. Здесь и далее под операцией [x] будем понимать операцию округления x до ближайшего меньшего целого. В случае если ресурса РВС недостаточно, то для того, чтобы реализовать вычислительную структуру со степенью распараллеливания l<1, необходимо провести сокращение аппаратных затрат на её реализацию. Требуемый коэффициент сокращения аппаратных затрат составит .

Традиционно для сокращения аппаратных затрат A на реализацию базового подграфа задачи выполнялась r-кратная редукция числа базовых подграфов fi всех подзадач Pi:. Однако этот прием применим, если выполняется условие . В противном случае редукция считалась невозможной.

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

,

где Ki - число операций базового подграфа подзадачи Pi; i - разрядность обрабатываемых операндов; i - тактовая частота работы вычислительной структуры подзадачи Pi; Si - скважность потока данных на входе подзадачи базового подграфа.

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

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

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

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

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

Правило первое. Для синтеза параллельно-конвейерных программ редукция производительности вычислительной структуры подзадачи должна осуществляться не только путем сокращения числа базовых подграфов подзадачи fi, но и путем сокращения числа операций базового подграфа подзадачи Ki, разрядности обрабатываемых операндов i, тактовой частоты работы вычислительной структуры подзадачи i, а также за счет увеличения скважности потока данных Si на входе подзадачи базового подграфа. Это обуславливается тем, что не всегда возможно сокращение числа базовых подграфов до одного, поскольку в противном случае могут возникать вложенные циклы обработки данных, приводящие к временной остановке вычислительного процесса в других подзадачах.

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

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

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

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

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

Сокращение числа устройств K в r раз приведет к пропорциональному падению производительности W(P) вычислительной структуры. Однако потребуется дополнительное коммутационное оборудование для последовательной реализации r редуцированных базовых подграфов подзадачи P, что должно быть учтено при расчете аппаратных затрат N(P).

Объем Nr(P) редуцированной вычислительной структуры подзадачи P можно рассчитать по формуле , где N(C) - объем аппаратных затрат на реализацию коммутационного оборудования редуцированного базового подграфа подзадачи P.

Для каждого входа устройства, реализующего операцию базового подграфа подзадачи, в общем случае число источников информации будет равно r, что соответствует установке r-входового коммутатора. C учетом того, что практически все математические операции Oi - двухместные, число таких коммутаторов будет определяться отношением . Аппаратные затраты на реализацию коммутационного оборудования можно рассчитать по формуле , где N(MXr) - объем аппаратного ресурса на реализацию r-входового коммутатора, - разрядность операндов.

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

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

Объем аппаратного ресурса Nr(Oi) на реализацию редуцированного по разрядам (секционированного) устройства, выполняющего математическую операцию Oi, можно оценить по формуле , где N(Oi1) - объем аппаратных затрат на реализацию одноразрядной операции преобразования данных; N(D) - аппаратные затраты на дополнительное оборудование для последовательно секционированного устройства; - функция, определяющая коэффициент аппаратных затрат на реализацию определенной математической операции Oi. Метод редукции по разрядности выполняемых операций целесообразно применять, если обрабатываются данные в формате с фиксированной запятой.

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

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

1) Предварительный этап.

1.1) Выполнить анализ алгоритма задачи, реализуемой на РВС.

1.2) Построить информационный граф задачи.

1.3) В информационном графе упростить вычислительно избыточные фрагменты.

1.4) Построить вычислительную структуру информационного графа задачи.

1.5) В вычислительной структуре информационного графа исключить фрагменты вычисления констант для решаемой задачи.

2) Основной этап.

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

2.2) Выполнить редукцию производительности для всех подзадач исходного базового подграфа.

2.2.1) Выполнить редукцию производительности по числу базовых подграфов.

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

2.2.3) Выполнить редукцию производительности по скважности или частоте.

3) Анализ результатов.

3.1) Если требуемые аппаратные затраты меньше ресурса РВС, то редукция выполнена успешно.

3.2) Если произведение параметров редукции для всех подзадач меньше коэффициента редукции, то структурная реализация задачи на данной РВС невозможна.

4) Синтезировать вычислительную структуру на основе редуцированного базового подграфа.

5) Определить организацию потоков данных в синтезированной вычислительной структуре.

6) На основе синтезированной вычислительной структуры и организованных потоков данных разработать параллельно-конвейерную программу.

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

В третьей главе показано применение методики синтеза параллельно-конвейерных программ на основе многокритериальной редукции на примере реализации на РВС задачи молекулярного докинга в едином вычислительном контуре.

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

Поскольку на практике обрабатываются лиганды размерностью до n=200 атомов c числом параметров до k=27 и размером массива минимальных энергий до =128, то для того чтобы выполнить структурную реализацию исходного базового подграфа на РВС и решить задачу в едином вычислительном контуре, может потребоваться аппаратный ресурс объемом около 917518 вычислительных устройств стандарта IEEE754.

Аппаратной платформой для решения задачи докинга была выбрана плата базового модуля РВС Орион, которая содержит 16 кристаллов ПЛИС, связанных пространственной коммутационной системой и обладает вычислительным ресурсом объемом около 1500 вычислительных устройств обработки 32-разрядных операндов с плавающей запятой в стандарте IEEE754.

Таблица 1

Аппаратные затраты на реализацию подзадач базового подграфа задачи докинга

Подзадача

Аппаратные затраты

до редукции

после редукции

1-я итерация

2-я итерация

P1

Cross

15

15

15

Mut_a

160

8

8

Mut_d

54

18

18

Mut_q

76

19

19

P2

Rotate

84940

760

500

Rotate_translate

4230

26

12

P3

E_grid

10600

53

53

E_es

258700

416

208

E_vdw

517400

832

416

E_tors

1320

51

51

P4

40019

48

48

P5

4

2

2

общие затраты

917518

2248

1350

Требуемый аппаратный ресурс на реализацию исходного базового подграфа задачи докинга существенно превышает имеющийся ресурс базового модуля Орион. Для его сокращения, применяя разработанную методику многокритериальной редукции, производительность всех подзадач была редуцирована с коэффициентом r=1220. Аппаратные затраты на реализацию базового подграфа составят Ar=1350. Поскольку Ar<L, то редукция производительностей подзадач базового подграфа задачи докинга выполнена успешно. На рис. 2 представлен базовый подграф реализуемой на плате базового модуля РВС Орион задачи докинга после проведенных преобразований.

Рис. 2. Редуцированный базовый подграф задачи молекулярного докинга

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

Рис. 3. Редуцированная вычислительная структура задачи молекулярного докинга

На рис. 3 приведены следующие обозначения: A1j и A2j - адреса первого и второго кортежей параметров, выбираемых из массива МР={<1,2,Е,k>1, <1,2,Е,k>2,Е,<1,2,Е,k>b}, лучших кортежей, которым соответствуют минимальные значения энергий связывания Eall; Parent1j и Parent2j - первый <A11,A12,Е,A1k>j и второй <A21,A22,Е,A2k>j кортежи параметров, выбранные из массива МР по адресам A1j и A2j; Childj - кортеж параметров <'1,'2,Е,'k>, сформированный из Parent1j и Parent2j; <xi,yi,zi>nЦ исходные координаты атомов лиганда; <xi,yi,zi>''n - координаты атомов лиганда, модифицированные с учетом параметров <i1,i2,Е,ik>.

Для всех подзадач синтезированной вычислительной структуры в виде временных диаграмм были описаны правила формирования информационных потоков. На рис. 4 для подзадачи P1 представлена временная диаграмма формирования параметров <i1,i2,Е,ik>, определяющих пространственную конфигурацию лиганда в декартовой системе координат. Здесь большими делениями показаны интервалы подачи данных в вычислительную структуру, пунктиром отделены такты работы. Величина параметра определяется скважностью работы процедуры Matting pool selection и числом n обрабатываемых атомов лиганда.

Рис. 4. Временная диаграмма формирования параметров <i1,i2,Е,ik>

В основном цикле определения оптимальной конфигурации лиганда процедура Crossover формирует два случайных адреса A1j и A2j, по которым из массива МР считываются кортежи параметров Рarent1j=<A11,A12,Е,A1k>j и Рarent2j=<A21,A22,Е,A2k>j (см. рис. 4). Затем в процедуре Crossover по алгоритму диффузионного кроссовера формируется новый кортеж Childj=<'1,'2,Е,'k>. Путем случайной модификации параметров Childj в процедуре Mutate формируется новый кортеж параметров <i1,i2,Е,ik>. Аналогичным образом формируются информационные потоки для остальных подзадач. На рис. 5 для подзадачи P2 представлена временная диаграмма расчета декартовых координат всех атомов лиганда с учетом параметров преобразования <i1,i2,Е,ik>.

Рис. 5. Временная диаграмма расчета декартовых координат атомов лиганда

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

Для сравнения скорости решения задачи докинга на базовом модуле РВС Орион с современными кластерными вычислительными системами было проведено исследование времени докинга тестовых выборок программой SOL на вычислительном кластере НИВЦ МГУ Чебышев. Каждый узел этого кластера представляет собой двухпроцессорную систему с четырехъядерным процессором Intel Xeon E5472 3.0 ГГц. Программа SOL выполнялась на 32-х узлах кластерной МВС Чебышев, при этом осуществлялось распараллеливание по данным и каждый процессор обрабатывал свою часть популяции. Проведенные эксперименты показали, что применение реконфигурируемых вычислительных систем более эффективно для решения таких сильносвязанных задач с существенно переменной интенсивностью потоков данных, как задача докинга молекулярных соединений. Главным критерием эксперимента выступает достигаемое ускорение (SРВС) решения задачи на РВС в сравнении с кластерной системой (отношение времени решения задачи на кластере к времени решения задачи на РВС).

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

Рис. 6. Зависимость ускорения докинга лигандов от числа атомов в сравнении

с 32-мя узлами МВС Чебышев

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

При проведении исследований и разработок по теме настоящей работы получены следующие теоретические и прикладные результаты, обладающие научной новизной:

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

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

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

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

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

- разработан параллельно-конвейерный алгоритм решения задачи молекулярного докинга на РВС;

- разработана параллельно-конвейерная программа молекулярного докинга в составе средств суперкомпьютерного молекулярного моделирования на РВС.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в рецензируемых журналах и изданиях:

1) Сорокин, Д.А. Реализация докинга для молекулярного моделирования на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин, А.И. Дордопуло, И.И. Левин // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - №7. - С. 217-224 (ведущий рецензируемый журнал, входит в перечень ВАК);

2)аСорокин, Д.А. Оптимизация вычислительной структуры докинга для молекулярного моделирования на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин, А.И. Дордопуло, И.И. Левин // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - №12. - С. 232-238 (ведущий рецензируемый журнал, входит в перечень ВАК);

3)аСорокин, Д.А. Решение задач с существенно-переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин, А.И. Дордопуло, И.И. Левин, А.К. Мельников // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2012. - №2. - С.49-56 (ведущий рецензируемый журнал, входит в перечень ВАК);

4)аСорокин, Д.А. Методика сокращения аппаратных затрат в сложных системах при решении задач с существенно-переменной интенсивностью потоков данных [Текст] / Д.А.аСорокин, А.И. Дордопуло // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2012. - №4. - С. 213-219 (ведущий рецензируемый журнал, входит в перечень ВАК);

Другие наиболее значимые публикации:

5)аСорокин, Д.А. Аппаратная реализация докинга лигандов на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин, А.И. Дордопуло // Информатика, вычислительная техника и инженерное образование. Эл № ФС77-39729 от л29 апреля 2010 г. Выпуск №4(6), 2011. - С.30-46;

6)аСорокин, Д.А. Аппаратная реализация докинга ингибиторов на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин, А.В. Бовкун // Материалы VI ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. Ростов-на-Дону, 2010. - С.121-122;

7)аСорокин, Д.А. Решение проблемы выбора рационального варианта реализации задачи докинга ингибиторов на реконфигурируемых вычислительных системах [Текст] / Д.А.аСорокин,  А.В. Бовкун // Материалы Седьмой Международной научной молодежной школы Высокопроизводительные вычислительные системы. - Таганрог: Изд-во ТТИ ЮФУ, 2010. - С.327-329;

8)аСвидетельство о государственной регистрации программы для ЭВМ № 2009614741, РФ. PLISDOCK. Зарегистр. в Реестре программ для ЭВМ 3.09.2009 г. Правообладатель: Государственное учреждение Научно-Исследовательского Вычислительного Центра Московского государственного университета имени М.В. Ломоносова. Дордопуло А.И., Сорокин Д.А. и др., всего 7 соавт.

В совместных работах автором получены следующие результаты: в [1] разработаны методы оптимизации фрагментов задач с переменной интенсивностью потоков данных и средства адаптации архитектуры РВС под структуру решаемой задачи; в [2] показана эффективность применения методов оптимизации и адаптации архитектуры РВС под структуру решаемой задачи с переменной интенсивностью потоков данных; в [3,4] разработана методика многокритериальной редукции вычислительной структуры базового подграфа задачи с существенно-переменной интенсивностью потоков данных; в [5,6,7] описан синтез параллельно-конвейерного алгоритма решения задачи докинга ингибиторов на РВС на основе разработанной методики многокритериальной редукции.

Р №020565 от 23 июня 1997г. Подписано к печати ___.04.2012 г.

Формат 60х841/16. Бумага офсетная. Печать офсетная.

Усл. п.л. - 1,4.                 Уч.-изд.л. - 1,1.

Заказ № _____.                Тираж 120 экз.

ГСП 17А, Таганрог, 347928, Некрасовский, 44

Типография Технологического института

Южного федерального университета в г. Таганроге

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям