FFT.mc

   1 #ifndef __MONTIUMCC__\r
   2 #include <memory.h>\r
   3 #include <math.h>\r
   4 #include <stdio.h>\r
   5 #endif\r
   6 \r
   7 #include "FFT.h"\r
   8 \r
   9 int stage = 1;\r
  10 /**\r
  11  * Executes a single butterfly on ALU 0-3. The inputs are the words taken from\r
  12  * in, which will be read on various inputs of ALU 0-3. Outputs will be\r
  13  * returned and will we be available on the output ports of ALU 0 and 2.\r
  14  */\r
  15 INLINE struct bf_out butterfly(struct bf_in in) {\r
  16         struct bf_out out;\r
  17         /* ALU 0 & 1 */\r
  18                 /* im(W) * im(b) */\r
  19                 aluexp Wixbi = west(fmul(rd1(in.W_im), rb1(in.b_im)));\r
  20         \r
  21                 /* re(W * b) = re(W) * re(b) - im(W) * im(b) */\r
  22                 aluexp Wxbr  = ssub_acc(fmul(rc1(in.W_re), ra1(in.b_re)), Wixbi);\r
  23 \r
  24                 \r
  25                 /* re(out_a) = re(a) + re(W * b) */\r
  26                 out.a_re =   p0o0(sadd_bf(rb1(in.a_re), Wxbr));\r
  27                 /* re(out_b) = re(a) - re(W * b) */\r
  28                 out.b_re = p0o1(ssub_bf(rb1(in.a_re), Wxbr));\r
  29                 \r
  30         /* ALU 2 & 3 */ \r
  31                 /* im(W) * re(b) */\r
  32                 aluexp Wixbr = west(fmul(rd1(in.W_im), rb1(in.b_re)));\r
  33                 /* im(W * b) = re(W) * im(b) + im(W) * re(b) */\r
  34                 aluexp Wxbi  = sadd_acc(fmul(rc1(in.W_re), ra1(in.b_im)), Wixbr);\r
  35                 \r
  36                 /* im(out_a) = im(a) + im(W * b) */\r
  37                 out.a_im =   p2o0(sadd_bf(rb1(in.a_im), Wxbi));\r
  38                 /* im(out_b) = im(a) - im(W * b) */\r
  39                 out.b_im = p2o1(ssub_bf(rb1(in.a_im), Wxbi));\r
  40                 \r
  41                 return out;\r
  42 }\r
  43 \r
  44 /**\r
  45  * Writes the output of a butterfly given in res to the correct memory\r
  46  * locations.\r
  47  * @param  second_half   Are we in the second half of the stage?\r
  48  */\r
  49 INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half) {\r
  50         add_offset(m.output_a_re, 2);\r
  51         add_offset(m.output_a_im, 2);\r
  52         add_offset(m.output_b_re, 2);\r
  53         add_offset(m.output_b_im, 2);\r
  54         \r
  55         if (second_half) {\r
  56                 write_mem(m.output_a_re, res.a_re);\r
  57                 write_mem(m.output_a_im, res.a_im);\r
  58                 write_mem(m.output_b_re, res.b_re);\r
  59                 write_mem(m.output_b_im, res.b_im);\r
  60         } else {\r
  61                 /* Write a results to memory b and v.v. */\r
  62                 write_mem(m.output_a_re, res.b_re);\r
  63                 write_mem(m.output_a_im, res.b_im);\r
  64                 write_mem(m.output_b_re, res.a_re);\r
  65                 write_mem(m.output_b_im, res.a_im);\r
  66         }\r
  67 }\r
  68 \r
  69 /**\r
  70  * Reads four inputs and two twiddle factors from memory. \r
  71  * Also increases memory offsets by 1 after reading.\r
  72  * @param    stage_odd Is this an odd stage? If so, read from the left\r
  73  *                     memories, else read from the right memories\r
  74  *                     (not implemented yet).\r
  75  * @param    cycle_odd Is this an odd cycle within the stage? If so, \r
  76  *                     read input a from memory b and v.v. If not, \r
  77  *                     simply read a from memory a and b from memory b.\r
  78  */\r
  79 INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage_odd) {\r
  80         struct bf_in in;\r
  81          /* Swap memory a and b during the odd cycles */\r
  82         if (cycle_odd) {\r
  83                 in.a_re = read_mem(m.input_a_re);\r
  84                 in.a_im = read_mem(m.input_a_im);\r
  85                 in.b_re = read_mem(m.input_b_re);               \r
  86                 in.b_im = read_mem(m.input_b_im);\r
  87         } else {\r
  88                 in.b_re = read_mem(m.input_a_re);\r
  89                 in.b_im = read_mem(m.input_a_im);\r
  90                 in.a_re = read_mem(m.input_b_re);               \r
  91                 in.a_im = read_mem(m.input_b_im);\r
  92         }\r
  93         in.W_re = read_mem(m.twiddle_re);\r
  94         in.W_im = read_mem(m.twiddle_im);\r
  95         \r
  96         \r
  97         /* Read inputs sequentially */\r
  98         add_offset(m.input_a_re, 1);\r
  99         add_offset(m.input_a_im, 1);\r
 100         add_offset(m.input_b_re, 1);\r
 101         add_offset(m.input_b_im, 1);\r
 102         \r
 103         /* TODO: Is this true? */\r
 104         add_offset(m.twiddle_re, (PARAM_N_t>>stage));\r
 105         add_offset(m.twiddle_im, (PARAM_N_t>>stage));\r
 106         use_mask(m.twiddle_re, (PARAM_N_t/2)-1);\r
 107         use_mask(m.twiddle_im, (PARAM_N_t/2)-1);\r
 108 \r
 109         return in;\r
 110 }\r
 111 \r
 112 /**\r
 113  * Initializes the addresses for writing the outputs.\r
 114  * @param stage_odd   True if this is an odd stage.\r
 115  * @param second_half True if we are initing halfway a stage.\r
 116  */ \r
 117 INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) {\r
 118         /* We simply start reading at address 0 incrementally */\r
 119         set_base(m.input_a_im, 0);\r
 120         set_base(m.input_b_re, 0);\r
 121         set_base(m.input_b_im, 0);\r
 122         set_base(m.twiddle_re, 0);\r
 123         set_base(m.twiddle_im, 0);\r
 124         \r
 125         set_offset(m.input_a_re, 0);\r
 126         set_offset(m.input_a_im, 0);\r
 127         set_offset(m.input_b_re, 0);\r
 128         set_offset(m.input_b_im, 0);\r
 129         set_offset(m.twiddle_re, 0);\r
 130         set_offset(m.twiddle_im, 0);\r
 131 }\r
 132 \r
 133 /**\r
 134  * Initializes the addresses for reading the inputs. This function must be\r
 135  * called twice per stage, since halfway the stage the addressing changes.\r
 136  */\r
 137 INLINE void init_output_addresses_regular(struct mems m, bool stage_odd, bool second_half) {\r
 138         /* \r
 139          * For the second half of the stage, the starting addresses are \r
 140          * reversed. write_output_regular above will also swap the output\r
 141          * memories.\r
 142          * TODO: Better comments :-)\r
 143          */\r
 144 \r
 145         set_base(m.output_a_re, 0);\r
 146         set_base(m.output_a_im, 0);\r
 147         set_base(m.output_b_re, 0);\r
 148         set_base(m.output_b_im, 0);\r
 149         \r
 150         /* We subtract two from every address, since write_output_regular \r
 151          * adds two to the offset before writing the first (and every other) \r
 152          * result. */\r
 153         if (second_half) {\r
 154                 set_offset(m.output_a_re, 1-2);\r
 155                 set_offset(m.output_a_im, 1-2);\r
 156                 set_offset(m.output_b_re, 0-2);\r
 157                 set_offset(m.output_b_im, 0-2);\r
 158         } else {\r
 159                 set_offset(m.output_a_re, 0-2);\r
 160                 set_offset(m.output_a_im, 0-2);\r
 161                 set_offset(m.output_b_re, 1-2);\r
 162                 set_offset(m.output_b_im, 1-2);\r
 163         }\r
 164 }\r
 165 \r
 166 INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_half){\r
 167          /*\r
 168          * We are doing two cycles in each iteration, so we can alternate the\r
 169          * cycle_odd argument (which only works with constants, I don't expect\r
 170          * the optimizer to do this loop unrolling for us). Since we need to\r
 171          * write outputs before reading, but don't have any outputs to write\r
 172          * in the first cycle, we must put the first cycle outside of the\r
 173          * loop. Since the loop does two cycles at a time, this means there\r
 174          * must be two cycles outside of the loop, so we put one at the end as\r
 175          * well. Additionally, we also need to write the outputs of the last\r
 176          * cycle in an extra cycle at the end. We probably can't combine this\r
 177          * last cycle with the first cycle of the next stage, because they\r
 178          * need the same memories (input becomes output and v.v.).\r
 179          */\r
 180 \r
 181         /* Initialize output addresses, this must be done twice per stage */\r
 182         init_output_addresses_regular(m, stage_odd, second_half);\r
 183 \r
 184         /* First cycle (no previous output to write) */\r
 185         struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage_odd);\r
 186         struct bf_out out = butterfly(in);\r
 187 \r
 188         /* Now, do half a single stage. That means N_t / 4 cycles. Since we do 2\r
 189          * cycles on every iteration, plus one before and after the loop,\r
 190          * we will loop N_t / 8 - 1 times. */\r
 191         init_loop(LC2, (PARAM_N_t / 8) - 1);\r
 192         do {\r
 193                 /* Write outputs of previous cycle */\r
 194                 write_output_regular(m, out, second_half);\r
 195 \r
 196                 /* Odd cycle */\r
 197                 in = read_input_regular(m, ODD_CYCLE, second_half);\r
 198                 out = butterfly(in);\r
 199                 next_cycle();\r
 200 \r
 201                 /* Write outputs of previous cycle */\r
 202                 write_output_regular(m, out, second_half);\r
 203 \r
 204                 /* Even cycle */\r
 205                 in = read_input_regular(m, EVEN_CYCLE, second_half);\r
 206                 out = butterfly(in);\r
 207         } while (loop_next(LC2));\r
 208         \r
 209         /* Write outputs of previous cycle */\r
 210         write_output_regular(m, out, second_half);\r
 211 \r
 212         /* Last cycle */\r
 213         in = read_input_regular(m, ODD_CYCLE, second_half);\r
 214         out = butterfly(in);\r
 215         next_cycle();\r
 216 \r
 217         /* Write outputs of last cycle */\r
 218         write_output_regular(m, out, second_half);\r
 219         \r
 220         /* Force the next cycle, because the next stage must read from\r
 221          * the memory we just wrote to */\r
 222         next_cycle();\r
 223 }\r
 224 \r
 225 INLINE struct mems init_mem_mapping(bool stage_odd){\r
 226         struct mems res;\r
 227         if (stage_odd) {\r
 228                 res.input_a_re   = alloc_mem(P0M1);\r
 229                 res.input_a_im   = alloc_mem(P1M1);\r
 230                 res.input_b_re   = alloc_mem(P2M1);\r
 231                 res.input_b_im   = alloc_mem(P3M1);\r
 232                 res.output_a_re  = alloc_mem(P0M0);\r
 233                 res.output_a_im  = alloc_mem(P1M0);\r
 234                 res.output_b_re  = alloc_mem(P2M0);\r
 235                 res.output_b_im  = alloc_mem(P3M0);\r
 236         } else {\r
 237                 res.input_a_re   = alloc_mem(P0M0);\r
 238                 res.input_a_im   = alloc_mem(P1M0);\r
 239                 res.input_b_re   = alloc_mem(P2M0);\r
 240                 res.input_b_im   = alloc_mem(P3M0);\r
 241                 res.output_a_re  = alloc_mem(P0M1);\r
 242                 res.output_a_im  = alloc_mem(P1M1);\r
 243                 res.output_b_re  = alloc_mem(P2M1);\r
 244                 res.output_b_im  = alloc_mem(P3M1);\r
 245         }\r
 246         \r
 247         res.twiddle_re   = alloc_mem(P4M0);\r
 248         res.twiddle_im   = alloc_mem(P4M1);\r
 249         \r
 250         return res;\r
 251 }\r
 252 void run() {\r
 253         do { freeze(); } while (gpi(0) == 0);\r
 254         struct mems m;\r
 255 \r
 256         /* We need to do n_t regular stages. Since we do two stages each\r
 257          * iteration, we'll do n_t / 2 iterations. */\r
 258         init_loop(LC1, (PARAM_n_t / 2));\r
 259         do {\r
 260                 m = init_mem_mapping(EVEN_STAGE);\r
 261                 init_input_addresses_regular(m, EVEN_STAGE);\r
 262                 /* do_half_regular_stage will init output addresses */\r
 263                 next_cycle();\r
 264                 do_half_regular_stage(m, EVEN_STAGE, FIRST_HALF);\r
 265                 do_half_regular_stage(m, EVEN_STAGE, SECOND_HALF);\r
 266                 stage++;\r
 267                 next_cycle();\r
 268                 init_input_addresses_regular(m, ODD_STAGE);\r
 269                 m = init_mem_mapping(ODD_STAGE);\r
 270                 next_cycle();\r
 271                 do_half_regular_stage(m, ODD_STAGE, FIRST_HALF);\r
 272                 do_half_regular_stage(m, ODD_STAGE, SECOND_HALF);\r
 273                 stage++;\r
 274         } while (loop_next(LC1));\r
 275 }\r