src/add/queue.py

   1 # Copyright (c) 2014 - 2019 The Regents of the University of
   2 # California (Regents). All Rights Reserved.  Redistribution and use in
   3 # source and binary forms, with or without modification, are permitted
   4 # provided that the following conditions are met:
   5 #    * Redistributions of source code must retain the above
   6 #      copyright notice, this list of conditions and the following
   7 #      two paragraphs of disclaimer.
   8 #    * Redistributions in binary form must reproduce the above
   9 #      copyright notice, this list of conditions and the following
  10 #      two paragraphs of disclaimer in the documentation and/or other materials
  11 #      provided with the distribution.
  12 #    * Neither the name of the Regents nor the names of its contributors
  13 #      may be used to endorse or promote products derived from this
  14 #      software without specific prior written permission.
  15 # IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
  16 # SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS,
  17 # ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
  18 # REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  19 # REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
  20 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 # A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF
  22 # ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION
  23 # TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
  24 # MODIFICATIONS.
  25
  26 from nmigen import Module, Signal, Memory, Mux
  27 from nmigen.tools import bits_for
  28 from nmigen.cli import main
  29 from nmigen.lib.fifo import FIFOInterface
  30
  31 # translated from https://github.com/freechipsproject/chisel3/blob/a4a29e29c3f1eed18f851dcf10bdc845571dfcb6/src/main/scala/chisel3/util/Decoupled.scala#L185   # noqa
  32
  33
  34 class Queue(FIFOInterface):
  35     def __init__(self, width, depth, fwft=True, pipe=False):
  36         """ Queue (FIFO) with pipe mode and first-write fall-through capability
  37
  38             * width: width of Queue data in/out
  39             * depth: queue depth.  NOTE: may be set to 0 (this is ok)
  40             * fwft : first-write, fall-through mode (Chisel Queue "flow" mode)
  41             * pipe : pipe mode.  NOTE: this mode can cause unanticipated
  42                      problems.  when read is enabled, so is writeable.
  43                      therefore if read is enabled, the data ABSOLUTELY MUST
  44                      be read.
  45
  46             din  = enq_data, writable  = enq_ready, we = enq_valid
  47             dout = deq_data, re = deq_ready, readable = deq_valid
  48         """
  49         FIFOInterface.__init__(self, width, depth, fwft)
  50         self.pipe = pipe
  51         self.depth = depth
  52         self.count = Signal(bits_for(depth))
  53
  54     def elaborate(self, platform):
  55         m = Module()
  56
  57         # set up an SRAM.  XXX bug in Memory: cannot create SRAM of depth 1
  58         ram = Memory(self.width, self.depth if self.depth > 1 else 2)
  59         m.submodules.ram_read = ram_read = ram.read_port(synchronous=False)
  60         m.submodules.ram_write = ram_write = ram.write_port()
  61
  62         # intermediaries
  63         ptr_width = bits_for(self.depth - 1) if self.depth > 1 else 0
  64         enq_ptr = Signal(ptr_width) # cyclic pointer to "insert" point (wrport)
  65         deq_ptr = Signal(ptr_width) # cyclic pointer to "remove" point (rdport)
  66         maybe_full = Signal() # not reset_less (set by sync)
  67
  68         # temporaries
  69         do_enq = Signal(reset_less=True)
  70         do_deq = Signal(reset_less=True)
  71         ptr_diff = Signal(ptr_width)
  72         ptr_match = Signal(reset_less=True)
  73         empty = Signal(reset_less=True)
  74         full = Signal(reset_less=True)
  75         enq_max = Signal(reset_less=True)
  76         deq_max = Signal(reset_less=True)
  77
  78         m.d.comb += [ptr_match.eq(enq_ptr == deq_ptr), # read-ptr = write-ptr
  79                      ptr_diff.eq(enq_ptr - deq_ptr),
  80                      enq_max.eq(enq_ptr == self.depth - 1),
  81                      deq_max.eq(deq_ptr == self.depth - 1),
  82                      empty.eq(ptr_match & ~maybe_full),
  83                      full.eq(ptr_match & maybe_full),
  84                      do_enq.eq(self.writable & self.we), # write conditions ok
  85                      do_deq.eq(self.re & self.readable), # read conditions ok
  86
  87                      # set readable and writable (NOTE: see pipe mode below)
  88                      self.readable.eq(~empty), # cannot read if empty!
  89                      self.writable.eq(~full),  # cannot write if full!
  90
  91                      # set up memory and connect to input and output
  92                      ram_write.addr.eq(enq_ptr),
  93                      ram_write.data.eq(self.din),
  94                      ram_write.en.eq(do_enq),
  95                      ram_read.addr.eq(deq_ptr),
  96                      self.dout.eq(ram_read.data) # NOTE: overridden in fwft mode
  97                     ]
  98
  99         # under write conditions, SRAM write-pointer moves on next clock
 100         with m.If(do_enq):
 101             m.d.sync += enq_ptr.eq(Mux(enq_max, 0, enq_ptr+1))
 102
 103         # under read conditions, SRAM read-pointer moves on next clock
 104         with m.If(do_deq):
 105             m.d.sync += deq_ptr.eq(Mux(deq_max, 0, deq_ptr+1))
 106
 107         # if read-but-not-write or write-but-not-read, maybe_full set
 108         with m.If(do_enq != do_deq):
 109             m.d.sync += maybe_full.eq(do_enq)
 110
 111         # first-word fall-through: same as "flow" parameter in Chisel3 Queue
 112         # basically instead of relying on the Memory characteristics (which
 113         # in FPGAs do not have write-through), then when the queue is empty
 114         # take the output directly from the input, i.e. *bypass* the SRAM.
 115         # this done combinatorially to give the exact same characteristics
 116         # as Memory "write-through"... without relying on a changing API
 117         if self.fwft:
 118             with m.If(self.we):
 119                 m.d.comb += self.readable.eq(1)
 120             with m.If(empty):
 121                 m.d.comb += self.dout.eq(self.din)
 122                 m.d.comb += do_deq.eq(0)
 123                 with m.If(self.re):
 124                     m.d.comb += do_enq.eq(0)
 125
 126         # pipe mode: read-enabled requires writability.
 127         if self.pipe:
 128             with m.If(self.re):
 129                 m.d.comb += self.writable.eq(1)
 130
 131         if self.depth == 1 << len(self.count):  # is depth a power of 2
 132             m.d.comb += self.count.eq(
 133                 Mux(self.maybe_full & self.ptr_match, self.depth, 0)
 134                 | self.ptr_diff)
 135         else:
 136             m.d.comb += self.count.eq(Mux(ptr_match,
 137                                           Mux(maybe_full, self.depth, 0),
 138                                           Mux(deq_ptr > enq_ptr,
 139                                               self.depth + ptr_diff,
 140                                               ptr_diff)))
 141
 142         return m
 143
 144
 145 if __name__ == "__main__":
 146     reg_stage = Queue(1, 1, pipe=True)
 147     break_ready_chain_stage = Queue(1, 1, pipe=True, fwft=True)
 148     m = Module()
 149     ports = []
 150
 151     def queue_ports(queue, name_prefix):
 152         retval = []
 153         for name in ["count",
 154                      "dout",
 155                      "readable",
 156                      "writable"]:
 157             port = getattr(queue, name)
 158             signal = Signal(port.shape(), name=name_prefix+name)
 159             m.d.comb += signal.eq(port)
 160             retval.append(signal)
 161         for name in ["re",
 162                      "din",
 163                      "we"]:
 164             port = getattr(queue, name)
 165             signal = Signal(port.shape(), name=name_prefix+name)
 166             m.d.comb += port.eq(signal)
 167             retval.append(signal)
 168         return retval
 169     m.submodules.reg_stage = reg_stage
 170     ports += queue_ports(reg_stage, "reg_stage_")
 171     m.submodules.break_ready_chain_stage = break_ready_chain_stage
 172     ports += queue_ports(break_ready_chain_stage, "break_ready_chain_stage_")
 173     main(m, ports=ports)