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

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

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

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

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

Автореферат

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

.1 7 МАЙ 2012

Таганрог-2012

005043774

005043774

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

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

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

доктор технических наук, профессор, НИИ МВС ЮФУ

Золотовский Виктор Евдокимович, доктор технических наук, профессор, ТТИ ЮФУ

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

директора ЗАО «Эврика» (г. Санкт-Петербург)

Федеральное государственное бюджетное учреждение науки Южный научный центр Российской академии наук (ЮНЦ РАН, г. Ростов-на-Дону)

Защита диссертации состоится «15» нюня 2012 г. в 14го на заседании диссертационного совета Д 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; ' у'

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

ш'з^О^^^о^'о^оо^ВЗвдР11 ^ас11Ределеиных вычислений» (шифр 2009-1.1-215-002-

-ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой элементной базы», шифр «Медведь» выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг» по

госконтракту №02.447.11.1007, №ГР0122.0510630;

- НИР «Разработка теоретических основ построения с^рхвысокопроизводительньхх реконфигурируемых вычислительных систем» (шифр «Маска», 2011), №ГР01201153442. 111

Результаты диссертации внедрены в НИВЦ МГУ (г. Москва), НИИ МВС ЮФУ (г. Таганрог), в.ч. 26165 (г. Москва), НИЦ ФГУП «18 ЦНИИ» МО РФ (г Курск)

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссииских и международных научно-технических конференциях: нанаучно-практическои конференции молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (University of Amsterdam, г. Амстердам, Нидерланды, 2012); на седьмой международной научной молодежной школе «Высокопроизводительные вычислительные системы» (Таганрог

11\пипрд^Ж,10ДИ0Й 1,аУ""°Й конФеР™ студентов и аспирантов базовый кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2010); на пятой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону 2009)- на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы (МВУС-2009)» (Таганрог 2009)- на международной молодежной научно-технической конференции и пятой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2008)» (Таганрог, 2008); на международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008)» (пос. Кацивели, АР Крым, Украина, 2008)- на третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2007);. 4

Личный вклад автора. Все научные результаты диссертации получены автором лично.

Публикации. По результатам диссертации опубликовано 19 работ из них 5 статей, из которых 4 статьи опубликованы в ведущих рецензируемых научных журналах и изданиях, входящих в Перечень ВАК РФ, 7 материалов докладов на международных

и российских научно-технических конференциях, 1 свидетельство об официальной регистрации программ для ЭВМ, 6 отчетов о НИОКР.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка использованных источников и пяти приложений. Работа содержит 165 страниц основного текста, 91 рисунок, список используемой литературы из 90 источников, 22 страницы приложений.

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

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

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

