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     # create the breakpoints dictionary.
 126     # do multi-stage version https://bugs.libre-soc.org/show_bug.cgi?id=713#c34
 127     # https://stackoverflow.com/questions/26367812/
 128     dpoints = defaultdict(list)  # if empty key, create a (empty) list
 129     for i, c in vec_el_counts.items():
 130         # calculate part_wid based on overall width divided by number
 131         # of elements.
 132         part_wid = width // c
 133         def add_p(p):
 134             dpoints[p].append(i)  # auto-creates list if key non-existent
 135         # for each elwidth, create the required number of vector elements
 136         for start in range(c):
 137             add_p(start * part_wid)  # start of lane
 138             add_p(start * part_wid + lane_shapes[i])  # start of padding
 139     # do not need the breakpoints at the very start or the very end
 140     dpoints.pop(0, None)
 141     dpoints.pop(width, None)
 142     plist = list(dpoints.keys())
 143     plist.sort()
 144     print("dpoints")
 145     pprint(dict(dpoints))
 146     # second stage, add (map to) the elwidth==i expressions.
 147     # TODO: use nmutil.treereduce?
 148     points = {}
 149     for p in plist:
 150         points[p] = map(lambda i: elwid == i, dpoints[p])
 151         points[p] = reduce(operator.or_, points[p])
 152     # third stage, create the binary values which *if* elwidth is set to i
 153     # *would* result in the mask at that elwidth being set to this value
 154     # these can easily be double-checked through Assertion
 155     bitp = {}
 156     for i in vec_el_counts.keys():
 157         bitp[i] = 0
 158         for p, elwidths in dpoints.items():
 159             if i in elwidths:
 160                 bitpos = plist.index(p)
 161                 bitp[i] |= 1 << bitpos
 162     # fourth stage: determine which partitions are 100% unused.
 163     # these can then be "blanked out"
 164     bmask = (1 << len(plist))-1
 165     for p in bitp.values():
 166         bmask &= ~p
 167     return (PartitionPoints(points), bitp, bmask, width, lane_shapes,
 168             part_wid, part_count)
 169
 170
 171 if __name__ == '__main__':
 172
 173     # for each element-width (elwidth 0-3) the number of Vector Elements is:
 174     # elwidth=0b00 QTY 1 partitions:   |          ?          |
 175     # elwidth=0b01 QTY 1 partitions:   |          ?          |
 176     # elwidth=0b10 QTY 2 partitions:   |    ?     |     ?    |
 177     # elwidth=0b11 QTY 4 partitions:   | ?  |  ?  |  ?  | ?  |
 178     # actual widths of Signals *within* those partitions is given separately
 179     vec_el_counts = {
 180         0: 1,
 181         1: 1,
 182         2: 2,
 183         3: 4,
 184     }
 185
 186     # width=3 indicates "same width Vector Elements (3) at all elwidths"
 187     # elwidth=0b00 1x 5-bit     |  unused xx      ..3 |
 188     # elwidth=0b01 1x 6-bit     |  unused xx      ..3 |
 189     # elwidth=0b10 2x 12-bit    | xxx  ..3 | xxx  ..3 |
 190     # elwidth=0b11 3x 24-bit    | ..3| ..3 | ..3 |..3 |
 191     # expected partitions      (^)   |     |     |   (^)
 192     # to be at these points:   (|)   |     |     |    |
 193     width_in_all_parts = 3
 194
 195     for i in range(4):
 196         pprint((i, layout(i, True, vec_el_counts, width_in_all_parts)))
 197
 198     # fixed_width=32 and no lane_widths says "allocate maximum"
 199     # i.e. Vector Element Widths are auto-allocated
 200     # elwidth=0b00 1x 32-bit    | .................32 |
 201     # elwidth=0b01 1x 32-bit    | .................32 |
 202     # elwidth=0b10 2x 12-bit    | ......16 | ......16 |
 203     # elwidth=0b11 3x 24-bit    | ..8| ..8 | ..8 |..8 |
 204     # expected partitions      (^)   |     |     |   (^)
 205     # to be at these points:   (|)   |     |     |    |
 206
 207     # TODO, fix this so that it is correct
 208     #print ("maximum allocation from fixed_width=32")
 209     # for i in range(4):
 210     #    pprint((i, layout(i, True, vec_el_counts, fixed_width=32)))
 211
 212     # specify that the Vector Element lengths are to be *different* at
 213     # each of the elwidths.
 214     # combined with vec_el_counts we have:
 215     # elwidth=0b00 1x 5-bit     | <--  unused               -->....5 |
 216     # elwidth=0b01 1x 6-bit     | <--  unused              -->.....6 |
 217     # elwidth=0b10 2x 12-bit    | unused   .....6 | unused    .....6 |
 218     # elwidth=0b11 3x 24-bit    | .....6 | .....6 |  .....6 | .....6 |
 219     # expected partitions      (^)       ^        ^         ^^      (^)
 220     # to be at these points:   (|)       |        |         ||      (|)
 221     #                          (24)     18       12         65      (0)
 222     widths_at_elwidth = {
 223         0: 5,
 224         1: 6,
 225         2: 6,
 226         3: 6
 227     }
 228
 229     print ("5,6,6,6 elements", widths_at_elwidth)
 230     for i in range(4):
 231         pp, bitp, bm, b, c, d, e = \
 232                     layout(i, False, vec_el_counts, widths_at_elwidth)
 233         pprint((i, (pp, bitp, bm, b, c, d, e)))
 234     # now check that the expected partition points occur
 235     print("5,6,6,6 ppt keys", pp.keys())
 236     assert list(pp.keys()) == [5,6,12,18]
 237
 238
 239     # this tests elwidth as an actual Signal. layout is allowed to
 240     # determine arbitrarily the overall length
 241     # https://bugs.libre-soc.org/show_bug.cgi?id=713#c30
 242
 243     elwid = Signal(2)
 244     pp, bitp, bm, b, c, d, e = layout(
 245         elwid, False, vec_el_counts, widths_at_elwidth)
 246     pprint((pp, b, c, d, e))
 247     for k, v in bitp.items():
 248         print("bitp elwidth=%d" % k, bin(v))
 249     print("bmask", bin(bm))
 250
 251     m = Module()
 252
 253     def process():
 254         for i in range(4):
 255             yield elwid.eq(i)
 256             yield Settle()
 257             ppt = []
 258             for pval in list(pp.values()):
 259                 val = yield pval  # get nmigen to evaluate pp
 260                 ppt.append(val)
 261             pprint((i, (ppt, b, c, d, e)))
 262             # check the results against bitp static-expected partition points
 263             # https://bugs.libre-soc.org/show_bug.cgi?id=713#c47
 264             # https://stackoverflow.com/a/27165694
 265             ival = int(''.join(map(str, ppt[::-1])), 2)
 266             assert ival == bitp[i]
 267
 268     sim = Simulator(m)
 269     sim.add_process(process)
 270     sim.run()
 271
 272     # this tests elwidth as an actual Signal. layout is *not* allowed to
 273     # determine arbitrarily the overall length, it is fixed to 64
 274     # https://bugs.libre-soc.org/show_bug.cgi?id=713#c22
 275
 276     elwid = Signal(2)
 277     pp, bitp, bm, b, c, d, e = layout(elwid, False, vec_el_counts,
 278                                       widths_at_elwidth,
 279                                       fixed_width=64)
 280     pprint((pp, b, c, d, e))
 281     for k, v in bitp.items():
 282         print("bitp elwidth=%d" % k, bin(v))
 283     print("bmask", bin(bm))
 284
 285     m = Module()
 286
 287     def process():
 288         for i in range(4):
 289             yield elwid.eq(i)
 290             yield Settle()
 291             ppt = []
 292             for pval in list(pp.values()):
 293                 val = yield pval  # get nmigen to evaluate pp
 294                 ppt.append(val)
 295             print("test elwidth=%d" % i)
 296             pprint((i, (ppt, b, c, d, e)))
 297             # check the results against bitp static-expected partition points
 298             # https://bugs.libre-soc.org/show_bug.cgi?id=713#c47
 299             # https://stackoverflow.com/a/27165694
 300             ival = int(''.join(map(str, ppt[::-1])), 2)
 301             assert ival == bitp[i], "ival %s actual %s" % (bin(ival),
 302                                                            bin(bitp[i]))
 303
 304     sim = Simulator(m)
 305     sim.add_process(process)
 306     sim.run()