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

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

Я почти уверен, что смогу предварительно рассчитать 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 ответа

Решение

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

Вот что я думаю, что вы пытаетесь сделать:

let N = 7240
let F = 1.0f/50.0f
let pi = single System.Math.PI

let signal = [| for i in 1 .. N*N -> 0.5f |]

let real = 
  seq { for i in 0 .. N*N-1 -> signal.[i] * (cos (2.0f * pi * F * (single i))) }
  |> Seq.sum

let img = 
  seq { for i in 0 .. N*N-1 -> signal.[i] * (sin (2.0f * pi * F * (single i))) }
  |> Seq.sum

let power = real*real + img*img

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

Источник

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

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

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

let a : float[] = ...

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

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

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

Источник
Другие вопросы по тегам