Конфигурация лиганда в трехмерном пространстве определяется кортежем параметров <a'i,a'2,...,a'k>. Параметры (a'i,a'2,as) задают поступательное движение лиганда как целого, параметры (a'j,a'5,a'6,a7) задают вращение лиганда как целого, а параметры (a's,a'9, ...,а'к) задают внутренние торсионные вращения частей лиганда.

Базовый подграф состоит из пяти подзадач. Подзадача Р, состоит из процедур Crossover и Mutate. Процедура Crossover формирует поток параметров <a'i,a':,...,a'i,> по алгоритму диффузионного кроссовера. Процедура Mutate состоит из трех независимых

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

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

процедур: Mutjd- процедуры модификации параметров (а',,а'2,а'3); Mut_q - процедуры модификации параметров (a'4,a's,a'&a!7); Mut_a - процедуры модификации параметров

Подзадача Р2

состоит из процедур Rotate и Rotate translate. Процедура Rotate выполняет пересчет декартовых координат атомов лиганда с учетом параметров (a's,a'9,... ,aV- Процедура Rotate_translate выполняет пересчет декартовых, координат атомов лиганда с учетом параметров (а',,а'2,а3) и (а'4,а?;,а'6,а'7).

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

Подзадача Р4 реализует расчет общей энергии связывания Еы, комплекса «лиганд-белок». Подзадача Р5 реализует процедуру Matting pool selection - отбор 6=MatingPoolSize лучших кортежей <а'¡,а'2,...,а'к>, которым соответствуют минимальные значения энергий связывания Еац.

При переходе от подзадачи Р, к подзадаче Р2 интенсивность потока данных увеличивается в п раз, при переходе от подзадачи Р2 к подзадаче Р3 интенсивность потока данных увеличивается еще в т раз. В подзадаче Р4 интенсивность потока данных уменьшается в п-т раз, а в подзадаче Р5 уменьшается в к раз. Таким образом, при «=20 интенсивность потока данных меняется более чем в 400 раз, а при п= 100 - более чем в 10000 раз.

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

распараллеливания базового подграфа составит 1 = ^, где А - объем требуемых

аппаратных затрат на реализацию базового подграфа задачи. Объем аппаратных затрат А можно определить по формуле

I* I

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

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

коэффициент сокращения аппаратных затрат составит г = i.

Традиционно для сокращения аппаратных затрат А на реализацию базового подграфа задачи выполнялась /--кратная редукция числа базовых подграфов ft всех

подзадач Р{. Лг = £

/

//(р). Однако этот прием применим, если выполняется условие

V/: / > г. В противном случае редукция считалась невозможной.

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

/-1 ¿1

где К, — число операций базового подграфа подзадачи Р,\ pi - разрядность обрабатываемых операндов; vi — тактовая частота работы вычислительной структуры подзадачи Р,; Б, - скважность потока данных на входе подзадачи базового подграфа

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

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

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

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

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

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

и

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

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

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

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

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

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

затрачиваемый на аппаратную реализацию базового подграфа р подзадачи Р, можно

к

оценить по формуле N{p) = ^N(0,).

/-1

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

Объем hr{P) редуцированной вычислительной структуры подзадачи Р можно

( *

рассчитать по формуле Nr(P) = f-

±N(p,) + N(C)

, где N(C) - объем аппаратных затрат

на реализацию коммутационного оборудования редуцированного базового подграфа подзадачи Р.

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

определяться отношением 2 ■ —. Аппаратные затраты на реализацию коммутационного

оборудования можно рассчитать по формуле Ы(С] = 2-(К1г)-р И(МХ,), где ЩМХГ) -объем аппаратного ресурса на реализацию г-входового коммутатора, р - разрядность операндов.

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

Если множество математических операций О,, / = 1Д базового подграфа подзадачи Р выполняет преобразования над р-разрядными операндами и каждое вычислительное устройство, реализующее математическую операцию, - /»-разрядное, то сокращение числа одновременно обрабатываемых разрядов операнда в г раз для каждой операции 0( приведет к соответствующему падению производительности вычислительной структуры. Однако уменьшение аппаратных затрат на реализацию математических операция происходит нелинейно.

Объем аппаратного ресурса Л'(0,) на реализацию редуцированного по разрядам (секционированного) устройства, выполняющего математическую операцию О,, можно

оценить по формуле N'(0,)-<р(0„р,г)-N(Oj) + N(D), где Лг(0/) - объем аппаратных затрат на реализацию одноразрядной операции преобразования данных; N(D) -аппаратные затраты на дополнительное оборудование для последовательно секционированного устройства; <р(0„р,г) - функция, определяющая коэффициент аппаратных затрат на реализацию определенной математической операции £),. Метод редукции по разрядности выполняемых операций целесообразно применять, если обрабатываются данные в формате с фиксированной запятой.

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

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

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 представлены показатели по аппаратным затратам на реализацию всех подзадач исходного и редуцированных базовых подграфов задачи докинга после первой и второй итераций редукции производительности. Для простоты понимания аппаратные затраты на реализацию каждой подзадачи условно рассчитываются в количестве задействованных вычислительных устройств, реализующих различные математические операции в стандарте 1ЕЕЕ754.

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

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

Таблица. 1

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

Подзадача

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

до редукции

Р1

Р2

РЗ

Cross

Мш а

Мщ <1

Мт

Rotate

Rotate translate

Е grid

Е es

Е vdw

Е tors

Р4

Р5

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

15

160

54

76

84940

4230

10600

258700

517400

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

1-я итерация

15

18

19

760

26

53

416

832

1320

40019

917518

51

48

2248

2-я

итерация

15

18

19

500

12

53

208

416

51

48

1350

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

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

На рис. 3 приведены следующие обозначения: А1} и А2] - адреса первого и

второго кортежей параметров, выбираемых из массива МР={<а;,аг.....ак>,,

<а!'а2.....ак>2,--,<0-1,0.,.....ак>ь), лучших кортежей, которым соответствуют

минимальные значения энергий связывания Ел\ РагеЫи Рагепй) - первый ,,</.' к>] и второй «х*21,аА22,...,аА\>1 кортежи параметров, выбранные из массива МР по адресам А1} и Л2]\ СИЩ - кортеж параметров <а'1,а'2,...,а'к>, сформированный из РагепИ) и Рагеы2/, <х',у',г'>„- исходные координаты атомов лиганда; <х',у',г> "„ - координаты атомов лиганда, модифицированные с учетом параметров <а'/,а'2, ...,«'*>.

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

А-!33+6п тактов

тактовая

частота %

Parentlj Parent2j Child] <aual...,ai>

T-П_Л_П_Г.. .-TLTLF...

ж>-

-ООО •••О-...

о-...

Рис. 4. Временная диаграмма формирования параметров <a',,al2....,a\> В основном цикле определения оптимальной конфигурации лиганда процедура Crossover формирует два случайных адреса А1, и А2Р по которым из массива MP считываются кортежи параметров Parent l,=<cf' i.of и

Pareni2j=<ctt2J,ai2!,...,o(i2ii>j (см. рис. 4). Затем в процедуре Crossover по алгоритму

диффузионного кроссовера формируется новый кортеж СЫЦ=<а',,а'2.....а'к>. Путем

случайной модификации параметров Childj в процедуре Mutate формируется новый кортеж параметров <a',,a'2,...,aik>. Аналогичным образом формируются информационные потоки для остальных подзадач. На рис. 5 для подзадачи Р2 представлена временная диаграмма расчета декартовых координат всех атомов, лиганда с учетом параметров преобразования <а' ¡,а'2,...,а'к>.

_t\=133+6n тактов_

_Р_П_Г1Х~.. .лиги. .n-TLTLT.. .|~1_Л_П_Г...

тактовая частота <as,aj,...lail> o¡J,¿>n

<j20,f20,j20>

... <§2КЗ>—• •'

••• OGO<"<3x®S^" а____

ooo»;. • • в®©-« • • joo-o ••«

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

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

Для сравнения скорости решения задачи докинга на базовом модуле РВС «Орион» с современными кластерными вычислительными системами было проведено исследование времени докинга тестовых выборок программой SOL на вычислительном

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

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

48 51 53 п

Рис. 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 г. http://digital-mag.tti.sfedu.ru. Выпуск №4(6), 2011. - С.30-46;

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

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

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

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

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

Формат 60x84'"®. Бумага офсетная. Печать офсетная. Усл. п.л. -1,4. Уч.-изд л. -1,1.

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

ГСП 17А, Таганрог, 347928, Некрасовский, 44 Типография Технологического института Южного федерального университета в г. Таганроге

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.

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

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

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

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

1.5. Выводы.

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

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

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

2.3. Метод синтеза параллельно-конвейерных программ на основе редукции по разрядности обрабатываемых операндов.

2.4. Метод синтеза параллельно-конвейерных программ на основе редукции по скважности и частоте.

2.5. Методика синтеза параллельно-конвейерных программ на основе многокритериальной редукции.

2.6. Выводы.

3. РЕШЕНИЕ ЗАДАЧИ ДОКИНГА НА РВС В ЕДИНОМ ВЫЧИСЛИТЕЛЬНОМ КОНТУРЕ.

3.1. Описание математической модели задачи докинга.

3.2. Анализ вычислительной структуры исходного информационного графа задачи докинга.

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

3.4. Экспериментальные исследования.

3.5. Выводы.

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

Альтернативой кластерным системам являются активно развиваемые в настоящее время реконфигурируемые вычислительные системы [4, 5] (РВС), построенные на программируемых логических интегральных схемах (ПЛИС) типа FPGA (Field Programmable Gâte Array) [6]. FPGA представляет собой матрицу логических вентилей, реализующих базовые двоичные операции AND, NAND, OR, NOR и XOR, а также могут дополнительно содержать блоки, аппаратно поддерживающие высокоскоростные интерфейсы ввода-вывода, блоки встроенной памяти и блоки цифровой обработки сигналов. Благодаря возможностям программирования на ПЛИС FPGA гибкой и сложной логики, РВС с успехом применяются для решения сильносвязанных задач различных проблемных областей науки и техники и демонстрируют при этом линейный рост производительности при увеличении аппаратного ресурса. Это достигается за счет того, что в РВС каждый функциональный блок активно используется при решении задачи и при этом аппаратно реализуется множество каналов связи. Данное обстоятельство избавляет от таких проблем, свойственных кластерным системам, как задержки при межпроцессорном обмене или при обращении к общей памяти.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- НИР «Исследование и разработка методов и средств технологии суперкомпыотерного молекулярного моделирования на базе реконфигурируемых вычислительных систем» (шифр 2008-04-1.4-15-05-001, 2009), №ГР01200853499;

- ОКР «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» по государственному контракту №02.524.12.4002 от 20.04.2007 г. на выполнение опытно-конструкторских работ, шифр «Большая медведица», №ГР 01.2.007 05707;

- НИР «Принципы и методы программирования реконфигурируемых многопроцессорных вычислительных систем» №ГР 0120.085.00115, Ростов-на-Дону, ЮНЦ РАН, 2009;

- НИР «Разработка научно-технических основ создания многопроцессорных вычислительных систем сверх-петафлопсной производительности и подготовка кадров высшей квалификации в области распределенных вычислений» (шифр 2009-1.1-215-002-013, 2010), №ГР 01200958384;

- ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой элементной базы», шифр «Медведь», выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг.» по госконтракту №02.447.11.1007 от «6» июля 2005 года, №ГР 0122.0510630;

- НИР «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем» (шифр «Маска», 2011), №ГР01201153442.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях: на научно-практической конференции молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (University of Amsterdam, г. Амстердам, Нидерланды, 2012); на седьмой международной научной молодежной школе «Высокопроизводительные вычислительные системы» (Таганрог, 2010); на шестой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2010); на пятой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2009); на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы (МВУС-2009)» (Таганрог, 2009); на международной молодежной научно-технической конференции и пятой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2008)» (Таганрог,

2008); на международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008)» (пос. Кацивели, АР Крым, Украина, 2008); на третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН (г. Ростов-на-Дону, 2007);.

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

