For posterity, the lowest cycle count I am aware of is 133.
The first optimization is to only pass inputs in one direction left-to-right or right-to-left. Your current approach has left and right sides exchange values with each other. Because this exchange cannot happen simultaneously, each side ends up spending a lot of cycles waiting for the other side. Look at the breakdown below:
Cy Top Left Top Right
0: MOV UP, ACC MOV UP, ACC
1: SAV SAV
2: MOV ACC, RIGHT
3: #(WRITE) SUB LEFT
4: SWP MOV ACC, DOWN
5: #(WRITE)
6: SWP
7: MOV ACC, LEFT
8: SUB RIGHT #(WRITE)
9: MOV ACC, DOWN MOV UP, ACC
10: #(WRITE) SAV
11: MOV UP, ACC
12: SAV
13: MOV ACC, RIGHT
14: #(WRITE) SUB LEFT
Each line is one cycle. Lines that are blank mean the node is stalled waiting for input from the node on the other side. As you can see, each side spends at least 3 cycles just waiting for input. The total length of the loop is 11 cycles (compare lines 3 and 14).
The first optimization, as mentioned in the other answers, is to avoid this double exchange of values by using a negation for the other side's output.
Cy Top Left Top Right
0: MOV UP, RIGHT MOV UP, ACC
1: #(WRITE) SUB LEFT
2: MOV ACC, DOWN
3: #(WRITE)
4: NEG
5: MOV ACC, LEFT
6: MOV RIGHT, DOWN #(WRITE)
7: #(WRITE) MOV UP, ACC
8: MOV UP, RIGHT
9: #(WRITE) SUB LEFT
This loop is only 8 cycles long (compare lines 1 and 9). Compared to the first iteration, we no longer need SAV
/SWP
, and the right side spends fewer blank cycles blocking on input from the left side.
However, the left side is now only 2 lines long: MOV UP, RIGHT
and MOV RIGHT, DOWN
. As a result it has a lot of spare time (blank cycles) so if we could figure out how to use those spare cycles to take some load off the right side, we could save more cycles. It turns out that if we move the NEG
to the left side we can save another cycle:
Cy Top Left Top Right
0: MOV UP, RIGHT MOV UP, ACC
1: #(WRITE) SUB LEFT
2: MOV ACC, LEFT
3: MOV RIGHT, ACC #(WRITE)
4: NEG MOV ACC, DOWN
5: MOV ACC, DOWN #(WRITE)
6: #(WRITE) MOV UP, ACC
7: MOV UP, RIGHT
8: #(WRITE) SUB LEFT
Now we are down to 7 cycles, but there is still one blank cycle on each side and it turns out we can get rid of it. The problem is that the left side wants to read the value to negate one cycle before the right side is finished computing it. We can't speed up the right side any more but we can rearrange the left side by realizing that -1 * X
(NEG
) produces the same value as 0 - X
. With this change we can use that wasted cycle to do MOV 0 ACC
and change the NEG
to a SUB
:
Cy Top Left Top Right
0: MOV UP, RIGHT MOV UP, ACC
1: #(WRITE) SUB LEFT
2: MOV 0, ACC MOV ACC, LEFT
3: SUB RIGHT #(WRITE)
4: MOV ACC, DOWN MOV ACC, DOWN
5: #(WRITE) #(WRITE)
6: MOV UP, RIGHT MOV UP, ACC
This version shaves the loop down to 6 cycles.
This loop is about as tight as you can get, but there is one final optimization, which is to parallelize. You may have noticed that while the top two nodes are doing all the work while the middle and bottom rows are not doing anything other than passing values through, a simple 2-cyle instruction. We can put those middle and bottom rows to work, by copy-pasting our code from the top row into them. We can divide the input into thirds with a few extra MOV
instructions and have 3 rows processing at the same time. The idea is as follows:
# TOP ROW
MOV UP, DOWN # Shunt inputs 0, 3, 6, 9, ... to bottom row
MOV UP, DOWN # Shunt inputs 1, 4, 7, 10, ... to middle row
# COPY PASTE LOOP to handle 2, 5, 8, 11, ...
# ...
# MIDDLE ROW
MOV UP, DOWN # Shunt inputs 0, 3, 6, 9, ... to bottom row
# COPY PASTE LOOP to handle inputs 1, 4, 7, 10 ...
# ...
MOV UP, DOWN # Pass along outputs 2, 5, 8, 11, ... from top row
# BOTTOM ROW
# COPY PASTE LOOP to handle inputs 0, 3, 6, 9, ...
MOV UP, DOWN # Pass along outputs 1, 4, 7, 10 ... from middle row
MOV UP, DOWN # Pass along outputs 2, 5, 8, 11 ... from top row
The 2 extra MOV
instructions we inserted in each row cost a total of 4 cycles but in exchange we can now process 3 inputs in 6+4 = 10 cycles instead of 6 * 3 = 18 cycles.