Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

CLASS HARDWARE-ORIENTED ALGORITHMS OF DISCRETE LINEAR TRANSFORMATIONS

Egunov V.A. 1
1 Volgograd state technical university, Volgograd
Is the basic algorithm class hardware-oriented algorithms of discrete linear transformations (DLP). Considered modifications of the basic algorithm intended for the hardware and software for the computers that use different ways to increase the speed of convergence of the basic algorithm. These modifications of the basic algorithm requires on the one hand a different number of iterations to achieve the necessary accuracy of the calculations, on the other hand, for their implementation need different amounts of additional computations, which ultimately leads to increased operational complexity separate iteration, depending on the specific modification of the basic algorithm. As a result of the proposed generalized class of algorithms of discrete linear transformations. The obtained generalized DLP-class can be used to construct algorithms intended for the hardware and software implementation and using different computational scheme for the implementation of individual iterations - reflection, rotation, etc.
discrete linear transformations
hardware-oriented algorithms
Одним из подходов к созданию аппаратурно-ориентированных алгоритмов является синтез дискретных линейных преобразований (ДЛП)[4]. Под ДЛП-реализацией линейного оператора А понима­ется разложение исходного линейного оператора в бесконечное произведение матриц

, (1)

таких, что произведение  стремится к исходной  матрице A при n→∞. Элементы матриц Bi выбираются таким образом, что умножение на очередную матрицу ДЛП сводится к последова­тельности сложений и сдвигов, то есть элементы матриц Bi вы­бираются равными нулю или целой степени основания системы счисления (в двоичной системе - целой степени двух). Это приводит к понижению аппаратурно-временной сложности алго­ритма, откуда сле­дует снижение стоимости вычислительных устройств, реализованных на базе этого алгоритма.

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

 (2)

Преобразование начинается с нулевой итерации (i=0). Далее на каждой итерации проверяется, не достигнута ли требуемая точность (например, сравнением с эталоном). Если не достигнута, выполняется ДЛП-оператор, инкрементируется номер итерации и далее выполняется следующая ДЛП-итерация. Очевидно, что при базовой реализации ДЛП-алгоритма число итераций для различных наборов входных данных будет отличаться. В частности, для наборов, которые совпадают с результатом, никаких итераций производить вообще не надо. Для других наборов число итераций будет отличаться от нуля. Максимально необходимое число итераций базового алгоритма обозначим через k. Очевидно, что базовый алгоритм может быть использован только при моделировании для определения минимально необходимого числа итераций, т.к. при выполнении реальных вычислений эталонное (точное) значение вычисляемого параметра неизвестно (собственно, оно и должно быть вычислено). Однако базовый алгоритм может быть полезен для определения потенциальных возможностей алгоритмов данного ДЛП-класса.

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

ДЛП-алгоритм со строго определенным количеством итераций

В данном случае аналитическим путем или путем моделирования определяется число итераций k1, при которых ДЛП-алгоритм гарантированно сходится на любом наборе входных данных [2].

 (3)

Преобразование в данном случае выполняется всегда, в т.ч. и для набора, который совпадает с результатом, а затем, путем последовательного уточнения на каждой итерации, приближает к искомому результату. Значение k1 зависит от ряда параметров, в т.ч. от требуемой точности вычислений, но, очевидно, что k1>k,  т.е. для данного варианта реализации ДЛП-алгоритма число итераций будет заведомо больше числа итераций базового алгоритма.

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

ДЛП-алгоритм с оценкой текущей точности вычислений

 (4)

Число итераций в данном случае будет равно k2, причем k<k2<k1.

Еще одним способом, уменьшающим общее число итераций по сравнению с ДЛП-алгоритмом со строго определенным количеством итераций, является отказ от выполнения «неудачных» итераций в процессе преобразования [5]. Не все итерации приближают вычисляемые параметры к искомому результату, т.е являются «удачными». Для того же примера с набором входных данных, совпадающим с результатом, любая итерация будет являться «неудачным». Таким образом, выполнение только «удачных» итераций поможет снизить число итераций относительно k1[3].

ДЛП-алгоритм с выполнением только «удачных» итераций

 (5)

Число итераций в данном случае будет равно k3, причем k<k3<k1. Соотношение итераций k2 и k3 будет зависеть от конкретного ДЛП-оператора (отражение, вращение и т.д.).

К наименьшему числу итераций должно привести совмещение технологии оценки текущей точности вычислений и выполнения только «удачных» итераций.

ДЛП-алгоритм с оценкой текущей точности вычислений и выполнением только «удачных» итераций

 (6)

Число итераций в данном случае будет равно k4.

Очевидно, что

 (7)

Учитывая все вышеизложенное, обобщенный класс ДЛП-алгоритмов будет выглядеть следующим образом (табл.1).

Таблица 1. Варианты реализации базового алгоритма дискретного линейного преобразования

№ п/п

Наименование реализации базового алгоритма

Косвенная оценка текущей точности

Определение необходимости выполнения текущей итерации

1

ДЛП-алгоритм со строго определенным количеством итераций

-

-

2

ДЛП-алгоритм с оценкой текущей точности вычислений

+

-

3

ДЛП-алгоритм с выполнением только «удачных» итераций

-

+

4

ДЛП-алгоритм с оценкой текущей точности вычислений и выполнением только «удачных» итераций

+

+

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

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

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

Рецензенты:

  • Шилин А.Н., д.т.н., профессор, заведующий кафедрой «Энергообеспечение предприятий» филиала ФГБОУ ВПО «Национальный исследовательский университет (МЭИ)»,  г. Волжский.
  • Кравец А.Г., д.т.н., профессор кафедры САПР и ПК, ФГБОУ ВПО Волгоградский государственный технический университет, Волгоград.