Разработка математической модели и пакета прикладных программ для нахождения численного значения элементарных функций средствами СБИС программируемой логики тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Попов, Святослав Дмитриевич

• Попов, Святослав Дмитриевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Попов, Святослав Дмитриевич

СОДЕРЖАНИЕ

Введение

Глава 1. Особенности вычисления многочлена на СБИС ПЛ

1.1. Значение многочленов применительно к вычислениям на СБИС ПЛ

1.2. Определения

1.3. Схема Горнера

1.4. Индивидуальные схемы

1.5. Универсальные схемы с предварительной обработкой коэффициентов для многочленов четвёртой и шестой степеней

1.6. Универсальная схема с предварительной обработкой коэффициентов для многочлена произвольной степени

1.7. Параллельный метод вычисления многочлена средствами СБИС ПЛ

1.8. Сравнительный анализ рассмотренных схем

1.9. Выводы

Глава 2. Оптимизация алгоритма вычисления многочлена средствами СБИС ПЛ

2.1. Преобразование и схема вычисления многочлена

2.2. Анализ алгоритма применительно к СБИС ПЛ

2.3. Сравнительный анализ рассмотренных схем

2.4. Выводы

Глава 3. Вычисление экспоненциальной функции средствами СБИС ПЛ

3.1. Метод БВЕ

3.2. Применение метода БВЕ для нахождения численного значения экспоненциальной функции

3.3. Применение метода БВЕ для нахождения численного значения экспоненциальной функции средствами СБИС ПЛ

3.4. Оптимизированная математическая модель нахождения численного значения экспоненциальной функции применительно к СБИС ПЛ

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

3.4.2. Оптимизированная математическая модель

3.4.3. Табличный метод

3.4.4. Явное вычисление множителей М£

3.4.5. Точность вычислений при п Е [17,32]

3.4.6. Точность вычислений при п 6 [9,16]

3.4.7. Приведение произвольного аргумента к области определения алгоритма

3.4.8. Оптимальное применение табличного метода

3.4.9. Вычисление показательной функции

3.5. Методика подбора параметров алгоритма

3.6. Выводы

Глава 4. Эксперименты

4.1. Цель и условия моделирования

4.2. Результаты эксперимента для конфигурации К = 4, к4 = 1

4.3. Результаты эксперимента для конфигурации К = 4, к4 = 2

4.4. Результаты эксперимента для конфигурации К = 5, к4 = 2, к5 = 1

4.5. Результаты эксперимента для конфигурации К = 5, к4 = 3, к5 = 1

4.6. Результаты эксперимента для конфигурации /Г = 5, к4 = 3, к5 = 2

4.7. Сравнение со стандартной мегафункцией altf р_ехр

4.8. Сравнение с актуальными методами вычисления экспоненциальной функции

4.9. Выводы

Заключение

Литература

Приложение

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

ВВЕДЕНИЕ

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

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

Специализированные вычислители реализуются на основе заказных или полузаказных сверхбольших интегральных схем (СБИС) [24, 33, 31], позволяющих распараллелить алгоритм работы на аппаратном уровне и обеспечить минимизацию массо-объёмных характеристик оборудования при заданном уровне быстродействия. Лучшие показатели быстродействия и массо-

объёмных характеристик обеспечивают заказные СБИС, однако, производство таких СБИС оправдано только в больших объёмах. Применение полузаказных СБИС, например, базовых матричных кристаллов (БМК) [28], позволяет снизить стоимость производства, однако, в случае малых объёмов стоимость производства остаётся высокой, т.к. требуется заводской производственный процесс и отсутствует возможность корректировать конечное устройство.

Сегодня наиболее оптимальным решением для малобюджетных и среднебюджетных проектов являются СБИС программируемой логики (СБИС ПЛ) [1, 5, 7, 14], совмещающие возможность аппаратного распараллеливания алгоритмов и гибкость реализации, как у любых программных решений.

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

