автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Применение специальных арифметических кодов в функционально ориентированных процессорах

На правах рукописи

Федотов Александр Борисович

ПРИМЕНЕНИЕ СПЕЦИАЛЬНЫХ АРИФМЕТИЧЕСКИХ КОДОВ В ФУНКЦИОНАЛЬНО ОРИЕНТИРОВАННЫХ ПРОЦЕССОРАХ

Специальность: 05.13.05- Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2005

Работа выполнена в Санкт-Петербургском государственном электротехническом университете "ЛЭТИ" им. В.И. Ульянова (Ленина)

Научный руководитель -

доктор технических наук, профессор Куприянов М.С. Официальные оппоненты:

доктор технических наук, профессор Петровский Б.С. кандидат технических наук, доцент Лячек Ю.Т.

Ведущая организация - ЗАО КТБ "Светлана - микроэлектроника".

на заседании диссертационного совета Д 212.238.02 Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" им. В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан 2005 г.

Защита диссертации состоится

диссертационного совета

Ученый секретарь

Юрков Ю.В.

ОБЩАЯ ХАРАКТЕРИСТИКА АБОТЫ

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

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

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

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

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

Р (х)=АХ4+ВХ3+СХ2+ОХ+Е.

Если обратить внимание на самый распространенный способ вычисления полиномов - схему Горнера, то можно заметить, что этот метод представляет собой цепь чередующихся умножений и сложений: Р(х)=(((Ах + В)х + С)х + 0)х + Е.

Схематично этот процесс вычисления значения полинома Р(Х) можно представить ломаной линией на рисунке (рис.1), где умножение обозначено значком *, а сложение -2.

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

ножения и суммирования, которые являются своеобразными ступенями на пути получения значения Р(х). Важно отметить, что вычисление этих промежуточных результатов не является основной задачей вычисления значения Р(х). Это наводит на мысль о том, что, объективно, должен существовать более стремительный, более непосредственный метод вычисления значения полинома одного аргумента Р(Х). В идеальном случае такой метод можно интерпретировать вектором, который имеет начало в точке X, а конец в точке Р(х).

X

Рис.1.

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

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

• применения специального кодирования данных;

• результатов исследования специфики, присущей процессам вычисления значений степенных функций и полиномов;

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

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

1. Исследование графовой интерпретации процессов вычисления значений степенных функций и полиномов.

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

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

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

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

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

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

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

Непосредственно научная новизна проведенного исследования заключается в следующем:

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертационных исследований докладывались и обсуждались на научных конференциях СПбГЭТУ «ЛЭТИ» (1996-2002 гг.), на заседаниях и семинарах кафедры вычислительной техники, а также на семинарах, проводимых учебной лабораторией фирмы Motorola.

Реализация результатов работы. Научные и практические результаты, полученные в диссертационной работе, были использованы в ОАО "Радиоавионика" при выполнении НИР ВТ-201 "Исследование методов построения семейства высокопроизводительных отказоустойчивых БЦВМ нового поколения с элементами ИИ на основе RISC-микропроцессоров".

Публикации. По теме диссертационной работы опубликованы 6 статей.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

1) алгоритмические методы;

2) табличные методы;

3) таблично-алгоритмические методы.

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

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

• ориентация на таблично-алгоритмические методы, позволяющие в • широких пределах варьировать точность, быстродействие и аппаратные затраты;

• использование процедуры сегментации для построения машинных формул;

• ориентация на применение современных больших интегральных схем ROM и PLD).

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

1) Методы полиномиальной аппроксимации элементарных функций и

дробно-рациональные приближения.

2) Итерационные методы вычисления значений элементарных функций.

3) Аппаратно-ориентированные методы вычисления значений элементарных функций.

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

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

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

1) Схема Горнера.

2) Алгоритм Дорна.

3) Алгоритм Эстрина.

4) Алгоритм Мураоко.

5) Алгоритм Мунро и Патерсона.

6) Алгоритм Мураямы.

7) Алгоритм Папакристу.

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

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

ным затратам и делает алгоритм "цифра за цифрой" непопулярным при организации процесса вычисления значений полиномов.

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

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

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

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

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

Рассматривается представление аргумента X множеством номеров бит имеющих единичное значение вкодеХв{М;,Мз.1,... .N2.N1}.

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