3.5 Выводы

1) Выполнен анализ вычислительной структуры задачи докинга. Определены аппаратные затраты на реализацию вычислительной структуры исходного базового подграфа задачи докинга, состоящего из подзадач Р\, Р2, Рз, Р4 и Р5.

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

Основные научные результаты диссертационной работы опубликованы в работах [60, 66-69, 77-78].

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

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

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

Результаты диссертации внедрены в НИВЦ МГУ (г. Москва), НИИ МВС ЮФУ (г.Таганрог), в.ч. 26165 (г. Москва), НИЦ ФГУП «18 ЦНИИ» МО РФ (г. Курск).

1. Гергель, В.П. Технологии построения и использования кластерных систем / Интернет университет информационных технологий intuit.ru -электронный ресурс. http://www.intuit.ru/department/supercomputing/tbucs/

2. Слуцкин, А.И. Направления развития отечественных высокопроизводительных систем. Текст. / А.И. Слуцкин, Л.К. Эйсымонт // «Открытые системы». М., 2004. - № 5.

3. Воеводин, Вл.В. «Вычислительное дело и кластерные системы» Текст.: монография / Вл.В. Воеводин, С.А. Жуматий. М.: Изд-во МГУ, 2007. -150 с.

4. Каляев, A.B. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений Текст.: монография /