Проектирование структуры СБИС ПЛ требует применения соответствующих САПР электронной аппаратуры. В современных САПР используется некоторый язык описания аппаратуры — HDL (Hardware Description Language). Например, универсальный язык VHDL (Verilog HDL), разработанный с целью формального описания логических схем для всех этапов разработки электронных систем, начиная с модулей микросхем и заканчивая крупными вычислительными системами. Универсальный подход в языке VHDL не позволяет учитывать особенности конкретных интегральных схем, поэтому производители аппаратных средств предлагают собственные языки HDL.

Например, фирма Altéra в собственной САПР электронной аппаратуры Quartus II [25], кроме поддержки языка VHDL, предлагает язык AHDL (Altéra Hardware Description Language) [1, 2, 26], учитывающий особенности элементной базы продуктов фирмы Altéra.

Языки HDL позволяют многократно использовать однажды написанный код. Предназначенный для многократного применения код оформляется в виде мегафункций или подключаемых модулей. Благодаря такой возможности появились обширные библиотеки мегафункций, в том числе поставляемых в комплекте с САПР. В виде мегафункций или подключаемых модулей доступны реализации различных микропроцессоров и микроконтроллеров, реализации быстрого преобразования Фурье, различные математические функции и т.д. [27].

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

Решение конкретных практических задач в большинстве случаев требует вычисления значений элементарных математических функций. В составе САПР электронной аппаратуры Quartus II поставляются мегафункции, обеспечивающие синтез универсальных блоков для вычисления различных элементарных функций. Эти блоки работают с данными, представленными, согласно стандарту IEEE-754, в виде 32-битных или 64-битных слов. При решении практических задач часто возникают ситуации, при которых либо точность, либо затраты аппаратных ресурсов на реализацию, обеспечиваемые стандартными мегафункциями, являются чрезмерными.

Таким образом, вопрос нахождения численных значений элементарных математических функций [8, 9, 10, 16], несмотря на известные технические

решения, например, [19], по-прежнему, является весьма актуальным. Решение этого вопроса, на практике, требует вычисления некоторого многочлена, степень которого определяет точность получаемого результата. Известны такие методы вычисления многочлена [3], как схема Горнера [15], или методы, основанные на предварительной обработке коэффициентов. Пан В.Я. предложил универсальную схему вычисления многочлена с предварительной обработкой коэффициентов [20 ... 23], отличающуюся меньшим количеством операций умножения по сравнению со схемой Горнера. Однако, указанные схемы нацелены на использование стандартных для ЭВМ последовательных методов вычисления, что не позволяет минимизировать время вычисления на СБИС ПЛ, предоставляющих возможности для распараллеливания алгоритма работы.

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

Вопрос нахождения численного значения экспоненциальной функции средствами СБИС ПЛ подробно рассмотрен в работах [17, 18]. В работе [18] рассмотрено большинство известных методов, например, [4] и [6]. Среди рассмотренных методов наиболее оптимальным в плане быстродействия СБИС ПЛ признан метод ортогональных приближений с использованием многочленов Чебышёва.

В работе [18] присутствует упоминание предложенного Карацубой Е.А. метода БВЕ [12, 32] (быстрого вычисления Е-функций) — метода быстрого суммирования рядов специального вида. В работе [11] предложен алгоритм нахождения численного значения экспоненциальной функции на основе метода

БВЕ. Однако, вопрос применения этого алгоритма на СБИС ПЛ не был рассмотрен.

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

Задачи исследования:

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

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

• Исследование возможности применения алгоритма на основе метода БВЕ для нахождения численного значения экспоненциальной функции средствами СБИС ПЛ.

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

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

Научная новизна:

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

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

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

Практическая значимость:

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на Всероссийской научно-технической конференции «Новые материалы и технологии» в 2012 году и на Международных молодежных научных конференциях «Гагаринские чтения» 2010,2011 и 2012 годов.

Основные результаты работы опубликованы в шести научных трудах, два из которых — в изданиях, рекомендованных ВАК РФ.

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

