Анализ временных затрат на вычисление с помощью полосковой диаграммы

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

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

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

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

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

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

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

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

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

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

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

времени, что и для вычисления спектра мощности с помощью вещественной и мнимой частей ДПФ.

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

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

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

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