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

Актуальность темы

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

Для решения таких вычислительно сложных задач в разумные промежутки времени, в том числе, в режиме on-line часто необходимы сверхвысокопроизводительные системы. Повышение производительности вычислительных систем в последние десятилетия XX века и начале XXI века определялось, прежде всего, прогрессом в микроэлектронной технологии. В то же время известно, что ресурс повышения производительности за счет одновременного выполнения операций во много раз превышает аналогичный ресурс за счет развития микроэлектронной технологии.

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

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

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

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

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

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

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

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

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

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

Для достижения указанной цели должны быть решены следующие научные задачи.

1) Проведен анализ методов и моделей одновременных вычислений.

2) Разработаны методы оценки эффективности реализации параллельных и конвейерных вычислений.

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

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

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

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

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

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

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

Практическая значимость. Использование созданных методов и программных средств позволяет повысить производительность при решении ряда вычислительно сложных задач в 1,5 — 2 раза.

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

Созданные методы и программные средства обеспечивают расширение класса решаемых задач.

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

Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИОКР «Фактор», «Начинка», «Радикал», «Прокол-Б1», выполняемыми ЗАО «Эврика» и ОАО «СКБ Топаз», а также при разработке специального программного обеспечения в войсковой части 26 165. Кроме того, созданные программные средства были использованы при разработке и отладке программно-технических средств перегрузочной машины ядерного реактора, выполняемых в рамках ОКР «Контроль», что подтверждается соответствующими актами внедрения.

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

— Научная международная школа «Высокопроизводительные вычислительные системы (ВПВС-2004)», Москва-Ростов-на-Дону-Таганрог, 2004 г.;

— Всероссийская Научно-Техническая Конференция «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 2004 г.;

— Международная конференция «Интеллектуальные и многопроцессорные системы-2004», Украина, пос. Кацивели, 2004 г.

Наиболее важными из публикаций являются:

1) Иванов А. И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Высокопроизводительные вычислительные системы (ВГТВС-2004). Материалы научной международной школы. — Таганрог: Изд-во ТРТУ, 2004. — С. 75−79.

2) Иванов А. И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. — Донецк: Наука осв1та, 2004. — Т 4. — С. 15−26.

3) Иванов А. И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. — Таганрог: Изд-во ТРТУ, 2004. -Т 1. — С. 101−106.

4) Иванов А. И., Коновальчик П. М., Левин И. И., Малеванчук А. Д. Модульно-наращиваемые многопроцессорные вычислительные системы для решения задач математической физики // Материалы Всероссийской Научно-Технической Конференции «Параллельные вычисления в задачах математической физики». — Ростов-на-Дону: Изд-во ЮГИНФО РГУ, 2004. -С. 77−83.

5) Иванов А. И., Коновальчик П. М., Левин И. И., Малеванчук А. Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. — Таганрог: Изд-во ТРТУ, 2004. — Т 1. — С. 34−38.

6) Иванов А. И., Коновальчик П. М., Левин И. И., Малеванчук А. Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Высокопроизводительные вычислительные системы.

ВПВС-2004). Материалы научной международной школы. — Таганрог: Изд-во ТРТУ, 2004. — С. 44−49.

7) Иванов А. И., Коновальчик П. М., Левин И. И., Малеванчук А. Д. Многопроцессорная система, адаптируемая под информационную структуру задач различных классов // Искусственный интеллект. — Донецк: Наука i освгга, 2004.-ТЗ.-С. 140−148.

8) Иванов А. И., Коновальчик П. М., Левин И. И., Малеванчук А. Д. Макрообъектная вычислительная система // Тематический выпуск «Интеллектуальные и многопроцессорные системы». Известия ТРТУ. -Таганрог: Изд-во ТРТУ, 2004. — С. 28−36.

9. Иванов А. И., Коновальчик П. М. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач // Информационные технологии. Москва, 2004. — № 12. — С. 38−43.

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

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

3.4. Выводы.

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

2) Проектирование вычислительных устройств на основе ПЛИС требует рационального сочетания следующих принципов:

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

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

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

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

4) В состав средств описания входят: графический редактор описания фрагмента конвейерного вычисления, программы анализа синхронизации, программа оптимизации информационного графа конвейера, а также транслятор конвейерного графа в УЬГОЬ-описание.

Средства исполнения, прежде всего, включают в себя компоненты ядра встраиваемой ОС.

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

3) Показано, что при конвейерной реализации вычислений на ПЛИС основными препятствиями повышению производительности являются:

— условные операторы;

— обратные связи (рекурсии);

— необходимость обработки значительных объемов данных на каждой ступени конвейера;

— большой объем информационно-незначимых пересылок.

4) Для каждого из этих препятствий определены методы преодоления.

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

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

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

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