Сравнение быстродействия

Аватара пользователя
Santik
Сообщения: 609
Зарегистрирован: 28 дек 2010, 08:04
Откуда: Мирный (Якутия)
Контактная информация:

Сравнение быстродействия

Сообщение Santik »

Кто-нибудь сравнивал быстродействие FFT на С с аналогичной процедурой из Фортрановской библиотеки?

SPACUM
Сообщения: 10
Зарегистрирован: 19 дек 2010, 21:35

Re: Сравнение быстродействия

Сообщение SPACUM »

О каких именно библиотеках иднт речь? Мой С такой не имеет, наверное ФОРТРАН тоже. В интернете много готовых текстов программ и несколько библиотек. Если у Вас есть обе, почему не проверили сами?

Теперь о быстродействии;
1.Программа БПФ - это большое число комплексных умножений и сложений и некоторая управляющая логика.
Причем, обычно, 90% времени тратится на умножения и сложения. Алгоритмы давно вылизаны и значительного различия в быстродействии не предвидится.

2.Вообще должно быть 3 функции БПФ.
Это RealFFT - для одной действительной выборки, она же самая быстрая.
По алгоритму Кули-Тьюки, тоже быстрая, если учесть, что рассчитывает два RealFFT одновременно.

По алгоритму Винограда, немного помедленнее, для выборок не кратных степени 2 в частности на 1000 или

2000 точек, что позволяет и время и частоту иметь в приятных десятичных единицах.(исторически на древнем ФОРТРАНе с медленным программным умножением этот метод был самым быстрым т.к. количество умножений уменьшено)

3. Еще одним параметром влияющим на скорость является разрядность. Чем больше разрядность тем меньше

скорость. Наличие плавающей точки значительно уменьшает скорость и сильно уменьшает точность

(для float вместо long - это 3 байта вместо 4-х = 256 раз и еще хуже для double вместо int_64). Однако на относительно медленных процессорах с очень быстрым арифметическим блоком наличие плавающей точки не критично.

4.Библиотека должна быть привязана к процессору. Особенно если есть несколько арифметических блоков или несколько ядер. Если производитель процессора не предоставил библиотеку - пишите сами. БПФ не слишком сложный алгоритм и есть множество примеров. Написанная Вами библиотека привязанная к процессору всегда будет быстрее любой универсальной.

5.Еще можно немного выиграть имея таблицу перестановок. Не думаю, что она включена в стандартную

функцию для любой длины выборки.

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Re: Сравнение быстродействия

Сообщение Ivan Karamazov »

