Моделирование вычислительного процесса, разработка алгоритмов и пакета прикладных программ для вычисления экспоненциальной функции на программируемых логических интегральных схемах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Мо Чжо Чо

• Мо Чжо Чо
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Мо Чжо Чо

Введение.

ГЛАВА 1. Методы вычисления показательной функции.

1 Л.О.бщие свойства показательной функции.

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

1.3.Метод разложения в степенной ряд.

1.3.1 .Исходная формула разложения.

1.3.2.Повышение точности вычисления.

1.4.Методы ортогонального приближения.

1.4.1 .Многочлены Чебышева.

1.4.2.Многочлены Лежандра.

1.5.Метод многочленного приближения.

1 .б.Метод разложения в цепные дроби.

1.7.Метод рациональных приближений.:.

1.8.Метод БВЕ.

1.9.Сравнительный анализ различных методов вычисления.

Выводы по главе 1.56 »■>

ГЛАВА 2. Аппаратная реализация основных математических операций.

2.1 .Реализация операций сложения-вычитания.

2.2.Реализация операции умножения.

2.2.1.Реализация умножителя на логических блоках.

2.2.2.Реализация умножителя с использованием встроенных блоков.'.

2.3.Понятие сложности вычисления произвольной функции f(x).

2.4.Методы быстрого умножения.

2.4.1.Алгоритм умножения методом Карацубы.

2.4.2.Граф алгоритма быстрого умножения.

2.4.3.Программная реализация алгоритма быстрого умножения.

2.5.Сравнение умножителей реализующих мегафункцию lpmmult и метод быстрого умножения.

2.5.1.У множите ль на основе только логических блоков.

2.5.2.Умножитель, использующий встроенные модули.

2.5.3.Временные соотношения метода быстрого умножения.

2.6.Реализация операции деления.

Выводы по главе 2.

ГЛАВА 3.Особенности организации алгоритма вычисления показательной функции.

3.1.Методы сокращения диапазона изменения значения аргумента.

3.2.Методы реализации вычисления степенных функций.

3.3.Алгоритмы вычисления многочленов Чебышева.

3.4.0птимизация алгоритма вычисления функции с использованием многочленов

Чебышева.

3.4.1 .Оптимизация расчетного выражения.

3.4.2.0птимизация метода вычисления.

3.5.Процедура построения графа вычислительного процесса.

Выводы по главе 3.

ГЛАВА 4.Вопросы обеспечения точности вычисления экспоненциальной функции на

ПЛИС.

4.1 .Основные положения.

4.2.Понятие числа верных знаков приближенного числа.

4.3.Правила округления.

4.4.Связь относительной погрешности с числом верных знаков числа.

4.5.Определение погрешности при выполнении основных математических операций.

4.5.1.Определение погрешности суммы.

4.5.2.0пределение погрешности разности.

4.5.3.Определение погрешности произведения.

4.5.4.Определение погрешности частного.

4.5.5. Определение погрешности возведения в степень.

4.5.6. Определение погрешности извлечения корня.

4.6.0пределения количества верных знаков результата.

4.7.0бщая задача определения погрешности вычисления.

4.8.Исследование связи между погрешностями аргументов и вычисляемой функции. 132 4.8.1 .Исходный многочлен Чебышева при j=l и у=х.

4.8.2.Многочлен Чебышева при j=l и у=2х-1.

4.8.3.Многочлен Чебышева при j=l и у=Зх-1.

4.8.4.Многочлен Чебышева при j=2 и у=2х-1.

4.8.5.Многочлен Чебышева при j=2 и у=Зх-1.

4.8.6.Многочлен Чебышева при j=l и у=2,8бх-1.

4.8.7.Многочлен Чебышева при j-2 и у=2,86х-1.-.

4.9.Сопоставительный анализ различных методов аппроксимации.

Выводы по главе 4.

ГЛАВА 5.Практическая реализация алгоритма вычисления.

5.1.Блок схема вычислителя.

5.2.Нахождение числа правильных разрядов результата основных математических операций.

5.2.1 Операция умножения.

5.2.20перация возведения в степень.

5.2.30перация сложения.

5.3.Блок подготовки данных.

5.3.1. Реализация блока подготовки данных на умножителях.

5.3.2 Определение разрядности используемых аргументов.

5.3.3. Реализация блока на сумматоре.

5.4. Блок вычисления ЕХР(х).

5.4.1.Реализация алгоритма 4.8.1 (многочлен Чебышева при j-1 иу=х).