ГЛАВА 1. ОСОБЕННОСТИ ВЫЧИСЛЕНИЯ МНОГОЧЛЕНА НА

СБИС ПЛ

1.1. Значение многочленов применительно к вычислениям на СБИС ПЛ

Многочлен степени п в канонической форме — это функция Рп(х) следующего вида:

п

РпМ =^01Х1, (1.1)

1=0

где = 0,п, — коэффициенты многочлена.

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

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

1.2. Определения

Приведём набор определений, связанных с понятием схемы вычисления многочлена.

Определение 1.1: схема вычисления многочлена — это последовательность арифметических операций, в которых участвуют аргумент, параметры схемы Ьъ Ь2, ..., Ьт и результаты предшествующих операций. Результат последней операции назовём результатом схемы.

Определение 1.2: если при некотором наборе значений параметров схемы blt b2, bm результат вычислений по схеме совпадает со значением данного многочлена степени п для любого значения аргумента х, то схема представляет этот многочлен.

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

Определение 1.4: схема вычисления многочлена степени п называется универсальной, если она представляет любой многочлен степени п.

13. Схема Горнера

Схема Горнера (Horner's Rule) [16] — алгоритм вычисления многочлена, названный по имени британского математика Горнера В. (W.G. Horner), который опубликовал этот алгоритм в начале XIX века. Однако, как утверждает Кнут Д. [13], ещё за 150 лет до Горнера данный метод использовался Ньютоном И.

Суть схемы Горнера заключается в специальном преобразовании канонической формы многочлена (1.1) путём последовательного вынесения аргумента х за скобки с образованием многочленов меньших степеней:

Рп(х) = х ^Г а(х} ^ + а0 = хР^О) + а0.

К многочлену степени п указанное преобразование применяется (п — 1) раз. Например, при п = 4 получаем следующее выражение:

Р4(х) = х(х(х(а4х + а3) + а2) + ах) + а0.

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

Р1 = апх + ап-ъ

р2=х-р1 + ап_2,

р3=х-р2 + Оп-з,

Р1= х- + = Рп-

Введём следующие обозначения: — количество операций умножения, необходимое для вычисления значения многочлена степени п по некоторой схеме; пусть — количество операций сложения, необходимое для вычисления значения многочлена степени п по некоторой схеме. Эти величины позволяют оценить аппаратные затраты СБИС ПЛ на реализацию.

На каждом шаге схемы Горнера используется одно сложение и одно умножение. Всего в схеме Горнера п шагов. Следовательно, для схемы Горнера величины С£ и равны п:

С* = С+ = п

Схема Горнера — оптимальный в плане количества операций умножения и сложения алгоритм для вычисления многочленов без предварительной обработки коэффициентов. Доказательство эффективности алгоритма схемы Горнера как схемы без предварительной обработки коэффициентов приведено Паном В.Я в статье [25].

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

Введём следующие обозначения: I% — количество ярусов умножения в составе графа алгоритма; пусть — количество ярусов сложения в составе графа алгоритма. Эти величины применительно к вычислению значения многочлена с помощью некоторой схемы позволяют оценить время вычисления.

Так как алгоритм схемы Горнера не поддаётся распараллеливанию, величины и Ьп равны степени многочлена:

= « = п.

1.4. Индивидуальные схемы

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

Пример 1:

Рп{х) = Р2к(х) = х2\

где к 6 М. Значение этого многочлена можно вычислить с использованием к операций умножения по следующей схеме:

VI = *2>

VI = VlVl = х4,

_ _ 2к Vk — Vk-lVk-l ~ х >

Рп(х) = Р2к(х) = Vk■

Пример 2:

Р4(х) = х4 - 4х3 + 6х2 - 4х + 1.

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

х4 - 4х3 + 6х2-4х+1 = (х- I)4.

Из этого преобразования следует схема вычисления значения этого многочлена:

V! = х - 1, Р2 = VlVl> Vз = VгVг> Р*(х) = Vз^

