Datapath.xtl

1⍝# Datapath: the vector examples at a stated width: the whole-array operations a circuit realizes directly
2⍝# Import it with an alias of your choice: "dp:" u_se< "Datapath".
3⍝# Put libs/Datapath/src on XETAL_PATH ("just path"); the reference is libs/Datapath/docs.
4⍝# Names with l: are exported; the others are private to this file.
5⍝#
6⍝# Each function here is one whole-array expression a circuit can take
7⍝# on directly: arithmetic and comparisons item by item with scalar
8⍝# extension (one unit per element, or one unit and a counter), a
9⍝# select by mask (a mux), and reductions (a tree of adders). The
10⍝# arithmetic is Fixed's (a wrap at every unit), so every result is what w-bit units give, and
11⍝# the X_eTaL evaluator is the reference the generated circuit must
12⍝# match bit for bit (the demos are the programs it checks). The width
13⍝# comes first; a function of three or four arguments is used curried,
14⍝# the width bound once: u:v_add := dp:v_add 16, then x u:v_add y.
15ᶠˣ⁼u̲se< "Fixed"
16
17⍝## Elementwise: one unit per element
18
19⍝# w v_add x y: the sum, item by item, wrapped to w bits (eight 16-bit
20⍝# numbers: eight 16-bit adders).
21⍝# >> "dp:" u_se< "Datapath"
22⍝# >> u:v_add := dp:v_add 16
23⍝# >> 30000 u:v_add 30000 -30000
24⍝# -5536 0
25ˡv̲add ← { w x y → w ᶠˣw̲rap x + y }
26
27⍝# w s_axpy a x y: a times x plus y, wrapped at each unit (a multiplier
28⍝# and an adder per element); bind w and a: u:s_axpy := 16 dp:s_axpy 3.
29⍝# >> "dp:" u_se< "Datapath"
30⍝# >> u:s_axpy := 16 dp:s_axpy 3
31⍝# >> 1 2 3 4 u:s_axpy 100 200 300 400
32⍝# 103 206 309 412
33ˡs̲axpy ← { w a x y → w ᶠˣw̲rap y + w ᶠˣw̲rap a × x }
34
35⍝# r_elu x: x where positive, 0 elsewhere (a comparator and a mux).
36⍝# >> "dp:" u_se< "Datapath"
37⍝# >> dp:r_elu 1 -2 3 -4
38⍝# 1 0 3 0
39ˡr̲elu ← { x → x m̲ax 0 }
40
41⍝## Masks and select: a mux
42
43⍝# t t_hreshold x: x where x > t, 0 elsewhere: the mask x > t is the
44⍝# mux's select line.
45⍝# >> "dp:" u_se< "Datapath"
46⍝# >> 2 dp:t_hreshold 1 2 3 4
47⍝# 0 0 3 4
48ˡt̲hreshold ← { t x → x × x > t }
49
50⍝# m k_eep x: x where the mask m is 1, 0 elsewhere.
51⍝# >> "dp:" u_se< "Datapath"
52⍝# >> (1 0 1 0) dp:k_eep 5 6 7 8
53⍝# 5 0 7 0
54ˡk̲eep ← { m x → x × m }
55
56⍝## Reductions: a tree of adders
57
58⍝# w s_um x: the sum of a vector as a balanced tree of w-bit adders:
59⍝# the first half added to the second half, item by item, then that
60⍝# vector likewise, down to one number (a loop over the log2 n levels
61⍝# of the tree; an odd length is padded with a 0). Wrapping at every
62⍝# adder gives the same bits as wrapping the exact sum once (checked in
63⍝# tests/checks.xtl).
64⍝# >> "dp:" u_se< "Datapath"
65⍝# >> 16 dp:s_um 20000 20000 20000 20000
66⍝# 14464
67ˡs̲um ← { w x →
68  levels ← '+ r̲/ (2 ^ o̲ffsets 63) < t̲ally x
69  f̲irst levels '{ v → w ʰh̲alve v } p̲ower x
70}
71
72⍝# One level of the tree: the first half added to the second (after a
73⍝# 0 pads an odd length).
74ʰh̲alve ← { w v →
75  e ← v c̲at ((t̲ally v) m̲od 2) r̲eshape 0
76  h ← (t̲ally e) d̲iv 2
77  w ᶠˣw̲rap (h t̲ake e) + h d̲rop e
78}
79
80⍝# l_argest x: the largest item (a tree of comparators and muxes).
81⍝# >> "dp:" u_se< "Datapath"
82⍝# >> dp:l_argest 3 9 2
83⍝# 9
84ˡl̲argest ← { x → 'm̲ax r̲/ x }
85
86⍝# w d_ot x y: the inner product, a multiplier per element then the
87⍝# tree.
88⍝# >> "dp:" u_se< "Datapath"
89⍝# >> u:d_ot := dp:d_ot 16
90⍝# >> 1 2 3 u:d_ot 4 5 6
91⍝# 32
92ˡd̲ot ← { w x y → w ˡs̲um w ᶠˣw̲rap x × y }
93
94⍝## The acceptance pipeline
95
96⍝# w p_ipeline x k: multiply, add, select, reduce in one expression,
97⍝# the sum of the positive items of x + x * k, every unit w bits: the
98⍝# first end-to-end test research7 asks for (arithmetic, map, zip,
99⍝# comparison, selection, reduction).
100⍝# >> "dp:" u_se< "Datapath"
101⍝# >> u:p_ipeline := dp:p_ipeline 16
102⍝# >> 1 2 3 4 u:p_ipeline 1 -2 1 -2
103⍝# 8
104ˡp̲ipeline ← { w x k → w ˡs̲um ˡr̲elu w ᶠˣw̲rap x + w ᶠˣw̲rap x × k }