1. Формирование всевозможных М-местнных наборов номеров единичных бит.

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

V ^М-1

Ь Ом-1+1

где, в - число единиц в коде X.

Назовем число цифр в наборе вместимостью (М) набора, а количество одинаковых цифр в наборе активностью (А) этой цифры в данном наборе.

2. Вычисление вклада каждого набора.

Поставим в соответствие каждому набору число О, которое назовем вкладом этого набора в общую сумму. Формула для вычисления вклада О имеет следующий вод:

где, к- число разных цифр в наборе,

Д1 - активность 1-ой цифры,

М - вместимость набора.

3. Расстановка вкладов наборов.

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

4. Суммирование расставленных вкладов.

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

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

Если число единичных бит в коде X равно Б, то в процессе формирования всех наборов будет сделано Б шагов. Если 1-номер шага формирования всех наборов (I =0,1,2. Б-1), то всего по окончании процесса всего будет сформировано

рО

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

В данной главе предлагается алгоритм вычисления значения полинома Рм(х), подразумевающий выполнение ряда этапов.

1. Формирование всевозможных М-местнных наборов номеров единичных бит.

На этом этапе формируются всевозможные М-местные наборы номеров единиц из нового представления аргумента X такие, что в каждом наборе цифры в направлении справа налево не убывают. Всего будет сформировано

2См-ТИ наборов.

2. Вычисление вклада каждого М-местнного набора.

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

где i - число отбрасываемых номеров (позиций).

После выполнения операции усечения вместимость набора уменьшается на i . Усечение на ноль позиций 0 =0) оставляет набор неизменным. Поставим в соответствие каждому набору число D, которое назовем вкладом этого набора в общую сумму. Величина вклада каждого М-местного набора в общую сумму зависит от знака аргумента X.

Введем функцию знака аргумента X, которую определим в виде

(-1 если Х<0 если Х<0 .

8£,пХ

41

Обозначим через Р число номеров N1 в наборе Т,

где N1 - наименьший (первый) номер из представления X = {N$,N,.1,... .N2.N1}.

Величина вклада каждого М-местного набора в результирующую сумму вычисляется по формуле: Мн

о=Х(зёпХ) кшиЧа (Т)].

где

¡=0

Р - число номеров N1 в наборе Т,

Ку.] - коэффициент из множества { Км, Кцн,..., Кг, К1, Ко.}, в| (Т) - набор после выполнения усечения на \ позиций, 0 [8| (Т)] - вклад усеченного набора, вычисляемый по формуле:

015.0)]

(Мм)!

—к-

ПА^ н

где к-число разных цифр в наборе Б|(Т),

А, ■ активность ¡-ой цифры в наборе (Т).

3. Расстановка вкладов М-местнных наборов.

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

4. Суммирование расставленных вкладов.

После того, как все вклады будут расставлены по разрядной сетке надо выполнить массовое сложение всех этих чисел. В результате сложения будет получено значение полинома Р" (х).

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

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

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

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

Исходными данными для проводимого в третьей главе исследования являются три характеристики:

1 ) разрядность вычислительного процессора;

2) показатель степенной функции или степень полинома;

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

Для сокращения времени на вычислительный процесс рационально коды

с малым числом единиц обрабатывать специальной операционной частью, а коды большим числом единиц (больше 5-ти) - общей операционной частью, в состав которой входит матричный умножитель. Специальные операционные части выполняют процедуры RSA (Read, Shift, Add - Чтение, Сдвиг, Сложение).

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

Таблица 1.

Оценки временных затрат выражены через время срабатывания логического вентиля - Т.

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

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

В предположении равновероятного появление нулей и единиц в прямых кодах аргументов, выигрыш в быстродействии (для полиномов степени 7 и 8) составляет 24% по отношению к вычислениям значений полиномов по алгоритму Горнера. При этом, затраты на оборудование для специальной операционной части составляют примерно 22% от затрат на универсальную операционную часть.

Таблица 2.

Степень вычисляемого Время вычисления значения полинома общей операционной частью (т) Время вычисления значения полинома специальной операционной частью (т)

полинома

(М) Разрядность (п) Число единиц в коде аргумента (Б)

п=16 п=24 п=32 1 2 3 4 5