5. A.B. Каляев, И.И. Левин; под ред. A.B. Каляева. М.: Янус-К, 2003. - 380 с.

6. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемьте мультиконвейерные вычислительные структуры. Ростов н/Д: Изд-во ЮНЦ РАН, 2008. - 320 с.6. http://ru.wikipedia.org/wiki/FPGA

7. Кластеры на многоядерных процессорах Текст. / И.И. Ладыгин, A.B. Логинов, A.B. Филатов, С.Г. Яньков. М.: Издательский дом МЭИ, 2008. -112 с.

8. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. Москва: Радио и связь, 1981 - 208 с.

9. Бурцев B.C. Выбор новой системы организации выполнениявысокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ / Труды академика

10. B.C. Бурцева "Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ" // ИВВС РАН, М„ 1997.

11. En Route to Petaflop Computing Speed: Introducing the Cray XI Supercomputer. Cray Inc., 2002.

12. R. Partridge. Cray Launches XI for Extreme Supercomputing. D.H. Brown Associates.

13. Корнеев В. Эволюция микропроцессорных архитектур / Открытые системы , № 04, 2000/13. http://www.cray.com/

14. Суперкомпьютеры для графовых задач Текст. / А.Семенов, А.Фролов, А. Никитин, В. Кабыкин // Открытые системы.СУБД. Выпуск №07/2011.15. http://www.clearspeed.com/

