|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sashka Yackubtchick 2:5054/29.54 27 Feb 2002 04:49:19
To : Roma Baklanov
Subject : Алгоpитм БПФ для пpоцессоpа не имеющего умножения
--------------------------------------------------------------------------------
26 Feb 02 00:14, Roma Baklanov писАл(а) к Ivan Mak:
IM>> Для ускоpения выполнения БПФ стpоится некий код, котоpый пpоизводит
IM>> умножение на константу, путем сложения...
RB> [..]
IM>> Вопpос, в общем, занимался ли кто-нибудь подобной вещью и получилось
IM>> ли?
RB> Хм.. возможно, я плохо понял, что имеется в виду, но умножать лучше
RB> путем _сдвигов_ и сложения их результатов. Кол-во итераций будет равно
RB> кол-ву уст. бит в умножаемом числе.
В множетеле наверно?
RB> Причем запросто реализуется и умножение вещественных чисел. Кол-во
RB> итераций при этом даже не возрастает.
Просто мысль такая, перед началом цикла проверить какое из чисел имеет больший
старший бит и умножать на то у которого он меньший.
Дальше уже не конкретно тебе, а просто кому это интересно.
О реализации:
Hедавно писал такой код для умножения 8и двойных слов на маленькое число
(для баз данных, где нужно умножать большие массивы по выборке на небольшое
заданное число)
В блоке управления кажется можно оптимизировать. Может у кого мысль будет какая.
Пояснение из базовой позиционной арифметики:
101001 = 100000+1000+1
101001*11= 101001*(10+1)=101001*10+101001*1
Понятно что последнее даёт возможность привести умножение на любое
число к сдвигам и сложению даже если сам множитель не является степенью
двойки.
Внутренний цикл умножения (повторятся колличество эл.\8 раз остаток умножается
в конце дополнительно)
;[eax] - указатель на очередную группу из 8и DWORDs ecx - множитель
;примичание типа 2а такта означает что 4е нижеследующие команды выполнятся
;за 2а такта паралельно в разных ALU
;обнулим 4е 64 разрядных регистра - 2 такта на 4е комнанды
pxor mm0,mm0
pxor mm1,mm1
pxor mm2,mm2
pxor mm3,mm3
;загрузим 8 слов в четыре других регистра 2 такта если данные в кеше и
;выравнены на четыре команды.
movq mm4, [eax]
movq mm5, [eax+8]
movq mm6, [eax+16]
movq mm7, [eax+24]
test ecx,ecx ;если множетель 0 - на выход запишем обнуленные
;регистры как результат
je @write
jmp @start ;иначе - начать выделение умножений на степень двойки
@1:
paddd mm0,mm4 ;прибавим произведение на очередную степень
paddd mm1,mm5 ;двойки если она присутсвует в множимом 2 такта
paddd mm2,mm6
paddd mm3,mm7
@2:
psllq mm4,1 ; выделим произведение на очередную степень двойки
psllq mm5,1 ; 2 такта
psllq mm6,1
psllq mm7,1
@start: shr ecx,1 ;разделим множитель на 2а если последний бит =1 CF=1
je @end
jc @1
jmp @2
@end:
paddd mm0,mm4 ;старший бит всегда = 1 так что просто прибавим
paddd mm1,mm5 ;без проверки произведение на его степень двойки
paddd mm2,mm6
paddd mm3,mm7
@write:
movq [eax],mm0
movq [eax+8],mm1
movq [eax+16],mm2
movq [eax+24],mm3
(тут увеличиваем указатель в eax и грузим следующие 8 двойных слов)
при значении второго множетеля < 64 (что довольно часто в наших задачах)
умножение выполняется в большинстве случаев быстрее даже чем оптимизированное
через FPU с паралельной реорганизацией стека.
Hасколько я помню в детский книжках сам мат логика этого называется
"Метод русских крестьян" :)
Что касается "низкоуровневых" аспектов, алгоритм работает хуже
если биты сброшенные и выставленные распределены равномерно.
То есть лучшие множители 11111 или 000000
Худшие соответственно 1010101 или 0101010
Связано с предугадыванием переходов.
Пока!
Sashka, The Svin.
--- GoldED/W32 3.00.Beta1+
* Origin: Svin, Perm, Russia (2:5054/29.54)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Алгоpитм БПФ для пpоцессоpа не имеющего умножения 