5.4.2.Реализация алгоритма 4.8.2 (многочлен Чебышева при j=l и у=2х-1).

5.4.3.Реализация алгоритма 4.8.3 (многочлен Чебышева при j=l и у=Зх-1).

5.4.4.Реализация алгоритма 4.8.6 (многочлен Чебышева при j=l и у=2.86х-1).

5.4.5.Реализация алгоритма 4.8.4 (многочлен Чебышева при j=2 и у=2-х-1).

5.4.6.Реализация алгоритма 4.8.5 (многочлен Чебышева при j=2 и у=3-х-1).

5.4.7.Реализация алгоритма 4.8.7 (многочлен Чебышева при j=2 и у=2.86-х-1).

5.4.8. Анализ результатов эксперимента.

Выводы по главе 5.

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

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

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

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

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

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

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

По существу ПЛИС [47, 49, 50] является СБИС, содержащей последовательно 1 соединенные матрицы логических элементов И и ИЛИ, допускающие программирование внутренних межэлементных связей, дополнительно укомплектованные триггерными и буферными элементами, причем вид внутренних соединений между ними может задаваться с использованием внешних управляющих сигналов. Таким образом, в ПЛИС принципиально заложена возможность аппаратной реализации любой функции цифровой логики, то есть выполнения произвольного алгоритма обработки входной информации. Емкость современных ПЛИС превышает 10б эквивалентных базовых логических элементов (2И-НЕ), что предполагает аналогичное число внутренних программируемых межсоединений. Очевидно, что программирование такого кристалла не может быть выполнено без применения соответствующих САПР электронной аппаратуры (EDA -Electronic Design Automation).

В настоящее время основными производителями ПЛИС, занимающими до 80% рынка производства и являющимися главными разработчиками идеологии их построения и применения являются созданные в середине 80-х годов фирмы Altera Corporation, Xilinx Inc. и Actel Corporation. Каждая их этих фирм, кроме самих ПЛИС, внедряет и свой EDA продукт, предназначенный для проектирования устройств с применением тех или иных языков описания аппаратуры (IIDL - Hardware Description Languages). При этом значимость EDA составляющей постоянно увеличивается. Существовавший в прошлом веке подход к проектированию, базировавшийся на описании проекта с использованием графического редактора и библиотеки 1 стандартных логических примитивов (простейшие узлы комбинационной и последовательностной логики, такие как мультиплексоры, дешифраторы, счетчики, регистры и т.д.) все больше вытесняется описанием с использованием таких HDL как VHDL Verilog HDL, или специально разработанными фирмами изготовителями языков, учитывающих особенности реально существующей элементной базы. Таким примером является разработанный фирмой Altera язык AHDL (Altera Hardware Description Languages) [46, 48].

Рост сложности ПЛИС привел к тому, что кроме непосредственно фирм изготовителей интегральных схем, вопросами программной поддержки проектирования в настоящее время занимается большое число различных фирм. С целью координации этих работ в 1995 г была создана программа поддержки партнеров-разработчиков мегафункций (Altera Megafunction Partners Program). Это привело к разработке большого числа готовых модулей и мегафункций, предназначенных для реализации стандартных микропроцессоров и микроконтроллеров, устройств обслуживания различных шин (например, ISA и PCI), сетевых контроллеров, устройств, реализующих быстрое преобразование Фурье, фильтры конечной и бесконечной импульсной характеристики (КИХ и БИХ-фильтры) и т.д.[1].

Стандартные пакеты EDA содержат так же мегафункции, позволяющие реализовать основные математические операции. На рис.В.1 приведен перечень мегафункций, содержащихся в САПР Quartus II фирмы Altera и предназначенных для выполнения основных математических операций. Здесь присутствуют все основные математические операции (сложение, вычитание, умножение, деление, извлечение корня, модуль и т.д.)

В й Installed Plug-Ins Altera SO PC Builder В fil arithmetic

7] ALTACCUMULATE /j ALTFPMULT J ALTMEMMULT A ALTMULT.ACCUM (MAC) /] ALTMULTADD A ALTSQRT LPMABS A LPMADDSUB 7} LPMCOMPARE A LPMCOUNTER A LPMDIVIDE

7) LPMMULT

PARALLELEDD [£] ARM-Based Excalibur i±j gates в Ш 1/0

EE! §Й memory compiler

2) SignalTap II Logic Analyzer W fcil storage ffl Ш IP MegaStore

Рис.В.1

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

