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