Well, for that job you ain't going to be using an N**2 algorithm (straight DFT), multicore or no multicore.
That seems pessimistic. My EM simulator code scales nearly linearly up to 40 processors, which is as far as I've tested it. Of course you folks probably didn't have Infiniband or GbE connections. The biggest killer is handshake latency, IME.
That, I believe. One reason FPGAs don't get used for ordinary computing workloads is the gigantic task switching overhead that would impose. But when you don't need to switch tasks, a big array is very very powerful.
Only if the kernel occupies the whole interval for all values of the parameters. Wavelet transforms, for instance, are more or less well localized in both time and frequency.
Yes, and in practice we truncate infinite tails as well, and live with the resulting errors.
In radar, the 2^20 point FFTs are often for pulse compression in chirp radars, and at least half of the kernel cells are set to zero, because we don't know in advance where the targets and thus echoes are in advance.
This was the measured result of a direct test of a 2^20-point FFT of random data, on the chosen platform. The benchmark is slightly pessimistic in that in actual use, because less than half of the points are non-zero, but still ...
At the time, it was all in main memory of a big "massively parallel" (maybe 128 processors?) enterprise server, and part of the test was if this particular make and model of machine could do the job, and it was shown that it was not even close. (It was really intended to be a web server handling web inquiries, a massively parallel application.)
I think EM simulators are structurally similar to finite-element stress analysis analyzers in that all communications is with the abutting finite elements, and if so the linear scaling you observed is plausible.
We do now. And yes, handshake latency (needed for command and control to forge all those moving parts into a functional whole) still dominates.
This is Amdahl territory - I rejected signal-processing's estimate of performance because it omitted this very thing, the control plane.
Also missing was how to coordinate actions that must be atomic across the whole processing fabric.
And because they were using throughput estimates, versus latency estimates - in realtime, one usually runs out of timeline first, often long before saturating the CPUs.
In the old days, the poster child was a spinning-metal disk - all latency, no CPU.
Now days, the poster child is a processor core - these are limited by how fast random data can get to the processor, and how fast it can be put where it must go - in short, the memory system is the bottleneck, and it is shared by many processors. And so on.
Yes. We now use FPGAs in place of those array processors. FPGAs are much faster and much more flexible.
Out of curiosity do you do it the same way as in radio astronomy to kill off edge effects or just rely on uniform temporal sampling? (which you generally have in a radar system - and we don't)
The radio astronomy trick is to preconvolve the raw data with a gridding function on a compact support of 5 or 7 cells centred on the data point so that when the FFT is done the resulting transform is a very close approximation to the DFT apart from very close to the edges where the results are haywire so you discard a narrow guard band. Schwab at the VLA first catalogued the most interesting functions for this trick.
formatting link
This is a later version by Sze Tan that formalises the guard band and generalises the functions beyond prolate spheroidal Bessel functions.
formatting link
Failure to use the right functions on an irregularly sampled dataset seriously compromises signal to noise in the resulting transform.
The data is always taken with uniform temporal sampling, but usually with missing samples (often due to blanking of impulse noise or CW tones in the frequency domain). At low SNR levels, the result can be pretty ragged, so the gaps are generally repaired by complex interpolating of flanking stretches of samples into the gap. The detailed algorithms are tightly held.
Another approach, sometimes combined with interpolating across the gap, is resample and decimate in a combined algorithm, where the original sample rate and reduced sample rate are not an integer multiple of one another.
This sounds similar to the above combined decimate and resample scheme described above.
Yes. The signal-processing folk perform massive trade studies of algorithms and the best order in which to apply them.
I'll read the above memos. Some of the s-p folk follow the radio astronomy literature, so I'd guess that they already know of these algorithms.
Same story here. We have lots of wayward astronomers, actually. The screen saver is often the tell.
While I'm no astronomer, the rule isn't absolute - my screen saver is a hot Neptune (Kepler 36b):
.
formatting link
I've read both articles. The radar s-p folk do things resembling what Sze Tan describes, but optimized for processing speed (short latency) and for seeing small objects close to large objects at almost the same range. The window and kernel functions are similar to Gaussian, to reduce sidelobes appearing as false targets. Taylor, Bessel, and the like being common. No prolate spheroids.
Prolate spheroids will beat truncated Gaussian hands down. The reason we moved from simpler kernels was precisely to maximise the dynamic range in images made from Fourier data. In our case the measurements taken on ellipses as the Earth rotates so must be resampled prior to transform.
The images tended to be very faint nebulosity flowing away from and in close proximity to incredibly bright hotspots where relativistic particle beams slam into the intergalactic medium. Think poached eggs!
formatting link
Seems it still holds surprises - new object resolved recently that wasn't there back when I was involved in this sort of stuff.
The PSB functions main claim to fame it that like the Gaussian it is its own Fourier transform when band limited to a particular length - but without the restriction of remaining everywhere positive.
Superficially it looks a lot like a truncated sinc(x)exp(-ax^2) but the zeroes are not precisely aligned with the sampling grid.
The big difference is that in all cases the multiplicative correction factor in the transform domain corresponding to the convolution done in sample regridding is exactly the same.
I don't know the reason, but although prolate spheroids are mentioned from time to time, I don't recall seeing them winning the tradeoffs in radar. Now that I'm sensitized, I'll probably begin to see them everywhere. But see later herein.
That's interesting. My bet is on a black-hole merger in progress, as a larger galaxy messily eats a smaller galaxy. I assume that LIGO cannot see this yet.
Hmm. This may be the key. In radar, we are looking for a finite number of solid physical targets, versus an extended image containing an unknown large number of physical objects that need not be solid.
And for speed, we zero as many array elements as possible.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.