Re: FFT Multiplication on Disk?

On Sep 20, 7:45 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Sep 20, 11:17 am, mike3 <mike4...@xxxxxxxxx> wrote:



On Sep 20, 9:17 am, c...@xxxxxxxx (Richard Harter) wrote:

On Wed, 19 Sep 2007 23:37:04 -0700, mike3 <mike4...@xxxxxxxxx>
wrote:

On Sep 19, 5:55 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
mike3 <mike4...@xxxxxxxxx> writes:
However the problem is that this involves three in-place matrix
transpositions of a square matrix. Does anyone know of an
efficient algorithm to do those?

Here's one paper on the topic:http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/8931/28260/0126...
--
"J'avais trouv'e ma religion :
rien ne me parut plus important qu'un livre.
La biblioth`eque, j'y voyais un temple."
--Jean-Paul Sartre

That looks like it's going to cost me a good sum of MONEY
to get that paper. I don't have lots of that nice green stuff on
hand given my current financial situation, unfortunately.

A simple alternative that you can roll on your own is to
recursively partition the transposition. Here is the idea:
Suppose we have a matrix that looks like this:

A B
M = C D

where M is 2Nx2N and A, B, C, and D are all NxN. Transpose each
component separately and then swap A and B. If you do things
soothly the number of cache misses drops sharply.

Richard Harter, c...@xxxxxxxxxxxx://home.tiac.net/~cri,http://www.varinoma.com
But the rhetoric of holistic harmony can generate into a kind of
dotty, Prince Charles-style mysticism. -- Richard Dawkins

The problem though is that it is very non-sequential. Is
this as close to sequential as one can get it, or is there
better? I want to minimize the amount of disk operations,
especially seeks, as much as possible. It's the _disk_
part that's the real chokepoint here.-

Why are you multiplying numbers from disk anyway?

Buy more RAM. Even if you are multiplying numbers that consume over a
gigabyte, you will be glad you did it that way. RAM is going to be
thousands of times faster than disk. Here's an ad blurb for something
that claims to be the fastest hard disk in the world:


RAM is pretty pricey, for one.

Two, the multiplication would take a huge
amount of RAM, several GB. I only have
768 MB, however I have seen programs out there
that use disk storage and yet can compute way
faster than my program on this machine. So why
spend big piles of money when you can optimize
the program?

<snip>
How many memory fetches do you think you can do in 3.2 ms (that's
milliseconds, not microseconds)? Fast RAM can be accessed in 9
nanoseconds. That's about 355,556 times faster. Let's suppose that
in RAM you could solve it in one second. On disk it would take 4
days.

Here is an example of memory pricing:http://www.computermemoryoutlet.com/Compaq-ProLiant-8500_6%5Eslsh700-...

I would rather spend a little money and wait one second than spend
nothing and wait 4 days.

$374 for 2GB RAM is a LOT of money. My budget
is tight.

For one I think there are only 3 slots on my motherboard,
and they're all full. So either I'd need to throw the RAM
and get more, or get a new motherboard (which would
cost even more money.).

.

Relevant Pages

  • Re: FFT Multiplication on Disk?
    ... Transform multiplication program. ... numbers stored on disk and then multiply them using only one full- ... RAM for the sizes of N I'm considering (hence one could actually do ... is that this involves three in-place matrix transpositions of a square ...
    (comp.programming)
  • Re: OT/drift: when is a RAMdisk an appropriate solution
    ... include the "ram disk" component in your project. ... Sometimes, a physical RAM ... only to wind up going directly to regular old ordinary memory, ... testing the file system software. ...
    (comp.lang.c)
  • Re: teaching a child - console or GUI
    ... >> possible to set up some pretty fancy 'accelerators' ... disk under a file name that is ... ... or are they really a bunch of pointers ... You mean that you had to be convinced of the 'CD in RAM' approach? ...
    (comp.lang.pascal.delphi.misc)
  • Re: Future Linux on Bistable Storage
    ... One major difference between disk and RAM is the tradeoffs between size, ... resume the system -- except perhaps for I/O initialisation. ... Writing all of RAM to disk burns more power than powering RAM for several ...
    (Linux-Kernel)
  • Re: Hard disk speed - Maybe OT
    ... This will of course all be disk cache. ... The current capture uses ... I dont think RAM will help all that much. ...
    (alt.os.linux.suse)