src/ieee754/part/layout_experiment.py

   1 #!/usr/bin/env python3
   2 # SPDX-License-Identifier: LGPL-3-or-later
   3 # See Notices.txt for copyright information
   4 """
   5 Links:
   6 * https://libre-soc.org/3d_gpu/architecture/dynamic_simd/shape/
   7 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c20
   8 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c30
   9 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c34
  10 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c47
  11 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c22
  12 * https://bugs.libre-soc.org/show_bug.cgi?id=713#c67
  13 """
  14
  15 from nmigen import Signal, Module, Elaboratable, Mux, Cat, Shape, Repl
  16 from nmigen.back.pysim import Simulator, Delay, Settle
  17 from nmigen.cli import rtlil
  18
  19 from collections.abc import Mapping
  20 from functools import reduce
  21 import operator
  22 from collections import defaultdict
  23 from pprint import pprint
  24
  25 from ieee754.part_mul_add.partpoints import PartitionPoints
  26
  27
  28 # main fn, which started out here in the bugtracker:
  29 # https://bugs.libre-soc.org/show_bug.cgi?id=713#c20
  30 def layout(elwid, signed, vec_el_counts, lane_shapes=None, fixed_width=None):
  31     """calculate a SIMD layout.
  32
  33     Glossary:
  34     * element: a single scalar value that is an element of a SIMD vector.
  35         it has a width in bits, and a signedness. Every element is made of 1 or
  36         more parts.
  37     * ElWid: the element-width (really the element type) of an instruction.
  38         Either an integer or a FP type. Integer `ElWid`s are sign-agnostic.
  39         In Python, `ElWid` is either an enum type or is `int`.
  40         Example `ElWid` definition for integers:
  41
  42         class ElWid(Enum):
  43             I64 = ...       # SVP64 value 0b00
  44             I32 = ...       # SVP64 value 0b01
  45             I16 = ...       # SVP64 value 0b10
  46             I8 = ...        # SVP64 value 0b11
  47
  48         Example `ElWid` definition for floats:
  49
  50         class ElWid(Enum):
  51             F64 = ...    # SVP64 value 0b00
  52             F32 = ...    # SVP64 value 0b01
  53             F16 = ...    # SVP64 value 0b10
  54             BF16 = ...   # SVP64 value 0b11
  55
  56     # XXX this is redundant and out-of-date with respect to the
  57     # clarification that the input is in counts of *elements*
  58     # *NOT* "fixed width parts".
  59     # fixed-width parts results in 14 such parts being created
  60     # when 5 will do, for a simple example 5-6-6-6
  61     * part: A piece of a SIMD vector, every SIMD vector is made of a
  62         non-negative integer of parts. Elements are made of a power-of-two
  63         number of parts. A part is a fixed number of bits wide for each
  64         different SIMD layout, it doesn't vary when `elwid` changes. A part
  65         can have a bit width of any non-negative integer, it is not restricted
  66         to power-of-two. SIMD vectors should have as few parts as necessary,
  67         since some circuits have size proportional to the number of parts.
  68
  69     * elwid: ElWid or nmigen Value with ElWid as the shape
  70         the current element-width
  71     * signed: bool
  72         the signedness of all elements in a SIMD layout
  73     * vec_el_counts: dict[ElWid, int]
  74         a map from `ElWid` values `k` to the number of vector elements
  75         required within a partition when `elwid == k`.
  76
  77         Example:
  78         vec_el_counts = {ElWid.I8(==0b11): 8, # 8 vector elements
  79                        ElWid.I16(==0b10): 4,  # 4 vector elements
  80                        ElWid.I32(==0b01): 2,  # 2 vector elements
  81                        ElWid.I64(==0b00): 1}  # 1 vector (aka scalar) element
  82
  83         Another Example:
  84         # here, there is one
  85         vec_el_counts = {ElWid.BF16(==0b11): 4,
  86                          ElWid.F16(==0b10): 4,
  87                          ElWid.F32(==0b01): 2,
  88                          ElWid.F64(==0b00): 1}
  89
  90     * lane_shapes: int or Mapping[ElWid, int] (optional)
  91         the bit-width of all elements in a SIMD layout.
  92
  93     * fixed_width: int (optional)
  94         the total width of a SIMD vector. One or both of lane_shapes or
  95         fixed_width may be provided.  Both may not be left out.
  96     """
  97     # when there are no lane_shapes specified, this indicates a
  98     # desire to use the maximum available space based on the fixed width
  99     # https://bugs.libre-soc.org/show_bug.cgi?id=713#c67
 100     if lane_shapes is None:
 101         assert fixed_width is not None, \
 102             "both fixed_width and lane_shapes cannot be None"
 103         lane_shapes = {i: fixed_width // vec_el_counts[i]
 104                        for i in vec_el_counts}
 105         print("lane_shapes", fixed_width, lane_shapes)
 106     # identify if the lane_shapes is a mapping (dict, etc.)
 107     # if not, then assume that it is an integer (width) that
 108     # needs to be requested across all partitions
 109     if not isinstance(lane_shapes, Mapping):
 110         lane_shapes = {i: lane_shapes for i in vec_el_counts}
 111     # compute a set of partition widths
 112     print("lane_shapes", lane_shapes, "vec_el_counts", vec_el_counts)
 113     cpart_wid = max(lane_shapes.values())
 114     part_count = max(vec_el_counts.values())
 115     # calculate the minumum width required
 116     width = cpart_wid * part_count
 117     print("width", width, cpart_wid, part_count)
 118     if fixed_width is not None:  # override the width and part_wid
 119         assert width < fixed_width, "not enough space to fit partitions"
 120         part_wid = fixed_width // part_count
 121         assert part_wid * part_count == fixed_width, \
 122             "calculated width not aligned multiples"
 123         width = fixed_width
 124         print("part_wid", part_wid, "count", part_count)
 125     else:
 126         # go with computed width
 127         part_wid = cpart_wid
 128     # create the breakpoints dictionary.
 129     # do multi-stage version https://bugs.libre-soc.org/show_bug.cgi?id=713#c34
 130     # https://stackoverflow.com/questions/26367812/
 131     dpoints = defaultdict(list)  # if empty key, create a (empty) list
 132     for i, c in vec_el_counts.items():
 133         def add_p(p):
 134             dpoints[p].append(i)  # auto-creates list if key non-existent
 135         for start in range(0, part_count, c):
 136             add_p(start * part_wid)  # start of lane
 137             add_p(start * part_wid + lane_shapes[i])  # start of padding
 138     # do not need the breakpoints at the very start or the very end
 139     dpoints.pop(0, None)
 140     dpoints.pop(width, None)
 141     plist = list(dpoints.keys())
 142     plist.sort()
 143     print("dpoints")
 144     pprint(dict(dpoints))
 145     # second stage, add (map to) the elwidth==i expressions.
 146     # TODO: use nmutil.treereduce?
 147     points = {}
 148     for p in plist:
 149         points[p] = map(lambda i: elwid == i, dpoints[p])
 150         points[p] = reduce(operator.or_, points[p])
 151     # third stage, create the binary values which *if* elwidth is set to i
 152     # *would* result in the mask at that elwidth being set to this value
 153     # these can easily be double-checked through Assertion
 154     bitp = {}
 155     for i in vec_el_counts.keys():
 156         bitp[i] = 0
 157         for p, elwidths in dpoints.items():
 158             if i in elwidths:
 159                 bitpos = plist.index(p)
 160                 bitp[i] |= 1 << bitpos
 161     # fourth stage: determine which partitions are 100% unused.
 162     # these can then be "blanked out"
 163     bmask = (1 << len(plist))-1
 164     for p in bitp.values():
 165         bmask &= ~p
 166     return (PartitionPoints(points), bitp, bmask, width, lane_shapes,
 167             part_wid, part_count)
 168
 169
 170 if __name__ == '__main__':
 171
 172     # for each element-width (elwidth 0-3) the number of Vector Elements is:
 173     # elwidth=0b00 QTY 1 partitions:   |          ?          |
 174     # elwidth=0b01 QTY 1 partitions:   |          ?          |
 175     # elwidth=0b10 QTY 2 partitions:   |    ?     |     ?    |
 176     # elwidth=0b11 QTY 4 partitions:   | ?  |  ?  |  ?  | ?  |
 177     # actual widths of Signals *within* those partitions is given separately
 178     vec_el_counts = {
 179         0: 1,
 180         1: 1,
 181         2: 2,
 182         3: 4,
 183     }
 184
 185     # width=3 indicates "same width Vector Elements (3) at all elwidths"
 186     # elwidth=0b00 1x 5-bit     |  unused xx      ..3 |
 187     # elwidth=0b01 1x 6-bit     |  unused xx      ..3 |
 188     # elwidth=0b10 2x 12-bit    | xxx  ..3 | xxx  ..3 |
 189     # elwidth=0b11 3x 24-bit    | ..3| ..3 | ..3 |..3 |
 190     # expected partitions      (^)   |     |     |   (^)
 191     # to be at these points:   (|)   |     |     |    |
 192     width_in_all_parts = 3
 193
 194     for i in range(4):
 195         pprint((i, layout(i, True, vec_el_counts, width_in_all_parts)))
 196
 197     # fixed_width=32 and no lane_widths says "allocate maximum"
 198     # i.e. Vector Element Widths are auto-allocated
 199     # elwidth=0b00 1x 32-bit    | .................32 |
 200     # elwidth=0b01 1x 32-bit    | .................32 |
 201     # elwidth=0b10 2x 12-bit    | ......16 | ......16 |
 202     # elwidth=0b11 3x 24-bit    | ..8| ..8 | ..8 |..8 |
 203     # expected partitions      (^)   |     |     |   (^)
 204     # to be at these points:   (|)   |     |     |    |
 205
 206     # TODO, fix this so that it is correct
 207     #print ("maximum allocation from fixed_width=32")
 208     # for i in range(4):
 209     #    pprint((i, layout(i, True, vec_el_counts, fixed_width=32)))
 210
 211     # specify that the Vector Element lengths are to be *different* at
 212     # each of the elwidths.
 213     # combined with vec_el_counts we have:
 214     # elwidth=0b00 1x 5-bit     | <--  unused               -->....5 |
 215     # elwidth=0b01 1x 6-bit     | <--  unused              -->.....6 |
 216     # elwidth=0b10 2x 12-bit    | unused   .....6 | unused    .....6 |
 217     # elwidth=0b11 3x 24-bit    | .....6 | .....6 |  .....6 | .....6 |
 218     # expected partitions      (^)       ^        ^         ^^      (^)
 219     # to be at these points:   (|)       |        |         ||      (|)
 220     widths_at_elwidth = {
 221         0: 5,
 222         1: 6,
 223         2: 6,
 224         3: 6
 225     }
 226
 227     print ("5,6,6,6 elements", widths_at_elwidth)
 228     for i in range(4):
 229         pprint((i, layout(i, False, vec_el_counts, widths_at_elwidth)))
 230
 231     # this tests elwidth as an actual Signal. layout is allowed to
 232     # determine arbitrarily the overall length
 233     # https://bugs.libre-soc.org/show_bug.cgi?id=713#c30
 234
 235     elwid = Signal(2)
 236     pp, bitp, bm, b, c, d, e = layout(
 237         elwid, False, vec_el_counts, widths_at_elwidth)
 238     pprint((pp, b, c, d, e))
 239     for k, v in bitp.items():
 240         print("bitp elwidth=%d" % k, bin(v))
 241     print("bmask", bin(bm))
 242
 243     m = Module()
 244
 245     def process():
 246         for i in range(4):
 247             yield elwid.eq(i)
 248             yield Settle()
 249             ppt = []
 250             for pval in list(pp.values()):
 251                 val = yield pval  # get nmigen to evaluate pp
 252                 ppt.append(val)
 253             pprint((i, (ppt, b, c, d, e)))
 254             # check the results against bitp static-expected partition points
 255             # https://bugs.libre-soc.org/show_bug.cgi?id=713#c47
 256             # https://stackoverflow.com/a/27165694
 257             ival = int(''.join(map(str, ppt[::-1])), 2)
 258             assert ival == bitp[i]
 259
 260     sim = Simulator(m)
 261     sim.add_process(process)
 262     sim.run()
 263
 264     # this tests elwidth as an actual Signal. layout is *not* allowed to
 265     # determine arbitrarily the overall length, it is fixed to 64
 266     # https://bugs.libre-soc.org/show_bug.cgi?id=713#c22
 267
 268     elwid = Signal(2)
 269     pp, bitp, bm, b, c, d, e = layout(elwid, False, vec_el_counts,
 270                                       widths_at_elwidth,
 271                                       fixed_width=64)
 272     pprint((pp, b, c, d, e))
 273     for k, v in bitp.items():
 274         print("bitp elwidth=%d" % k, bin(v))
 275     print("bmask", bin(bm))
 276
 277     m = Module()
 278
 279     def process():
 280         for i in range(4):
 281             yield elwid.eq(i)
 282             yield Settle()
 283             ppt = []
 284             for pval in list(pp.values()):
 285                 val = yield pval  # get nmigen to evaluate pp
 286                 ppt.append(val)
 287             print("test elwidth=%d" % i)
 288             pprint((i, (ppt, b, c, d, e)))
 289             # check the results against bitp static-expected partition points
 290             # https://bugs.libre-soc.org/show_bug.cgi?id=713#c47
 291             # https://stackoverflow.com/a/27165694
 292             ival = int(''.join(map(str, ppt[::-1])), 2)
 293             assert ival == bitp[i], "ival %s actual %s" % (bin(ival),
 294                                                            bin(bitp[i]))
 295
 296     sim = Simulator(m)
 297     sim.add_process(process)
 298     sim.run()