2 100т 132 т 164 т 6т 6т 26т 29т 32т

3 150 т 198 т 246 т 6т 6т 34т 38т 41т

4 200т 264 т 328 т 6т 6т 42т 47т 50т 1

5 250 т 330 т 410 т 6т 6т 50т 56т 59т

6 300т 396т 492 т 6т 6т 58т 65т 68т

7 350 т 462т 574 т 6т 6т 66т 74т 77т

8 400 т 528 т 656т 6т 6т 74т 83т 86т

Аппаратные затраты на специальную операционную часть состоят из затрат на ярус блоков ПЗУ - ROM1, ROM2, ROM3 и ROM4, блок комбинационного сдвигателя, мультиплексоры МХ1, МХ2 и регистр управления CR. Аккумулятор можно не учитывать, поскольку он является обязательной деталью каждого универсального микропроцессора. Размер аппаратных затрат на специ-

альную операционную часть зависит от разрядности обрабатываемых чисел -"п" и от степени вычисляемого полинома - "М".

Суммарный требуемый объем постоянной памяти равен

V = 2(п-1) + [(п- 1)(п-2)] +Kn-3)(n-2)]+2MVc3_1_, .

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

С=Зп!+»1.

2

Схема мультиплексора МХ1 представляет собой ярус n-входовых элементов ИЛИ. На каждый вход каждого элемента ИЛИ подключен 2-х входовой элемент И. Аппаратные затраты на мультиплексор МХ1 равны

С = 1 2n.

Схема мультиплексора МХ2 представляет собой ярус элементов ИЛИ. Суммарное количество элементов ИЛИ равно степени воспроизводимого полинома - М. Каждый элемент ИЛИ имеет (п -2) входов. На каждый вход каждого элемента ИЛИ подключен 2-х входовой элемент И. Аппаратные затраты на МХ2 равны

С = ЗМ(п-2).

Все оценки аппаратных затрат выполнены по Квайну.

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

Т = 2т- log2n+ Ts«*(Llog2 log2 nJ +1), где п - разрядность слагаемых (п=2к , к-целое),

Tsm - время суммирования двух слагаемых на аккумуляторе.

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

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

1. Метод преобразования массива подлежащих сложению кодов к прямоугольной форме может быть использован при аппаратной реализации операции умножения двух сомножителей. При этом один сомножитель должен быть представлен унитарным кодом, а другой - двоичным прямым позиционным п-разрядным кодом. Время выполнения операции умножения (также как и для сложения многих чисел) равно Т = Т = 2 х • logj n + Tsm(LIojj2 1одг nJ +1).

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

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

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

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

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

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

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

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

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

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

7. Предложен вариант методики проектирования специализированных

процессоров предназначенных для вычисления значений полиномов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Курдиков, Б А Учебно-исследовательский стенд на базе микропроцессора цифровой обработки сигналов ТМБ320С25 [Текст] / Б.А. Курдиков, А.Б. Федотов.// Изв. СПб ГЭТУ, Вып. 462. -СПб.: 1993. -С.46-54.

2. Курдиков, Б.А. Параллельная организация вычисления быстрого преобразования Фурье [Текст] / Б А Курдиков, А.Б. Федотов. // Изв. СПб ГЭТУ, Вып. 475. -СПб.: 1994.-С.38-45.

3. Федотов, А.Б. Один из подходов к организации вычисления полиномов одного аргумента [Текст] / А.Б. Федотов // Изв. СПб ГЭТУ, Вып. 482. -СПб.: 1995.-С.28-33.

4. Федотов, А.Б. Графовая интерпретация одного из подходов к вычислению полинома [Текст] /А.Б.Федотов // Изв. СПб ГЭТУ, Вып. 498. -СПб.: 1996. -С.16-22.

5. Федотов, А.Б. Увеличение доли логических операций при вычислении квадратичной зависимости [Текст] / А.Б. Федотов. // Изв. СПб ГЭТУ, Вып.510. -СПб.: 1997.-С.50-54

6. Федотов, А.Б. Логическое вычисление квадратичной функции [Текст] / А.Б. Федотов // Изв. СПбГЭТУ, Вып.520. -СПб.:1998. -С.47-53.