15. ClearSpeed Advance е620 Accelerator. ClearSpeed Technology, Product Brief, 2007.17. http://www.3dnews.ru/cpu/cell18.http://www.ixbt.com/news/hard/index.shtml?l 1/24/47

16. Архитектура фон Неймана, реконфигурируемые компьютерные системы и антимашина Текст. / Л.Черняк // Открытые системы.СУБД. -Выпуск №06/2008.20. http://ru.wikipedia.org/wiki/WEIZAC

17. Estrin G. Organization of computer system: the fixed plus variable structure computer // Proc. Western Joint Computer Conf. 1960. - N5. - P. 33-40.22. http://ru.wikipedia.org/wiki/DEC23. http://ru.wikipedia.org/wiki/DEC PDP

18. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. Новосибирск: Наука, 1978 - 320 с.

19. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966-308 с.26. http://ru.wikipedia.org/wiki/MHHCK-222

20. Каляев А.В. Многопроцессорные системы с распределенной памятью, универсальной коммутацией и программируемой структурой микропроцессоров. Электронное моделирование. - Киев, 1979, № 1. - с.31 -41.

21. Каляев, A.B. Перенастраиваемые цифровые структуры на основе интегрирующих процессоров Текст.: монография / А.Г. Алексеенко, A.B. Каляев, В.И. Лукиенко и др. Под ред. A.B. Каляева. М.: Радио и связь, 1982.-368 с.

22. Энциклопедия ТРТУ. Электронный ресурс http://pitis.tsure.ru/pdf/inst.pdf30. http:// www.altera.com31. http:// www.xilinx.com

23. Пряхин В.Н. Обзор отечественных суперкомпьютеров последнего десятилетия. М.: «Мир ПК», № 09, 2010

24. Левин, И.И. Структурно-процедурное программирование. Тезисы докладов Международой научной конференции "Искусственный интеллект2000", п. Кацивели, 2000. С. 148-150.

25. Воеводин, В.В. Параллельное программирование Текст.: монография / В.В. Воеводин, Вл.В. Воеводин. С-Пб. Изд-во «БХВ-Петербург», 2002.

26. Зотов В.Ю. Программирование встраиваемых микропроцессорных систем на основе плис фирмы Xilinx. М.:Горячая линия - 2006. - 520 е., ил.51. http://ru.wikipedia.org/wiki/Message Passing Interface52. http://www.mitrionics.com/

27. Mitrion Users' Guide 2.0.3-001

28. Каляев A.B. Многопроцессорные вычислительные системы с программируемой архитектурой. М.: Радио и Связь, 1984. 240 с.

29. Романов А.Н., Кондакова О.А., Григорьев Ф.В. и др. Компьютерный дизайн лекарственных средств: программа докинга SOL // Вычислительные методы и программирование, 2008. Т. 9. - С. 213-233.

30. Meng ЕС, Shoichet ВК, Kuntz ID (2004). «Automated docking with grid-based energy evaluation». Journal of Computational Chemistry 13 (4): 505-524.

31. Morris GM, Goodsell DS, Halliday RS, Huey R, Hart WE, Belew RK, Olson AJ (1998). «Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function». Journal of Computational Chemistry 19 (14): 1639-1662.

32. Большая советская энциклопедия: В 30 т. М.: "Советская энциклопедия", 1969-1978

33. Системы параллельной обработки: Пер. с англ./Под ред. Д. Ивенса. -М.: Мир, 1985.-416 е., ил.

34. Mago, G. A. 'A network of microprocessors to execute reduction languages' Int. Journ. Of Computer and information Sciences, 8,5 and 8,6 (1979).

35. Параллельные вычислительные системы. Головкин Б.А. М.: Наука. Главная редация физико-математической литературы, 1980, 520 е., ил.

36. Коуги П.М. Архитектура конвейерных ЭВМ. Перевод с английского Peter M. Kogge IBM Federal Systems Division M. Радио и Связь 1985г. 358с.

37. Сорокин, Д.А. Решение задач с существенно-переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах Текст. /

38. Д.А. Сорокин, А.И. Дордопуло, И.И. Левин, А.К. Мельников // Вестник компьютерных и информационных технологий. М.: Машиностроение, 2012. - №2. -С.49-56.

39. Сорокин, Д.А. Реализация докинга для молекулярного моделирования на реконфигурируемых вычислительных системах Текст. / Д.А. Сорокин, А.И. Дордопуло, И.И. Левин // Известия ЮФУ. Технические науки. Таганрог: Изд-во ТТИ ЮФУ, 2011. - №7. - С. 217-224,

