betaFeedback

WorksComputer Science

MAC units for a 2x2 int8 systolic array on Tiny Tapeout

Abstract

We take the multiply-accumulate (MAC) unit of an open-source 2×\times2 int8 systolic array taped out on Tiny Tapeout (GF180 process) and propose two replacements. The first one, hybrid, uses a different arithmetic structure for each row of the array. It reduces the logic area of one MAC unit by 4–6% and of the whole chip by 0.7–3.2% after place and route. The second one, fused_eq, never builds the long carry chain of the accumulation. It shortens the critical path by 20% for one MAC unit and by 14% for the whole chip. All numbers come from the standard Tiny Tapeout flow (LibreLane) run in GitHub Actions. Correctness is checked by exhaustive simulation of all 2242^{24} inputs, a formal equivalence proof, and the original test bench.

Introduction

Tiny Tapeout [1] lets many people put small designs on one shared chip. Each design gets one or more tiles. A tile is a fixed piece of silicon. On the GF180 process [2] one tile is about 347×161347 \times161 μ\mum. Area is the main cost, so compact arithmetic blocks are useful for this community.

As a test case we use tt_um_essen, a 2×22 \times2 systolic array for int8 matrix multiplication [3]. It was taped out on a Tiny Tapeout GF180 shuttle. A systolic array [4] is a grid of identical units. Data move from unit to unit at each clock cycle, so each value is reused many times. Each unit of this array is a multiply–accumulate (MAC) unit: it multiplies two numbers and adds the result to a value from its neighbour.

We optimize the MAC unit for area or for speed. The function and the design stay the same as it is in the standard Tiny Tapeout flow with its default tools and settings. Only the arithmetic inside the unit changes. We describe two proposed architectures and compare them with the original on the real flow. We share the Verilog files of both units and all files needed to rerun the flow.

The original design

The array

Figure 1 represents the array, where input values ii move to the right, weights ww are stored inside the units, partial sums move down, the units in the top row get 0 from above, the bottom row gives the results.

2×2 systolic array of MAC units, with inputs $i_0$, $i_1$, weights $w_{00}$, $w_{10}$, $w_{01}$, $w_{11}$, and outputs $r_0$, $r_1$

Figure 1. The 2×2 systolic array of tt_um_essen. The top row always gets 0 from above.

All numbers in the array are int8: signed integers of 8 bits. They are stored in two’s complement, the usual way to store negative numbers in hardware. The rule is simple. Read the 8 bits as an ordinary binary number from 0 to 255. If the top bit (bit 7) is 0, this is the value. If the top bit is 1, subtract 256. So the top bit is the sign, and the range is from −128 to 127. Table 1 gives examples.

8 bitsas an unsigned numberint8 value
0000010155
01111111127127 (the largest)
10000000128128−256=−128128 - 256 = -128 (the smallest)
11111101253253−256=−3253 - 256 = -3
11111111255255−256=−1255 - 256 = -1

Table 1. How 8 bits are read as an int8 number.

Each unit computes

r=clamp⁡(a⋅w+c),clamp⁡(x)=min⁡(127,max⁡(−128,x)),(1)r = \operatorname{clamp}(a \cdot w + c), \qquad\operatorname{clamp}(x) = \min(127,\max(-128,x)), \tag*{(1)}

where aa is the input, ww the weight, cc the value from above and rr the result. All four numbers aa, ww, cc, rr are int8. The function clamp is saturation: a value that does not fit in int8 becomes the nearest limit. There are three examples:

  • a=10a = 10, w=10w = 10, c=20c = 20: 100+20=120100 + 20 = 120. It fits, so r=120r = 120.

  • a=10a = 10, w=10w = 10, c=50c = 50: 100+50=150>127100 + 50 = 150 > 127, so r=127r = 127.

  • a=−100a = -100, w=2w = 2, c=0c = 0: −200<−128-200 < -128, so r=−128r = -128.

The product a⋅wa \cdot w needs 16 bits, so without saturation the data width would grow at each step.

The MAC unit

Fig. 2 shows the original unit with three registers which hold aa, ww and cc. The product is computed by a radix-4 Booth multiplier [5, 6]. Booth encoding looks at the bits of ww in groups of three. Each group selects 00, ±a\pm a or ±2a\pm2a, so an 8-bit multiplier needs only four partial products (shifted rows to be added) instead of eight. Hence an adder tree sums the four rows into a 16-bit product pp.