3. Еще одним параметром влияющим на скорость является разрядность. Чем больше разрядность тем меньше скорость. Наличие плавающей точки значительно уменьшает скорость и сильно уменьшает точность
(для float вместо long - это 3 байта вместо 4-х = 256 раз и еще хуже для double вместо int_64). Однако на относительно медленных процессорах с очень быстрым арифметическим блоком наличие плавающей точки не критично.
Нет, к сожалению Вы ОЧЕНЬ глубоко заблуждаетесь. Скорость в пределах плав. точки не зависит от разрядности -- по кр. мере до тех пор, пока используется компилятор Микрософт (т.е. система команд i387) -- вычисления с плав. точкой всегда делаются для 10-байтового представления, а далее по мере необходимости округляются для сохранения в переменных double (8 байтов) либо float (4 байта). При использовании SSE2 (GNU GCC для x64 по умолчанию) ситуациия, слегка отличаясь в деталях, в целом та же. С точки зрения времени доступа к памяти -- тоже ни выигрыша, ни проигрыша нет -- потому как процессор (точнее, контроллер памяти) за один раз считывает не менее Cache Line Size (обычно 8 или 16) 32-разрядных слов.
С целочисленной арифметикой, ситуация хуже -- операции с ней делаются много медленнее (т.е умножение/деление, чего вполне достаточно :( ) чем с плавающей. Особенно это заметно на (относительно медленном :) ) Intel iCore; достоверно известно (из data sheet'ов), что AMD-K10 делает целочисленное умножение в 2 раза быстреее, чем iCore i7 (при равной тактовой), но все равно, код с double на AMD делается быстрее, чем целыми числами. (Вот конкретно К-10 не проверял за неимением.) -- т.е. приходится считать, что все современные процессоры эволюционируют в сторону "относительно медленных".
пример -- свертка:
double / C:

Код: Выделить всё

/* make the one sample conversion
*/
static void MakeSample(LRCH *ch, const double *hpr)
{
  double hilb;
  int i, ix;
 
  hilb = ch -> s_in * hpr[0];       // все переменные -- double
  for(i = 1, ix = ch -> ixCur; i <= n_delay; ++i)
  {
    ix -= 2;					// take PREVIOUS value (step 2)
    if(ix < 0)
      ix += k_M;
    hilb += ch -> s_buf[ix] * hpr[i];
  }
 // ....................
 // indexes
  ch -> ixCur = (ch -> ixCur + 1) % k_M;
  ch -> ixOutRe = (ch -> ixOutRe + 1) % k_M;
}


все рабочие переменные -- double.
Альтернатива -- то же в целых числах:

Код: Выделить всё

/* make the one sample conversion
*/
static void MakeSample(LRCH *ch, const HSI32 *hpr)
{
  HSI32 hilb;
 
#if	0                                      // это все закомментировано до #else !!!!!!
  int i, ix;
  hilb = ch -> s_in * (long long)hpr[0];
  for(i = 1, ix = ch -> ixCur; i <= n_delay; ++i)
  {
    ix -= 2;					// take PREVIOUS value (step 2)
    if(ix < 0)
      ix += k_M;
    hi += ch -> s_buf[ix] * (long long)hpr[i];
  }
#else
  hilb = mk_hilb(ch -> s_in, ch -> s_buf, hpr, ch -> ixCur);
#endif

// .....................
 // indexes
  ch -> ixCur = (ch -> ixCur + 1) % k_M;
  ch -> ixOutRe = (ch -> ixOutRe + 1) % k_M;
}

/* make Hilbert's transform
*/
static HSI32 mk_hilb(HSI32 s_in, HSI32 *s_buf, const HSI32 *hpr,
	int ixCur)
{
  int cnt;
  HSI32 k_M_bytes;
__asm
  {
// умножение 32*32->64; сложения -- 64-битные; результат округляется до 32 бит
	mov	eax, k_M
	shl	eax, 2
	mov	k_M_bytes, eax
	mov	edi, hpr	// hilb = s_in * hpr[0]
	mov	eax, s_in
	imul	DWORD PTR [edi]
	mov	ebx, eax	// ecx:ebx -- accumulator
	mov	ecx, edx
	mov	eax, n_delay	// counter
	mov	cnt, eax
	mov	esi, ixCur
	shl	esi, 2              // здесь была копирования  shl esi, 255
	add	esi, s_buf	// esi = &s_buf[ixCur]
hilb_loop:
	sub	esi, 2 * 4	// take previous value
	add	edi, 4
	cmp	esi, s_buf
	jae	SHORT s_buf_ptr_ok
	add	esi, k_M_bytes
s_buf_ptr_ok:
	mov	eax, [esi]
	imul	DWORD PTR [edi]
	add	ebx, eax
	adc	ecx, edx
	dec	cnt
	jnz	SHORT hilb_loop
	mov	eax, ecx	// the result must be 32 bits
	shld	eax, ebx, 1	// s32 * s32 == s63, not i64!!
  }
}
Этот код выполняется примерно в 1.5 раза медленне на АМД К8, чем предыдущий, на на Intel i7/i5 -- почти в 2 раза медленне!! Несмотря на максимальную оптимизацию, использующую (почти) недоступные для C умножения int32*int32 == int64 за одну команду + сложение с переносом за две простых команды. (Закомментировный условной трансляцией код с использовонием __int64 настолько медленный, что даже ждать нет смысла :) -- там умножение выполняется вызовом внутренней ф-и, хотя для отдельно взятого компилятора и можно получить код, зкв. ассемблерному, но это будет ненадежный хак .)
Заметьте, что здесь четко соблюдены базовые правила оптимизации под Intel!!!
ps: когда то я где-то писал (и не получил возражений): -- performance difference:
I had try both versions to convert a file about 55 minutes. The results for different CPU:
iNTEL Core I7: int: 5' 40"; double 3' 06"
AMD K8: int 8' 15"; double 5' 55"
AMD K7: int 11' 52"; double 8' 06"
*So, I prefer double version.* -- это реальная статистика
ВНИМАНИЕ: -- если сомневаетесь, прежде чем гневно возражать, проверьте сами на любом примере, который нравится. Учтите при этом, что челочисленные сложения/вычитания, да, быстрые операции, а вот умножения/деления -- это да. Но без по кр. мере умножения -- ну никуда, к сожалению.
Если говорить о точности -- 52 бита+знак у double теоритически в некоторых случаях несколько хуже, чем 63 бита+знак у __int64. Тем не менее, (1) это соизмеримо (2) это много больше реальных разрядностей ЦАП и АЦП и (3) при выполнении "однородных" преобразований типа БИХ фильтра высокого порядка Вам придется масштабировать коэффициенты так, что потеря точности будет на самом деле больше, чем разница в разрядности double и __int64.
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

SPACUM
Сообщения: 10
Зарегистрирован: 19 дек 2010, 21:35

Re: Сравнение быстродействия

Сообщение SPACUM »

"прежде чем гневно возражать"
Ну зачем же возражать? Последние 3 года программирую только на микроконтроллерах. И не самых быстрых.
Использую 32-битную арифметику(float не хватает по точности). При переходе на новый процессор переписываю умножение в ассемблере и считаю все оптимизированным. Выигрыш 1.5 раза.
Абсолютно так-же делал проверку на моем AMD.
Перепроверю не скоро на работе запарка, прибор сдаем. Пока будем считать, что Вы правы.
* Если можно, ответьте топикстартеру по скорости БПФ (Процессор->алгоритм->число точек->время выполнения.)

