Subject: Summary of 3D-FFT

From: "Y Z" <[email-masked]>
Date: Tue, 22 Feb 2000 18:42:20 EST

After I asked the question for 3D-FFT,
I got a lot of  responses. Thanks a lot for
their helps , my problem have been solved.

Here is the summary

My original question is:

Hi,

Are there any way to calculate a (256,256,256) order
DOUBLE COMPLEX FFT in FORTRAN77? I tried to do the
following subrouitine but cannot pass the compiling.

By f77 in SGI :

Warning: Stack frame size (270015328) larger than system limit (67108864)

+++++++++++++++++++++++++++++++++

     program test
     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     DOUBLE COMPLEX AA(256,256,256)
     DIMENSION ID(64),CC(64)
     DIMENSION NORD(3)
     DO 100 i=1,256
      DO 100 j=1,256
        DO 100 k=1,256
          xx=DBLE(I+j+k)
          AA(i,j,k)=DCMPLX(xx,0.0D0)
100   CONTINUE
     NORD(1)=8
     NORD(2)=8
     NORD(3)=8
     IERR=0
     CALL DFFT3D(dta,NORD,ID,CC,1,IERR)
     STOP
     END

--------------------------------------

Below is the responses from people:

-----------------------------------

From: [email-masked]

I don't know if you realize this by the array AA is 268435456 bytes long 
(268
MB).  You have exceeded some system limit on how big an area you can have by
default.  I don't know what machine you are compiling this on, but on some
machines and if you are using the c shell you can type limit to get the 
limits
and
limit name_of_limit  new_value_for_limit.  This may work unless your system 
will
not allow you to set it up high enough.

Bill

P.S. On my SGI Indigo 2 this is what the limit command gives:

cputime         unlimited
filesize        unlimited
datasize        2097152 kbytes
stacksize       524288 kbytes
coredumpsize    0 kbytes
memoryuse       524288 kbytes
vmemoryuse      2097152 kbytes
descriptors     2500
threads         1024

From: David Heisterberg <[email-masked]>

Try putting your large array in a common block.  It looks like the default
allocation is to put your 256MB array on the stack!  Naming it in a SAVE
statement or compiling with static allocation may work too.

Dave Heisterberg

From: "Serguei Patchkovskii" <[email-masked]>

>       IMPLICIT DOUBLE PRECISION (A-H,O-Z)
>       DOUBLE COMPLEX AA(256,256,256)

This is a rather large array, requiring 256megabytes of memory to
store. I presume that you do have enough memory to handle it (and
whatever temporary space FFT might need in addition to that).

If you do, you'll have to make sure your resource limits are set
high enough to allow such array (use limit if you run under csh or
descendants; ulimit under sh & friends). It is possible that your
system is not configured to handle arrays of this size; in this case
you will have to increase the system-wide limits (since you say you
are using an SGI, this can be done with systune; see it's manual
page).

Finally, unless the default settings has been overriden on your
computer, SGI compiler will allocate locally declared arrays on
stack - so this is the limit you'll be looking for. You can force
the compiler to allocate the array in the data segment by either
using -static compilation switch, or by placing AA in a common
block.

/Serge.P

From: Iraj Daizadeh <[email-masked]>

check limit (csh/tcsh) on unix box

supercede with

ulimit stacksize
or limit stacksize unlimited

iraj.

From: David van der Spoel <[email-masked]>

To: Y Z <[email-masked]> Save Address
Subject: Re: CCL:Three dimensional FFT
Date: Sun, 20 Feb 2000 22:17:32 +0100 (CET)

Use the UNIX limit command to increase your limit.

From: [email-masked] Save Address Block Sender
Reply-To: [email-masked]
To: Y Z <[email-masked]> Save Address
Subject: Re: CCL:Three dimensional FFT
Date: Sun, 20 Feb 2000 14:22:27 +0000

I wonder if your system guru couldn't ive some assistance about the stack..

John McKelvey

From: Niri Govind <[email-masked]>

  there are very good 3d-fft routines as part of the
  libcomplib.sgimath libraries on the sgis. you can get
  information on how to use them by looking at the man pages.

  you will need to link to this library when you compile your
  program...

  try man fft, this should give you all the info you need.
  hope this helps