Then a 16-bit adder computes p+cp + c, with cc sign-extended to 16 bits. Finally, the saturation logic checks the upper bits of the sum. If bits 15 to 7 are all equal, the sum fits in 8 bits. Otherwise the result is 127 or −128-128. The whole unit works in one clock cycle. The chip was signed off at 50 MHz.

Proposed units

bits of the product are enough

The value cc is between −128-128 and 127. If p≥256p \ge256, then p+c≥128p + c \ge128 and the result is 127 for any cc. In the same way, if p≤−257p \le-257, the result is −128-128 for any cc. So we can replace pp by

p9=min⁡(255,max⁡(−256,p)),(2)p_9 = \min(255, \max(-256, p)), \tag*{(2)}
The original MAC unit

Figure 2. The original MAC unit. The product and the accumulation use two separate carry-propagate adders in series.

which fits in 9 bits, and still get exactly clamp⁡(p9+c)=clamp⁡(p+c)\operatorname{clamp}(p_{9} + c) = \operatorname{clamp}(p + c). We checked this for all 2242^{24} triples (a,w,c)(a, w, c). A flag big tells that pp does not fit in 9 bits (bits 15 to 8 of pp are not all equal). Then the result is chosen by the sign of pp. In parallel, a short 10-bit adder computes p[8:0]+cp_{[8:0]} + c. We call this structure presat.

hybrid: a different structure for each row

The two units that get 0 from above form the top row: MAC (0,0) and MAC (1,0) in Figure 1. For them c=0c = 0 always. All other units get cc from the unit above, so cc can be any int8 value. In the 2×22 \times2 array these are the two units of the bottom row, in a larger array they would be all rows except the first.

Synthesis tools recognize the constant c=0c = 0 and remove the parts of the circuit that add cc. So a top-row unit is much smaller: 9 562 μm2\mu\mathrm{m}^{2} against 12 697 μm2\mu\mathrm{m}^{2} for the original (Table 2). For the same reason the structure that is best for one row is not the best for the other:

Structuretop row, c=0c = 0other rows, any cc
original9 56212 697
presat9 349 (−2.2%)12 539 (−1.2%)
tree9 687 (+1.3%)12 078 (−4.9%)

Table 2. Synthesis area of one MAC unit in μm2\mu\mathrm{m}^{2}. No structure is the best in both columns, which is why hybrid uses two of them.

  • top row (c=0c = 0): presat gives 9 349 μm2\mu\mathrm{m}^{2}, 2.2% less than the original. tree (described below) gives 9 687 μm2\mu\mathrm{m}^{2}, 1.3% more;

  • other rows (any cc): tree gives 12 078 μm2\mu\mathrm{m}^{2}, 4.9% less. presat gives 12 539 μm2\mu\mathrm{m}^{2}, only 1.2% less.

So hybrid uses presat for the top row and tree for the other rows.

In tree (Figure 3, bottom) the four Booth rows and cc are written as one sum with several terms. Yosys [7] then builds one adder tree for the whole a⋅w+ca \cdot w + c, without a separate adder for cc. To add an 8-bit signed cc to a 16-bit sum, cc must first be sign-extended: its top bit is copied into bits 8 to 15. For example, −3=11111101-3 = 11111101 becomes 11111111111111011111111111111101. These eight copies are extra inputs of the adder tree. A standard trick removes them:

Hybrid MAC unit diagram

Figure 3. The hybrid MAC unit. Orange blocks are new. c′c' is cc with the top bit inverted, Eq. (3). Both structures compute Eq. (1) for any input.

c=c′−128,c′=c⊕0x80.(3)c = c^{\prime} - 128,\qquad c^{\prime} = c \oplus0\mathrm{x}80. \tag*{(3)}

Here 0x80 is the number 80 written in hexadecimal (base 16), that is 8⋅16=1288 \cdot16 = 128, or 10000000 in binary. The sign ⊕\oplus is bitwise XOR: a bit XOR 1 is inverted, a bit XOR 0 stays the same. So c′c^{\prime} is cc with only the top bit inverted. We read c′c^{\prime} as an unsigned number from 0 to 255. Two examples:

  • c=−3=11111101c = -3 = 11111101. Then c′=01111101=125c^{\prime} = 01111101 = 125, and 125−128=−3125 - 128 = -3.

  • c=5=00000101c = 5 = 00000101. Then c′=10000101=133c^{\prime} = 10000101 = 133, and 133−128=5133 - 128 = 5.

c′c' is unsigned, so its bits 8 to 15 are 0 and it takes only 8 bits in the tree. The term −128-128 is a constant. A constant costs almost nothing, because the tools simplify every adder input that is always 0 or always 1. So the tree gets an 8-bit row instead of a 16-bit row.

