Параллельное преобразование Уолша

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

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

Временная сложность максимально параллельного вычисления конечного множества функций по схеме с динамическим распараллеливанием сохраняет оценку T(R) = 0(1) , где R зависит от максимального количества одновременно готовых аргументов. По величине порядка оценка не изменится, если в схему максимально параллельного вычисления функций дополнительно включить ярус аналогичного вычисления производных и определенных интегралов.

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

1. Аксайская Л.Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций: автореф. дис. ... тех. наук. Таганрог: Изд-во ЮФУ, 2008. 20 с.

2. Березин И.С., Жидков Н.Г. Методы вычислений. М.: Наука, 1970. Т. 1. 464 с.

3. Ромм Я.Е. Параллельные итерационные схемы линейной алгебры с приложением к анализу устойчивости решений систем линейных дифференциальных уравнений // Кибернетика и системный анализ. Киев, 2004. № 4. С. 119-142.

4. Ромм Я.Е., Аксайская Л.Н. Кусочно-полиномиальная аппроксимация функций на основе интерполяции по Ньютону в приложении к параллельной цифровой обработке сигналов // Вопросы современной науки и практики. Университет им. В.И. Вернадского. Серия «Технические науки», 2007. Т. 2. С. 107-118.

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

Исходные соотношения преобразования Уолша и определения. Функции Уолша представляют собой полную систему ортонормированных прямоугольных функций. Для нормированных функций Уолша принято обозначение 0 , где V - номер функции, а в находится в полуинтервале 0 < 0 < 1. Обычно рассматривается множество функций Уолша Ч'С{1 О при

БИБЛИОГРАФИЧЕСКИМ СПИСОК

Я.Е. Ромм, В.В. Забеглов

ПАРАЛЛЕЛЬНОЕ ПРЕОБРАЗОВАНИЕ УОЛША

j 1

где ТJ - 7 -й разряд представления числа Т в двоичной системе счисления, Г1оё = 1 : © -

символ поразрядного суммирования по модулю 2 ; Шб1, 0 - функции Радемахера, определяются следующим соотношением:

rad f,в J= sign Cn 4,J ттв^. в G 1,1

где у - целое неотрицательное число, а Л'/^Л ^ - функция, такая что Л'/^Я ^ 1, если

X > 0; % = -1, если X < 0. При X = 0 значение функции определяется по непре-

рывности справа.

Любая функция х(О) €= I, | ^ может быть разложена в ряд Уолша

х(6>) = 1>г>га/<, в],

г=0

коэффициенты разложения определяются по формуле

cr = e^jie.

Ограничиваясь N членами разложения, можно получить формулу усечённого ряда Уолша

N-\

x(e) = ^crwal4, в\

г—0

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

Алгоритм построения системы, содержащей N базисных функций, состоит из следующих этапов:

1. Вычисление функций / ^ j= sin ^ ' жв , в €Е 1 . / = 1, 2,... , log2 N;

2. По определению (2) вычисляются функции Радемахера rad4,6l 0е Г,

7=1, 2, ... , log2 N;

3. Функции Уолша \ш/ 6> е |), Г, г = 0,1,..., N -1, N = 2™ , JW = 1, 2, ... вычисляются посредством перемножения функций Радемахера в соответствии с (1).

Для поставленной цели может использоваться схема таблично-алгоритмической аппроксимации функций f — SHI ^ 7г0 на основе интерполяционного полинома с минимизацией

временной сложности [1]. Рассматриваются функциональная последовательность одной действительной переменной вида

f sin iJ тгв~~, в е |), Г, j = 1, 2,... , log2 N.

Выбирается система непересекающихся подынтервалов равной длины, объединение которых совпадает с Ц, 1 :

о

р-1 -1л>и М,

Р для определенности предполагается целой степенью по основанию 2. Таким образом,

вм-в1= 1/Р,/ = 0, 1, Р-1, Р = 2\£ = 0,

При априори заданной границе £ абсолютной погрешности аппроксимации функций (3) и для каждого отдельно взятого подынтервала из (4), (5) строится интерполяционный полином степени П , где П выбирается минимальным для достижения заданной точности приближения одновременно на всех подынтервалах. При этом полином в общем случае преобразуется по дистрибутивности с приведением подобных так, что в результате преобразования на i -м подынтервале принимает канонический вид полинома от одной переменной:

Р ^п +ал в+ а0 в2 +...+ а ..в\

И ^ -> о 1] Ъ] 21] к lj

ве I , 0..Л п= const, / = 0, 1, ... , Р-1.

л ? г+1 S ' ? ? ?

В (6) индекс коэффициента i совпадает с номером подынтервала, индекс j соответствует

номеру аппроксимируемой функции.

Построение (6) выполняется для всех подынтервалов, причем так, чтобы на каждом из них не превышалась заданная граница погрешности

i = о, 1,

Р-1.

