Применение специальных арифметических кодов в функционально ориентированных процессорах

Новые нетрадиционные формы представления информации должны предоставить новые возможности при организации функционально ориентированных процессов, что, в свою очередь, позволяет рассчитывать на повышение производительности функционально ориентированных процессоров. Реализация нетрадиционных форм представления информации сводится к нетрадиционному специальному кодированию данных. В большинстве случаев специальное кодирование данных преследует цели обеспечения помехоустойчивости в двоичных каналах связи [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. Предложен вариант методики проектирования функционально ориентированных процессоров предназначенных для вычисления значений полиномов.

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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