The hybrid unit has a parameter TOP_ROW. If it is 1, the unit uses presat; otherwise it uses tree. Both structures are correct for any input, so each setting is bit-exact on its own. The only change outside the unit is one line in the array file mac.v: mac_unit #(.W(W), .TOP_ROW(y == 0)).

fused_eq: no long carry chain

The critical path of the original unit goes through two carry-propagate adders in series: the last adder of the multiplier and the 16-bit accumulation adder. A carry may have to propagate through all 16 bits of each of them.

In fused_eq (Figure 4) cc is added as one more row of the multiplier. Three levels of 3:2 compressors (full adders that turn three rows into two without carry propagation [8]) reduce the six rows to two numbers XX and YY with X+Y=a⋅w+cX+Y=a\cdot w+c modulo 2162^{16}. The long sum X+YX+Y is never computed, instead of this:

Block diagram of the fused_eq MAC unit

Figure 4. The fused_eq MAC unit. The three orange blocks on the right work in parallel.

  • an 8-bit adder gives the low 8 bits of the result and the carry into bit 7;

  • a check responses if bits 15 to 7 of X+YX+Y are all 0 or all 1, that is, if the sum fits in int8. For bit kk of a sum S=X+YS=X+Y we have Sk=Xk⊕Yk⊕CkS_k=X_k\mathbin{\oplus}Y_k\mathbin{\oplus}C_k, where CkC_k is the carry into bit kk. If all bits of SS must be 0, then the needed carry is Ck+1=Xk∨YkC_{k+1}=X_k\mathbin{\lor}Y_k; if all bits must be 1, then Ck+1=Xk∧YkC_{k+1}=X_k\mathbin{\land}Y_k. So each bit can be checked on its own, in parallel, with no carry chain;

  • the direction of overflow is the sign of the product. It is known early from the signs of aa and ww and from a zero check.

A multiplexer then selects the 8-bit sum, 127 or −128-128.

The difference

The original unit has a debug register that can be read through JTAG. Address 3 returns the upper byte of the 16-bit sum. The new units never build this sum, so address 3 returns the saturation flags instead. Addresses 0 to 2 and all computed results are the same.

Measurements

Flow and settings

We use the flow Tiny Tapeout uses (Table 3): the tt-support-tools scripts [9] and LibreLane [10]. LibreLane runs synthesis with Yosys and ABC [7, 11], then floorplan, placement, clock tree, routing and static timing analysis (STA) with OpenROAD [12]. STA computes the delay of every path with the real wires. All settings are the default Tiny Tapeout settings for GF180 at 3.3 V. Only the clock period changes between runs. All runs are done in GitHub Actions, a GitHub service that runs scripts on its own virtual machines.

ItemVersion
Original designEssenceia/Systolic_MAC_with_DFT, commit 6a3c04e
Tiny Tapeout toolstt-support-tools, commit 01d5d28
FlowLibreLane 3.0.14 (in its Docker image)
ProcessGF180MCU D, cell library gf180mcu_fd_sc_mcu7t5v0, 3.3 V
ComputersGitHub Actions virtual machines, Ubuntu 24.04

Table 3. Fixed versions. All variants, including the original, use the same versions.

Two levels

  • One unit. A small wrapper puts one MAC unit on a 1×11 \times1 tile. The timed path is the same as in the chip: input registers, multiplier, adder, saturation, output register. Little else is on the tile, so the difference between variants is the difference of the arithmetic.

  • Whole chip. The full tt_um_essen project on its 2 tiles, with only mac_unit.v replaced (and one line of mac.v for hybrid). This shows the real effect on the project.

Each level runs at clock periods of 40, 30 and 20 ns (20 ns is 50 MHz).

Metrics

  • Logic area: the sum of the areas of all cells after routing (gates, flip-flops, buffers), without fill, tap, end-cap, decap and antenna cells. These cells only fill empty space and depend on the tile, not on the design.

  • Synthesis area: the cell area right after synthesis, before the tools add buffers and resize cells for timing.

  • Critical path: clock period minus the worst setup slack. Slack is the time left before the end of the clock cycle. We report the typical corner (25 °C, 3.3 V). A corner is a set of process, voltage and temperature conditions. Tiny Tapeout signs off designs at this corner.

Correctness

