ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Michael Bolotnicov                   2:5030/1197.101 03 Mar 2002  01:34:00
 To : Evgeny Sharandin
 Subject : 8-based FFT
 -------------------------------------------------------------------------------- 
 

 
 Ровно в 10:22 Evgeny Sharandin написал Michael Bolotnicov...
 
  ES> Reply-To: shar@nep.cplire.ru
 
  ES> Привет Michael!
 
  ES> 24 февраля 2002 года (а было тогда 01:45)
  ES> Michael Bolotnicov в своем письме к All писал:
 
  MB>> Вопрос1: как-нибудь можно еще ускорить это?
 
  ES> Hемного можно, если поменять порядок вычислений и, тем самым, облегчить
  ES> компайлеру работу.
 
  MB>> Или уже пора записывать временные данные в регистры CPU, перписывать
  MB>> на асме и прочее?
 
  ES> Зачем? Hормальный компилятор (gcc или Intel C сойдут ;) сделает не хуже.
  ES> Intel C еще и SSE попытается раскрутить.
 
  MB>> Вопрос2: это портабельно (если договориться о длине float-a) ?
 
  ES> Портабельно. А специально договариваться уже давно не требуется - на то
  ES> ай-яй-яй с ansi и существуют.
 
  ;-)))
 
  MB>> == Hачало 8FFT.C ==
  MB>> #define sq2 0.707106781
 
  MB>> void fft8(float *data) {
  MB>>  float d[16],e[16];
 
  MB>>  // precalculations
  MB>>  // reusable values 1
  MB>>  d[0]=data[0]+data[8];     // (h0+h4)
  MB>>  d[2]=data[4]+data[12];    // (h2+h6)
 
  ES> Здесь сразу можно вычислить e[0], e[4]. А так как d[0]/d[2] в дальнейшем
  ES> не используется, то нет необходимости в их сохранении. Если
  ES> компилятор достойный, то лобовая запись e[0]=data[0]+...+...+...
  ES> e[4]=data[0]+...-...-... сгенерится в код без лишних обращений к памяти.
 
  Угу.
 
  MB>>  d[4]=data[0]-data[8];     // (h0-h4)
  MB>>  d[6]=data[4]-data[12];    // (h2-h6)
 
  ES> аналогично с e[2]/e[6].
 
  угу ;-)
 
  MB>>  d[8]=data[2]+data[10];    // (h1+h5)
  MB>>  d[10]=data[6]+data[14];   // (h3+h7)
 
  ES> e[8]/e[12]. Причем, пока они еще в регистрах сопроцессора, то можно сразу
  ES> вычислить и data[0].
 
  Это хорошо.
 
  MB>>  d[12]=data[2]-data[10];   // (h1-h5)
  MB>>  d[14]=data[6]-data[14];   // (h3-h7)
 
  ES> И.т.д. ;). Просто учти, что дублирование содержимого регистров (коих в х86
  ES> всего-то 8 штук) и  сложение с вычитанием современные процы делают в разы
  ES> быстрее загрузки/сохранения содержимого из/в L1 (не говоря уже о l2 или
  ES> памяти). Да даже умножение (но не деление) куда менее болезненная
  ES> операция, чем обращение за операндами в память.
 
  Кстати, насколько быстрее обычного FFT будет FFT с приведением
  вычислений к таким вот FFT8 или FFT4 (т.е. бабочка рекурсивная
  до разбиения на длины 8 или 4 соответственно, затем вычисляются
  эти самые FFT4 и FFT8. Получившееся пересчитывается в конечный
  результат) ? Говорят, что всего на 20%-30%...
 
  P.S. спасибо за подсказку насчет дальнейшей оптимизации.
 
 ... The colors are fading...
 --- [ SPb LEEI ]__[ Psychedelic tribe ]__[ TB 303 ]__[ Simon Posford ]
  * Origin: Just a stunning stream of incomplete thoughts. (2:5030/1197.101)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    8-based FFT   Michael Bolotnicov   24 Feb 2002 02:45:00   8-based FFT   Evgeny Sharandin   28 Feb 2002 11:22:00   8-based FFT   Michael Bolotnicov   03 Mar 2002 01:34:00   8-based FFT   Evgeny Sharandin   11 Mar 2002 11:37:00   8-based FFT   Michael Bolotnicov   14 Mar 2002 02:31:00   8-based FFT   Evgeny Sharandin   17 Mar 2002 20:50:00   8-based FFT   Comoderator Of Ru Algorithms   05 Mar 2002 21:34:47