cheers
-niri

From: Niri Govind <[email-masked]>

hi,

  there are very good 3d-fft routines as part of the
  libcomplib.sgimath libraries on the sgis. you can get
  information on how to use them by looking at the man pages.

  you will need to link to this library when you compile your
  program...

  try man fft, this should give you all the info you need.
  hope this helps

cheers
-niri

From: "Daniel Mok" <[email-masked]>

I've got a similar message problem in a different fortran subroutine. It
seems to be the problem of the allocated memory size. I don't how to
increase the mentioned system limit. Please let me know if you got any reply
in doing this.

Daniel

From: "Jochen Küpper" <[email-masked]>

 > Are there any way to calculate a (256,256,256) order
 > DOUBLE COMPLEX FFT in FORTRAN77? I tried to do the
 > following subrouitine but cannot pass the compiling.

Nothing on netlib ?
fftw ?

Jochen

From: Gijs Schaftenaar <[email-masked]>

a double array(256,256,256) cost roughly 134 MB of memory, you probably
dont have this.

Best Regards,

Gijs Schaftenaar

From: Sigismondo Boschi <[email-masked]>

DOUBLE COMPLEX AA(256,256,256)

The problem is that SGI compiler allocates all automatic variables in the
stack that usually is limited and not well swited for large arrays (even
if we are in the "program").

The ways to avoid it are:
1. put the array in a common block
2. SAVE AA
3. compile with option "-static"
4. allocate memory dynamically (OK, thats Fortran90...)

I would avoid the first if you do not really need it, and I would use the
second, except it is just for a short test case - with the third it works
just fine.

I strongly discourage to enlarge the stack size for such problems.

I Hope This Helps!

Bye

Sigismondo Boschi

From: [email-masked]

Compile using the -static flag and the error will go away.

(not pretty, but it works)

Dave

From: "Jochen Küpper"

 > Are there any way to calculate a (256,256,256) order
 > DOUBLE COMPLEX FFT in FORTRAN77? I tried to do the
 > following subrouitine but cannot pass the compiling.

Nothing on netlib ?
fftw ?

Jochen

From: Huub van Dam <[email-masked]>

Hmm, you are trying to statically allocate an array of 256 MB and your 
compiler doesn't like it. There are a few options
you could try:

1) Find where the system limit is defined and increase it so that it will 
allow what you want to do.
2) Change the code to run in parallel in a memory distributed fashion so 
that each node needs to store maximul 64 MB
(i.e. your current system limit)
3) Change your code to use disc space in stead of main memory.
4) Think of a smarter approach that avoids doing a 3D FFT at once.
5) Wait for someone else to mail you a ready to go solution.

Each option has its pro's and con's and certain requirements:

Option 1 is the easiest (no code changes required) but you need to have 
sufficient (virtual) memory to store an
executable with a data space of 256 MB. I.e. you would need to have about 
320 MB of (virtual) memory. Note that if
you physical memory is smaller than 256 MB your code may run very slowly. 
And you need to have the root
permissions to mess around with the system parameters. For a quick solution 
though this is probably your best bet.