Подписано в печать 03.05.05. Формат 60*84 1/16.

Бумага офсетная. Печать офсетная. Печ. л. 1,0. _Тираж 100 экз. Заказ 36

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ «ЛЭТИ»

Издательство СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5

969

09 ИЮ:!?005

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЩИЕ ВОПРОСЫ ОРГАНИЗАЦИИ РАБОТЫ ФУНКЦИОНАЛЬНО ОРИЕНТИРОВАННЫХ ПРОЦЕССОРОВ.

1.1.Принципы построения функционально ориентированных. процессоров.

1.2. Методы приближенного вычисления значений.

1.3. Методы вычисления значений полиномов одного аргумента.

1.4. Выводы по главе 1.

ГЛАВА 2. АДАПТИВНЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ЗНАЧЕНИЙ СТЕПЕННЫХ ФУНКЦИЙ И ПОЛИНОМОВ.

2.1. Использование специального кодирования данных в процессе вычисления значений степенных функций.

2.2. Использование специального кодирования данных в процессе вычисления значений полиномов.

2.3. Метод геометрической фиксации.

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

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ, ПРЕДНАЗНАЧЕННЫЕ ДЛЯ ВЫЧИСЛЕНИЯ ЗНАЧЕНИЙ СТЕПЕННЫХ ФУНКЦИЙ И ПОЛИНОМОВ

3.1. Структуры, предназначенные для вычисления значений степенных функций.

3.2. Структуры, предназначенные для вычисления значений полиномов.

3.3. Структуры, предназначенные для ускоренного вычисления суммы многих чисел.

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

ГЛАВА 4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЗНАЧЕНИЯ ПОЛИНОМА И СУММЫ МНОГИХ ЧИСЕЛ НА ПРАКТИКЕ.

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

4.2. Увеличение производительности цифровых фильтров за счет ускорения процедуры сложения многих чисел.

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

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

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

Новые нетрадиционные формы представления информации должны предоставить новые возможности при организации функционально ориентированных процессов, что, в свою очередь, позволяет рассчитывать на повышение производительности функционально ориентированных процессоров. Реализация нетрадиционных форм представления информации сводится к нетрадиционному специальному кодированию данных. В большинстве случаев специальное кодирование данных преследует цели обеспечения помехоустойчивости в двоичных каналах связи [47], обнаружения и исправления ошибок при хранении и передаче двоичных кодов [73], и другие вспомогательные по отношению к обработке информации цели.

Однако попытки использовать особенные специальные формы кодирования информации для целей организации более эффективной обработки уже встречались. Например, в итерационных алгоритмах "цифра за цифрой" [8, 9] в процессе формирования итерационной последовательности, которая сходится к значению вычисляемой функции, осуществляется сопоставление кода аргумента с системой специальных констант. Для разных функций эти системы констант также различные (например, значения арктангенсов целой степени двойки, или значения логарифмов). Можно сказать, что происходит своеобразное перекодирование исходного кода аргумента. Другие способы использования специального кодирования данных рассмотрены и проанализированы в работе [62]. Здесь рассмотрены возможности применения кодов золотой пропорции и кодов Фиббоначи. По сути, эти методы сводятся к формам избыточного кодирования и требуют больших объемов памяти для хранения данных, чем обычное двоичное позиционное кодирование данных.

При этом бесспорная абсолютная эффективность применения кодов золотой пропорции и кодов Фиббоначи остается под вопросом.

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

Одним из самых популярных вычислительных инструментов является полином. При этом любой из известных способов вычисления полиномов представляет собой цепь арифметических действий умножения и сложения. Рассмотрим, например, процесс вычисления значения конкретного полинома: P(x)=Ax4+Bx3+Cx2+Dx+E.

Если обратить внимание на самый распространенный способ вычисления полиномов - схему Горнера, то можно заметить, что этот метод представляет собой цепь чередующихся умножений и сложений: Р(х)=( ((Ах + В) х + С) х + D) х + Е.

Схематично этот процесс вычисления значения полинома Р (X) можно представить ломаной линией на рисунке (рис. В.1), где умножение обозначено значком *, а сложение

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