В (6), (7) значение П выбирается минимально возможным, при условии, что оно одинаково для всех подынтервалов. Если такое П найдено, то для каждой функции из (3) и для каждого подынтервала из (4) набор коэффициентов в (6) можно записать в память машины и сделать хранимым. В дальнейшем, когда потребуется вычислить функции данного вида, вначале для каждого фиксированного номера функции у дешифруется значение номера I подынтервала, значения

номеров I и ] служат математическим адресом выборки коэффициентов (6), взаимно однозначно соответствующим данному номеру подынтервала. Если оказалось, что 0 €Е ^, 0М , то в обозначении И = 01 + 1 ~ 0 1 дешифрация значения индекса осуществляется по формуле

int

\hj

где int - целая часть. Порядок времени этой дешифрации оценивается как еди-

ничный

t = oC.

Если для рассматриваемых функций вычислить и хранить коэффициенты для всех 2к подынтервалов, то в дальнейшем время вычисления функций, с учетом (8), зависит только от степени полинома (6). По схеме Горнера значение этого полинома вычисляется с временной сложно/ ^ = П + I , где /. ( - время бинарного умножения и сложения соответственно.

стью

= о

За счет уменьшения длины подынтервала степень П в (8) можно сделать «сколь угодно» малой (но целой) при соответственном возрастании Р=Т в (5). При этом после выборки I, у -

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

С целью осуществления описываемого построения вычисление коэффициентов начинается

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

Затраты памяти в данном способе можно сократить следующим образом. При вычислении последовательности функций применительно к конструированию функций Радемахера (2) достаточно определить знак, который принимает функция (3). Если в системе подынтервалов (4), (5) число Р выбрать так, что каждая функция, входящая в последовательность (3), не будет менять знак на каждом подынтервале ^ , , то в ячейке памяти машины с математическим адресом I , ] можно хранить лишь одно битовое значение, которое соответствует знаку функции на данном подынтервале.

Обращаясь теперь к подынтервалу с дешифрированным адресом, можно считывать не

П+1 коэффициент и затем вычислять значение полинома П -й степени, аппроксимирующего

функцию (3) на данном подынтервале, а непосредственно, по тому же математическому адресу, считать значение знака, которое эта функция принимает на данном подынтервале.

Таким образом, при считывании знака с каждого подынтервала получаем систему функций Радемахера, не вычисляя последовательность функций (3). Временная сложность схемы вычисления функции Радемахера имеет порядок ¿ = <9 С , но при этом численное значение времени существенно ниже, чем при таблично-алгоритмической схеме, поскольку аппроксимирующий полином П -й степени с плавающей точкой не вычисляется вовсе.