Аватара пользователя
Santik
Сообщения: 609
Зарегистрирован: 28 дек 2010, 08:04
Откуда: Мирный (Якутия)
Контактная информация:

Re: Сравнение быстродействия

Сообщение Santik »

Интересует сравнение скорости FFT dsp.dll и FFTW 3.2.2

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Re: Сравнение быстродействия

Сообщение Ivan Karamazov »

Про dsp.dll -- не скажу, т.к. согласно описанию она делает БПФ только при числе отсчетов 2**N. Про FFTW3.2.2 -- процессор iCore I5 мобильный, 3 МБ L3, 2 ядра, 2.4 -> 2.66 ГГц, HiperThreading(tm) отключен (!!! -- ОБЯЗАТЕЛЬНО); ОС -- Win7Pro-x64, 4 ГБ RAM.
FFTW -- авторская 64-битная сборка (MinGW64, кросс-компилирована, +SSE2, +многопоточность). Wisdom's не используютя, планы удаляются сразу после применения + полня очиска после каждого преобразования (fftw_cleanup() -- все для экономии памяти). Тюнинга никакого, т.е. FFTW_ESTIMATE. Преобразования -- по месту (т.е. входной буфер -- он же выходной (наихудший вариант). Число потоков преобразования -- 2 (по числу ядер).
Сигнал -- 139'140'336 отсчетов. Последовательно делаются 2 преобразования:
dft_r2c_1d и dft_1d с опцией FFTW_BACKWARD. Все вместе с подготовкой планов и не включая чтения/записи занимает 1'9" +-5".
Важные замечания по FFTW: (1) она распротраняется строго под GNU GPL (без компромиссных LGPL и коммерческих лицензий).
(2) Общая схема построения библиотеки приведена в http://www.fftw.org/fftw-paper-ieee.pdf. Статья написана весьма простым языком и является, на мой взгляд, неплохим продолжением темы БПФ этого сайта, равно как и источником дополнительных ссылок.
(3) FFTW не слишком быстрая при малых значениях числа отсчетов -- определить понятие "малости", ниже которой применение FFTW нерентабельно, каждый должен сам, экспериментально, поскольку это очень сильно зависит от особенностей конкретной системы (даже в классе современных x86 / x64).
(4) Компиляция под MS VC: на сайте http://www.fftw.org выложены два набора проектов для компиляции библиотеки под Микрософтовской студией -- для VC2008 и VC2010. Те, которые для VC2008 -- однозначно не годятся (согласно прилагаемому config.h) для x64, с x86 -- тоже проблемы (хоть компилится и без ошибок). Те, которые для 2010 -- вроде как работают (x86/x64) (все равно желательно просмотреть все свойства проектов, что-то очевидное я там правил -- типа использования CRT DLL и имен библиотек). Серьезно не проверял, и не все помню -- кажется, там SSE2 не поддерживается, хотя могу ошибаться. В общем, компиляция для 2010 имеет смысл, только если вы пишите все на VC2010 -- чтобы избежать крайне неприятного different runtime (для FFTW и своей проги) -- и придется потратиться на доп. тестирование -- если, конечно, результат для вас имеет значение :)
(5) -- FFTW plan -- сам по себе -- компактная структура данных. Тем не менее ф-и, его вычисляющие (даже при FFTW_ESTIMATE) (типа fftw_plan_dft_XXX...() -- в процессе построения в импульсе могут жрать очень много памяти (по их завершении все освобождается), каковой может не хватить (особенно, для 32-битных систем). При этом возвращаемый plan (на самом деле -- указатель) может оказаться == 0 без спец. предупреждений. Т.е. прежде нежели передавать его fftw_execute() -- обязательно проверяйте его на неравенство NULL, иначе все вылетит либо по эксепшену, либо по ассерту (не вполне очевидно из мануала).

Для SPACUM::
Вообще говоря, я склонен во всем сомневаться (хотя, конечно, после "лобовой" реализации свертки очень трудно). Если Вы действительно хотите / найдете время сравнить double с int32-64 на x86 (x64), и получите результаты, опровергающие мои, пожалйста, заведите тему. Я буду рад конструктивно поучаствовать, только очень медленно, по причине, что мне не только прибор сдавать. Тема представляется важной, хотя бы уже потому, что море народа совершают чудеса героизма, чтобы обеспечить "целочисленнось" своих алгоритмов -- что, конечно, весьма актуально для встраиваемых систем, но на процессорах общего назначения ничего, на мой текущий (уже почти 3 года как) взгляд, не дает. Кстати, AMD K5/K6 не считаются -- у них плавающая точка была реально медленная, но они, кажется, уже вполне забытая история.
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

Ответить