Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 20

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

Текст из файла (страница 20)

Можно заметить, что в табл. 8.2 и 8.3 массив Е(0, ч) содержит не только элементы исходной последовательности, но и результаты их перестановки, обеспечивающей экономию числа ячеек памяти ЭВМ, для чего потребуется ряд искусственных приемов. Например, если элемент Г(0, 8) должен быть размещен на позипди (0,1)„то, как обусловлено второй строкой столбца «Перестановка», сначала элемент Р(0,1) следует занести на временную позицию. Затем этот элемент может быть размещен на позиции (0,8), что определено 9-й строкой. Аналогичные приемы предусматриваются в случае, когда результаты выполнения 1-го этапа преобразования должны быть возвращены к расположению исходной последовательности.

Для каждого элемента на входе блока, реализующего 1-й этап преобразования, потребуются две временные позиции, на входе блока, реализующего 2-й этап — четыре позиции и т.д. В программе вычислений количество позиций, используемых для запоминания элементов массива, равно ИР, а для наиболее эффективного варианта это число просто равно А1. Тогда после завершения вычислительного процесса элементы преобразования займут позиции элементов исходной последовательности. Это означает, что будет выполнено стирание исходных данных; естественно, исходные данные всегда могут быть восстановлены в результате дальнейшего преобразования, но в общем случае следует заблаговременно уделить внимание выполнению любых требуемых операций над исходными доследовательностями, таких, как табулирование или графическое построение, если массив памяти ограничен .э( позициями. Вычислительная процедура с замещением используется в программах ГНТЯ)В и ГНТРОК.РОК (приложение 1).

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

Анализ фактических временных затрат показывает, что отдельные компоненты программы вычисления имеют разный удельный вес в суммарном времени счета (машинном времени), изменяющийся при изменении величины /т'; в результате отсутствует простое соотношение между скоростями выполнения математических программ (соответственно, между временем их реализации) для БПХ и БПФ. С !04 О в и га Л-1еуея Рис. 8,4.

Полосковая диаграмма, иллюстрирующая зависимость затрат времеви, необходимых для выполнения ДПХ, от числа элементов послеловательисспг данных. полной определенностью можно допустить зависимость отношения интервалов машинного времени для двух преобразований от л/, однако наряду с этим данное отношение будет зависеть и от других факторов. Чтобы понять это, необходимо проанализировать процедуру хронометрирования для какого-либо частного случая. Реальная программа, которая л(етально будет исследоваться ниже, может быть проанализирована с помощью результатов, представленных на рис. 8.4 в виде полосковой диаграммы.

Программа разбивается на ряд отдельных подпрограмм следующим образом: а) название программы, б) ввод данных, в) предварительное вычисление степеней числа 2, г) предварительное вычисление синусов и косинусов, д) перестановка, е) совокупность 1-го и 2-го этапов, ж) этапы с 3-го по (Р— 1)-й, з) преобразование в ДПФ. Название программы является одной из ее существенных компонент, которая, однако, незначительно зависит (или совсем не зависит) от величины Х; для прецедуры ввода данных специальные комментарии не требуются.

Предварительное составление расчетной таблицы степеней числа 2 оказывается полезным в силу того, что многие элементы структуры программы связаны с блоками ее компонент, имеющими длину /9/2, 19/4 и т.д. Все зти величины являются степенями числа 2, если А1 представляет собой степень этого же числа, и гораздо целесообразнее располагать этими степенями заранее, чем вычислять требуемые Ж/2 значений (в случаях, когда деление на 2 занимает время, сравнимое с затратами времени на реализацию других операций); числа, субкратные величине /1/, встречаются в итерациях (циклах), и многократное повторение одного и того же 105 действия деления связано с неоправданными потерями времени. В некоторых ЭВМ действие деления на 2 может быть реализовано с помощью регистров сдвига; в подобных ситуациях вопрос предварительного вычисления, возможно, может быть пересмотрен.

Этим примером иллюстрируется толкование вопроса, касаи>щегося отношения скоростей (быстродействия в реализации алгоритмов БПХ и БПФ), которая, как очевидно, зависит как от параметра 1э', так и от типа используемой ЭВМ. Даже если рассматривать это отношение для одной ЭВМ при фиксированном 1>1, то применительно к двум алгоритмам, использую>цим один и тот же метод реализации процедуры получения степеней числа 2, отношение скоростей будет изменяться при переходе к другому методу, если данная часть программы требует неодинаковых затрат времени в каждом случае. Предварительное вычисление синусов и косинусов выполняется с той же целью: во избежание многократного повторения этих операций, однако оно требует временных затрат, превышающих на порядок величины время вычисления степеней числа 2, и явилось объектом внимания специалистов.

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

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

Для всех последующих этапов, а именно с 3-го но (Р— !)-й использовалась общая формула, даже несмотря на незначительную экономию, которая была обнаружена при отдельном анализе 3-го этапа. Программа, представленная в приложении 1, реализует повторное вычисление константы г = 0,707, фигурирующей в процедуре выполнения 3-го этапа.

Наконец, значительное дополнительное время требуется при необходимости формирования ДПФ. Однако при определении спектра мощности не реализуются требуемые дополнительные резервы времени, так как спектр мощности может быть вычислен исходя из ДПХ путем оценки величины (Н(и))'+ 1Н(14 — ч)3'. Эта операция может быть реализована в пределах того же интервала 106 времени, что и для вычисления спектра мощности с помощью вещественной и мнимой частей ДПФ.

Естественно, время, требуемое на процедуру вычисления в целом, возрастает с увеличением А>, однако зависимость от Х по-разному проявляется на разных этапах выполнения преобразования. Как хорошо известно, время счета (машинное время) приближенно описывается законом вида 1>'!ой>А>, или 1>1Р, по этой причине по оси ординат откладывается отношение времени к произведению 1>7Р. Можно убедиться в том, что по мере увеличения 1ч Машинное время — 0,045 А>Р секУнд.

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

Идея заключается в нормировке относительно Т,, †време, затрачиваемого на выполнение четырех действий умножения. Тогда имеем Машинное время = уПРТ4. Коэффициент качества, как оказывается, приближенно равен 1, а для приведенного выше случая он приближается к значению 1,3 при Р- 20. Дчя более коротких последовательностей у несколько больше, в чем можно убедиться из анализа соотношения, поясняющего процедуру нормировки.

Характеристики

Список файлов книги