Нужно рассчитать корреляционные функции для 4 массивов данных по 21 млн точек.
Соответственно 4 автокорреляционные функции и 12 взаимнокорреляционных функций.
Проблема в том, что по примерным моим подсчетам вычисление функций займет минимум 45 дней(!!!)
Это при всем при том, если вести рассчет, разделив вычисления на потоки, и загрузив все ядра процессора Intel Core i7
(за 4 суток непрерывной работы было выполнено всего лишь около одной десятой доли всех рассчетов).
Можно ли переложить код на С/С++ для исполнения под CUDA и как будет выглядеть этот код?
Написал и оптимизировал(на мой взгляд дальше оптимизировать некуда, разве что меньше циклов сделать...) код на Delphi для рассчета этих функций(приведен ниже. Думаю для тех, кто пишет на Си, прочитать код будет тоже нетрудно).

Фактически считаются суммы произведений - это место как раз я и хочу переложить на исполнение видеокартой.

NPackets - число точек минус 1 (в случае NPackets=74999 программа работает 5 минут на 1 ядре проца "Intel Core 2 Duo 2.26MHz")
Kans[1..4] - 4 массива чисел типа Double по NPackets+1 элементов
NKV=16 - 16 вариантов взаимнокорреляционных функций.
Vzaimkorr[1..NKV] - все взаимнокорреляционные функции, включая автокорреляционные(с 1 по 4)
vk[1..NKV,1..2] - все возможные варианты взаимнокорреляционных функций. Включает номера массивов с 1 по 4 в разных комбинациях(значения "1,1" или "2,2" означают автокорреляционную функцию, "1,2" или "1,4" - взаимнокорреляционную)



 for k1:=1 to NK do // NK=4 - число массивов данных
  begin
    Means  [k1]:=Mean  (Kans[k1]);         //считаем все средние значения
    stddevs[k1]:=stddev(Kans[k1]);         //считаем все стандартные отклонения
    for k:=0 to NPackets Do
      Kans   [k1][k]:=Kans[k1][k]-Means[k1];    /// нормируем все значения всех массивов данных      
  end;

  For k1:=1 to NKV do //все 16 вариантов взаимнокорреляционных функций
    For t1:=0 to NPackets Do  //t=0...T
      For t2:=t1 to NPackets Do  //k=t...T  (смещение одной функции относительно другой)
        vzaimkorr[k1][t2-t1]:=Vzaimkorr[k1][t2-t1]+Kans[vk[k1,1]][t1]*Kans[vk[k1,2]][t2];//

  for k1:=1 to NKV do     
  begin
    For t2:=0 to NPackets-1 Do
      VzaimKorr[k1][t2]:=VzaimKorr[k1][t2]/(NPackets-t2);
      Vzaimkorr[k1][NPackets]:=0;
    For t2:=0 to NPackets Do
      Vzaimkorr[k1][t2]:=VzaimKorr[k1][t2]/(stddevs[vk[k1,1]]*stddevs[vk[k1,2]]); //делим на знаменатель
  end;

...........

  vk[1 ,1]:=1;
  vk[1 ,2]:=1;
  vk[2 ,1]:=2;
  vk[2 ,2]:=2;
  vk[3 ,1]:=3;
  vk[3 ,2]:=3;
  vk[4 ,1]:=4;
  vk[4 ,2]:=4;

  vk[5 ,1]:=1;
  vk[5 ,2]:=2;
  vk[6 ,1]:=1;
  vk[6 ,2]:=3;
  vk[7 ,1]:=1;
  vk[7 ,2]:=4;

  vk[8 ,1]:=2;
  vk[8 ,2]:=3;
  vk[9 ,1]:=2;
  vk[9 ,2]:=4;
  vk[10,1]:=2;
  vk[10,2]:=1;

  vk[11,1]:=3;
  vk[11,2]:=4;
  vk[12,1]:=3;
  vk[12,2]:=1;
  vk[13,1]:=3;
  vk[13,2]:=2;

  vk[14,1]:=4;
  vk[14,2]:=1;
  vk[15,1]:=4;
  vk[15,2]:=2;
  vk[16,1]:=4;
  vk[16,2]:=3;


Это сообщение отредактировал(а) daemvil - 10.12.2010, 17:29

Раз на Delphi пишите, думаю вам будет комфортнее использовать OpenCL.NET + Delphi.NET. Ну и набор видеокарт, на которых это будет работать будет пошире.


Это сообщение отредактировал(а) Sartorius - 10.12.2010, 17:32

1) а на быстродействии это никак не скажется?
2) код будет фактически на Дельфи?

оф сайт OpenCL.NET
OpenCL



Счет идет на карте, так что использование различных оберток-интерфейсов к GPU не влияет на производительность практически


На Delphi.NET. Синтаксис Delphi

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

Это сообщение отредактировал(а) daemvil - 17.12.2010, 11:59

