src/nmutil/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, Elaboratable
  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, Elaboratable):
  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             fwft mode = True basically means that the data may be transferred
  47             combinatorially from input to output.
  48
  49             Attributes:
  50             * level: available free space (number of unread entries)
  51
  52             din  = enq_data, writable  = enq_ready, we = enq_valid
  53             dout = deq_data, re = deq_ready, readable = deq_valid
  54         """
  55         FIFOInterface.__init__(self, width, depth, fwft)
  56         self.pipe = pipe
  57         self.depth = depth
  58         self.level = Signal(bits_for(depth))
  59
  60     def elaborate(self, platform):
  61         m = Module()
  62
  63         # set up an SRAM.  XXX bug in Memory: cannot create SRAM of depth 1
  64         ram = Memory(self.width, self.depth if self.depth > 1 else 2)
  65         m.submodules.ram_read = ram_read = ram.read_port(domain="comb")
  66         m.submodules.ram_write = ram_write = ram.write_port()
  67
  68         # convenience names, for people familiar with ready/valid terminology
  69         # "p" stands for "previous stage", "n" stands for "next stage"
  70         # for people familiar with the chisel Decoupled library:
  71         # enq is "enqueue" (data in, aka "prev stage"),
  72         # deq is "dequeue" (data out, aka "next stage")
  73         p_ready_o = self.writable
  74         p_valid_i = self.we
  75         enq_data = self.din # aka p_data_i
  76
  77         n_valid_o = self.readable
  78         n_ready_i = self.re
  79         deq_data = self.dout # aka n_data_o
  80
  81         # intermediaries
  82         ptr_width = bits_for(self.depth - 1) if self.depth > 1 else 0
  83         enq_ptr = Signal(ptr_width) # cyclic pointer to "insert" point (wrport)
  84         deq_ptr = Signal(ptr_width) # cyclic pointer to "remove" point (rdport)
  85         maybe_full = Signal() # not reset_less (set by sync)
  86
  87         # temporaries
  88         do_enq = Signal(reset_less=True)
  89         do_deq = Signal(reset_less=True)
  90         ptr_diff = Signal(ptr_width)
  91         ptr_match = Signal(reset_less=True)
  92         empty = Signal(reset_less=True)
  93         full = Signal(reset_less=True)
  94         enq_max = Signal(reset_less=True)
  95         deq_max = Signal(reset_less=True)
  96
  97         m.d.comb += [ptr_match.eq(enq_ptr == deq_ptr), # read-ptr = write-ptr
  98                      ptr_diff.eq(enq_ptr - deq_ptr),
  99                      enq_max.eq(enq_ptr == self.depth - 1),
 100                      deq_max.eq(deq_ptr == self.depth - 1),
 101                      empty.eq(ptr_match & ~maybe_full),
 102                      full.eq(ptr_match & maybe_full),
 103                      do_enq.eq(p_ready_o & p_valid_i), # write conditions ok
 104                      do_deq.eq(n_ready_i & n_valid_o), # read conditions ok
 105
 106                      # set readable and writable (NOTE: see pipe mode below)
 107                      n_valid_o.eq(~empty), # cannot read if empty!
 108                      p_ready_o.eq(~full),  # cannot write if full!
 109
 110                      # set up memory and connect to input and output
 111                      ram_write.addr.eq(enq_ptr),
 112                      ram_write.data.eq(enq_data),
 113                      ram_write.en.eq(do_enq),
 114                      ram_read.addr.eq(deq_ptr),
 115                      deq_data.eq(ram_read.data) # NOTE: overridden in fwft mode
 116                     ]
 117
 118         # under write conditions, SRAM write-pointer moves on next clock
 119         with m.If(do_enq):
 120             m.d.sync += enq_ptr.eq(Mux(enq_max, 0, enq_ptr+1))
 121
 122         # under read conditions, SRAM read-pointer moves on next clock
 123         with m.If(do_deq):
 124             m.d.sync += deq_ptr.eq(Mux(deq_max, 0, deq_ptr+1))
 125
 126         # if read-but-not-write or write-but-not-read, maybe_full set
 127         with m.If(do_enq != do_deq):
 128             m.d.sync += maybe_full.eq(do_enq)
 129
 130         # first-word fall-through: same as "flow" parameter in Chisel3 Queue
 131         # basically instead of relying on the Memory characteristics (which
 132         # in FPGAs do not have write-through), then when the queue is empty
 133         # take the output directly from the input, i.e. *bypass* the SRAM.
 134         # this done combinatorially to give the exact same characteristics
 135         # as Memory "write-through"... without relying on a changing API
 136         if self.fwft:
 137             with m.If(p_valid_i):
 138                 m.d.comb += n_valid_o.eq(1)
 139             with m.If(empty):
 140                 m.d.comb += deq_data.eq(enq_data)
 141                 m.d.comb += do_deq.eq(0)
 142                 with m.If(n_ready_i):
 143                     m.d.comb += do_enq.eq(0)
 144
 145         # pipe mode: if next stage says it's ready (readable), we
 146         #            *must* declare the input ready (writeable).
 147         if self.pipe:
 148             with m.If(n_ready_i):
 149                 m.d.comb += p_ready_o.eq(1)
 150
 151         # set the count (available free space), optimise on power-of-two
 152         if self.depth == 1 << ptr_width:  # is depth a power of 2
 153             m.d.comb += self.level.eq(
 154                 Mux(maybe_full & ptr_match, self.depth, 0) | ptr_diff)
 155         else:
 156             m.d.comb += self.level.eq(Mux(ptr_match,
 157                                           Mux(maybe_full, self.depth, 0),
 158                                           Mux(deq_ptr > enq_ptr,
 159                                               self.depth + ptr_diff,
 160                                               ptr_diff)))
 161
 162         return m
 163
 164
 165 if __name__ == "__main__":
 166     reg_stage = Queue(1, 1, pipe=True)
 167     break_ready_chain_stage = Queue(1, 1, pipe=True, fwft=True)
 168     m = Module()
 169     ports = []
 170
 171     def queue_ports(queue, name_prefix):
 172         retval = []
 173         for name in ["level",
 174                      "dout",
 175                      "readable",
 176                      "writable"]:
 177             port = getattr(queue, name)
 178             signal = Signal(port.shape(), name=name_prefix+name)
 179             m.d.comb += signal.eq(port)
 180             retval.append(signal)
 181         for name in ["re",
 182                      "din",
 183                      "we"]:
 184             port = getattr(queue, name)
 185             signal = Signal(port.shape(), name=name_prefix+name)
 186             m.d.comb += port.eq(signal)
 187             retval.append(signal)
 188         return retval
 189
 190     m.submodules.reg_stage = reg_stage
 191     ports += queue_ports(reg_stage, "reg_stage_")
 192     m.submodules.break_ready_chain_stage = break_ready_chain_stage
 193     ports += queue_ports(break_ready_chain_stage, "break_ready_chain_stage_")
 194     main(m, ports=ports)