Введение к работе
Актуальность темы. Существует два подхода к проектированию устройств вычислительной ники. Первый базируется на реализации принципов, сформулированных в 1945 году Джоном фон маном. К основным из них относятся представление алгоритма обработки информации в виде по-довательности управляющих команд и поочередному выполнению этих команд одними и теми же ническими средствами. Другими словами, при решении различных задач аппаратные средства ком-тера остаются неизменными. Изменяется последовательность команд, то есть алгоритм работы. Ис-ьзование этих принципов позволило разработать универсальное устройство способное решать ши-ий круг практических задач, однако последовательный принцип решения приводит к значительным менным затратам, что ограничивает применение таких устройств для решения задач в реальном штабе времени.
Второй подход предполагает разработку для каждой конкретной задачи специализированного ислителя, аппаратная структура которого ориентирована на выполнение заданного алгоритма. В м случае возможны распараллеливание вычислительной процедуры и его конвейеризация, что зна-ельно сокращает временные затраты на получение конечного результата. Вместе с тем такое устрой-о теряет универсальность и его применение оправдано только в тех случаях, когда алгоритм работы ройства неизменен в течение всего жизненного цикла изделия. Существует целый ряд задач, напри-задачи связанные с навигацией или управлением специализированным оборудованием, мобильны-объектами и т.д., для которых такое решение является оправданным. Однако проектирование такого ройства, особенно с применение современной технологии БИС и СБИС является весьма дорого-ящим и оправдано только при больших сериях выпуска изделий, что не характерно для указанного сса задач.
Значительно сократить затраты и время проектирования можно при построении таких устройств рименением ПЛИС. Данный класс ИС позволяет в короткие сроки реализовать практически любой оритм обработки информации. Этому способствует наличие соответствующих САПР электронных м, включающих большое число стандартных мегафункций, предназначенных для проектирования онченных узлов устройства. В этом случае разработчику нет необходимости полностью разрабаты-ь схему всего устройства. Достаточно собрать его структуру из уже имеющихся блоков.
В стандартных библиотеках таких САПР, например САПР Quartos II фирмы Altera, существуют гафункции, предназначенные для аппаратной реализации основных математических операций. Одна-их применение не во всех случаях позволяет получить устройство оптимизированное по времени вы-сления и требуемым аппаратным ресурсом ПЛИС. К тому же в стандартном наборе отсутствуют ме-|>ункции, предназначенные длячвычисления специальных функций, таких как показательные, лога-фмические и тригонометрические функции. Известные попытки реализовать вычисление таких нкций сводятся к использованию случайных алгоритмов, не оптимизированных применительно к
реализации на ПЛИС. К тому же при их разработке не учитываются вопросы, связанные с обеспечени требуемой точности вычисления, а именно вопросы минимизации остаточной погрешности, погреші стей округления и действия. Вследствие этого вопросы, связанные с разработкой алгоритмов вычиа ния специальных математических функций, ориентированные на разработку мегафункций стандарти библиотеки известных САПР электронных схем являются весьма актуальными.
Целью работы является разработка алгоритма нахождения численного значения функц ехр(х) предназначенного для реализации в виде стандартной мегафункций САПР ПЛИС, обеспс вающего компромисс между быстродействием, точностью вычисления и затратами материальных | сурсов на реализацию и разработка на его основе комплекса программ для его практической реали ции, учитывающего все виды погрешностей вычисления.
Задачи исследования. Для достижения поставленной цели необходимо решить следующие за; чи:
Выявить для известных методов нахождения численного значения функции ехр(х) завн мость точности вычисления от вида используемой аппроксимации, диапазона изменения ; гумента, и определить для каждого случая состав и количество выполняемых математическ операций.
Для различных типов ПЛИС проанализировать существующие алгоритмы выполнения ( новных математических операций, выявить зависимости аппаратных затрат и времени в полнения операции от разрядности аргументов и определить оптимальные диапазоны прт нения различных алгоритмов вычисления.
Разработать алгоритм вычисления функции ехр(х) для произвольного диапазона изменен аргумента и произвести его оптимизацию с точки зрения минимизации требуемых аппар* ных ресурсов ПЛИС и времени счета.
- Исследовать погрешности вычисления функции ехр(х), обусловленные использовани
разработанного метода реализации.
Разработать пакет прикладных программ необходимый для разработки мегафункций вьічі ления функции ехр(х) и проанализировать полученные программы с точки зрения обесі чения требуемой точности и аппаратных затрат ПЛИС на их реализацию. Научная новизна: К новым результатам проведенных исследований по теме диссертации оті сятся:
Определение областей применения различных алгоритмов выполнения операции матема ческого умножения, оптимальных с точки зрения быстродействия и затрат материальных сурсов ПЛИС.
Алгоритм вычисления функции ехр(х), обеспечивающий при получении требуемой ТОЧ1 ста и минимизации необходимых аппаратных ресурсов ПЛИС предельное снижение сумм
ного времени получения результата.
Оптимальное для разработанного алгоритма соотношение между разбиением диапазона изменения аргумента функции на расчетные области и используемым методом замен переменных в многочленах Чебышева, обеспечивающее при заданной степени аппроксимирующего многочлена минимизацию погрешности вычисления функции.
Функциональные зависимости точности вычисления функции ехр(х) по разработанному алгоритму от числа разрядов исходного аргумента, учитывающие остаточную и начальную погрешности, а так же погрешность действия для различных методов замены переменных в многочленах Чебышева.
Практическая значимость проведенных исследований заключается в следующем:
- Разработан комплекс программ, предназначенных для аппаратного вычисления функции
ехр(х) с помощью ПЛИС, обеспечивающих как минимизацию аппаратных ресурсов, так и
время вычисления, реальное быстродействие которых определяется только возможностями
используемой элементной базы.
Предложена процедура построения параллельной канонической формы графа вычисления степенного многочлена, и получены выражения определяющие зависимость длины его критического пути от степени используемого многочлена.
Разработана программа для аппаратной реализации на ПЛИС операции математического умножения чисел большой разрядности, применение которой обеспечивает минимизацию необходимых аппаратных ресурсов ПЛИС и времени вычисления.
- Предложены рекомендации по выбору соотношения между разрядностями представления ар
гумента и используемых при вычислении коэффициентов степенного многочлена, обеспечи
вающего минимизацию погрешности вычисления.
Для основных математических функций найдены соотношения между требуемыми аппаратными ресурсами ПЛИС, быстродействием и разрядностью используемых аргументов. Достоверность полученных результатов, выводов и рекомендаций, сформулированных в ра-е, подтверждается использованием для их получения апробированного математического аппарата и ндартных средств формального описания цифровых устройств, а так же результатами вычислитель-о эксперимента, выполненного с использованием общепринятых в промышленности систем автома-ированного проектирования электронных средств (EDA), а именно, системы проектирования Quartus (шрмы Altera.
Основные положения, выносимые на защиту:
- Оптимизированный применительно к реализации на ПЛИС алгоритм выполнения операции
арифметического умножения, и рекомендации по области его применения, гарантирующие
относительно стандартных алгоритмов, реализованных в САПР Quartus II фирмы Altera как
уменьшения требуемых на реализацию аппаратных ресурсов ПЛИС, так и сокращение вр менны вычисления. - Алгоритм построения аппроксимирующего многочлена высокой степени, предназначен!!! для численного вычисления экспоненциальной функции, обеспечивающий при реализации ПЛИС оптимальное разбиение аргумента на расчетные интервалы, что при произволык диапазоне изменения аргумента и требуемой точности вычисления позволяет минимшир вать как аппаратный затраты, так и время вычисления.
Пакет прикладных программ, реализующий разработанные алгоритмы и включающий пр граммы для реализации операции арифметического умножения и вычисления зкспонеші альной функции от произвольного аргумента, применение которого позволяет сократить а паратные ресурсы ПЛИС и время вычисления. Апробация работы и публикации
Основные результаты работы докладывались на Международной молодежной научной конф ренции «Гагаринские чтения» 2006 и 2007 годов, III научной международной конференции «Совремс ные проблемы науки и образования», г. Москва, 13-15 мая 2008г, Всероссийской научно-техническ конференции «Новые материалы и технологии», Москва 11-13 ноября 2008г и международной научи конференции «Технические науки и современное производство», Китай (Пекин), 26 ноября - 4 декаб 2008 г.
Основные результаты работы опубликованы в 9 научных трудах, включая 1 работу [9] опублнк ванную в журнале, рекомендованном ВАК .
Структура диссертационной работы.
Диссертация состоит из введения, 5-й глав, заключения, списка использованных источников приложений. Объем диссертации 185 страниц машинописного текста, приложений 16 страниц, 129 р сунков и 72 таблицы. Список литературы включает 62 наименования.
