Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

КЛАСС АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ ЛИНЕЙНЫХ ПРЕОБРАЗОВАНИЙ

Егунов В.А. 1
1 ФГБОУ ВПО Волгоградский государственный технический университет, Волгоград
Приведен базовый алгоритм класса аппаратурно-ориентированных алгоритмов дискретных линейных преобразований (ДЛП). Рассмотрены модификации базового алгоритма, предназначенные для программно-аппаратной реализации на средствах вычислительной техники, использующие различные способы повышения скорости сходимости базового алгоритма. Данные модификации базового алгоритма требуют с одной стороны различного числа итераций для достижения необходимой точности вычислений, с другой стороны, для их реализации необходимы различные объемы дополнительных вычислений, что в итоге приводит к росту операционной сложности отдельной итерации, зависящему от конкретной модификации базового алгоритма. В результате предложен обобщенный класс алгоритмов дискретных линейных преобразований. Полученный обобщенный ДЛП-класс может быть использован для построения алгоритмов, предназначенных для программно-аппаратной реализации и использующих различные вычислительные схемы для реализации отдельных итераций – отражение, вращение и т.д.
дискретные линейные преобразования
аппаратурно-ориентированные алгоритмы
1. Андреев А.Е., Стрельников О.И., Егунов В.А. Программное обеспечение реконфигурируемых вычислителей на базе ПЛИС // Информационные технологии в образовании, технике и медицине: материалы международной конференции / ВолгГТУ. – Волгоград, 2006. – С.125-126.
2. Егунов В.А., Андреев А.Е., Стрельников О.И. Моделирование алгоритмов дискретных линейных преобразований // Известия Волгоградского государственного технического университета: межвуз. сб. науч. Ст. №1(27) / ВолгГТУ. – Волгоград, 2007. - С.51-53 [Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып.1].
3. Егунов В.А., Андреев А.Е., Стрельников О.И. Определение условия оптимальности процесса дискретного линейного преобразования отражения // Известия Волгоградского государственного технического университета: межвуз. сб. науч. Ст. №1(27) / ВолгГТУ. – Волгоград, 2007. – С. 53-54 [Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып.1].
4. Егунов В.А. Аппаратные методы решения задач линейной алгебры: монография/ В.А.Егунов, В.С. Лукьянов/ВолгГТУ, Волгоград, 2007. – 152 с.
5. Лукьянов В.С. Алгоритм ускоренного дискретного линейного преобразования отражения / В.С.Лукьянов, В.А.Егунов // Открытое образование: прил. к журн.: по матер. XXXIII межд. конф. к IV межд. конф. мол. уч. IT+S&E`06 (Ялта – Гурзуф, Крым). – 2006. – Б/н (май). – С.105-106.
Одним из подходов к созданию аппаратурно-ориентированных алгоритмов является синтез дискретных линейных преобразований (ДЛП)[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].

Рецензенты:

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

Библиографическая ссылка

Егунов В.А. КЛАСС АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ ЛИНЕЙНЫХ ПРЕОБРАЗОВАНИЙ // Современные проблемы науки и образования. – 2012. – № 2.;
URL: http://www.science-education.ru/ru/article/view?id=5649 (дата обращения: 09.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074