Option 2 requires you to have access to more and one processor at a time. In 
this case you would need at least 4
processors. Also you need to have access to either a compiler that can 
generate a parallel executable for you or you
need to change the code substantially. In the latter case the global array 
tools
(http://www.emsl.pnl.gov:2080/docs/global/) may be very useful as they allow 
you to mimic a shared memory parallel
system on distributed memory hardware. Also they provide parallelised 
essential matrix operations.

Option 3 require a lot of code changes (and a lot of time). You would have 
to break up the complete operation in
partial operations each of which fits in the memory you have available. The 
data you don't need in each partial step you
store on disk. This may well require a significant rewrite of you algorithm, 
and will certainly involve a lot of file handling.

Option 4 probably requires the most time. It means rethinking your 
scientific problem and trying to formulate your
solution in such a way that you avoid doing the full 3D FFT in one step. Eg. 
try to write your solution as 3 one
dimensional FFT's or something like that. Although this may take the most 
time, if you expect to do these kinds of
calculations often going this way may be best solution.

Option 5 requires a significant amount of luck.

Huub

From: Jeff Saxe <[email-masked]>

In SGI's online books I found:

Arrays that are allocated on the process stack must not exceed 2 GB,
but the total of all stack variables can exceed that limit.

Apparently your routine is exceeding this limit.  I get the same message
on my SGI.  However if I change from double precision to single
precision it will compile.  To get it to compile using double precision
you will have to decrease your dimensions from 256 to about 160.

I also have a suggestion concerning your FORTRAN program.  Consider
using  parameter statements.  I'd write the subroutine as

      program test
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
      parameter (nn = 256)
      DOUBLE COMPLEX AA(nn,nn,nn)
      DIMENSION ID(64),CC(64)
      DIMENSION NORD(3)
      DO 100 i=1,nn
       DO 100 j=1,nn
         DO 100 k=1,nn
           xx=DBLE(I+j+k)
           AA(i,j,k)=DCMPLX(xx,0.0D0)
100   CONTINUE
      NORD(1)=8
      NORD(2)=8
      NORD(3)=8
      IERR=0
      CALL DFFT3D(dta,NORD,ID,CC,1,IERR)
      STOP
      END

This way, should you have to change the size, you simply change the
parameter statement, and all the dimension statements and DO loops are
automatically properly set.  It avoids the possibility of forgetting to
change something should you make a change.

Another suggestion, though this is very picky and likely unnecessary
these days, is to not end multiple DO loops with the same CONTINUE
statement.  I would have
        DO 100
          DO 110
             DO 120
             ...
   120       CONTINUE
   110    CONTINUE
   100 CONTINUE
My only reason for this is that I have seen compilers make mistakes with
this in the past, e.g. when the innermost loop in your code finished, it
made the mistake of saying the outermost loop was done.  Admittedly this
was long ago (I've been writing FORTRAN for 22 years) and unlikely to
happen now, but I still don't take chances myself.

Jeff

From: "Jochen Küpper" <[email-masked]>

Y Z writes:
 > It is not because of FFT subroutine. It is
 > because of the large array size that I meet.
 > Anyway, I will try to use three one dimensional
 > FFT instead of a 3D-FFT. That will decrease the
 > speed of my code.

Well, I don't see a problem in _that_ ?

256^3 =3D 2^{24} =3D 16777216
sizeof( double complex ) =3D 16 (I assume)

  =3D> 256 MB of RAM needed for the array

If you need that amount of RAM, that's no problem at all (well,
besides the money, probably :-).
Anyway, it should work even in "swap space", although very slow
and a better algorithm (memory wise) would do much better. But I don't=20=

see any reason it doesn't compile - besides you are working on
(Win)Doze ??? And of course your code has been correct.
(Actually I never really looked through your code, and don't have your=20=

first mail anymore.)

But then I was thinking of memory-optimized algorithms that might be
implemented in FFTW or available at netlib ?

Just to let you know - I have written programs that allocate GB's
(GigaBytes) of main-memory. And they actually compile and run :-)

Since your code was FORTRAN - the program might actually crash at run=20=

time due to missing stack-memory - you then need to increase the stack=20=

size for the program or the system - need to be admin for that :-)
But it shouldn't affect compilation.

Jochen

From: wsteinmetz <[email-masked]>

It appears that you have run out of memory.  Have you tried a (128,128,128)
matrix
that will be smaller
by a multiplicative factor of 8.  that should fit.

From: [email-masked]

As I mentioned, if you are running the c shell (or tcsh) as your UNIX shell 
you
should be able to type:

limit stacksize newstacksize

where newstacksize is an integer variable of the new byte size limit

This should work on all SGI's.  Check with the command:

limit

If you are running another shell I don't know the command to use.  Also, if 
the
new limit is larger than the maximum size then your system manager will have 
to
up the kernel parameter for the max. of this value (I don't remember the
variable name) and have to reboot.  Hope this helps, Bill

From: Aeint de Boer <[email-masked]>

I would add the statement:
      SAVE AA
to your program and give it another try.

______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com