From 0d35b7f16985392b1cd2d312fbdca51dc3084bcc Mon Sep 17 00:00:00 2001 From: Matthijs Kooijman Date: Tue, 8 Apr 2008 15:28:43 +0200 Subject: [PATCH] * Make the FFT size a bit larger. * Explicitely pass the addressing strategies to use for reading input and writing output on each stage. So far, only REGULAR_IN is supported for input (ie, no changes) and REGULAR_OUT and BITREVERSED_OUT are supported for output (ie, add support for bitreversing the last stage). --- FFT.h | 13 ++++++- FFT.mc | 118 ++++++++++++++++++++++++++++++++++++++------------------- 2 files changed, 90 insertions(+), 41 deletions(-) diff --git a/FFT.h b/FFT.h index 5941e93..b94386e 100644 --- a/FFT.h +++ b/FFT.h @@ -8,7 +8,7 @@ /* 2log of number of tiles */ #define PARAM_q 2 /** 2log of total FFT size */ -#define PARAM_n 6 +#define PARAM_n 12 /* Note that the FFT size on each tile 2^(n-q) must be at least * 8 and always a multiple of 4. The number of stages on each @@ -75,5 +75,16 @@ /* Values for the cycle_odd argument */ #define EVEN_CYCLE 0 #define ODD_CYCLE 1 + +enum in_strategy { + REGULAR_IN, + DISTRIBUTED_IN, +}; + +enum out_strategy { + REGULAR_OUT, + DISTRIBUTED_OUT, + BITREVERSED_OUT, +}; #endif // !FFT_H_INCLUDED diff --git a/FFT.mc b/FFT.mc index 8fb50f1..a76377e 100644 --- a/FFT.mc +++ b/FFT.mc @@ -45,23 +45,50 @@ INLINE struct bf_out butterfly(struct bf_in in) { * locations. * @param second_half Are we in the second half of the stage? */ -INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half) { - add_offset(m.output_a_re, 2); - add_offset(m.output_a_im, 2); - add_offset(m.output_b_re, 2); - add_offset(m.output_b_im, 2); - - if (!second_half) { - write_mem(m.output_a_re, res.a_re); - write_mem(m.output_a_im, res.a_im); - write_mem(m.output_b_re, res.b_re); - write_mem(m.output_b_im, res.b_im); +INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half, enum out_strategy out_s) { + if (out_s == REGULAR_OUT) { + /* Skip a memory on each cycle during the regular stages */ + add_offset(m.output_a_re, 2); + add_offset(m.output_a_im, 2); + add_offset(m.output_b_re, 2); + add_offset(m.output_b_im, 2); } else { - /* Write a results to memory b and v.v. */ + /* Simply write output linearly */ + add_offset(m.output_a_re, 1); + add_offset(m.output_a_im, 1); + add_offset(m.output_b_re, 1); + add_offset(m.output_b_im, 1); + } + if (out_s == BITREVERSED_OUT) { + /* + Use the memories (which are n_t - 1 bits wide) bitreversed. + Since we are generating the samples in sequence (0, 1, 2, 3, + ...) but are writing them to two different memories (0, 8, + 1, 9, ...) The last bit is already bitreversed, so in effect + we have fully bitreversed the results. Note that this holds + in the non-distributed case (Q = 1), but might also hold in + the distributed case (if the tile numbers are bitreversed + before concatenating memory). + */ + use_bitreverse(m.output_a_re, PARAM_n_t - 1); + use_bitreverse(m.output_a_im, PARAM_n_t - 1); + use_bitreverse(m.output_b_re, PARAM_n_t - 1); + use_bitreverse(m.output_b_im, PARAM_n_t - 1); + } + + if (out_s == REGULAR_OUT && second_half) { + /* When in the regular stages, reverse memory a and b during + * the second half */ write_mem(m.output_a_re, res.b_re); write_mem(m.output_a_im, res.b_im); write_mem(m.output_b_re, res.a_re); write_mem(m.output_b_im, res.a_im); + } else { + /* Simply write a to mem a and b to mem b */ + write_mem(m.output_a_re, res.a_re); + write_mem(m.output_a_im, res.a_im); + write_mem(m.output_b_re, res.b_re); + write_mem(m.output_b_im, res.b_im); } } @@ -132,36 +159,46 @@ INLINE void init_input_addresses_regular(struct mems m) { * Initializes the addresses for reading the inputs. This function must be * called twice per stage, since halfway the stage the addressing changes. */ -INLINE void init_output_addresses_regular(struct mems m, bool second_half) { +INLINE void init_output_addresses_regular(struct mems m, bool second_half, enum out_strategy out_s) { + /* Only reset the memory addresses for the second half for the regular + * stages */ + if (out_s != REGULAR_OUT && second_half) + return; /* * For the second half of the stage, the starting addresses are * reversed. write_output_regular above will also swap the output * memories. * TODO: Better comments :-) */ - set_base(m.output_a_re, 0); set_base(m.output_a_im, 0); set_base(m.output_b_re, 0); set_base(m.output_b_im, 0); - - /* We subtract two from every address, since write_output_regular - * adds two to the offset before writing the first (and every other) - * result. */ - if (second_half) { - set_offset(m.output_a_re, 1-2); - set_offset(m.output_a_im, 1-2); - set_offset(m.output_b_re, 0-2); - set_offset(m.output_b_im, 0-2); + if (out_s == REGULAR_OUT) { + /* We subtract two from every address, since write_output_regular + * adds two to the offset before writing the first (and every other) + * result. */ + if (second_half) { + set_offset(m.output_a_re, 1-2); + set_offset(m.output_a_im, 1-2); + set_offset(m.output_b_re, 0-2); + set_offset(m.output_b_im, 0-2); + } else { + set_offset(m.output_a_re, 0-2); + set_offset(m.output_a_im, 0-2); + set_offset(m.output_b_re, 1-2); + set_offset(m.output_b_im, 1-2); + } } else { - set_offset(m.output_a_re, 0-2); - set_offset(m.output_a_im, 0-2); - set_offset(m.output_b_re, 1-2); - set_offset(m.output_b_im, 1-2); + /* Write sequentially, starting at 0 for both memories */ + set_offset(m.output_a_re, 0-1); + set_offset(m.output_a_im, 0-1); + set_offset(m.output_b_re, 0-1); + set_offset(m.output_b_im, 0-1); } } -INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ +INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half, enum in_strategy in_s, enum out_strategy out_s){ /* * We are doing two cycles in each iteration, so we can alternate the * cycle_odd argument (which only works with constants, I don't expect @@ -177,7 +214,7 @@ INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ */ /* Initialize output addresses, this must be done twice per stage */ - init_output_addresses_regular(m, second_half); + init_output_addresses_regular(m, second_half, out_s); /* First cycle (no previous output to write) */ struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage); @@ -189,7 +226,7 @@ INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ init_loop(LC2, (PARAM_N_t / 8) - 1 - 1); do { /* Write outputs of previous cycle */ - write_output_regular(m, out, second_half); + write_output_regular(m, out, second_half, out_s); /* Odd cycle */ in = read_input_regular(m, ODD_CYCLE, stage); @@ -197,7 +234,7 @@ INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ next_cycle(); /* Write outputs of previous cycle */ - write_output_regular(m, out, second_half); + write_output_regular(m, out, second_half, out_s); /* Even cycle */ in = read_input_regular(m, EVEN_CYCLE, stage); @@ -205,7 +242,7 @@ INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ } while (loop_next(LC2)); /* Write outputs of previous cycle */ - write_output_regular(m, out, second_half); + write_output_regular(m, out, second_half, out_s); /* Last cycle */ in = read_input_regular(m, ODD_CYCLE, stage); @@ -213,7 +250,7 @@ INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half){ next_cycle(); /* Write outputs of last cycle */ - write_output_regular(m, out, second_half); + write_output_regular(m, out, second_half, out_s); /* Force the next cycle, because the next stage must read from * the memory we just wrote to */ @@ -254,22 +291,23 @@ INLINE struct mems init_mem_mapping(int stage){ return res; } -INLINE void do_regular_stage(int stage) +INLINE void do_regular_stage(int stage, enum in_strategy in_s, enum out_strategy out_s) { struct mems m = init_mem_mapping(stage); init_input_addresses_regular(m); /* do_half_regular_stage will init output addresses */ next_cycle(); - do_half_regular_stage(m, stage, FIRST_HALF); - do_half_regular_stage(m, stage, SECOND_HALF); + do_half_regular_stage(m, stage, FIRST_HALF, in_s, out_s); + do_half_regular_stage(m, stage, SECOND_HALF, in_s, out_s); } + void run() { do { freeze(); } while (gpi(0) == 0); - do_regular_stage(1); - do_regular_stage(2); - do_regular_stage(3); - do_regular_stage(4); + do_regular_stage(1, REGULAR_IN, REGULAR_OUT); + do_regular_stage(2, REGULAR_IN, REGULAR_OUT); + do_regular_stage(3, REGULAR_IN, REGULAR_OUT); + do_regular_stage(4, REGULAR_IN, BITREVERSED_OUT); set_gpo(0); next_cycle(); -- 2.30.2