Важно отметить, что вычисление этих промежуточных результатов не является основной задачей вычисления значения Р(х). Это наводит на мысль о том, что объективно должен существовать более стремительный, более непосредственный метод вычисления значения полинома одного аргумента Р (X). В идеальном случае такой метод можно интерпретировать вектором, который имеет начало в точке X, а конец в точке Р(х) (рис. В.1).

Рис. В.1. Геометрическая интерпретация вычисления значения полинома

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

Цель исследования

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

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

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

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

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

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

Предмет исследования

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

Новые научные результаты, выносимые на защиту

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

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

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

Практическая ценность полученных результатов

Практическая ценность полученных в работе результатов состоит в том, что при организации вычислений значений степенных функций и полиномов в режиме ОКМД, может быть получена заметная экономия времени, затрачиваемого на весь процесс вычисления. Кроме этого, разработанные аппаратные фрагменты, реализующие новый метод сложения многих чисел, могут быть использованы при проектировании разнообразных структур цифровых фильтров (например, цифровых усредняющих фильтров [85]), входящих в состав архитектуры современных микропроцессоров ЦОС.

Публикации

По материалам диссертационной работы имеется 6 публикаций.

Структура работы

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

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

1. число единиц в прямом двоичном позиционном коде аргумента равно 1;

2. число единиц в прямом двоичном позиционном коде аргумента равно 2;

3. число единиц в прямом двоичном позиционном коде аргумента равно 3;

4. число единиц в прямом двоичном позиционном коде аргумента равно 4.

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

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

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

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

2. Предложены варианты структур аппаратных фрагментов цифровых фильтров, входящих в состав архитектур сигнальных микропроцессоров.

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

4. Обозначены перспективные направления использования метода преобразования единичных бит массива подлежащих сложению чисел к разным геометрическим формам.

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

253

ЗАКЛЮЧЕНИЕ

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

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

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

3. Предложены новые более эффективные подходы к организации вычисления значений степенных функций и полиномов для аргументов, которые в своих прямых позиционных кодах содержат малое число единичных бит. При этом процесс вычисления сводится к простым операциям чтения из ПЗУ, сдвига и суммирования. При организации вычислений значений степенных функций и полиномов в режиме ОКМД данный подход обеспечивает повышение производительности на 24%. Алгоритмическая часть диссертации отработана на прозрачных графовых моделях. Но следует отметить, что материал, использованный для иллюстрации результатов исследования, оказался не достаточно эффективным. Анализ возможностей предлагаемых идей в сочетании с принципами параллельной, конвейерной, ассоциативной, поразрядной, ортогональной, систолической, волновой, потоковой и других способов обработки информации может дать значительно более высокий выигрыш в производительности.

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

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

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

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

По материалам диссертационной работы опубликовано 6 печатных работ.

1. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем Текст.: под ред. Ершова А.П. -М.: Наука, 1970-336 с.

2. Анисимов, A.B. Спецпроцессоры ЭВМ Текст.: учеб. пособие для студентов технических специальностей / A.B. Анисимов, В.Д. Байков, В.Б. Смолов. -Л.: Ротапринт ЛЭТИ. -1989. С.28- 42.

3. Анишин, Н.С. Проектирование алгоритмов вычисления функций для микропроцессоров Текст. Н.С. Анишин // Изв. вузов. Приборостроение.-1985. -№16.-С.41-46.

4. Специализированные алгоритмы и устройства обработки массивов данных Текст. /Е.И. Артамонов [и др.]. Махачкала: Дагестанское книжное изд-во, 1993.-336 с.

5. Артамонов, Е.И. Синтез структур специализированных средств машинной графики Текст. / Е.И. Артамонов, В.М. Хачумов. -М.: Ин-т проблем управления, 1991. С.34— 47.

6. Ахо, А. Построение и анализ вычислительных алгоритмов Текст. / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - С. 323 - 326.

7. Байков, В.Д. Анализ табличных и таблично-алгоритмических методов воспроизведения элементарных функций Текст. / В.Д. Байков, В. Б. Смолов // Электронное моделирование. -1980. -№1. -С.22-27.

8. Байков, В.Д. Аппаратная реализация элементарных функций в ЦВМ Текст. /В.Д. Байков, В.Б. Смолов. -Л.: Изд-во Л ГУ,1975.-96 с.