daemvil, c OpenCL замучаетесь. Я бы его точно использовать не стал. 

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



Задача с взаимными корреляциями это фактически расчёт корреляционной матрицы для 4 признаков. Для автокорреляции там всё зависит от размера окна с которой вы считаете корреляцию.

Тем не менее, я взял Matlab и посчитаз корр. матрицу для двумерного массива 21000000х4. Простой скрипт:



Эти вычисления матлаб не параллелит, процессор у меня Core i7 930 2.8 GHz. Как видите 12 секунд, а не 45 дней. 
Так что не знаю о чём вы и зачем вам тут графические ядра.

То есть это фактически автокорреляционные функции? тип точек должен быть - Double.
А еще сдается мне, что это всего лишь корреляционные коэффициенты, раз упоминается матрица(сдвиг по времени[по номеру точки] равен нулю). Значит, чтобы посчитать корреляционные функции, надо проделать эту операцию 21000000 раз.
а как взаимнокорреляционные считать в матлабе?(если это вообще он именно функцию этой командой считает)

Не знаю, по каким формулам матлаб считает, и считает ли он именно то что мне надо. Попробую поставить матлаб и проделать эту операцию. может и есть какие-то преобразования для упрощения рассчетов, чтобы не считать "в лоб", но...
я пробовал свободную программу SciDAVis (на sourceforge качал), она для 75000 точек считает одну взаимнокорреляционную функцию и строит ее график секунд только за 20.

....

Насчет функции corr() - так и есть, это коэффициент корреляции, так что решение с матлабом отпадает. к тому же, мне надо написать программу, а не пользоваться матлабами...

Добавлено через 12 минут и 58 секунд
а если в матлабе только 1 точка считается 11 секунд, то по моим прикидкам ему понадобится 89.12 мес на расчет всех 16 функций.

Это сообщение отредактировал(а) daemvil - 19.12.2010, 15:29

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

В таком случае тебе нужно гуглить на тему быстрого расчёта таких функций, например "fast cross-correltation function". 

Тут нужно использовать тот факт (и все быстрые алгоритмы это делают), что взаимная корреляция двух функций в исходной области их определения эквивалентен свёртке, а значит сложность у тебя сейчас O(N^2), для 16 функций получается 16 * 21 000 000 ^ 2 = 7 056 000 000 000 000. Это оценка порядка примерная.

Но свёртка во временной области эквивалентна перемножению спектров в частотной. А БПФ выполняется уже за O(N*log(N)). Таким образом порядок сложности ~ 16 * 21000000 * 16 * 2 ~ 11 000 000 000. На 2 умножаем потому что требуется ещё обратное преобразование. 

Начни смотреть отсюда: http://alglib.sources.ru/fasttransforms/crosscorrelation.php

Далее, если скорость не устроит в alglib, я советую воспользоваться библиотекой fftw, это пожалуй самая быстрая в мире библиотека для БПФ на архитектуре x86-64. 
Если и этого будет мало, то в стандартом SDK от NVIDIA для CUDA библиотека CUFFT, которая делает БПФ на GPU. Там же есть примеры вызова процедур оттуда. Но надо отметить, что на современном многоядерном процессоре fftw фору даст видеокартам среднего уровня. 



Это сообщение отредактировал(а) W4FhLF - 19.12.2010, 20:36

быстрее ipp ?

Все ж попробую с OpenCL разобраться до конца сначала. Использую пример, указанный в приложении к сообщению. При попытке компиляции выдает ошибку "[Fatal Error] Template.pas(204): Internal error: C1091". Список предупреждений и ошибку прикладываю. Даже не знаю на что грешить, никогда не сталкивался с такой ошибкой :(

Присоединённый файл ( Кол-во скачиваний: 4 )
 opencl.zip 32,23 Kb

Вот список предупреждений с ошибкой:

Присоединённый файл ( Кол-во скачиваний: 4 )
 errors.txt 2,77 Kb

http://www.fftw.org/speed/Pentium4-3.60GHz-icc/

Как я уже писал в соседней теме:



Так что тут тебе никто не помошник. Только танцы с бубном. OpenCL сырой, а тем более какой-то неофициальный порт под Делфи. 

А у CUDA уже есть готовая библиотека CUFFT, только функции вызывай.

baldina, ну да, на самом мощном процессоре от Интел с использованием компилятора (который платный под винду) интела и библиотек интела (которые не бесплатные и там ещё тонны стороннего функционала) в некоторых случаях ipp быстрее. В остальном FFTW рулит. 

'В некоторых' - это 'во всех больших 32' (64х и более точечный FFT) ? 

xvr, возможно у тебя стоит этот загадочный Пентиум 4 3.6 Ггц, у меня обычный Core Duo и х64 системы я не вижу большого смысла ставить кучу либ и компилятор от интела: http://www.fftw.org/speed/CoreDuo-3.0GHz-icc64/

Добавлено через 5 минут и 21 секунду
А на АМД ipp сливает везде.