Второй пример является частным случаем бинома Ньютона:

Рп(х) = (* + = (о) *п + * ® *п-1 + - + ак (I) Хп~к + ... + а" (*),

где к е М, а е к.

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

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

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

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

1.5. Универсальные схемы с предварительной обработкой коэффициентов для многочленов четвёртой и шестой степеней

В 1955 году была предложена универсальная схема совершенно иного типа, нежели схема Горнера, для многочлена шестой степени. Пусть

Р60) = х6 + ах5 + Ьх4 + сх3 + &х2 + ех + /. (1.2)

Тогда значение данного многочлена можно вычислять по следующей схеме:

р± = х(х + А),

Р2 = (Р1 + Ю(.Р± + * + О + £>,

(1.3)

Рз = P2C.P1 + Ю + Р, Рб(х) = Рз. где А, В, С, й, Е, F — параметры схемы.

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

Использование данной схемы требует, чтобы параметры А, В, С, Б, Е, Р были предварительно рассчитаны, что накладывает некоторые ограничения на область применения схемы. Эти ограничения заключаются в следующем: если коэффициенты многочлена а, Ъ, с, (I, е, / заранее известны, то нужно заранее рассчитать параметры А, В, С, И, Е, Р; если же коэффициенты многочлена неизвестны заранее, то параметры схемы придётся вычислять непосредственно перед их использованием в схеме, что, в случае однократного вычисления многочлена сведёт на нет преимущество схемы (1.3) перед схемой Горнера. Таким образом, необходимо, чтобы выполнялось одно из двух условий:

1) коэффициенты многочлена а, Ь, с, е, f заранее известны;

2) значение многочлена вычисляется многократно для одного и того же набора коэффициентов а, Ъ, с, с1, е, /.

Получим формулы, по которым вычисляются параметры схемы (1.3). Сначала выразим коэффициенты многочлена через параметры схемы.

Р2=Р1+ Р1О + В + С) + (Вх + ВС + й).

Тогда

Рз= х6 +

+х5(3 А + 1) +

+х4(3 А2 + 2А + В + С + Е) +

+х3(А3 + А2 + 2 А(В + С + Е) + В + Е) +

+х2(А2(В + С + Е) + А(В + Е) + ВС + ВЕ + СЕ + Я) +

+х(Л(ВС + ВЕ + СЕ) + ЕВ+ АИ) +

+ВСЕ + ЭЕ + F = = Р6(х) = х6 + ах5 + Ьх4 + сх3 + Ах2 + ех + /.

Получаем систему:

/■ а — 1

(В + Е) + С = Ь - ЗА2 - 2А, (В + Е)(2А + 1) + 2 АС = с-А3- А2, (В + ЕХА2 + А + С) + А2С + ВЕ + В = й, СВ + Е)А + ВЕ(А + 1) + АЭ = е, Ц? = / - ВСЕ - ЭЕ.

Решая приведённую систему, получаем выражение для параметров схемы (1.3):

< а-1 А = —-—

В =

М1 - ^М2 - 4М2

С = Ь(2А + 1) - с - 5Л3 - 6А2 - 2А, й = (с* -М^А2 + С) — СЛ2)-е-МХЛ2,

Е =

-Мг + VМ2 - 4Л/2

= /- ЯСЯ - БЕ,

где

М1 = с-2АЬ + 5 А3 + ЗА2,

М2 = е — Ай + Мг(А3 +А2+АС-А) + А3С.

