Введение к работе
Актуальность исследования. Основу одновременных вычислений составляют две широко применяемые формы организации вычислительных систем (ВС) - это конвейерные и параллельные ВС. При этом структура таких ВС должна быть изоморфна информационной структуре задачи, что обеспечивает естественное распараллеливание вычислительных процессов и минимизацию времени заполнения конвейера. Рассматриваемый тип ВС наиболее эффективно применяется при решении вычислительно сложных задач, в которых сочетаются условно независимые и существенно связанные между собой алгоритмы. В то же время, не вызывает сомнения, что создание множества специализированных устройств, решающих единственную задачу, экономически нецелесообразно.
Реализация параллельной формы организации одновременных вычислений требует построения решающего поля, объединяющего множество процессоров. Данный тип ВС наиболее эффективно используется для решения слабосвязанных задач. Однако внутри одной задачи найти полностью независимые участки практически невозможно, а межпроцессорные пересылки, даже при существенном увеличении темпов обмена, которое может дать размещение указанных процессоров в одном кристалле, неизбежно порождают проблемы согласования межпроцессорного взаимодействия, особенно при несбалансированной загрузке процессоров, что ведет к снижению эффективности системы.
Другой проблемой, которая существует при построении гидроакустических систем высокого разрешения, является необходимость работы с изменяемой разрядностью данных внутри вычислительного процесса. Подобные задачи не могут быть напрямую решены конвейерными вычислителями, так как аппаратные затраты на конвейерную реализацию ориентированные на максимальную разрядность чрезвычайно велики. Решение подобных задач на многопроцессорных системах возможно, однако это приводит к колоссальному росту накладных расходов на организацию вычислений, так как требует передачи значительного числа данных от младших процессоров к старшим, а это ведёт к увеличению временных затрат на решение задачи. Подобное увеличение времени решения зачастую делает полученные результаты неактуальными. Путем разрешения этого противоречия представляется организация, обеспечивающая независимость проведения операций при разбиении длинных слов на отдельные фрагменты. Однако простое комплексирование универсальных процессоров и специализированных конвейерных вычислителей в единой системе неэффективно из-за низкой пропускной способности каналов обмена процессорных элементов. Для построения систем с переменной разрядностью набольшая эффективность достигается, если базовые блоки строятся с ориентацией на системы с переменной разрядностью.
Появление программируемых логических интегральных схем (ПЛИС) высокой степени интеграции позволяет реализовывать вычислители, содержащие операционные блоки и простейшие soft-процессоры, с ориентацией по функциям на конкретные задачи.
Однако в настоящее время не существует математических методов и программных средств, которые позволили бы создавать аппаратные программы с реализацией такой конкретной задачи.
Цель работы и задачи исследования. Целью диссертационной работы является разработка методов и средств решения вычислительно сложных задач над данными переменной разрядности за счет создания аппаратных подпрограмм, позволяющих эффективно совмещать конвейерные и параллельные методы одновременных вычислений в одном устройстве, построенном на базе ПЛИС.
Для достижения этой цели в диссертационной работе решаются следующие задачи:
1) проводится анализ и оценка методов и моделей вычислений над данными с переменной разрядностью;
2) разрабатываются алгоритмы решения прикладных задач на основе операционных вычислений с переменной разрядностью;
3) разрабатывается методика организации одновременных вычислений сочетающих параллельные и конвейерные вычисления в едином вычислительном устройстве над операндами, представленных полями, допускающих работу с переменной разрядностью;
4) разрабатываются методы и способы организации основных операционных узлов для вычисления функциональных зависимостей, обеспечивающих высокую скорость получения результатов при работе с полями и допускающих реализацию в базисе существующих ПЛИС.
Методы исследования. При проведении исследований были использованы элементы вычислительной математики, численные методы, элементы теории вычислительных систем, теория графов, теория множеств.
Научная новизна проведенных исследований заключается в разработке новых методов и средств построения систем высокоточной обработки гидроакустических данных для обнаружения подводных объектов и систем картографирования на основе предложенных алгоритмов работы с операндами с изменяемой в процессе вычислений разрядностью.
В процессе работы над диссертацией были получены следующие результаты:
-
Проведен анализ существующих методов решения задачи высокого разрешения и в качестве базового выбран метод собственных векторов, обеспечивающий как высокую точность, так и приемлемую операционную сложность алгоритмов.
-
Выделен базовый набор типовых операций, определена их эффективность по критериям времени выполнения операций/расход оборудования.
-
Разработаны алгоритмы на основе кода "опережающий перенос" для выполнения вычислений над операндами с переменной разрядностью, обеспечивающих оптимальное соотношение время/длина поля операнда.
-
Разработана структура процессорного элемента для МВС, ориентированного на работу с комплексными операндами, с аппаратной и программной поддержкой вычислений над данными с изменяемой разрядностью в коде "опережающий перенос".
Научная ценность. В работе исследованы процессы создания и обработки гидроакустической информации, и на их основе разработаны методы преобразования информации с целью получения более точных данных о подводной обстановке, что является научной основой для создания современных информационных технологий на базе использования средств вычислительной техники в области гидроакустической локации.
Результаты научных исследований создали теоретическую базу, которая позволила перейти к разработке новых устройств вычислительной техники и систем управления в области первичных и вторичных преобразователей цифровой информации, совмещающих организацию параллельных, конвейерных и параллельно - конвейерных вычислений. В отличие от ранее применяемых, разработанные устройства обеспечивают работу в коде «опережающий перенос» над данными с переменной разрядностью, что обеспечило повышение качественных и эксплуатационных характеристик проблемно-ориентированных средств вычислительной техники.
Практическая ценность. В диссертационной работе решена важная научно-техническая задача, заключающаяся в создании новых методов и аппаратных средств, позволяющих повысить:
- точность определения координат подводных объектов до 1 угловой минуты в пределах интервала зондирования от 100 до 1000 м, что обеспечивается методами ориентированными на работу с операндами с переменной разрядностью;
- скорость преобразования информации до уровня, приближенного к реальному или даже ускоренному времени, применением предложенных в диссертационной работе параллельно-конвейерных вычислений в едином операционном устройстве, и обработки на каждом этапе оптимальных по разрядности данных.
Реализация и внедрение результатов работы. Результаты диссертационной работы использовались в НИОКР, выполняемых кафедрой ВТ ТТИ ЮФУ, а так же в учебном процессе по курсу «ПОВС» кафедры ВТ ТТИ ЮФУ, при выполнении ОКР “Диез”, выполненной ФНПЦ ОАО “НПО “Марс” (г. Ульяновск) в 2008 году, а также при разработке СЧ НИР “Афелий-Р” выполняемой ЗАО НТП “Реаконт” (г. Москва).
Достоверность и обоснованность полученных в работе результатов подтверждается полнотой и корректностью исходных посылок, теоретическим обоснованием, непротиворечивостью математических выкладок. Исследования и эксперименты проведены на действующих образцах вычислительных систем, построенных на основе ПЛИС-технологий.
Положения, выносимые на защиту:
1) Впервые предложенные алгоритмы аппаратной реализации операционных устройств обработки данных, обеспечивающих работу над данными с переменной разрядностью в коде «опережающий перенос». Предлагаемый метод обеспечивает работу с полями, разрядность которых может меняться от 16 до 128 разрядов и выше;
2) Разработанные новые методы реализации основных операций на базе ПЛИС, обеспечивающие максимизацию удельной производительности для задач гидроакустического зондирования. В отличие от известных предлагаемые методы совмещают параллельную, конвейерную и параллельно-конвейерную организацию вычислений для основных операций;
3) Новая методика организации одновременных вычислений над операндами представленных полями, которая в отличие от известных методов основана на коде «опережающий перенос» и позволяющая работать над операндами с переменной разрядностью;
4) На основе предложенных алгоритмов и методов реализации операций спроектированы основные операционные устройства, адаптированные к технологии ПЛИС и реализованные в реальном макете гидроакустической системы, разработанного и испытанного в рамках СЧ НИР «Афелий-Р».
Апробация основных идей и результатов исследований проведена на Международных научно-технических конференциях «Интеллектуальные системы (AIS’07) и (AIS’08)» и «Интеллектуальные САПР» (CAD-2007) и (CAD-2008).
Публикации. По материалам диссертации опубликовано 7 печатных работ, из них 1 - опубликована в перечне изданий, рекомендованных ВАК и 2 выступления на российских и международных научно-технических конференциях.
Структура и объем диссертации. Диссертация состоит из введения, трех глав с выводами, заключения, библиографического списка, включающего 77 наименований и двух приложений. Текст изложен на 155 страницах, содержит 43 рисунка и 14 таблиц.