Every variant passed all three checks below before any area or timing run. The checks test different things.

  1. Exhaustive simulation with Icarus Verilog [13]. It tests the arithmetic of one MAC unit. All 2242^{24} combinations of (a,w,c)(a,w,c) are applied. The original and all variants run side by side and must give the same rr. The original is also compared with Eq. (1) computed directly.

  1. Formal equivalence with Yosys (equiv_make, equiv_simple, equiv_induct). This is a proof, not a test: it uses no input values. The registers have the same names in both designs. The tool proves that the logic between them gives the same outputs for every possible register value. JTAG address 3 is excluded (§ 3.4).

  1. The original test bench: the 7 cocotb [14] tests of the original project. They test the unit inside the whole chip: the control logic, the data flow between the four units and JTAG. For hybrid they also test the changed mac.v.

Checks 1 and 2 overlap on purpose. Two different tools give the same answer, so an error in one tool is unlikely to hide a bug. For hybrid, both are done with both values of TOP_ROW.

Repeatability

The flow is deterministic and two separate sweeps gave identical results. On the other hand, the result of synthesis is sensitive to the structure of the input. Swapping two always blocks in the original code, which does not change the circuit, moved the synthesis area of the whole chip by 0.6%. So we do not treat differences below about 1% on the whole chip as real.

Results

Table 4 gives the logic area and Table 5 the critical path. Figure 5 shows both.

LevelVariant40 ns30 ns20 nssynthesis
One unitoriginal16 17017 22117 10512 697
hybrid15 204 (−6.0%)16 378 (−4.9%)16 381 (−4.2%)12 078 (−4.9%)
fused_eq16 695 (+3.2%)16 539 (−4.0%)18 042 (+5.5%)13 351 (+5.2%)
Whole chiporiginal68 12471 21071 08954 022
hybrid67 656 (−0.7%)68 940 (−3.2%)68 839 (−3.2%)53 330 (−1.3%)
fused_eq73 860 (+8.4%)74 400 (+4.5%)78 863 (+10.9%)57 927 (+7.2%)

Table 4. Logic area in μm2\mu\mathrm{m}^{2} after place and route at three clock periods, and after synthesis. On the one-unit level hybrid is the same as tree.

Leveloriginalhybridfused_eq
One unit18.2 ns18.4 ns14.5 ns (−20%)
Whole chip18.3 ns19.1 ns15.8 ns (−14%)

Table 5. Critical path at the typical corner, 20 ns run. All variants meet 50 MHz. Only fused_eq meets 15 ns (66 MHz) on the one-unit level; the original reaches 55 MHz.

Area change against the original and critical path

Figure 5. Area change against the original (left, middle) and critical path (right).

In short:

  • hybrid is the smaller unit: −4 to −6% of logic area for one unit, −0.7 to −3.2% for the whole chip. Its critical path is about the same as the original;

  • fused_eq is the faster unit: the critical path is 20% shorter for one unit and 14% shorter for the whole chip. It costs 4.5% to 11% more area for the whole chip; for one unit the change is from −4% to +5.5%.

Why the area gain is small

  1. The baseline is good. The original uses a hand-written radix-4 Booth multiplier, and for 8 bits Yosys and ABC are already close to the optimum.

  1. Arithmetic is less than half of the chip. We replaced the arithmetic of the four MAC units with a stub that keeps all registers. The synthesis area of the chip dropped from 54 k μm254\ \mathrm{k}\,\mu\mathrm{m}^{2} to 30 k μm230\ \mathrm{k}\,\mu\mathrm{m}^{2}. So the arithmetic is about 45% of the chip. The rest is flip-flops, the JTAG and design-for-test logic, and control.

  1. Half of the units are already simplified. The top row gets a constant 0, and the tools remove most of the addition there by themselves.

  1. The tile count does not depend on the arithmetic. One tile is about 55.7 k μm255.7\ \mathrm{k}\,\mu\mathrm{m}^{2}, but cells can fill only about 60–70% of it; the rest is for wires and power. The flow reports 67% fill for the original chip on 2 tiles, so one tile holds about 34 k μm234\ \mathrm{k}\,\mu\mathrm{m}^{2} of cells. The chip has about 68 k μm268\ \mathrm{k}\,\mu\mathrm{m}^{2}. Even with no MAC arithmetic at all it would have about 37 k μm237\ \mathrm{k}\,\mu\mathrm{m}^{2}, still more than one tile.

For larger arrays and wider number formats the arithmetic becomes the main part of the chip, the top row is a smaller share of the units, and the gain of one unit turns into the gain of the chip.