9. Байков, В.Д. Специализированные процессоры Текст. / В.Д. Байков, В.Б. Смолов. М.: Радио и связь, 1985. - 288 с.

10. Балашов, Е.П. Проектирование информационно-управляющих систем Текст. / Е.П. Балашов, Д.В. Пузанков. -М.: Радио и связь, 1987. -255 с.

11. Балашов, Е.П. Информационные системы Текст. / Е.П. Балашов,

12. B.Н. Негода, Д.В. Пузанков. -Л.: Энергоатомиздат, 1985. 181 с.

13. Бандман, О.Л. Параллельное программирование и высокопроизводительные системы. Текст. / О.Л. Бандман. -Новосибирск: 1980.1. C.98 -103.

14. Бандман, О.Л. Методы параллельного микропрограммирования Текст. / О.Л. Бандман. -Новосибирск: 1981. -С.16 23.

15. Барский, А.Б. Параллельные процессы в вычислительных системах. Текст. / Барский А.Б. М.: Радио и связь, 1990. -С. 182 204.

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

17. Васильев, Н.И. Применение полиномов Чебышева в численном анализе Текст. / Н.И. Васильев, Ю.А. Клоков, А.Я. Шкерестев. -Рига: Зинатне, 1984. -240 с.

18. Водовозов, В.М. Таблично-аналитический метод решения вычислительных задач в системах ЧПУ Текст. / В.М. Водовозов, А.И. Гури-нов, А.А. Тимофеев. // УСИМ.-1983. -№6 -С.18-21.

19. Водяхо, А.И. Функционально ориентированные процессоры Текст. / А.И. Водяхо [и др.]. -Л.: Машиностроение, 1988. С.152 -164.

20. Водяхо, А.И. Системы обработки данных. Текст. / А.И. Водяхо, H.H. Горнец, Д.В. Пузанков . -М.: Высшая школа, 1997. 304с.

21. Волков, Е.А. Численные методы Текст. / Е.А. Волков. -М.: Наука, 1982-С. 93.

22. Воробьев, H.H. Теория рядов Текст. / H.H. Воробьев. -М.: Наука, 1975.-368 с.

23. Гамкрелидзе, С.А. Цифровая обработка информации на основе быстродействующих БИС Текст. / С.А. Гамкрелидзе [и др.]. -М.: Энер-гоатомиздат, 1988. С.98.

24. Головкин Б.А. Параллельные вычислительные системы Текст. / С.А. Головкин. -М.: Наука, 1980. С.168.

25. Гун, С. Сверхбольшие интегральные схемы и современная обработка сигналов Текст. / С. Гун, X. Уайтхаус, Т. Кайлат. -М.: Радио и связь, 1989. -С. 284.

26. Демидович, Б.П. Основы вычислительной математики. Текст. / Б.П. Демидович, И.А. Марон. -М.: Наука, Гл. ред. физ. -мат. лит-ры, 1970. —С.664.

27. Евдокимов, В.Ф. Параллельные вычислительные структуры на основе разрядных методов вычислений Текст. / В.Ф. Евдокимов, А.И. , Стасюк . -Киев: Наукова думка, 1987. 311с.

28. Евреинов, Э.В. Однородные вычислительные системы, структуры и среды Текст. / Э.В. Евреинов. -М.: Радио и связь, 1981.- С.207.

29. Завьялов, Ю.С. Методы сплайн-функций Текст. / Ю.С. Завьялов [и др.]. -М.: Наука, 1980. С.96-145.

30. Ильин, В.А. О вычислении элементарных функций в управляющих ЦВМ методами кусочно-полиномиальной аппроксимации Текст. / В.А. Ильин. // УСИМ. -1977. -№4 -С.83-88.

31. Кнут, Д. Искусство программирования для ЭВМ Текст.: Том 2. -М.: Мир, 1977. -С.482- 537.

32. Козлов, О.С. Архитектура многопроцессорных вычислительных систем Текст./ О.С. Козлов [и др.]: под общ. ред. В.И. Тимохина -Л.: Изд-воЛГУ, 1981.-С.30.

33. Костяшкин, Л.Н. Усеченный разностно-итерационный алгоритм вычисления квадратного корня Текст. / Л.Н. Костяшкин // Изв. вузов. Приборостроение -1978. -№3 С.51 -53.

