src/nmutil/concurrentunit.py

   1 """ concurrent unit from mitch alsup augmentations to 6600 scoreboard
   2
   3     This work is funded through NLnet under Grant 2019-02-012
   4
   5     License: LGPLv3+
   6
   7
   8     * data fans in
   9     * data goes through a pipeline
  10     * results fan back out.
  11
  12     the output data format has to have a member "muxid", which is used
  13     as the array index on fan-out
  14
  15     Associated bugreports:
  16
  17     * https://bugs.libre-soc.org/show_bug.cgi?id=538
  18 """
  19
  20 from math import log
  21 from nmigen import Module, Elaboratable, Signal, Cat
  22 from nmigen.asserts import Assert
  23 from nmigen.lib.coding import PriorityEncoder
  24 from nmigen.cli import main, verilog
  25
  26 from nmutil.singlepipe import PassThroughStage
  27 from nmutil.multipipe import CombMuxOutPipe
  28 from nmutil.multipipe import PriorityCombMuxInPipe
  29 from nmutil.iocontrol import NextControl, PrevControl
  30 from nmutil import nmoperator
  31
  32
  33 def num_bits(n):
  34     return int(log(n) / log(2))
  35
  36
  37 class PipeContext:
  38
  39     def __init__(self, pspec):
  40         """ creates a pipeline context.  currently: operator (op) and muxid
  41
  42             opkls (within pspec) - the class to create that will be the
  43                                    "operator". instance must have an "eq"
  44                                    function.
  45         """
  46         self.id_wid = pspec.id_wid
  47         self.op_wid = pspec.op_wid
  48         self.muxid = Signal(self.id_wid, reset_less=True)   # RS multiplex ID
  49         opkls = pspec.opkls
  50         if opkls is None:
  51             self.op = Signal(self.op_wid, reset_less=True)
  52         else:
  53             self.op = opkls(pspec)
  54
  55     def eq(self, i):
  56         ret = [self.muxid.eq(i.muxid)]
  57         ret.append(self.op.eq(i.op))
  58         # don't forget to update matches if you add fields later.
  59         return ret
  60
  61     def matches(self, another):
  62         """
  63         Returns a list of Assert()s validating that this context
  64         matches the other context.
  65         """
  66         # I couldn't figure a clean way of overloading the == operator.
  67         return [
  68             Assert(self.muxid == another.muxid),
  69             Assert(self.op == another.op),
  70         ]
  71
  72     def __iter__(self):
  73         yield self.muxid
  74         yield self.op
  75
  76     def ports(self):
  77         if hasattr(self.op, "ports"):
  78             return [self.muxid] + self.op.ports()
  79         else:
  80             return list(self)
  81
  82
  83 class InMuxPipe(PriorityCombMuxInPipe):
  84     def __init__(self, num_rows, iospecfn, maskwid=0):
  85         self.num_rows = num_rows
  86         stage = PassThroughStage(iospecfn)
  87         PriorityCombMuxInPipe.__init__(self, stage, p_len=self.num_rows,
  88                                        maskwid=maskwid)
  89
  90
  91 class MuxOutPipe(CombMuxOutPipe):
  92     def __init__(self, num_rows, iospecfn, maskwid=0):
  93         self.num_rows = num_rows
  94         stage = PassThroughStage(iospecfn)
  95         CombMuxOutPipe.__init__(self, stage, n_len=self.num_rows,
  96                                 maskwid=maskwid)
  97
  98
  99 class ALUProxy:
 100     """ALUProxy: create a series of ALUs that look like the ALU being
 101     sandwiched in between the fan-in and fan-out.  One ALU looks like
 102     it is multiple concurrent ALUs
 103     """
 104     def __init__(self, alu, p, n):
 105         self.alu = alu
 106         self.p = p
 107         self.n = n
 108
 109
 110 class ReservationStations(Elaboratable):
 111     """ Reservation-Station pipeline
 112
 113         Input: num_rows - number of input and output Reservation Stations
 114
 115         Requires: the addition of an "alu" object, from which ispec and ospec
 116         are taken, and inpipe and outpipe are connected to it
 117
 118         * fan-in on inputs (an array of BaseData: a,b,mid)
 119         * ALU pipeline
 120         * fan-out on outputs (an array of FPPackData: z,mid)
 121
 122         Fan-in and Fan-out are combinatorial.
 123     """
 124     def __init__(self, num_rows, maskwid=0, feedback_width=None):
 125         self.num_rows = nr = num_rows
 126         self.feedback_width = feedback_width
 127         self.inpipe = InMuxPipe(nr, self.i_specfn, maskwid)   # fan-in
 128         self.outpipe = MuxOutPipe(nr, self.o_specfn, maskwid) # fan-out
 129
 130         self.p = self.inpipe.p  # kinda annoying,
 131         self.n = self.outpipe.n # use pipe in/out as this class in/out
 132         self._ports = self.inpipe.ports() + self.outpipe.ports()
 133
 134     def setup_pseudoalus(self):
 135         """setup_pseudoalus: establishes a suite of pseudo-alus
 136         that look to all pipeline-intents-and-purposes just like the original
 137         """
 138         self.pseudoalus = []
 139         for i in range(self.num_rows):
 140             self.pseudoalus.append(ALUProxy(self.alu, self.p[i], self.n[i]))
 141
 142     def elaborate(self, platform):
 143         m = Module()
 144         m.submodules.inpipe = self.inpipe
 145         m.submodules.alu = self.alu
 146         m.submodules.outpipe = self.outpipe
 147
 148         m.d.comb += self.inpipe.n.connect_to_next(self.alu.p)
 149         m.d.comb += self.alu.connect_to_next(self.outpipe)
 150
 151         if self.feedback_width is None:
 152             return m
 153
 154         # connect all outputs above the feedback width back to their inputs
 155         # (hence, feedback).  pipeline stages are then expected to *modify*
 156         # the muxid (with care) in order to use the "upper numbered" RSes
 157         # for storing partially-completed results.  micro-coding, basically
 158
 159         for i in range(self.feedback_width, self.num_rows):
 160             self.outpipe.n[i].connect_to_next(self.inpipe.p[i])
 161
 162         return m
 163
 164     def ports(self):
 165         return self._ports
 166
 167     def i_specfn(self):
 168         return self.alu.ispec()
 169
 170     def o_specfn(self):
 171         return self.alu.ospec()
 172
 173
 174 class ReservationStations2(Elaboratable):
 175     """ Reservation-Station pipeline.  Manages an ALU and makes it look like
 176         there are multiple of them, presenting the same ready/valid API
 177
 178         Input:
 179
 180         :alu: - an ALU to be "managed" by these ReservationStations
 181         :num_rows: - number of input and output Reservation Stations
 182
 183         Note that the ALU data (in and out specs) right the way down the
 184         entire chain *must* have a "muxid" data member.  this is picked
 185         up and used to route data correctly from input RS to output RS.
 186
 187         It is the responsibility of the USER of the ReservationStations
 188         class to correctly set that muxid in each data packet to the
 189         correct constant.  this could change in future.
 190
 191     """
 192     def __init__(self, alu, num_rows):
 193         self.num_rows = nr = num_rows
 194         id_wid = num_rows.bit_length()
 195         self.p = []
 196         self.n = []
 197         self.alu = alu
 198         # create prev and next ready/valid and add replica of ALU data specs
 199         for i in range(num_rows):
 200             suffix = "_%d" % i
 201             p = PrevControl(name=suffix)
 202             n = NextControl(name=suffix)
 203             p.i_data, n.o_data = self.alu.new_specs("rs_%d" % i)
 204             self.p.append(p)
 205             self.n.append(n)
 206
 207         self.pipe = self # for Arbiter to select the incoming prevcontrols
 208
 209         # set up pseudo-alus that look like a standard pipeline
 210         self.pseudoalus = []
 211         for i in range(self.num_rows):
 212             self.pseudoalus.append(ALUProxy(self.alu, self.p[i], self.n[i]))
 213
 214     def __iter__(self):
 215         for p in self.p:
 216             yield from p
 217         for n in self.n:
 218             yield from n
 219
 220     def ports(self):
 221         return list(self)
 222
 223     def elaborate(self, platform):
 224         m = Module()
 225         pe = PriorityEncoder(self.num_rows) # input priority picker
 226         m.submodules.alu = self.alu
 227         m.submodules.selector = pe
 228         for i, (p, n) in enumerate(zip(self.p, self.n)):
 229             m.submodules["rs_p_%d" % i] = p
 230             m.submodules["rs_n_%d" % i] = n
 231
 232         # Priority picker for one RS
 233         self.active = Signal()
 234         self.m_id = Signal.like(pe.o)
 235
 236         # ReservationStation status information, progressively updated in FSM
 237         rsvd = Signal(self.num_rows) # indicates RS data in flight
 238         sent = Signal(self.num_rows) # sent indicates data in pipeline
 239         wait = Signal(self.num_rows) # the outputs are waiting for accept
 240
 241         # pick first non-reserved ReservationStation with data not already
 242         # sent into the ALU
 243         m.d.comb += pe.i.eq(rsvd & ~sent)
 244         m.d.comb += self.active.eq(~pe.n)   # encoder active (one input valid)
 245         m.d.comb += self.m_id.eq(pe.o)       # output one active input
 246
 247         # mux in and mux out ids.  note that all data *must* have a muxid
 248         mid = self.m_id                   # input mux selector
 249         o_muxid = self.alu.n.o_data.muxid # output mux selector
 250
 251         # technically speaking this could be set permanently "HI".
 252         # when all the ReservationStations outputs are waiting,
 253         # the ALU cannot obviously accept any more data.  as the
 254         # ALU is effectively "decoupled" from (managed by) the RSes,
 255         # as long as there is sufficient RS allocation this should not
 256         # be necessary, i.e. at no time should the ALU be given more inputs
 257         # than there are outputs to accept (!) but just in case...
 258         m.d.comb += self.alu.n.i_ready.eq(~wait.all())
 259
 260         #####
 261         # input side
 262         #####
 263
 264         # first, establish input: select one input to pass data to (p_mux)
 265         for i in range(self.num_rows):
 266             i_buf, o_buf = self.alu.new_specs("buf%d" % i) # buffers
 267             with m.FSM():
 268                 # indicate ready to accept data, and accept it if incoming
 269                 # BUT, if there is an opportunity to send on immediately
 270                 # to the ALU, take it early (combinatorial)
 271                 with m.State("ACCEPTING%d" % i):
 272                     m.d.comb += self.p[i].o_ready.eq(1) # ready indicator
 273                     with m.If(self.p[i].i_valid):  # valid data incoming
 274                         m.d.sync += rsvd[i].eq(1)  # now reserved
 275                         # a unique opportunity: the ALU happens to be free
 276                         with m.If(mid == i): # picker selected us
 277                             with m.If(self.alu.p.o_ready):  # ALU can accept
 278                                 m.d.comb += self.alu.p.i_valid.eq(1) # transfer
 279                                 m.d.comb += nmoperator.eq(self.alu.p.i_data,
 280                                                          self.p[i].i_data)
 281                                 m.d.sync += sent[i].eq(1) # now reserved
 282                                 m.next = "WAITOUT%d" % i # move to "wait output"
 283                         with m.Else():
 284                             # nope. ALU wasn't free. try next cycle(s)
 285                             m.d.sync += nmoperator.eq(i_buf, self.p[i].i_data)
 286                             m.next = "ACCEPTED%d" % i # move to "accepted"
 287
 288                 # now try to deliver to the ALU, but only if we are "picked"
 289                 with m.State("ACCEPTED%d" % i):
 290                     with m.If(mid == i): # picker selected us
 291                         with m.If(self.alu.p.o_ready):  # ALU can accept
 292                             m.d.comb += self.alu.p.i_valid.eq(1) # transfer
 293                             m.d.comb += nmoperator.eq(self.alu.p.i_data, i_buf)
 294                             m.d.sync += sent[i].eq(1) # now reserved
 295                             m.next = "WAITOUT%d" % i # move to "wait output"
 296
 297                 # waiting for output to appear on the ALU, take a copy
 298                 # BUT, again, if there is an opportunity to send on
 299                 # immediately, take it (combinatorial)
 300                 with m.State("WAITOUT%d" % i):
 301                     with m.If(o_muxid == i): # when ALU output matches our RS
 302                         with m.If(self.alu.n.o_valid):  # ALU can accept
 303                             # second unique opportunity: the RS is ready
 304                             with m.If(self.n[i].i_ready): # ready to receive
 305                                 m.d.comb += self.n[i].o_valid.eq(1) # valid
 306                                 m.d.comb += nmoperator.eq(self.n[i].o_data,
 307                                                           self.alu.n.o_data)
 308                                 m.d.sync += wait[i].eq(0) # clear waiting
 309                                 m.d.sync += sent[i].eq(0) # and sending
 310                                 m.d.sync += rsvd[i].eq(0) # and reserved
 311                                 m.next = "ACCEPTING%d" % i # back to "accepting"
 312                             with m.Else():
 313                                 # nope. RS wasn't ready. try next cycles
 314                                 m.d.sync += wait[i].eq(1) # now waiting
 315                                 m.d.sync += nmoperator.eq(o_buf,
 316                                                           self.alu.n.o_data)
 317                                 m.next = "SENDON%d" % i # move to "send data on"
 318
 319                 # waiting for "valid" indicator on RS output: deliver it
 320                 with m.State("SENDON%d" % i):
 321                     with m.If(self.n[i].i_ready): # user is ready to receive
 322                         m.d.comb += self.n[i].o_valid.eq(1) # indicate valid
 323                         m.d.comb += nmoperator.eq(self.n[i].o_data, o_buf)
 324                         m.d.sync += wait[i].eq(0) # clear waiting
 325                         m.d.sync += sent[i].eq(0) # and sending
 326                         m.d.sync += rsvd[i].eq(0) # and reserved
 327                         m.next = "ACCEPTING%d" % i # and back to "accepting"
 328
 329         return m
 330