A ternary MAC
You will learn
How a dot product with ternary weights becomes adds, subtracts and skips.
A multiply-accumulate unit adds input times weight, clock after clock. With weights of -1, 0 and +1 each clock is an add, a subtract or nothing: the widget's nine clocks make 4 adds, 2 subtracts and 3 skips and land on -8, with no multiplier. The lesson spec, ternary_mac.t27, is the hardware version: a 27-trit dot product over packed vectors, 2 bits per trit.
Try it
Press weights until the accumulator lands on 0, then on the largest value you can reach.
Nine inputs, nine weights of -1, 0 or +1. Each clock the accumulator adds, subtracts or does nothing. Press a weight to change it.
specs/ternary/ternary_mac.t27
module TernaryMac;
// Sign-only ternary multiply of two packed trits {N=0b00, Z=0b01, P=0b10}.
fn tmul(ta: u8, tb: u8) -> i8 {
if (ta == 1) { return 0; }
if (tb == 1) { return 0; }
if (ta == tb) { return 1; }
return -1;
}
// One trit position i of two 54-bit packed vectors (trit i at [2i+1:2i]).
fn tp(a: u64, b: u64, i: u32) -> i8 {
return tmul(((a >> (i << 1)) & 3) as u8, ((b >> (i << 1)) & 3) as u8);
}
// 27-trit ternary dot product, loop-free (gen-verilog cannot yet lower a
// local-declaring while loop -- see #1741). Result in [-27, +27].
pub fn dot27(a: u64, b: u64) -> i8 {
return tp(a,b,0) + tp(a,b,1) + tp(a,b,2) + tp(a,b,3) + tp(a,b,4)
+ tp(a,b,5) + tp(a,b,6) + tp(a,b,7) + tp(a,b,8) + tp(a,b,9)
+ tp(a,b,10) + tp(a,b,11) + tp(a,b,12) + tp(a,b,13) + tp(a,b,14)
+ tp(a,b,15) + tp(a,b,16) + tp(a,b,17) + tp(a,b,18) + tp(a,b,19)
+ tp(a,b,20) + tp(a,b,21) + tp(a,b,22) + tp(a,b,23) + tp(a,b,24)
+ tp(a,b,25) + tp(a,b,26);
}
test dot_all_n_x_all_n { assert_eq(dot27(0, 0), 27); }
test dot_all_n_x_all_p { assert_eq(dot27(0, 12009599006321322), -27); }
test dot_all_p_x_all_p { assert_eq(dot27(12009599006321322, 12009599006321322), 27); }
test dot_all_z { assert_eq(dot27(6004799503160661, 6004799503160661), 0); }
// W697: the hardware boundary, derived from the CALL GRAPH.
//
// This spec has several functions that take a parameter and return a value,
// so W696's count rule left it AMBIGUOUS. But exactly ONE of them is called
// by no other function -- it is the root, and every other candidate is a
// helper it reaches. With one root the choice is forced by structure rather
// than by count, and forwarding to it still invents nothing.
//
// The call graph is built from FUNCTION BODIES ONLY. Counting `test` blocks
// as callers makes the rule vacuous -- every function is called by its own
// test, so nothing is ever a root.
//
// Measured: the rule resolved 14 of 136 ambiguous specs, 6 of them with
// types that can cross a module boundary. It is narrow because most of the
// rest are libraries of INDEPENDENT functions, which have several roots and
// correctly stay ambiguous.
fn on_comb(a: u64, b: u64) -> i8 { return dot27(a, b); }
endmodule
All lessons
Module 1 · Three values
Why three, how balanced ternary writes every number without a sign, and what flipping and cutting trits do.
Module 2 · Logic with unknown
Kleene's three-valued gates, two gates binary has no twin for, and addition as a pair of tables.
Module 3 · Adding trits
The half adder, the full adder and a carry that ripples left, one place at a time.
Module 4 · Multiplying without a multiplier
Copy, drop or flip: a product by one trit, long multiplication, and a MAC that only adds.
Module 5 · Trits in binary memory
Two bits per trit, five trits per byte, and the bits a 27-trit word needs.
Module 6 · The TRI-27 instruction word
The 32-bit word the Trinity emulator decodes: its fields, its 47 opcodes and its 15-bit immediate.
Module 7 · A ternary machine
An ALU built from this course's adders, a three-way jump, and a program you can step.
Module 8 · Three answers
Compare at the highest differing trit, find a number in thirds, sort with three-way compares.
Module 9 · Ternary neurons
Weights of -1, 0, +1: one neuron, a detector and a small layer, with no multiplier anywhere.