34. Коуги, П.М. Архитектура конвейерных ЭВМ Текст. / П.М. Коуги. -М.: Радио и связь, 1985. 356 с.

35. Кун, С. Матричные процессоры на СБИС Текст. / С. Кун. М.: Мир, 1991.-672 с.

36. Куприянов, М.С. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования Текст. / М.С. Куприянов, Б.Д. Ма-тюшкин. -СПб.: Плитехника, 1998. -592 с.

37. Курдиков, Б.А. Учебно-исследовательский стенд на базе микропроцессора цифровой обработки сигналов TMS320C25 Текст. / Б.А. Курдиков, А.Б. Федотов. // Изв. СПб ГЭТУ. -СПб. 1993. Вып. 462. -С.46-54.

38. Курдиков, Б.А. Параллельная организация вычисления быстрого преобразования Фурье Текст. / Б.А. Курдиков, А. Б. Федотов. // Изв. СПбГЭТУ. -СПб. 1994. Вып. 475. -С.38-45.

39. Кухарев, Г.А. Систолические процессоры для обработки сигналов Текст. / Г.А. Кухарев, В.П. Шмерко. -Минск: Беларусь, 1988. 127с.

40. Лкж,Ю. Специальные математические функции и их аппроксимация Текст./ Ю. Люк. -М.: Мир, 1980. -608 с.

41. Люстерик, Л.А. Вычисление элементарных функций Текст. / Л.А. Люстерик . -М.: Гос. издат. физ.-мат. лит-ры, 1963. -245 с.

42. Марков, A.A. Введение в теорию кодирования Текст. / A.A. Марков. -М.: Наука, 1982. -С.168- 178.

43. Марков, С.А. Цифровые сигнальные процессоры Текст. / С.А. Марков. М.: Микроарт, 1996. -С.35- 47.

44. Марчук, Г.И. Методы вычислительной математики Текст. / Г.И. Мар-чук. М.: Наука, 1980. - С.138 -142.

45. Мур, У. Систолические структуры Текст. / У. Мур, Э. Маккэйб, Р. Уркхарт. М.: Радио и связь, 1993. - 412 с.

46. Мухопад, Ю.Ф. Проектирование специализированных микропроцессорных вычислителей Текст. / Ю.Ф. Мухопад. -Новосибирск: Наука, 1981. —С.34- 68.

47. Мухопад, Ю.Ф. Многоразрядный вертикальный сумматор Текст.:/ Ю.Ф. Мухопад, В.П. Рудковский // Межвузовский сборник научных трудов. Новосибирск: 1991. - С. 55-62.

48. Оранский, AM. Аппаратные методы в цифровой вычислительной технике Текст. / А.М. Оранский. -Минск, изд-во БГУ, 1977. С. 96 -141.

49. Очин, Е.Ф. Вычислительные системы обработки изображений Текст. / Е.Ф. Очин. -П.: Энергоатомиздат, 1989. -133 с.

50. Петухова, Н.В. Расширение функциональных возможностей типовых матричных умножителей Текст. / Н.В. Петухова [и др.] // Изв. ЛЭТИ.-Л.: 1990. Вып. 423. -С.22-27

51. Поснов, H.H. Арифметика вычислительных машин в упражнениях и задачах Текст. / H.H. Поснов. Минск: изд-во БГУ, 1984. -220 с.

52. Прангишвили, И.В. Параллельные вычислительные системы с общим управлением Текст. / И.В. Прангишвили, С.Я. Виленкин, И.Л. Медведев-М.: Энергоатомиздат, 1983. -312с.

53. Ремез, Е.Я. Основы численных методов чебышевского приближения. Текст. / Е.Я. Ремез. -Киев: Наукова думка, 1969. -623 с.

54. Солонина, А.И. Алгоритмы и процессоры цифровой обработки сигналов Текст. / А.И. Солонина, Д.А. Улахович, Л.А. Яковлев. -СПб.: БХВ-Петербург, 2001. С.81 - 86.

55. Солонина, А.И. Цифровые процессоры обработки сигналов фирмы Motorola Текст. / А.И. Солонина, Д.А. Улахович, Л.А. Яковлев. -СПб.: БХВ-Петербург, 2000. -130 с.