Slow corner. At the slow corner (125 ∘C125\,^\circ\mathrm{C}, 3.0 V) no variant, including the original, meets its clock period in any run. The critical path there is 29–46 ns: the shorter the clock period, the harder the tools work and the shorter this path becomes. It does not affect the comparison, since all variants are measured the same way. It means that the place-and-route tools always try to repair this corner, and this makes the post-route area vary from one clock period to another. The synthesis area is free of this effect.

Reproducing and reusing the setup

All files are at https://github.com/ZeboZebo702/tt_matmul_2x2_int8. Table 6 lists the main folders and files.

Folder or fileWhat it does
variants/One file mac_unit_<name>.v per variant.
variants/extra/Other changed files of a variant (for hybrid: mac.v).
bench_single/A small wrapper that puts one MAC unit on a 1×11 \times1 tile.
verify/Test benches and the formal proof script (§ 4.4).
scripts/verify.shRuns all correctness checks.
scripts/prepare.shBuilds one project: the original design + one variant + one clock period.
scripts/run_one.shRuns prepare.sh, then the LibreLane flow, then collects the numbers of this run.
scripts/report.pyMakes the tables, a CSV file and the charts from all runs.
scripts/synth_local.pyRuns only the synthesis step of LibreLane, without Docker.
.github/workflows/sweep.yamlThe experiment on GitHub: all chosen levels, variants and clock periods.
.github/workflows/checks.yamlThe correctness checks on GitHub.
versions.envThe fixed versions of Table 3.

Table 6. Main folders and files of the repository.

To repeat the study:

  1. fork the repository, that is, make your own copy of it on GitHub;

  2. in the Actions tab, start the sweep workflow. Choose the levels, the variants and the clock periods;

  1. GitHub runs one job for each point (level, variant, clock period). The job downloads the original design at the fixed commit, puts in the variant, sets the clock period and runs the Tiny Tapeout hardening, the full flow from Verilog to layout;

  1. a last job collects all results into tables, a CSV file and charts.

To test a new block, put a new mac_unit_<name>.v in variants/ and add its name to the list of variants. For any other Tiny Tapeout project, change the repository and commit in versions.env and the file that is replaced in prepare.sh.

For quick experiments, synth_local.py runs only the synthesis step of LibreLane, with the same script and settings, in a few seconds. Its synthesis area matches the full flow within 0.1 μm20.1\,\mu\mathrm{m}^{2} on the one-unit level.

Conclusion

Two drop-in MAC units for the tt_um_essen systolic array give the same results as the original. hybrid makes one unit 4–6% smaller and the whole chip up to 3.2% smaller. fused_eq makes the critical path 14–20% shorter. For this design the gain in area is limited by the design itself: an 8-bit Booth multiplier that is already tight, and a chip where arithmetic is less than half of the area. The measurement setup is open and can be reused to compare any arithmetic block on the real Tiny Tapeout flow.

References

  1. [1]Tiny Tapeout. https://tinytapeout.com.
  2. [2]GF180MCU open source PDK. https://github.com/google/gf180mcu-pdk.
  3. [3]J. Desmazes. Systolic_MAC_with_DFT: GF180 ASIC tapeout of a 2x2 MAC with DFT infrastructure. https://github.com/Essenceia/Systolic_MAC_with_DFT.
  4. [4]H. T. Kung and C. E. Leiserson. Systolic arrays (for VLSI). In Sparse Matrix Proceedings, pages 256–282, 1978.
  5. [5]A. D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, 4(2):236–240, 1951.DOI
  6. [6]B. Parhami. Computer Arithmetic: Algorithms and Hardware Designs. Oxford University Press, 2nd edition, 2010.
  7. [7]Yosys Open SYnthesis Suite. https://yosysHQ.net/yosys/.
  8. [8]C. S. Wallace. A suggestion for a fast multiplier. IEEE Transactions on Electronic Computers, EC-13(1):14–17, 1964.DOI
  9. [9]Tiny Tapeout. tt-support-tools. https://github.com/TinyTapeout/tt-support-tools.
  10. [10]LibreLane: an ASIC implementation flow. https://librelane.org. Version 3.0.14.
  11. [11]R. Brayton and A. Mishchenko. ABC: An academic industrial-strength verification tool. In Computer Aided Verification (CAV), pages 24–40, 2010.DOI
  12. [12]OpenROAD: Toward a self-driving, open-source digital layout implementation tool chain. In Proc. GOMACTech, 2019.
  13. [13]Icarus Verilog. https://steveicarus.github.io/iverilog/.
  14. [14]cocotb: a coroutine based cosimulation library for writing VHDL and Verilog testbenches in Python. https://www.cocotb.org.

Paper details

vlnc:W_w99zszcs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents