[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

FFT: Problem with large dataset in memory

Simon Lu

9/24/2008 7:29:00 PM

Hi,

I am working in a project dealing with a big many of data. Now I have
a problem with doing the FFT on a very long time trace, a signal with
over 300 million sampling points. After testing with my computer, I
realise that I can store only 2**27 points into memory, which will
need 2 GB RAM. With an array of 2**28 Double_t points the program
crash ("segmentation violation"). I tried the Root cern framework, gsl
and fftw3 library. They all need to load the data into memory. So the
question is: Are there some mechanisms or algorithms to manage the
array on a TTree or somewhere else on the hard disk? And then load the
the data step by step into cache? Something likes a FileArray. Or you
get a better idea?
This is really urgent. I am very grateful if I can hear something from
you!
THX!

--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
8 Answers

Christoph Kliemt

9/24/2008 11:36:00 PM

0

Moin!

Simon Lu <luqsim@googlemail.com> writes:

> Hi,
>
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation").

[...]

> And then load the the data step by step into cache? Something likes
> a FileArray. Or you get a better idea? This is really urgent. I am
> very grateful if I can hear something from you! THX!

man mmap

hth,

Christoph

--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Erik Wikström

9/24/2008 11:36:00 PM

0

On 2008-09-24 21:28, Simon Lu wrote:
> Hi,
>
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation"). I tried the Root cern framework, gsl
> and fftw3 library. They all need to load the data into memory. So the
> question is: Are there some mechanisms or algorithms to manage the
> array on a TTree or somewhere else on the hard disk? And then load the
> the data step by step into cache? Something likes a FileArray. Or you
> get a better idea?
> This is really urgent. I am very grateful if I can hear something from

There are many ways to do what you want, and the best way depends on
your needs. If you need to operate on the whole dataset at once you have
somewhat of a problem, if you are able to work with just a few data-
points at a time you should be able to "stream" the data through your
algorithm and can probably get away with a fairly small memory footprint.

None of this is however directly topical in this group, is is on a to
high level and have no C++ specific parts, try asking in a general
programming group, such as comp.programming, instead.

If you are running on Windows you might also be able to increase the
virtual memory available for your application to 3GB, for more info:
http://www.microsoft.com/whdc/system/platform/server/PAE/P...

--
Erik Wikström


[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Rune Allnor

9/24/2008 11:40:00 PM

0

On 24 Sep, 21:28, Simon Lu <luq...@googlemail.com> wrote:
> Hi,
>
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation"). I tried the Root cern framework, gsl
> and fftw3 library. They all need to load the data into memory. So the
> question is: Are there some mechanisms or algorithms to manage the
> array on a TTree or somewhere else on the hard disk? And then load the
> the data step by step into cache? Something likes a FileArray. Or you
> get a better idea?
> This is really urgent. I am very grateful if I can hear something from
> you!
> THX!

The important question here is why you want to compute the FFT.
There are two main uses of the FFT:

1) Spectrum analysis
2) 'Fast' convolution

The numbers you state make no sense in the context of spectrum
analysis, so I assume you do this to do some filtering or
convolution.

If this is the case, be aware that the FFT is faster than
filtering or convolution in time domain only with 'short'
data sequences. The FFT is a O(NlogN) algorithm, while
direct convolution is O(N*M) where M is the number of
filter coefficients.

This means that if N is large enough and M is small enough,
M < log N and the program will actually run faster and the
data logistics become easier if you use the straight-forward
direct convolution algorithm.

Of course, inserting the numbers and deducing the limit
where the FFT is slower is not at all trivial, so you
might have to resort to trial-and-error. However, the
numbers you state are of such magnitude that you might
very well find that the direct implementation is faster.

Now, if you really need the FFT anyway, you can exploit
the fact that each level of the FFT is a composite of
lower-order FFTs. It is conceivable that you might
be able to compute 2^27-pt FFTs in RAM, store the
results to file and do whatever tricks are needed to
combine these intermediate data into the desired result.

The composite FFTs have been discussed numerous times
on comp.dsp.

Rune

--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

joseph cook

9/24/2008 11:40:00 PM

0


> This is really urgent. I am very grateful if I can hear something from
> you!
> THX!
>
This is off-topic and unrelated to C++.

You can do the FFT in parts in divide and conquer. Do the even
elements and the odd elements individually. If that's too much,
divide each of those FFTs into odd and even, then recombine.

FFT is a classic divide and conquer algorithm. I think the book
"Numerical Recipes" may be useful here.

Joe

--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

nobyjos

9/24/2008 11:40:00 PM

0

On Sep 24, 8:28 pm, Simon Lu <luq...@googlemail.com> wrote:
> Hi,
>
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation"). I tried the Root cern framework, gsl
> and fftw3 library. They all need to load the data into memory. So the
> question is: Are there some mechanisms or algorithms to manage the
> array on a TTree or somewhere else on the hard disk? And then load the
> the data step by step into cache? Something likes a FileArray. Or you
> get a better idea?
> This is really urgent. I am very grateful if I can hear something from
> you!
> THX!

Write the whole array into a file (binary format)
Then link the file to the process using mmap()
then you can use some sort of indexing to locate the data in the file.


--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Falk Tannhäuser

9/24/2008 11:43:00 PM

0

Simon Lu schrieb:
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation"). I tried the Root cern framework, gsl
> and fftw3 library. They all need to load the data into memory. So the
> question is: Are there some mechanisms or algorithms to manage the
> array on a TTree or somewhere else on the hard disk? And then load the
> the data step by step into cache? Something likes a FileArray. Or you
> get a better idea?

Although this is not directly C++-related: You may want to check the
Cooley-Tukey algorithm which lets you calculate an FFT by applying it to
(for instance) the even- and odd-indexed numbers separately and then
combining the result - see for example
<http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm#The_radix-2_DI....
This may be applied in a recursive manner, so you should be able to
reduce the block size until everything fits in memory. This algorithm
and its variants also allow to reach a O(N log N) runtime as opposed to
O(N^2) for a naive implementation, so it is probably already used
internally by the FFT libraries you mentioned.

HTH
Falk

--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Greg Herlihy

9/25/2008 9:54:00 AM

0

On Sep 24, 12:28 pm, Simon Lu <luq...@googlemail.com> wrote:
> I am working in a project dealing with a big many of data. Now I have
> a problem with doing the FFT on a very long time trace, a signal with
> over 300 million sampling points. After testing with my computer, I
> realise that I can store only 2**27 points into memory, which will
> need 2 GB RAM. With an array of 2**28 Double_t points the program
> crash ("segmentation violation").

Clearly, the most natural solution would be to port your current C++
program to a 64-bit execution environment. A 64-bit memory model would
be able to accommodate vastly larger amounts of data in RAM than is
possible under the program's current, 32-bit memory model.

Now porting a C++ program to a 64-bit environment might not turn out
to be as straightforward as one might expect. Issues with C++'s sign
promotion of integer types - especially - can lead to surprising
results. Apple's 64-bit transition programmer's guide: (http://
preview.tinyurl.com/3ns3b5) has some examples.

Greg


--
[ See http://www.gotw.ca/resource... for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Marco Manfredini

9/25/2008 9:59:00 PM

0