40. Van Court Т. FPGA acceleration of rigid molecule interactions / T. Van Court, Y. Gu, M. Her-bordt // Int. Conf. Meld Programmable Logic and Applications (FPL 2004). -Antwerpen, Belgium, 2004. P. 862-867.

41. Van Court Т., Gu Y., Mundada M.C., Herdbordt M.C. Rigid molecular4 docking: FPGA recinfiguration for alternative force laws //J Appl. Signal Processing v. 2006, 2006. -P.l-10.

42. Herdbordt M.C., Gu Y., Van Court Т., Model J., Sukhwani В., Chiu M. Computing models for FPGA-based accelerations with case studies in molecular modeling // Porcced. of the Reconfigurable systems summer institute (RSSI 2008), 2008.

43. Sukhwani B. Acceleration of a production rigid molecule docking code / B. Sukhwani, M. Herbordt // Int. Conf. Field Programmable Logic and Applications (FPL 2008). Heidelberg, Germany, 2008. - P. 341-346.

44. Sukhwani В., Herdbordt M.C. FPGA accelaration of rigid-molecule docking codes // IET Computers & digital techniques (ACM-TRETS), 2009 (accepted for publication).82. http://en.wikipedia.org/wiki/Bitonicsorter

45. Левин И.И., Пономарев И.М. Структурная реализация сортировки массивов на основе сети Батчера // Искусственный интеллект, №3, 2004 г., с. 198-202.

46. Антонов A.C. Параллельное программирование с использованием технологии MPI: Учебное пособие. М.: Изд-во МГУ, 2004. - 71 с.

47. Воеводин В.В. Математические основы параллельных вычислений.- М.: МГУ, 1991.-345 с.

48. Гук М. Ю. Аппаратные средства IBM PC. Энциклопедия. — Питер, 2006. — 1072 с.

49. Касперски К. Техника оптимизации программ. Эффективное использование памяти. — СПб.: БХВ-Петербург, 2003. — 464 с.

50. РЕДУКЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР ПРОЦЕДУР ПОДЗАДАЧИ Р1 БАЗОВОГО ПОДГРАФА ЗАДАЧИ ДОКИНГА

51. СОРОКИН ДМИТРИЙ АНАТОЛЬЕВИЧ

52. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ С ПЕРЕМЕННОЙ ИНТЕНСИВНОСТЬЮ ПОТОКОВ ДАННЫХ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ0513.11 Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей

53. Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:доктор технических наук, профессор Левин И.И.

54. ПЛ. РЕДУКЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР ПРОЦЕДУР ПОДЗАДАЧИ Р} БАЗОВОГО ПОДГРАФА ЗАДАЧИ ДОКИНГА

55. Анализ вычислительной структуры подзадачи Мша показал, что выполнять дальнейшую редукцию можно только по скважности Бма- Новое значение коэффициента редукции составит г/=га//Ма=30,5. При увеличении скважности Бма в раз получим Жма '-2,098-109 бит/сек.

56. Получим общий коэффициент редукции вычислительной структуры Мша гм"=1¥ма/ 1Ума"=610,1, что удовлетворяет заданным требованиям.

57. Производительность конвейерной вычислительной структуры подзадачи

58. Анализ вычислительной структуры подзадачи Мшс1 показал, что выполнять дальнейшую редукцию можно только по скважности Новоезначение коэффициента редукции составит г/=га//мсГ203,33. При увеличении скважности Sm<i в г/ раз, получим Жш-7,1 • 108 бит/сек.

59. Получим общий коэффициент редукции вычислительной структуры Mutd rMf- WMJWMd=& 10, что удовлетворяет заданным требованиям.

60. Производительность конвейерной вычислительной структуры подзадачи

61. Получим общий коэффициент редукции вычислительной структуры Mutq rMq"=WMq/WMq"=610, что удовлетворяет заданным требованиям.

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

63. СОРОКИН ДМИТРИЙ АНАТОЛЬЕВИЧ

64. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ С ПЕРЕМЕННОЙ ИНТЕНСИВНОСТЬЮ ПОТОКОВ ДАННЫХ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ0513.11 Математическое и программное обеспечение вычислительных машин,комплексов и компьютерных сетей

65. Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:доктор технических наук, профессор Левин И.И.

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