ships/Memory.ship

   1 ship: Memory
   2
   3 == Ports ===========================================================
   4 data  in:    inCBD
   5 data  in:    inAddrRead
   6 data  in:    inAddrWrite
   7 data  in:    inDataWrite
   8
   9 data  out:   out
  10
  11 == TeX ==============================================================
  12
  13 The {\tt Memory} ship represents an interface to a storage space,
  14 which can be used to read from it or write to it.  This storage space
  15 might be a fast on-chip cache, off chip DRAM, or perhaps even a disk
  16 drive.
  17
  18 Generally, distinct {\tt Memory} ships do not access the same backing
  19 storage, although this is not strictly prohibited.
  20
  21 Each {\tt Memory} ship may have multiple {\it interfaces}, numbered
  22 starting with {\tt 0}.  Each interface may have any subset of the
  23 following docks: {\tt inCBD}, {\tt inAddrRead}, {\tt inAddrWrite},
  24 {\tt inDataWrite}, and {\tt out}.  If {\tt inCBD} or {\tt inAddrRead}
  25 is present on an interface, then {\tt out} must be present as well.
  26 If {\tt inAddrWrite} is present then {\tt inDataWrite} must be present
  27 as well.
  28
  29 Each interface serializes the operations presented to it; this means
  30 that an interface with both read and write capabilities will not be
  31 able to read and write concurrently.  Instead, a {\tt Memory} ship
  32 with the ability to read and write concurrently should have two
  33 interfaces, one which is read-only and one which is write-only.
  34
  35 There may be multiple {\tt Memory} ships which interface to the same
  36 physical storage space.  An implementation of Fleet must provide
  37 additional documentation to the programmer indicating which {\tt
  38 Memory} ships correspond to which storage spaces.  A single {\tt
  39 Memory} ship may also access a ``virtual storage space'' formed by
  40 concatenating multiple physical storage spaces.
  41
  42 \subsection*{Code Bag Fetch}
  43
  44 When a word appears at the {\tt inCBD} port, it is treated as a {\it
  45 code bag descriptor}, as shown below:
  46
  47 \begin{center}
  48 \setlength{\bitwidth}{3mm}
  49 {\tt
  50 \begin{bytefield}{37}
  51   \bitheader[b]{36,6,5,0}\\
  52   \bitbox{31}{Address}
  53   \bitbox{6}{size}
  54 \end{bytefield}
  55 }
  56 \end{center}
  57
  58 When a word arrives at the {\tt inCBD} port, it is treated as a memory
  59 read with {\tt inAddrRead=Address}, {\tt inStride=1}, and {\tt
  60 inCount=size}.
  61
  62 \subsection*{Reading}
  63
  64 When a word is delivered to {\tt inAddrRead}, the word residing in
  65 memory at that address is provided at {\tt out}.  The {\tt c-flag} at
  66 the {\tt out} port is set to zero.
  67
  68 \subsection*{Writing}
  69
  70 When a word is delivered to {\tt inAddrWrite} and {\tt inDataWrite},
  71 the word at {\tt inDataWrite} is written to the address specified by
  72 {\tt inAddrWrite}.  Once the word is successfully committed to memory,
  73 the value {\tt inAddr+inStride} is provided at {\tt out} (that is, the
  74 address of the next word to be written).  The {\tt c-flag} at
  75 the {\tt out} port is set to one.
  76
  77 \subsection*{To Do}
  78
  79 Stride and count are not implemented.
  80
  81 We need a way to do an ``unordered fetch'' -- a way to tell the memory
  82 unit to retrieve some block of words in any order it likes.  This can
  83 considerably accelerate fetches when the first word of the region is
  84 not cached, but other parts are cached.  This can also be used for
  85 dispatching codebags efficiently -- but how will we make sure that
  86 instructions destined for a given pump are dispatched in the correct
  87 order (source sequence guarantee)?
  88
  89 A more advanced form would be ``unordered fetch of ordered records''
  90 -- the ability to specify a record size (in words), the offset of the
  91 first record, and the number of records to be fetched.  The memory
  92 unit would then fetch the records in any order it likes, but would be
  93 sure to return the words comprising a record in the order in which
  94 they appear in memory.  This feature could be used to solve the source
  95 sequence guarantee problem mentioned in the previous paragraph.
  96
  97 == Fleeterpreter ====================================================
  98     private long[] mem = new long[0];
  99     public long readMem(int addr) { return addr >= mem.length ? 0 : mem[addr]; }
 100     public void writeMem(int addr, long val) {
 101         if (addr >= mem.length) {
 102             long[] newmem = new long[addr * 2 + 1];
 103             System.arraycopy(mem, 0, newmem, 0, mem.length);
 104             mem = newmem;
 105         }
 106         mem[addr] = val;
 107     }
 108
 109     private long stride = 0;
 110     private long count = 0;
 111     private long addr = 0;
 112     private boolean writing = false;
 113
 114     private Queue<Long> toDispatch = new LinkedList<Long>();
 115     public void service() {
 116
 117         if (toDispatch.size() > 0) {
 118             //if (!box_out.readyForDataFromShip()) return;
 119             //box_out.addDataFromShip(toDispatch.remove());
 120             getInterpreter().dispatch(getInterpreter().readInstruction(toDispatch.remove(), getDock("out")));
 121         }
 122
 123         if (box_inCBD.dataReadyForShip() && box_out.readyForDataFromShip()) {
 124             long val = box_inCBD.removeDataForShip();
 125             long addr = val >> 6;
 126             long size = val & 0x3f;
 127             for(int i=0; i<size; i++)
 128               toDispatch.add(readMem((int)(addr+i)));
 129         }
 130         if (count > 0) {
 131             if (writing) {
 132               if (box_inDataWrite.dataReadyForShip() && box_out.readyForDataFromShip()) {
 133                  writeMem((int)addr, box_inDataWrite.removeDataForShip());
 134                  box_out.addDataFromShip(0);
 135                  count--;
 136                  addr += stride;
 137               }
 138             } else {
 139               if (box_out.readyForDataFromShip()) {
 140                  box_out.addDataFromShip(readMem((int)addr));
 141                  count--;
 142                  addr += stride;
 143               }
 144             }
 145
 146         } else if (box_inAddrRead.dataReadyForShip()) {
 147             addr = box_inAddrRead.removeDataForShip();
 148             stride = 0;
 149             count = 1;
 150             writing = false;
 151
 152         } else if (box_inAddrWrite.dataReadyForShip()) {
 153             addr = box_inAddrWrite.removeDataForShip();
 154             stride = 0;
 155             count = 1;
 156             writing = true;
 157         }
 158     }
 159
 160 == FleetSim ==============================================================
 161
 162 == FPGA ==============================================================
 163
 164   reg                              write_flag;
 165   reg [(`BRAM_ADDR_WIDTH-1):0]     cursor;
 166   wire [(`BRAM_ADDR_WIDTH-1):0]   addr1;
 167
 168   // bram //////////////////////////////////////////////////////////////////////////////
 169 `define BRAM_ADDR_WIDTH 14
 170 `define BRAM_SIZE (1<<(`BRAM_ADDR_WIDTH))
 171
 172     reg    [(`WORDWIDTH-1):0]       ram [((`BRAM_SIZE)-1):0];
 173     reg    [(`BRAM_ADDR_WIDTH-1):0] read_a;
 174     reg    [(`BRAM_ADDR_WIDTH-1):0] read_dpra;
 175     always @(posedge clk) begin
 176         if (write_flag)
 177             ram[addr1] <= inDataWrite_d;
 178         read_a <= addr1;
 179         read_dpra <= cursor;
 180     end
 181
 182   ////////////////////////////////////////////////////////////////////////////////
 183
 184   wire [(`WORDWIDTH-1):0] out1;
 185   wire [(`WORDWIDTH-1):0] out2;
 186
 187   assign out1 = ram[read_a];
 188   assign out2 = ram[read_dpra];
 189
 190   reg [(`CODEBAG_SIZE_BITS-1):0]   counter;
 191   initial cursor = 0;
 192   initial counter = 0;
 193
 194   reg                              out_w;
 195   reg                              dispatching_cbd;
 196   initial write_flag = 0;
 197   initial dispatching_cbd = 0;
 198
 199   assign addr1 = write_flag ? inAddrWrite_d[(`WORDWIDTH-1):0] : inAddrRead_d[(`WORDWIDTH-1):0];
 200
 201   assign out_d_ = { out_w , (dispatching_cbd ? out2 : out1) };
 202
 203   always @(posedge clk) begin
 204
 205     write_flag <= 0;
 206
 207     if (!rst) begin
 208       `reset
 209       cursor  <= 0;
 210       counter <= 0;
 211       write_flag <= 0;
 212       dispatching_cbd <= 0;
 213     end else begin
 214       `flush
 215       `cleanup
 216       write_flag <= 0;
 217
 218       // assumes we never want a zero-length codebag
 219       if (`inCBD_full && `out_empty) begin
 220         if (!dispatching_cbd) begin
 221           cursor          <= inCBD_d[(`WORDWIDTH-1):(`CODEBAG_SIZE_BITS)];
 222           counter         <= 0;
 223           dispatching_cbd <= 1;
 224         end
 225         `fill_out
 226         out_w <= 0;
 227
 228       end else if (`inCBD_full && `out_draining) begin
 229         if (counter != inCBD_d[(`CODEBAG_SIZE_BITS-1):0]) begin
 230           cursor  <= cursor + 1;
 231           counter <= counter + 1;
 232         end else begin
 233           `drain_inCBD
 234           counter <= 0;
 235           dispatching_cbd <= 0;
 236         end
 237
 238       end else if (!dispatching_cbd && `out_empty && `inAddrRead_full) begin
 239         `drain_inAddrRead
 240         `fill_out
 241         out_w <= 0;
 242
 243       end else if (!dispatching_cbd && `out_empty && `inAddrWrite_full && `inDataWrite_full) begin
 244         // timing note: it's okay to drain here because *_d will still
 245         // be valid on the *very next* cycle, which is all we care about
 246         `drain_inAddrWrite
 247         `drain_inDataWrite
 248         `fill_out
 249         write_flag      <= 1;
 250         out_w           <= 1;
 251       end
 252     end
 253   end
 254
 255
 256
 257
 258 == Test ==============================================================
 259 // FIXME: test c-flag at out dock
 260 // FIXME: rename to inCBD0, inAddrWrite0, etc
 261
 262 // expected output
 263 #expect 12
 264 #expect 13
 265 #expect 14
 266
 267 // ships required in order to run this code
 268 #ship debug          : Debug
 269 #ship memory         : Memory
 270
 271 // instructions not in any codebag are part of the "root codebag"
 272 // which is dispatched when the code is loaded
 273
 274 memory.out:
 275   set ilc=*;  collect packet, send;
 276
 277 memory.inCBD:
 278   set word= BOB;
 279   deliver;
 280
 281 BOB: {
 282   debug.in:
 283     set word= 12; deliver;
 284     set word= 13; deliver;
 285     set word= 14; deliver;
 286 }
 287
 288
 289 == Constants ========================================================
 290
 291 == Contributors =========================================================
 292 Adam Megacz <megacz@cs.berkeley.edu>