Из сказанного следует, что ПЛИС является идеальной элементной базой для разработки устройств, основными требованиями к которым наряду с высоким быстродействием является обеспечение высоких массо-объемных показателей, высокой надежности и малой стоимости. При этом обеспечивается крайне короткий и полностью автоматизированный цикл проектирования. Проиллюстрируем сказанное заимствованным из [2] типовым маршрутом проектирования устройства цифровой обработки сигнала (ЦОС) на основе ПЛИС фирмы Xilinx.

1. Используя программный продукт компании Math Works (MATLAB и Simulink) разрабатывается и проверяется модель устройства ЦОС;

2. Используя программный продукт Xilinx SystemGenerator, генерируется синтезируемое HDL описание, соответствующее функциональным возможностям, описанным в Simulink/System модели;

3. Используя средство синтеза САПР Xilinx ISE, компилируется проект и генерируется программный код для ПЛИС.

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

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

Применительно в традиционным ЭВМ значения элементарных математических функций вычисляются с использованием стандартных подпрограмм. В них, как правило, реализуется одно из известных разложений требуемой функции в степенные ряды вида [10. 14]: п 0

При этом сам алгоритм вычисления строится, как правило, по схеме Горнера [15]: п f(x) = Yuan =(-(arn -x + a^-x + .-. + a^-x + ciQ . о

Суммарное время требуемое для вычисления функции приблизительно можно оценить выражением: h -m-{tmult+tadd)^ где: ш - степень полинома; tmuit - время выполнения операции умножения; tadd " вРемя выполнения операции сложения-вычитания.

Для вычисления значение у = л[х обычно используется итерационный метод Герона: r<+i=°-5{yt+/y,) причем используемые алгоритмы различаются только выбором начального приближения у0 .

Существуют итерационные методы и для вычисления функций ехр(х) и 1п(х) [16]. Вычисление выполняется в два этапа. На первом этапе аргумент функции 1п(х) представляется в виде: 1

П& + 5.-2-')' i= 1 а функции exp(x) в виде: i где: n - разрядность вычисляемой функции;

- коэффициент, принимающий значения 0 и 1 или-1,+1.

На втором этапе, на основании найденного на предыдущем этапе набора значений , определяется величина вычисляемой функции. Это выполняется либо путем суммирования слагаемых вида //?(l + • 2-'где i-oe слагаемое соответствует i-ому произведению первого этапа, либо с помощью вычисления произведения (l + *2-/ ], где i-ый член произведения соответствует i-ому слагаемому, используемому на первом этапе. Каждый этап вычисления выполняется за п шагов и представляет собой итерационный процесс, состоящий в построении последовательности xl — f{xtj) с шагом итерации 5,- = хг- — Хг|. Каждая итерация первого этапа состоит в определении значения ^ на основании знака 8г-. На каждой итерации второго этапа определяется очередной член последовательности х{, сходящийся к вычисляемой функции.

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

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

В [17,18] описаны алгоритмы вычисления тригонометрических функций sin(x), cos(x), arcsin(x) и arctg(x) с использованием ПЛИС. Рассмотрены различные виды аппроксимации этих функций степенными рядами и применение табличного метода с линейной интерполяцией. Проведен сопоставительный анализ данных методов с точки зрения компромисса между получением максимального быстродействия, точностью вычисления и затратам аппаратных ресурсов на реализации. Приведены последовательно-параллельные графы рассмотренных алгоритмов. Показано, что наиболее рациональным при вычислении функций sin(x), cos(x), arctg(x) является табличный метод с линейной интерполяцией.

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

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

Следует отметить, что работы, аналогичные [17, 18] применительно к функциям ехр(х) и 1п(х) полностью отсутствуют.

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

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

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

- Исследовать погрешности вычисления функции ехр( х), обусловленные 1 использованием разработанного метода реализации. I

- Разработать пакет прикладных программ необходимый для разработки мегафункции

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

Научная новизна: К новым результатам проведенных исследований по теме

11 диссертации относятся:

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

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

Апробация работы и публикации

Основные результаты работы докладывались на Международной молодежной научной конференции «Гагаринские чтения» 2006 и 2007 годов, III научной международной конференции «Современные проблемы науки и образования», г.Москва, 13-15 мая 2008г, Всероссийской научно-технической конференции «Новые материалы и технологии», Москва 11-13 ноября 2008г и Международной научной конференции «Технические науки и современное производство» Пекин 26 ноября - 4 декабря 2008 г .Основные результаты работы опубликованы в 9 научных трудах.

Структура диссертационной работы.

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

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Мо Чжо Чо

Выводы по главе 5

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

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

3. Выполнен вычислительный эксперимент для различных способов модификации исходных многочленов Чебышева и показано, что оптимальным, с точки зрения точности вычисления является случай использование замены j=2 и у=2.86х-1.

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

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

Заключение

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

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

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

4. Показано, что с точки зрения реализации на ПЛИС, наиболее перспективным является метод использующий многочлены Чебышева, с оптимизированной под заданный диапазон изменения аргумента заменой переменных. Предложена методика модификации переменной в многочлене Чебышева из условия получения максимальной точности вычисления при заданном диапазоне изменения аргумента. На основе предложенной методики найдено, что для диапазона изменения аргумента Q<x<ln2 оптимальной является подстановка переменной в многочлене Чебышева (2.86-х-1 1 ^ вида у ■ 2-2.86 2-2.86.

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

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

5. Для стандартных мегафункций САПР Quartus II Ipmaddsub и lpmmult, реализующих операции сложения-вычитания и умножения, получены аналитические зависимости, связывающие необходимые аппаратные ресурсы ПЛИС и время выполнения операции с разрядностью операндов.

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

7. Разработаны алгоритмы вычисления, позволяющие вычислять значение функции при произвольном диапазоне изменения аргумента. Получены зависимости точности вычисления и количества выполняемых математических операций от расчетного диапазона изменения аргумента. Показано, что с точки зрения обеспечения требуемой точности вычисления при требовании минимизации аппаратных ресурсов ПЛИС на реализацию, оптимальным является расчетный диапазон изменения аргумента, определяемый условием 0 < х < In 2 .

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Мо Чжо Чо, 2009 год

1. В.Б.Стешеико. EDA Практика автоматизированного производства радиоэлектронных устройств- М.: Издатель Молгачева С.В., Издательство «Нолидж», 2002г. - 768с.

2. В.А.Хацук. Реализация ЦОС на ПЛИС структуры РРОА:высокая производительность и низкая стоимость реализации. «Электроника инфо» №6, 2004г., стр. 23.26.

3. О.А. Бабич Обработка информации в навигационных комплексах. М.Машиностроение, 1991 г.-512 с.

4. Воробьев Л.М. Воздушная навигация. М.: Машиностроение, 1984. - 256с., ил.

5. Фарина А., Студер Ф. Цифровая обработка радиолокационной информации. Сопровождение целей: Перев.с англ. М.: Радио и Связь, 1993. — 320с., ил.

6. Матричный метод стандартных кинематических связей при разработке алгоритмов управления в системах угловой ориентации. / Волков Н.Н., Волков А.Н.// ICA'97 II Международный Аэрокосмический Конгресс. -М., Сентябрь 1997. Сб. докладов, -с. 193196.

7. Харин Е.Г. Комплексная обработка информации навигационных систем летательных аппаратов. Опыт многолетнего практического применения. Учебное пособие. М.: Изд-во МАИ, 2002.-264с.: ил.

8. Беляевский Л.С., Новиков B.C., Олянюк П.В. Обработка и отображение радионавигационной информации. М.: Радио и связь, 1990. - 233 е.: ил.

9. Виноградов А.П. Основы обработки радиолокационной информации. 4.2 Вторичная обработка радиолокационной информации. СПб: Издание ВУ ПВО (филиал) 2002г.

10. Бут Э., Бут К. автоматические цифровые машины. М.,Физматгиз, 1959 г.

11. Ленский В.П. Вычисление элементарных функций на автоматических цифровых машинах. В сб, «Вычислительная математика»., вып.2 1957 г.- с90.119.

12. Kogbetliants E.G., Computation of eN for — со <N < +oo using an electronic computer., IBM Journal Research and Development 1. №2 1957 p.110. 115.

13. Kogbetliants E.G., Computation of arctan N for — со < N < +oo using an electronic computer., IBM Journal Research and Development 2. № 1958 p.43.53.

14. Kogbetliants E.G., Computation of sin(N), cos(N) and using an electronic computer.,

15. M Journal Research and Development 3. №2 1959.

16. Благовещенский Ю.В. Теслер Г.С. Вычисление элементарных функции на ЭВМ. ,Киев, из-во «Техника», 1977г.

17. Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций t в ЦВМ., Ленинград, Изд-во Ленинградского университета, 1975 г.17.