Example: Two Butterfly Algorithms
This is an example of
efficient prototyping of recurrences
used on algorithms that exhibit a butterfly dependency pattern.
The butterfly is a graph with a regular pattern, but the pattern
depends on the position in and size of the butterfly. A height 4
butterfly looks like
A butterfly of height h will have h+1 rows (indexed
0 through h) and 2^h
columns (indexed 0 through 2^h-1). A node is identified
by index pairs in
the the row-column order, thus for a height h butterfly we will be using
indices in the range <0,0>; through <h,2^h-1>. A precise
definition of the butterfly is given by the following:
- A height 0 butterfly has 1 node indexed by <0,0>
- A height h, for h>0, butterfly is composed horizontally from two
height h-1 butterflies placed side by side, such that 2^(h-1) is
added to the column numbers of the rightmost subbutterfly. Then a
new top row with indices <h,0> through <h,2^h-1> is added. A
node p=<i,j>; in the top row is connected by a vertical arc to
the node <i-1,j> (a top node in one of the butterflies of
height h-1) and by a diagonal arc to the node
<i-1,complementbit(j,i-1)>. That is, each new node is connect to the
node right under it (a topmost node in one of the subbutterflies)
and diagonally to the corresponding top node of the other
subbutterfly.
Replicated sum
Assume that the 0'th row of the butterfly has been assigned some number.
The replicated sum will add these numbers together, so that each node at
the top will receive a copy of the sum. The intermediate nodes will
contain various subsums.
sum(p) = sum(D(p,1)) + sum(D(p,2))
Fast Fourier Transform
The fast Fourier transform, the FFT, is a standard algorithm which
utilises the butterfly structure fully. The inputs are placed on the
bottom row, and the outputs appear on the top row.
fft(p) = fft(D(p,1)) + exp(a*row(p)/(2**col(p)))*fft(D(p,2))
The total execution time is n log n, where n=2^h is the number of input
nodes, as expected of the FFT algorithm.
This was an example of efficient prototyping of recurrences.
© 1997 Magne Haveraaen, University of Bergen, Norway.