Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!nrl-cmf!cmcl2!yale!lisper
From: lisper@yale.UUCP (Bjorn Lisper)
Newsgroups: comp.arch
Subject: Re: Powers of 2, was Re: RISC is a nasty no-no!
Message-ID: <24529@yale-celray.yale.UUCP>
Date: 5 Mar 88 00:15:34 GMT
References: <17415@think.UUCP> <1339@alliant.Alliant.COM>
Reply-To: lisper@yale-celray.UUCP (Bjorn Lisper)
Organization: Yale University Computer Science Dept, New Haven CT
Lines: 22

In article <1339@alliant.Alliant.COM> muller@alliant.UUCP (Jim Muller) writes:
>In <17415@think.UUCP> barmar@fafnir.think.com.UUCP (Barry Margolin) writes:
>
>>...What scientific applications naturally map onto
>>power-of-two arrays?  I suspect that making arrays a power of two in
>>size is a habit mostly of systems programmers, who know to make things
>>fit neatly into memory pages in order to reduce paging.
>
>Practically anything involving Fourier Transforms will tend to use
>power-of-2-length arrays, since this is required to do FFT's (Fast Fourier
>Transforms) - the requirement is built into the algorithm.

As I and Jim have pointed out, FFT. As a matter of fact the divide-and-
conquer paradigm leads to algorithms which typically works well on power-of
two arrays. A scientific computing example that comes to mind is odd-even
cyclic reduction of tridiagonal linear equation systems (a way to solve such
a nxn system in parallel in O(log n) time).

To design a machine so that arrays of length 2^n gives a slowdown must be a
grave error, considered the importance of the divide-and-conquer paradigm in
parallel processing.

Bjorn Lisper