Вычисление функций j¡ ^ ^ ^ Т[0 может выполняться с помощью полиномов Чебышева. Зависимости между полиномами Чебышева можно представить в матричной форме [5]:

/ = 1, 2,

с теми же начальными значениями. Отсюда

^ * '2* -IY/^O

T €

1 о

i\V

При помощи схемы Стоуна [1] вычисление [2х -1

1 О

для всех значении

/, / = 1, 2,

N

можно выполнить на Otf процессорах с временной сложностью О Cog 2 N . Доказательство приведено в [4].

Имеет место

лемма 1. Последовательность всех функций вида f j= 7l0 ,

J = 1,2,..., log 2 N можно вычислить с помощью схемы Стоуна на N процессорах с временной сложностью О Cog 2 N . 118

Построение функций Радемахера. Вычислив систему функций вида fJ С0= sin С' 710 . / = 1, 2, ... , log2 N, используя соотношение

rad sign {sin С ' 710^ , j = 1, 2, ... , log2 N, вычисляется система функций

Радемахера. По определению (2), каждому значению 0, в зависимости от номера J , ставится в

соответствие значение 1 или — 1.

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

radii, ОУ <-1 j"2 '" в е |), Г, j = 1, 2, ... , log2 N,

где | Ь - целая часть числа. Схема строится следующим образом. Сначала вычисляются, с по-

2'

мощью схемы Стоуна, степени двойки. А именно, находятся все двоичные степени a , / = 0,1, 2, ..„где Т <\og2N, а = 2,-

а2" = а,..., %i2'1 = а2', / = 0, 1, 2,... , log2 Cog2 N

Пусть j имеет двоичное разложение

iog2(iog2w) Го

j= Х>,-2',а,= /=1,2,... ,log2 N.

i-0 II

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

2 1 которой в (9) (X = 1. Временная сложность составит

re-log2AO=0<og2<og2AC

В полуинтервале J, 1 выбираются отсчёты 0j . / = 0, 1,___, Р — 1, постоянным шагом

}1 = 6-6 = Const. При фиксированном номере функции J каждому отсчёту 6 ставится процессор с номером ' , j . Процессоры параллельно выполнят умножение 21 -6 , далее

полученные произведения представляются в двоичной системе исчисления с точностью до целых. По значению младшего разряда (или непосредственной проверкой) определяется чётность числа и

в соответствии с чётностью ставится значение rod ({,0 sign ^sill ty 710 ^ . Таким образом, имеет место

лемма 2. Пусть выполнено рассматриваемое разбиение полуинтервала |), 1 на систему подынтервалов (4), (5). Тогда систему функций Радемахера, ограниченную log2 N членами, можно вычислить, с помощью схемы Стоуна, на О С'log2 N процессорах с временной сложностью О Cog2 Cog2

Если все степени двойки 2;, / =1, 2, ... , log 2 N вычислить наперёд, то в условиях (4), (5) для определения знака функции Радемахера достаточно выполнить только умножение 2; • 0.. На этой основе имеет место

лемма 3. Если в условиях леммы 2 все степени двойки 2;, J =1, 2, ... , log 2 N априори вычислены, то систему функций Радемахера, ограниченную log 2 N членами, можно вычислить на О ^ • log 2 N процессорах с временной сложностью О d или

rCMog2tf>0<C

Можно показать, что число ячеек памяти, указанное в лемме 3, можно сократить до значе-

log 2 N

ния I Р ,Р <Р . Таким образом, оценка сверху числа ячеек памяти составит

i=1

При этом общее число подынтервалов и ячеек памяти уменьшится, поскольку достаточно иметь длину подынтервала, сохраняющего знак 2; - О..

Вычисление функций Уолша. Каждой функции Уолша с номером Г, Г — О, 1, ... , N — 1, ставится в соответствие процессор с таким же номером. Процессоры, работая синхронно и независимо, параллельно перемножат функции Радемахера по формуле (1). Временная сложность схемы оценивается из соотношения

r«y><9<og27\T.

Таким образом, с учетом леммы 1 имеет место лемма 4. Значения ограниченной последовательности из

N функций Уолша можно вычислить на О процессорах с временной сложностью О Cog2 N , иными словами, вычисление выполнимо с временной сложностью (10).

Параллельное вычисление коэффициентов ряда Уолша. Коэффициенты ряда Уолша Сг, Г = 0, 1, ... , N — 1 вычисляются по формуле

1

г X

Cr = ¡x{/jval вув , r=0,1, 2,..., N-I.

о

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

cr = Jx^Tyval С, O^jix » ^х Сг 3З7

О i=0

где Р - число слагаемых формулы, И = \/Р , i = 0, 1,..., Р — 1, О = 0() + ih

г = 0,1, 2,..., N-1.

Соотношение (11) можно уточнить, если выбрать шаг П таким, что функции \VCll в ^

на каждом подынтервале , — С()П,\1 принимали только одно значение. Таким образом,

(11) примет вид

сг = | д-^ЗС в^х = ^х ^ 3С, вг У •

г

О ¿=0

Коэффициенты вычисляются независимо друг от друга по формуле (12) по схеме сдваивания за 1о§ 2 N шагов. Временная сложность схемы

Очевидно, порядок оценки (13) сохранится, если для вычисления коэффициентов С использовать формулы трапеций или формулу Симпсона. Однако количество процессоров будет зависеть от точности квадратурной формулы. Из изложенного вытекает

теорема 1. Если вычислена априори система базисных функций Уолша, содержащая

N

функций, то преобразование Уолша можно вычислить на процессорах с временной

сложностью О СоВ2 Р > иными словами, с временной сложностью (13).

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

теорема 2. Преобразование Уолша (12), ограниченное

N

членами, включая вычисление

системы базисных, полностью можно вычислить параллельно на процессорах с вре-

менной сложностью О 2 ^ О 2 ^

Заключение. Изложена схема параллельного выполнения преобразования Уолша. Алгоритм позволяет вычислять преобразование Уолша, изменяя количество отсчетов Р независимо от числа базисных функций N с временной сложностью Т ^  N О 2 N О Ср^ 2 Р . Следует отметить, что аналогичные схемы и оценки удаётся получить для преобразования Хаара [4].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Аксайская Л.Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций: автореф. дис. ... канд. тех. наук. Таганрог: Изд-во ТТИ ЮФУ. 2008. 18 с.

2. Залманзон Л.А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989.

3. Миклошко Й. Связь между алгоритмами, программами и структурой параллельных ЭВМ. // Алгоритмы математическое обеспечение и архитектура многопроцессорных вычислительных систем / под ред. А.П. Ершова. М.: Наука, 1982. С. 6-36.

4. Ромм Я.Е., Забеглов В.В. Параллельные схемы преобразований Уолша и Хаара. Таганрог: Изд-во Таганрог. пед. ин-та, 2008. 29 с.

5. Ромм Я.Е., Фирсова С.А. Параллельная схема дискретного и быстрого преобразований Фурье на основе полиномиального представления базиса // Известия РАН. Математическое моделирование, 2006. Т. 18. № 11. С. 3-12.

6. Хармут Х.Ф. Передача информации ортогональными функциями: пер. с англ. Дядюнова Н.Г. и Се-нина А.И. М.: Связь, 1975.