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         FAILING TO SET THE MUXID IS GUARANTEED TO RESULT IN CORRUPTED DATA.
 192     """
 193     def __init__(self, alu, num_rows, alu_name=None):
 194         if alu_name is None:
 195             alu_name = "alu"
 196         self.num_rows = nr = num_rows
 197         id_wid = num_rows.bit_length()
 198         self.p = []
 199         self.n = []
 200         self.alu = alu
 201         self.alu_name = alu_name
 202         # create prev and next ready/valid and add replica of ALU data specs
 203         for i in range(num_rows):
 204             suffix = "_%d" % i
 205             p = PrevControl(name=suffix)
 206             n = NextControl(name=suffix)
 207             p.i_data, n.o_data = self.alu.new_specs("rs_%d" % i)
 208             self.p.append(p)
 209             self.n.append(n)
 210
 211         self.pipe = self # for Arbiter to select the incoming prevcontrols
 212
 213         # set up pseudo-alus that look like a standard pipeline
 214         self.pseudoalus = []
 215         for i in range(self.num_rows):
 216             self.pseudoalus.append(ALUProxy(self.alu, self.p[i], self.n[i]))
 217
 218     def __iter__(self):
 219         for p in self.p:
 220             yield from p
 221         for n in self.n:
 222             yield from n
 223
 224     def ports(self):
 225         return list(self)
 226
 227     def elaborate(self, platform):
 228         m = Module()
 229         pe = PriorityEncoder(self.num_rows) # input priority picker
 230         m.submodules[self.alu_name] = self.alu
 231         m.submodules.selector = pe
 232         for i, (p, n) in enumerate(zip(self.p, self.n)):
 233             m.submodules["rs_p_%d" % i] = p
 234             m.submodules["rs_n_%d" % i] = n
 235
 236         # Priority picker for one RS
 237         self.active = Signal()
 238         self.m_id = Signal.like(pe.o)
 239
 240         # ReservationStation status information, progressively updated in FSM
 241         rsvd = Signal(self.num_rows) # indicates RS data in flight
 242         sent = Signal(self.num_rows) # sent indicates data in pipeline
 243         wait = Signal(self.num_rows) # the outputs are waiting for accept
 244
 245         # pick first non-reserved ReservationStation with data not already
 246         # sent into the ALU
 247         m.d.comb += pe.i.eq(rsvd & ~sent)
 248         m.d.comb += self.active.eq(~pe.n)   # encoder active (one input valid)
 249         m.d.comb += self.m_id.eq(pe.o)       # output one active input
 250
 251         # mux in and mux out ids.  note that all data *must* have a muxid
 252         mid = self.m_id                   # input mux selector
 253         o_muxid = self.alu.n.o_data.muxid # output mux selector
 254
 255         # technically speaking this could be set permanently "HI".
 256         # when all the ReservationStations outputs are waiting,
 257         # the ALU cannot obviously accept any more data.  as the
 258         # ALU is effectively "decoupled" from (managed by) the RSes,
 259         # as long as there is sufficient RS allocation this should not
 260         # be necessary, i.e. at no time should the ALU be given more inputs
 261         # than there are outputs to accept (!) but just in case...
 262         m.d.comb += self.alu.n.i_ready.eq(~wait.all())
 263
 264         #####
 265         # input side
 266         #####
 267
 268         # first, establish input: select one input to pass data to (p_mux)
 269         for i in range(self.num_rows):
 270             i_buf, o_buf = self.alu.new_specs("buf%d" % i) # buffers
 271             with m.FSM():
 272                 # indicate ready to accept data, and accept it if incoming
 273                 # BUT, if there is an opportunity to send on immediately
 274                 # to the ALU, take it early (combinatorial)
 275                 with m.State("ACCEPTING%d" % i):
 276                     m.d.comb += self.p[i].o_ready.eq(1) # ready indicator
 277                     with m.If(self.p[i].i_valid):  # valid data incoming
 278                         m.d.sync += rsvd[i].eq(1)  # now reserved
 279                         # a unique opportunity: the ALU happens to be free
 280                         with m.If(mid == i): # picker selected us
 281                             with m.If(self.alu.p.o_ready):  # ALU can accept
 282                                 m.d.comb += self.alu.p.i_valid.eq(1) # transfer
 283                                 m.d.comb += nmoperator.eq(self.alu.p.i_data,
 284                                                          self.p[i].i_data)
 285                                 m.d.sync += sent[i].eq(1) # now reserved
 286                                 m.next = "WAITOUT%d" % i # move to "wait output"
 287                         with m.Else():
 288                             # nope. ALU wasn't free. try next cycle(s)
 289                             m.d.sync += nmoperator.eq(i_buf, self.p[i].i_data)
 290                             m.next = "ACCEPTED%d" % i # move to "accepted"
 291
 292                 # now try to deliver to the ALU, but only if we are "picked"
 293                 with m.State("ACCEPTED%d" % i):
 294                     with m.If(mid == i): # picker selected us
 295                         with m.If(self.alu.p.o_ready):  # ALU can accept
 296                             m.d.comb += self.alu.p.i_valid.eq(1) # transfer
 297                             m.d.comb += nmoperator.eq(self.alu.p.i_data, i_buf)
 298                             m.d.sync += sent[i].eq(1) # now reserved
 299                             m.next = "WAITOUT%d" % i # move to "wait output"
 300
 301                 # waiting for output to appear on the ALU, take a copy
 302                 # BUT, again, if there is an opportunity to send on
 303                 # immediately, take it (combinatorial)
 304                 with m.State("WAITOUT%d" % i):
 305                     with m.If(o_muxid == i): # when ALU output matches our RS
 306                         with m.If(self.alu.n.o_valid):  # ALU can accept
 307                             # second unique opportunity: the RS is ready
 308                             with m.If(self.n[i].i_ready): # ready to receive
 309                                 m.d.comb += self.n[i].o_valid.eq(1) # valid
 310                                 m.d.comb += nmoperator.eq(self.n[i].o_data,
 311                                                           self.alu.n.o_data)
 312                                 m.d.sync += wait[i].eq(0) # clear waiting
 313                                 m.d.sync += sent[i].eq(0) # and sending
 314                                 m.d.sync += rsvd[i].eq(0) # and reserved
 315                                 m.next = "ACCEPTING%d" % i # back to "accepting"
 316                             with m.Else():
 317                                 # nope. RS wasn't ready. try next cycles
 318                                 m.d.sync += wait[i].eq(1) # now waiting
 319                                 m.d.sync += nmoperator.eq(o_buf,
 320                                                           self.alu.n.o_data)
 321                                 m.next = "SENDON%d" % i # move to "send data on"
 322
 323                 # waiting for "valid" indicator on RS output: deliver it
 324                 with m.State("SENDON%d" % i):
 325                     with m.If(self.n[i].i_ready): # user is ready to receive
 326                         m.d.comb += self.n[i].o_valid.eq(1) # indicate valid
 327                         m.d.comb += nmoperator.eq(self.n[i].o_data, o_buf)
 328                         m.d.sync += wait[i].eq(0) # clear waiting
 329                         m.d.sync += sent[i].eq(0) # and sending
 330                         m.d.sync += rsvd[i].eq(0) # and reserved
 331                         m.next = "ACCEPTING%d" % i # and back to "accepting"
 332
 333         return m
 334