\r
#include "FFT.h"\r
\r
-int stage = 1;\r
/**\r
* Executes a single butterfly on ALU 0-3. The inputs are the words taken from\r
* in, which will be read on various inputs of ALU 0-3. Outputs will be\r
* locations.\r
* @param second_half Are we in the second half of the stage?\r
*/\r
-INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half) {\r
- add_offset(m.output_a_re, 2);\r
- add_offset(m.output_a_im, 2);\r
- add_offset(m.output_b_re, 2);\r
- add_offset(m.output_b_im, 2);\r
- \r
- if (second_half) {\r
- write_mem(m.output_a_re, res.a_re);\r
- write_mem(m.output_a_im, res.a_im);\r
- write_mem(m.output_b_re, res.b_re);\r
- write_mem(m.output_b_im, res.b_im);\r
+INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half, enum out_strategy out_s) {\r
+ if (out_s == REGULAR_OUT) {\r
+ /* Skip a memory on each cycle during the regular stages */\r
+ add_offset(m.output_a_re, 2);\r
+ add_offset(m.output_a_im, 2);\r
+ add_offset(m.output_b_re, 2);\r
+ add_offset(m.output_b_im, 2);\r
} else {\r
- /* Write a results to memory b and v.v. */\r
+ /* Simply write output linearly */\r
+ add_offset(m.output_a_re, 1);\r
+ add_offset(m.output_a_im, 1);\r
+ add_offset(m.output_b_re, 1);\r
+ add_offset(m.output_b_im, 1);\r
+ }\r
+ if (out_s == BITREVERSED_OUT) {\r
+ /* \r
+ Use the memories (which are n_t - 1 bits wide) bitreversed.\r
+ Since we are generating the samples in sequence (0, 1, 2, 3,\r
+ ...) but are writing them to two different memories (0, 8,\r
+ 1, 9, ...) The last bit is already bitreversed, so in effect\r
+ we have fully bitreversed the results. Note that this holds\r
+ in the non-distributed case (Q = 1), but might also hold in\r
+ the distributed case (if the tile numbers are bitreversed\r
+ before concatenating memory).\r
+ */\r
+ use_bitreverse(m.output_a_re, PARAM_n_t - 1);\r
+ use_bitreverse(m.output_a_im, PARAM_n_t - 1);\r
+ use_bitreverse(m.output_b_re, PARAM_n_t - 1);\r
+ use_bitreverse(m.output_b_im, PARAM_n_t - 1);\r
+ }\r
+ \r
+ if (out_s == REGULAR_OUT && second_half) {\r
+ /* When in the regular stages, reverse memory a and b during\r
+ * the second half */\r
write_mem(m.output_a_re, res.b_re);\r
write_mem(m.output_a_im, res.b_im);\r
write_mem(m.output_b_re, res.a_re);\r
write_mem(m.output_b_im, res.a_im);\r
+ } else {\r
+ /* Simply write a to mem a and b to mem b */\r
+ write_mem(m.output_a_re, res.a_re);\r
+ write_mem(m.output_a_im, res.a_im);\r
+ write_mem(m.output_b_re, res.b_re);\r
+ write_mem(m.output_b_im, res.b_im);\r
}\r
}\r
\r
* read input a from memory b and v.v. If not, \r
* simply read a from memory a and b from memory b.\r
*/\r
-INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage_odd) {\r
+INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, int stage) {\r
struct bf_in in;\r
/* Swap memory a and b during the odd cycles */\r
if (cycle_odd) {\r
}\r
\r
/**\r
- * Initializes the addresses for writing the outputs.\r
- * @param stage_odd True if this is an odd stage.\r
- * @param second_half True if we are initing halfway a stage.\r
+ * Initializes the addresses for reading the inputs and twiddel factors.\r
+ * Should be called once at the start of each stage.\r
*/ \r
-INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) {\r
+INLINE void init_input_addresses_regular(struct mems m) {\r
/* We simply start reading at address 0 incrementally */\r
set_base(m.input_a_im, 0);\r
set_base(m.input_b_re, 0);\r
* Initializes the addresses for reading the inputs. This function must be\r
* called twice per stage, since halfway the stage the addressing changes.\r
*/\r
-INLINE void init_output_addresses_regular(struct mems m, bool stage_odd, bool second_half) {\r
+INLINE void init_output_addresses_regular(struct mems m, bool second_half, enum out_strategy out_s) {\r
+ /* Only reset the memory addresses for the second half for the regular\r
+ * stages */\r
+ if (out_s != REGULAR_OUT && second_half)\r
+ return;\r
/* \r
* For the second half of the stage, the starting addresses are \r
* reversed. write_output_regular above will also swap the output\r
* memories.\r
* TODO: Better comments :-)\r
*/\r
-\r
set_base(m.output_a_re, 0);\r
set_base(m.output_a_im, 0);\r
set_base(m.output_b_re, 0);\r
set_base(m.output_b_im, 0);\r
- \r
- /* We subtract two from every address, since write_output_regular \r
- * adds two to the offset before writing the first (and every other) \r
- * result. */\r
- if (second_half) {\r
- set_offset(m.output_a_re, 1-2);\r
- set_offset(m.output_a_im, 1-2);\r
- set_offset(m.output_b_re, 0-2);\r
- set_offset(m.output_b_im, 0-2);\r
+ if (out_s == REGULAR_OUT) {\r
+ /* We subtract two from every address, since write_output_regular \r
+ * adds two to the offset before writing the first (and every other) \r
+ * result. */\r
+ if (second_half) {\r
+ set_offset(m.output_a_re, 1-2);\r
+ set_offset(m.output_a_im, 1-2);\r
+ set_offset(m.output_b_re, 0-2);\r
+ set_offset(m.output_b_im, 0-2);\r
+ } else {\r
+ set_offset(m.output_a_re, 0-2);\r
+ set_offset(m.output_a_im, 0-2);\r
+ set_offset(m.output_b_re, 1-2);\r
+ set_offset(m.output_b_im, 1-2);\r
+ }\r
} else {\r
- set_offset(m.output_a_re, 0-2);\r
- set_offset(m.output_a_im, 0-2);\r
- set_offset(m.output_b_re, 1-2);\r
- set_offset(m.output_b_im, 1-2);\r
+ /* Write sequentially, starting at 0 for both memories */\r
+ set_offset(m.output_a_re, 0-1);\r
+ set_offset(m.output_a_im, 0-1);\r
+ set_offset(m.output_b_re, 0-1);\r
+ set_offset(m.output_b_im, 0-1);\r
}\r
}\r
\r
-INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_half){\r
+INLINE void do_half_regular_stage(struct mems m, int stage, bool second_half, enum in_strategy in_s, enum out_strategy out_s){\r
/*\r
* We are doing two cycles in each iteration, so we can alternate the\r
* cycle_odd argument (which only works with constants, I don't expect\r
*/\r
\r
/* Initialize output addresses, this must be done twice per stage */\r
- init_output_addresses_regular(m, stage_odd, second_half);\r
+ init_output_addresses_regular(m, second_half, out_s);\r
\r
/* First cycle (no previous output to write) */\r
- struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage_odd);\r
+ struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage);\r
struct bf_out out = butterfly(in);\r
\r
/* Now, do half a single stage. That means N_t / 4 cycles. Since we do 2\r
* cycles on every iteration, plus one before and after the loop,\r
- * we will loop N_t / 8 - 1 times. */\r
- init_loop(LC2, (PARAM_N_t / 8) - 1);\r
+ * we will loop N_t / 8 - 1 times. We add an extra - 1 because this is a do while loop... */\r
+ init_loop(LC2, (PARAM_N_t / 8) - 1 - 1);\r
do {\r
/* Write outputs of previous cycle */\r
- write_output_regular(m, out, second_half);\r
+ write_output_regular(m, out, second_half, out_s);\r
\r
/* Odd cycle */\r
- in = read_input_regular(m, ODD_CYCLE, second_half);\r
+ in = read_input_regular(m, ODD_CYCLE, stage);\r
out = butterfly(in);\r
next_cycle();\r
\r
/* Write outputs of previous cycle */\r
- write_output_regular(m, out, second_half);\r
+ write_output_regular(m, out, second_half, out_s);\r
\r
/* Even cycle */\r
- in = read_input_regular(m, EVEN_CYCLE, second_half);\r
+ in = read_input_regular(m, EVEN_CYCLE, stage);\r
out = butterfly(in);\r
} while (loop_next(LC2));\r
\r
/* Write outputs of previous cycle */\r
- write_output_regular(m, out, second_half);\r
+ write_output_regular(m, out, second_half, out_s);\r
\r
/* Last cycle */\r
- in = read_input_regular(m, ODD_CYCLE, second_half);\r
+ in = read_input_regular(m, ODD_CYCLE, stage);\r
out = butterfly(in);\r
next_cycle();\r
\r
/* Write outputs of last cycle */\r
- write_output_regular(m, out, second_half);\r
+ write_output_regular(m, out, second_half, out_s);\r
\r
/* Force the next cycle, because the next stage must read from\r
* the memory we just wrote to */\r
next_cycle();\r
}\r
\r
-INLINE struct mems init_mem_mapping(bool stage_odd){\r
+/**\r
+ * Assign the input and output memories, based on the current stage. Also \r
+ * assigns the twiddle memories, but those are fixed.\r
+ */\r
+INLINE struct mems init_mem_mapping(int stage){\r
struct mems res;\r
- if (stage_odd) {\r
+ /* Use left memories for input on odd (ie, first) \r
+ * stages and right memories on even stages. */\r
+ if ((stage % 2) == 0) {\r
res.input_a_re = alloc_mem(P0M1);\r
res.input_a_im = alloc_mem(P1M1);\r
res.input_b_re = alloc_mem(P2M1);\r
\r
return res;\r
}\r
+\r
+INLINE void do_regular_stage(int stage, enum in_strategy in_s, enum out_strategy out_s)\r
+{\r
+ struct mems m = init_mem_mapping(stage);\r
+ init_input_addresses_regular(m);\r
+ /* do_half_regular_stage will init output addresses */\r
+ next_cycle();\r
+ do_half_regular_stage(m, stage, FIRST_HALF, in_s, out_s);\r
+ do_half_regular_stage(m, stage, SECOND_HALF, in_s, out_s);\r
+}\r
+\r
void run() {\r
do { freeze(); } while (gpi(0) == 0);\r
- struct mems m;\r
\r
- /* We need to do n_t regular stages. Since we do two stages each\r
- * iteration, we'll do n_t / 2 iterations. */\r
- init_loop(LC1, (PARAM_n_t / 2));\r
- do {\r
- m = init_mem_mapping(EVEN_STAGE);\r
- init_input_addresses_regular(m, EVEN_STAGE);\r
- /* do_half_regular_stage will init output addresses */\r
- next_cycle();\r
- do_half_regular_stage(m, EVEN_STAGE, FIRST_HALF);\r
- do_half_regular_stage(m, EVEN_STAGE, SECOND_HALF);\r
- stage++;\r
- next_cycle();\r
- init_input_addresses_regular(m, ODD_STAGE);\r
- m = init_mem_mapping(ODD_STAGE);\r
- next_cycle();\r
- do_half_regular_stage(m, ODD_STAGE, FIRST_HALF);\r
- do_half_regular_stage(m, ODD_STAGE, SECOND_HALF);\r
- stage++;\r
- } while (loop_next(LC1));\r
+ do_regular_stage(1, REGULAR_IN, REGULAR_OUT);\r
+ do_regular_stage(2, REGULAR_IN, REGULAR_OUT);\r
+ do_regular_stage(3, REGULAR_IN, REGULAR_OUT);\r
+ do_regular_stage(4, REGULAR_IN, BITREVERSED_OUT);\r
+ \r
+ set_gpo(0);\r
+ next_cycle();\r
+ freeze();\r
+ clear_gpo(0);\r
+ next_cycle();\r
+ freeze();\r
}\r
projects / matthijs / projects / montium-fft.git / blobdiff