F # / "Accelerator v2" реализация алгоритма DFT, вероятно, некорректна - PullRequest
Новая
       22

F # / "Accelerator v2" реализация алгоритма DFT, вероятно, некорректна

2 голосов
/ 27 июня 2010

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

Я почти уверен, что смогу предварительно рассчитать 90 градусов sin (i) cos (i), а затем просто перевернуть и повторить, а не то, что я делаю в этом коде, и это ускорит его. Но пока я даже не думаю, что получаю правильные ответы. Вход со всеми нулями дает результат 0, как я ожидал, но все 0,5 как входы дают 78.9985886f (в этом случае я также ожидал бы результат 0). По сути, я просто в целом запутался. У меня нет хороших входных данных, и я не знаю, что делать с результатом или как его проверить.

Этот вопрос связан с моим другим постом здесь 

open Microsoft.ParallelArrays
open System

 // X64MulticoreTarget is faster on my machine, unexpectedly
let target = new DX9Target() // new X64MulticoreTarget()

ignore(target.ToArray1D(new FloatParallelArray([| 0.0f |]))) // Dummy operation to warm up the GPU

let stopwatch = new System.Diagnostics.Stopwatch() // For benchmarking

let Hz = 50.0f
let fStep = (2.0f * float32(Math.PI)) / Hz
let shift = 0.0f // offset, once we have to adjust for the last batch of samples of a stream

// If I knew that the periodic function is periodic 
// at whole-number intervals, I think I could keep 
// shift within a smaller range to support streams 
// without overflowing shift - but I haven't 
// figured that out

//let elements = 8192 // maximum for a 1D array - makes sense as 2^13
//let elements = 7240 // maximum on my machine for a 2D array, but why?
let elements = 7240

// need good data!!
let buffer : float32[,] = Array2D.init<float32> elements elements (fun i j -> 0.5f) //(float32(i * elements) + float32(j))) 

let input = new FloatParallelArray(buffer)
let seqN : float32[,] = Array2D.init<float32> elements elements (fun i j -> (float32(i * elements) + float32(j)))
let steps = new FloatParallelArray(seqN)
let shiftedSteps = ParallelArrays.Add(shift, steps)
let increments = ParallelArrays.Multiply(fStep, steps)
let cos_i = ParallelArrays.Cos(increments) // Real component series
let sin_i = ParallelArrays.Sin(increments) // Imaginary component series

stopwatch.Start()
// From the documentation, I think ParallelArrays.Multiply does standard element by 
// element multiplication, not matrix multiplication
// Then we sum each element for each complex component (I don't understand the relationship 
// of this, or the importance of the generalization to complex numbers)
let real = target.ToArray1D(ParallelArrays.Sum(ParallelArrays.Multiply(input, cos_i))).[0]
let imag = target.ToArray1D(ParallelArrays.Sum(ParallelArrays.Multiply(input, sin_i))).[0]
printf "%A in " ((real * real) + (imag * imag)) // sum the squares for the presence of the frequency
stopwatch.Stop()

printfn "%A" stopwatch.ElapsedMilliseconds

игнорировать (System.Console.ReadKey ())

Ответы [ 2 ]

2 голосов
/ 28 июня 2010

Я разделяю ваше удивление, что ваш ответ не ближе к нулю.Я бы предложил написать наивный код для выполнения вашего DFT на F # и посмотреть, сможете ли вы отследить источник несоответствия.

Вот что я думаю, вы пытаетесь сделать:1005 * Надеюсь, вы сможете использовать этот наивный код, чтобы лучше понять, как должен работать код ускорителя, что может помочь вам при тестировании кода ускорителя.Имейте в виду, что одной из причин расхождений может быть просто точность вычислений - в ваших массивах ~ 52 миллиона элементов, поэтому накопление общей ошибки в 79 может на самом деле не так уж и плохо.FWIW, я получаю мощность ~ 0,05 при выполнении вышеуказанного кода одинарной точности, но мощность ~ 4e-18 при использовании эквивалентного кода с числами двойной точности.

2 голосов
/ 27 июня 2010

Два предложения:

  • убедитесь, что вы не путаете градусы с радианами
  • попробуйте сделать это без параллелизма или просто с помощью асинхронности F # для параллелизма

(В F #, если у вас есть массив с плавающей точкой 

let a : float[] = ...

тогда вы можете «добавить шаг ко всем им параллельно», чтобы создать новый массив с 

let aShift = a |> (fun x -> async { return x + shift }) 
               |> Async.Parallel |> Async.RunSynchronously

(хотя я ожидаю, что это может быть медленнее, чем просто выполнение синхронного цикла). *

...