src/edu/berkeley/fleet/ir/Counter.java

   1 package edu.berkeley.fleet.ir;
   2 import edu.berkeley.fleet.loops.*;
   3 import java.util.concurrent.Semaphore;
   4 import java.util.*;
   5 import java.net.*;
   6 import edu.berkeley.fleet.two.*;
   7 import edu.berkeley.fleet.fpga.*;
   8 import edu.berkeley.fleet.api.*;
   9 import edu.berkeley.fleet.api.Instruction.*;
  10 import edu.berkeley.fleet.api.Instruction.Set;
  11 import edu.berkeley.fleet.api.Instruction.Set.*;
  12 import static edu.berkeley.fleet.util.BitManipulations.*;
  13 import edu.berkeley.fleet.api.Instruction.Set.FlagFunction;
  14 import edu.berkeley.fleet.api.Instruction.Set;
  15 import edu.berkeley.fleet.api.Instruction.Set.SetDest;
  16 import edu.berkeley.fleet.api.Instruction.Set.FlagFunction;
  17 import static edu.berkeley.fleet.api.Predicate.*;
  18
  19 public class Counter {
  20
  21
  22     /**
  23      *  Merge two sorted streams; it will issue tokens to provoke inputs
  24      */
  25     public static Dock merger(Context ctx,
  26                               Ship alu,
  27                               Destination in1_ack,
  28                               int inflight_in1,
  29                               Destination in2_ack,
  30                               int inflight_in2,
  31                               Destination d) {
  32
  33         Dock out  = alu.getDock("out");
  34         Dock inOp = alu.getDock("inOp");
  35         Dock in1  = alu.getDock("in1");
  36         Dock in2  = alu.getDock("in2");
  37
  38         LoopFactory lf_in1  = new LoopFactory(ctx, in1,  1);
  39         LoopFactory lf_in2  = new LoopFactory(ctx, in2,  1);
  40         LoopFactory lf_inOp = new LoopFactory(ctx, inOp, 1);
  41
  42         for(int i=0; i<inflight_in1; i++) lf_in1.sendToken(in1_ack);
  43         for(int i=0; i<inflight_in2; i++) lf_in2.sendToken(in2_ack);
  44
  45         lf_inOp.literal(4); // MAX
  46
  47         lf_in1  = lf_in1.makeNext(0);
  48         lf_in2  = lf_in2.makeNext(0);
  49         lf_inOp = lf_inOp.makeNext(0);
  50
  51         lf_in1.recvWord();
  52         lf_in1.deliver();
  53         lf_in1.sendToken(in1_ack);
  54
  55         lf_in2.recvWord();
  56         lf_in2.deliver();
  57         lf_in2.sendToken(in2_ack);
  58
  59         lf_inOp.deliver();
  60
  61         LoopFactory lf_out  = new LoopFactory(ctx, out, 0);
  62         lf_out.recvToken();
  63         lf_out.collectWord();
  64         lf_out.sendWord(d);
  65
  66         return out;
  67     }
  68
  69
  70     // FEATURE: optimize for short runs (use ILC counter, perhaps ILC+OLC combo)
  71     // FEATURE: stop-at-zero when counting downward
  72     /**
  73      *  A downward counter; returns the output dock that produces
  74      *  the values.
  75      *
  76      *  For each token sent to the output dock, a value will be sent
  77      *  to dest.
  78      */
  79     public static Dock counter(Context ctx,
  80                                Ship alu,
  81                                long start,
  82                                long incr,
  83                                int inflight,
  84                                Destination dest,
  85                                BitVector signal) {
  86
  87         if (inflight < 1) throw new RuntimeException();
  88
  89         boolean incr_is_positive   = false;
  90         boolean compile_time_start = true;
  91         boolean compile_time_incr  = true;
  92
  93         Dock out  = alu.getDock("out");
  94         Dock inOp = alu.getDock("inOp");
  95         Dock in1  = alu.getDock("in1");
  96         Dock in2  = alu.getDock("in2");
  97         LoopFactory lf;
  98
  99         //
 100         // FIXME: make sure we cope properly with getting torpedoed
 101         // before inflight-many tokens have arrived
 102         //
 103
 104         // FIXME: update Alu to "take-one" behavior, then fix stuff below
 105
 106         LoopFactory lf_in1  = new LoopFactory(ctx, in1,  1);
 107         LoopFactory lf_in2  = new LoopFactory(ctx, in2,  1);
 108         LoopFactory lf_inOp = new LoopFactory(ctx, inOp, 1);
 109         LoopFactory lf_out  = new LoopFactory(ctx, out, 1);
 110
 111         // Phase 1 //////////////////////////////////////////////////////////////////////////////
 112
 113         if (compile_time_incr)  lf_in1.literal(incr);  else lf_in1.recvWord();
 114         if (compile_time_start) lf_in2.literal(start); else lf_in2.recvWord();
 115         for(int i=0; i<inflight; i++) {
 116             lf_in1.deliver();
 117             lf_inOp.literal(0 /*IN1*/);
 118             lf_inOp.deliver();
 119             lf_out.collectWord();
 120             lf_out.sendWord(in1.getDataDestination());
 121
 122             lf_in2.deliver();
 123             lf_inOp.literal(1 /*IN2*/);
 124             lf_inOp.deliver();
 125             lf_out.collectWord();
 126             lf_out.sendWord(in1.getDataDestination());
 127         }
 128
 129         // Phase 2 //////////////////////////////////////////////////////////////////////////////
 130
 131         // FIXME: tokens for flow control here
 132         lf_inOp.literal(incr_is_positive ? 3/*SUB*/ : 2/*ADD*/);
 133         lf_inOp = lf_inOp.makeNext(0);
 134         lf_inOp.deliver();
 135
 136         lf_in2.literal(0);
 137         for(int i=0; i<inflight; i++) {
 138             lf_in1.recvWord();
 139             lf_in1.deliver();
 140             lf_in2.deliver();
 141             lf_out.collectWord();
 142             lf_out.sendWord(in2.getDataDestination());
 143
 144             lf_in1.recvWord();
 145             lf_in1.deliver();
 146             lf_in2.deliver();
 147
 148             lf_out.collectWord();
 149             lf_out.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 150             lf_out.setPredicate(Predicate.FlagA);
 151             lf_out.abort();
 152             lf_out.setPredicate(null);
 153             lf_out.sendWord(in1.getDataDestination());
 154             lf_out.recvToken();
 155             lf_out.sendWord(dest, signal);
 156
 157             lf_in2.recvWord();
 158         }
 159
 160         // Phase 3 //////////////////////////////////////////////////////////////////////////////
 161
 162         lf_in1 = lf_in1.makeNext(0);
 163         lf_in1.recvWord();
 164         lf_in1.deliver();
 165
 166         // FIXME: tokens for flow control here
 167         lf_in2 = lf_in2.makeNext(0);
 168         lf_in2.deliver();
 169
 170         lf_out = lf_out.makeNext(0);
 171         lf_out.collectWord();
 172         lf_out.sendWord(in1.getDataDestination());
 173         lf_out.recvToken();
 174         lf_out.sendWord(dest, signal);
 175
 176         // FIXME: ensure that if torpedoes arrive in phase1 or phase2 we deal with them properly
 177
 178         return out;
 179     }
 180
 181     /**
 182      *  A memory read with two address inputs.
 183      *
 184      *  Returns the address input dock of the memory ship.  Assumes
 185      *  that addresses will be sent to this dock from two distinct
 186      *  sources (in0 and in1), distinguished by the signal bit.
 187      *  Values read from memory will be routed to out0 or out1
 188      *  depending on which input source the address came from.
 189      *
 190      *  This widget does not send acknowledgement tokens; the
 191      *  recipients at out0 and out1 should send their tokens to in0
 192      *  and in1.
 193      */
 194     public static Dock memReadTwo(Context ctx,
 195                                   Ship mem,
 196                                   Destination out0,
 197                                   Destination out1) {
 198
 199         Dock inAddrRead = mem.getDock("inAddrRead");
 200         Dock out        = mem.getDock("out");
 201
 202         LoopFactory lf_inAddrRead = new LoopFactory(ctx, inAddrRead, 0);
 203         LoopFactory lf_out        = new LoopFactory(ctx, out, 0);
 204
 205         lf_inAddrRead.recvWord();
 206         lf_inAddrRead.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 207         lf_inAddrRead.setPredicate(Predicate.FlagA);
 208         lf_inAddrRead.sendToken(out.getDataDestination(), new BitVector(1).set(1));
 209         lf_inAddrRead.setPredicate(Predicate.NotFlagA);
 210         lf_inAddrRead.sendToken(out.getDataDestination(), new BitVector(1).set(0));
 211         lf_inAddrRead.setPredicate(null);
 212         lf_inAddrRead.deliver();
 213
 214         lf_out.recvToken();
 215         lf_out.setFlags(FlagFunction.ZERO.add(FlagC), FlagFunction.ZERO);
 216         lf_out.collectWord();
 217         lf_out.setPredicate(Predicate.FlagA);
 218         lf_out.sendWord(out1);
 219         lf_out.setPredicate(Predicate.NotFlagA);
 220         lf_out.sendWord(out0);
 221         lf_out.setPredicate(null);
 222
 223         return inAddrRead;
 224     }
 225
 226     public static void fillMemRandom(Fleet fleet, Ship memory, FleetProcess fp) {
 227         Random random = new Random(System.currentTimeMillis());
 228
 229         int SIZE = 256;
 230
 231         int[] ints = new int[SIZE/2];
 232         int[] intsbig = new int[SIZE];
 233         BitVector[] vals  = new BitVector[SIZE];
 234         BitVector[] vals2 = new BitVector[SIZE];
 235
 236         for(int j=0; j<2; j++) {
 237             for(int i=0; i<ints.length; i++) {
 238                 ints[i] = Math.abs(random.nextInt());
 239             }
 240             ints[ints.length-1] = Integer.MAX_VALUE;
 241             Arrays.sort(ints);
 242             for(int i=0; i<ints.length; i++) {
 243                 vals[i+j*ints.length] = new BitVector(fleet.getWordWidth()).set(ints[i]);
 244                 intsbig[i+j*ints.length] = ints[i];
 245             }
 246         }
 247         Arrays.sort(intsbig);
 248
 249         Gadgets.writeMem(fp, memory, 0, vals);
 250     }
 251
 252     public static void main(String[] s) throws Exception {
 253         Random random = new Random(System.currentTimeMillis());
 254         Fleet fleet = new Fpga();
 255         FleetProcess fp = fleet.run(new Instruction[0]);
 256
 257         int SIZE = 128;
 258
 259         Ship memory = fleet.getShip("DRAM",0);
 260         int[] ints = new int[SIZE/2];
 261         int[] intsbig = new int[SIZE];
 262         BitVector[] vals  = new BitVector[SIZE];
 263         BitVector[] vals2 = new BitVector[SIZE];
 264
 265         for(int j=0; j<2; j++) {
 266             for(int i=0; i<ints.length; i++) {
 267                 ints[i] = Math.abs(random.nextInt());
 268             }
 269             ints[ints.length-1] = Integer.MAX_VALUE;
 270             Arrays.sort(ints);
 271             for(int i=0; i<ints.length; i++) {
 272                 vals[i+j*ints.length] = new BitVector(fleet.getWordWidth()).set(ints[i]);
 273                 intsbig[i+j*ints.length] = ints[i];
 274             }
 275         }
 276         Arrays.sort(intsbig);
 277
 278         Gadgets.writeMem(fp, memory, 0, vals);
 279         Gadgets.readMem(fp, memory, 0, vals2);
 280         for(int i=0; i<vals.length; i++)
 281             if (!vals[i].equals(vals2[i]))
 282                 System.out.println("disagreement!  on index " + i + "\n  "+vals[i]+"\n  "+vals2[i]);
 283         System.out.println("done reading and verifying!");
 284         System.out.println();
 285         System.out.println();
 286
 287         Context ctx = new Context(fp.getFleet());
 288         Ship debug = fleet.getShip("Debug", 0);
 289
 290         Ship merger_alu = ctx.allocateShip("Alu");
 291
 292         Dock mem_in = memReadTwo(ctx, memory,
 293                                  merger_alu.getDock("in1").getDataDestination(),
 294                                  merger_alu.getDock("in2").getDataDestination());
 295
 296         Dock counter_0_ack = counter(ctx, ctx.allocateShip("Alu"), SIZE/2-1, -1, 1, mem_in.getDataDestination(), new BitVector(1).set(0));
 297
 298         Dock counter_1_ack = counter(ctx, ctx.allocateShip("Alu"), SIZE-1, -1, 1, mem_in.getDataDestination(), new BitVector(1).set(1));
 299
 300         Dock d3 = merger(ctx, merger_alu,
 301                          counter_0_ack.getDataDestination(), 1,
 302                          counter_1_ack.getDataDestination(), 1,
 303                          debug.getDock("in").getDataDestination());
 304
 305
 306         LoopFactory lf;
 307         lf = new LoopFactory(ctx, debug.getDock("in"), 0);
 308         lf.sendToken(d3.getDataDestination());
 309         lf.recvWord();
 310         lf.deliver();
 311
 312         ArrayList<Instruction> ai = new ArrayList<Instruction>();
 313         ctx.emit(ai);
 314         for(Instruction ins : ai)
 315             fp.sendInstruction(ins);
 316         fp.flush();
 317
 318         System.out.println("reading sorted words...");
 319         for(int i=intsbig.length-1; i>=0; i--) {
 320             BitVector bv = fp.recvWord();
 321             int x = (int)bv.toLong();
 322             if (x==intsbig[i]) System.out.println("agree " + x);
 323             else System.out.println("DISAGREE " + x + " " + intsbig[i]);
 324         }
 325         System.out.println("done.");
 326     }
 327
 328 }