Рассмотрим приведённое решение для параметров схемы (1.3). Из выражений для и М2 видно, что для некоторых наборов действительных коэффициентов а, Ъ, с, (I, е, / исходного многочлена (1.2) решение для набора параметров А, В, С, й, Е, Р схемы (1.3) может не существовать на множестве действительных чисел.

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

В рассматриваемом многочлене (1.2) отсутствует коэффициент при х6. Схему (1.3) можно применить в случае наличия коэффициента при х6. Пусть

Рб (*) = дх6 + ах5 + Ъх4 + сх3 + ах2 + ех + /, (1.4)

где д Ф 0. Тогда

Рб СО = д(х6+ —х5 + -х4 + -х3 + —х2 +-х + -)= д(26(х),

V д д д д д д) *

где <?б(*) — многочлен шестой степени, который подходит для вычислений по схеме (1.3).

Вычисление значения многочлена (1.4) по схеме (1.3) требует четырёх операций умножения и семи операций сложения против шести операций умножения и шести операций сложения по схеме Горнера.

Аналогично схеме (1.3) для многочлена шестой степени, можно предложить схему для многочлена четвёртой степени.

Рассмотрим многочлен четвёртой степени:

Р4(х) = х4 + ах3 + Ьх2 + сх + (I. (1.5)

Данный многочлен можно вычислить по следующей схеме:

= х(х + А),

р2 = (р,. + В)(р1+х + С) + £>, (1.6)

Р* О) = р2,

где А, В, С, Б — параметры схемы.

Подставим выражение для р± в выражение для р2:

р2 = (х2 +Ах + В){х2 + х(А + 1) + С) + В = = х4 +

+х3(2А +1) + +х2(А2 +А + В + С) + +х(АВ + АС + В) + +ВС + й.

Получаем систему для параметров схемы:

(2А + 1 = а, А2 +А + В + С = Ь, В (А + 1) + СА = с,

Vвс+ и = а.

Решая приведённую систему, получаем выражение для параметров схемы (1.6):

(1.7)

А В С ЧЕ>

(а- 1) 2 ' с-АЬ-А3- А2,

Ь(Л + 1) — с + А3 — А,

Список литературы диссертационного исследования кандидат наук Попов, Святослав Дмитриевич, 2013 год

ЛИТЕРАТУРА

1. Антонов А.П., МелехинВ.С., Филиппов A.C. Серия «Проектирование цифровых устройств на СБИС программируемой логики». Книга 1. Обзор элементной базы фирмы Altera. — ЭФО Санкт-Петербург. — 1997. — 142 с.

2. Антонов А.П., Язык описания цифровых устройств AlteraDHL. Практический курс. — М.: ИП РадиоСофт. — 2001. — 224 с.

3.БелагаЭ.Г. Некоторые вопросы вычисления многочленов. Докл. АН СССР. — 1958 — Т.123. — № 5. — С. 775-777.

4. Бескин Н.М. Бесконечные цепные дроби // — М.: Квант. — 1970. — Т. 8.

— С. 10-20.

5. Бродин В.Б., Калинин A.B. Системы на микроконтроллерах и БИС программируемой логики. — М.: Издательство ЭКОМ. — 2002. — 400с.

6. Васильев Н., Зелевинский А. Многочлены Чебышёва и рекуррентные соотношения // Квант. — 1982. — № 1. — С. 12-19.

7. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики. — СПб.: БХВ. — Петербург. — 2002.

— 608 с.

8. Демидович Б.П., Марон И.А. Основы вычислительной математики. — Изд-во «Наука», Москва, 1966. — 664 с.

9. Ильин В.А., Позняк Э.Г. Основы математического анализа. — М.: ФизМатЛит. — 2002. — С. 97.

10. Ильин В.А., Садовничий В.А., Сендов Б.Х. Математический анализ. — М.: Проспект. — 2004. — С. 125-136.

11. КарацубаЕ.А. Быстрое вычисление ехрх. // Проблемы передачи информации. — 1990. — Т. 26. — № 3. — С. 109.

12. КарацубаЕ.А. Быстрые алгоритмы и метод БВЕ. URL: http://www.ccas.ru/personal/karatsuba/alg.htm (дата обращения: 14.08.2013).

13. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы. — 3-е изд. — М.: ИД «Вильяме». — 2007. — 832 с.

14. Леклидер Т. Погружаясь в ПЛИС. // Электронный журнал «Компоненты и технологии». — 2006. — № 12. [Электронный ресурс]. URL: http://de.ifmo.ru/bk_netra/page.php?tutindex=25&index=43 (дата обращения: 14.08.2013).

15. Левитин А. Алгоритмы: Введение в разработку и анализ. — М.: ИД «Вильяме». — 2006. — 574 с.

16. Люстерник Л.А., Червоненкис O.A., Янпольский А.Р. Математический анализ. Вычисление элементарных функций. — М.: Физматгиз, 1963. — 248 с.

17. МоЧжоЧо, ОпадчийЮ.Ф. Алгоритм вычисления показательной функции на ПЛИС. // Новые, материалы и технологии: сборник трудов Всероссийской научно-технической конференции (Москва, 11-13 ноября 2008 г.). — М., 2008. — Т. 3. — С. 113-115.

18. Мо Чжо Чо. Моделирование вычислительного процесса, разработка алгоритмов и пакета прикладных программ для вычисления экспоненциальной функции на программируемых логических интегральных схемах : диссертация на соискание учёной степени кандидата технических наук : 12.11.2009 / Мо Чжо Чо. —М., 2009. —206 с.

19. Опадчий Ю.Ф., Чумакова Е.В. Реализация на ПЛИС вычисления элементарных математических функций // Проектирование и технология электронных средств. — Владимир. — 2005. — № 4. — С. 7-12.

20. Пан В.Я. Вычисление многочленов по схемам с предварительной обработкой коэффициентов и программа автоматического нахождения параметров. // Вычислительная математика и математическая физика. — 1962. — №1. — С. 133-140.

21. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами. // Проблемы кибернетики. — 1961. — №5. С. 17-29.

22. Пан В.Я. О вычислении многочленов пятой и седьмой степеней с вещественными коэффициентами. // Вычислительная математика и математическая физика. — 1965. — Т. 5. — № 1. — С. 116-118.

23. Пан В .Я. О способах вычисления значений многочленов // Успехи математических наук. — 1966. — Т. 21. — № 1. — С. 103-134.

24. Полташев Т. Введение в проблему разработки и производства СБИС. [Электронный ресурс]. URL: http://www.ifmo.ru/file/news/1481/introduction %20to%20vlsi.pdf (дата обращения: 14.08.2013).

25. Стешенко В.Б. ПЛИС фирмы Altera. Проектирование устройств обработки сигналов. — М.: Додека-ХХ1,2000. — 128 с.

26. Стешенко В.Б. ПЛИС фирмы ALTERA: элементная база, система проектирования и языки описания аппаратуры. — М.: Издательский дом, ДОДЕКА. — XXI. — 2002. — 576 с.

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

28. Угрюмов Е.П. Программируемые логические матрицы, программируемая матричная логика, базовые матричные кристаллы / Цифровая схемотехника. Учебное пособие для вузов. Изд. 2. — СПб.: БХВ. — 2004. — С. 357.

29. Шаурман A.M. Основы машинной арифметики. — Л.: Изд-во Ленинградского университета. — 1979. — 310 с.

30. Яшкардин В. IEEE 754 — стандарт двоичной арифметики с плавающей точкой. [Электронный ресурс]. URL: http://www.softelectro.ru/ieee754.html (дата обращения: 14.08.2013).

31. Hubert Kaeslin. Digital Integrated Circuit Design, Cambridge University Press, ISBN: 9780521882675 , United Kingdom, 2008.

32. D.W. Lozier, F.W.J. Olver. Numerical Evaluation of Special Functions. Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics, W.Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, Vol.48 (1994).

33. Michael J. S. Smith. Application-Specific Integrated Circuits, Addison-Wesley, ISBN 0-201-50022-1, 1997, P. 1040.

34. Floating Point Exponent (ALTFP_EXP) Megafunction User Guide. [Электронный ресурс]. URL: http://www.altera.co.jp/literature/ug/ug_altfp_exp.pdf (дата обращения: 14.08.2013).