56. Стахов, А.П. Коды золотой пропорции Текст. / А.П. Стахов. -М.: Радио и связь,1984. -151 с.

57. Трахтенгерц, Э.А. Некоторые оценки эффективности распараллеливания вычислений Текст. / Э.А. Трахтенгерц. // Автоматизация проектирования систем управления. -1981. -Вып. 3.-С.88-100.

58. Уфюмов, Е. П. Цифровая схемотехника Текст. / Е. П. Угрюмов -СПб.: БХВ-Петербург, 2001. С.93 - 99.

59. Угрюмов, Е.П. Цифровые таблично-алгоритмичесие функциональные преобразователи с линейной интерполяцией Текст./ Е. П. Угрюмов.

60. И Электронное моделирование. -1985. -№1 -С.56-60.

61. Федотов, А. Б. Один из подходов к организации вычисления полиномов одного аргумента Текст./ А.Б. Федотов // Изв. СПбГЭТУ. -СПб.:1995. Вып. 482. -С.28-33.

62. Федотов, А. Б. Графовая интерпретация одного из подходов к вычислению полинома Текст. / А.Б.Федотов // Изв.^СПбГЭТУ. -СПб.:1996. Вып. 498. -С. 16-22.

63. Федотов, А. Б. Увеличение доли логических операций при вычислении квадратичной зависимости Текст. / А.Б.Федотов // Изв. СПбГЭ-ТУ.-СПб.: 1997. Вып.510. -С.50-54

64. Федотов, А. Б. Логическое вычисление квадратичной функции Текст./А.Б. Федотов// Изв. СПбГЭТУ.-СПб.,1998. Вып.520. -С.47-53.

65. Фет,Я.И. Параллельные процессоры для управляющих систем Текст. / Я.И. Фет. -М.: Энергоиздат, 1981. -160 с.

66. Фостер, К. Ассоциативные параллельные процессоры Текст. / К. Фостер -М.: Энергоиздат, 1981.- 240 с.66/Фуре, С.Н. Простая и эффективная процедура для вычисления элементарных функций Текст./ С.Н. Фуре // Изв. вузов. Приборостроение -1982. -№10 -С.49-52.

67. Хэмминг, Р. В. Теория кодирования и теория информации Текст.:

68. Р.В. Хэмминг. -М.: Радио и связь, 1983. С.22 - 43.

69. Шихаев, К. Н. Разностные алгоритмы параллельных вычислительных процессов Текст. / К. Н. Шихаев. -М.: Радио и связь, 1984. С.96 -124.

70. Agrawal, R. P. High speed ariphmetic arrays Текст. / R. P. Agrawal. // IEEE Trans, on сотр. -1979. V.28. N.3 - P. 201-208.

71. Aoki, D. J. A machine language instruction set data flow processor Текст. / D.J. Aoki. // MIT Lab. Comput. Sci. Techn. Meto.- 1979. -N.146. -63 p.

72. Backus, J. Can programming be liberated frorrrthe von Neuman style Текст. / J. Backus // Comm. ACM. -1981 .-V. 21 (8). -P. 613-641.

73. Dorn, M.S. Generation of Homer's rule for polinomial evaluation Текст. / M.S. Dorn. // IBM J. Res. Dev. -1962. -V.6. -P. 323-347.

74. Estrin, G. Organization of computer system the fixed plus variable structure computer Текст. / G. Estrin. // Proc. West J/ Сотр. Conf. Montvale, May 1960 N.Y.: -AFIPS Press, 1960. -P. 33 - 40.

75. Munro, I. Optimal algorithms for parallel polinomial evaluation Текст. / I. Munro, M. Paterson //J. Сотр. Syst. Sci. -1973. -V.7. N. 2. -P. 189 -198.

76. Muraoka, Y. Parallelism expressure and exploitation in programs Текст. / Y. Muraoka, -Urbana: Dep. Сотр. Sci. Univ. N.Y. MR. 1971. -P. 33-41.

77. Papachristou C.A. Algorithms for parallel addition and parallel polinomial evaluation Текст./C.A. Papachristou//IEEE Trans, on сотр. 1981. -V.28. N. 2. -P. 256-263.

78. TMS320C5x User's Guide Текст. / Texas Instruments Inc. 1997 P. 3-3.