Inefficient differential converter

Question

Following Pimgd's question, I decided to take a look at the TIS-100 myself.

This is my solution to the 3rd challenge, building a differential converter.

Requirements:

Read values from IN.A and IN.B
Write IN.A - IN.B to OUT.P
Write IN.B - IN.A to OUT.N

Instruction set:

I got the basics down, but I'm doing something terribly inefficient. All the calculations are done in the top two nodes and 4 nodes are doing nothing else than just passing along the data.

It's efficient in amount of instructions and memory, but not in computation cycles. There is no guide about what's idiomatic yet, but I suppose the computation cycles are top priority.

Where Pimgd's question was using an extra node he wanted to get rid of, I don't mind using extra nodes if that brings the amount of computation cycles down.

Code overview:

For convenience, I've also included the code in text.

Top left:

MOV UP, ACC
SAV
MOV ACC, RIGHT
SWP
SUB RIGHT
MOV ACC, DOWN

Top right:

MOV UP, ACC
SAV
SUB LEFT
MOV ACC, DOWN
SWP
MOV ACC, LEFT

Other nodes:

MOV UP, DOWN

Benchmarks:

Luckily, the TIS-100 system has an in-built measurement of cycles, nodes and instructions. So I know exactly how good or bad it performs in which area.

My solution is overall considered 'nominal'. Is my solution inefficient performance-wise? If yes, how should I bring the required amount of cycles down?

Answer 1

So, my first attempt at this solution was very slightly more efficient. With 2 more instructions, I managed 39 fewer cycles. I'm not exactly certain right now what the difference is (it's pretty close), but I'm not concerned with that right now.

Thinking about this problem some more, I realized there's a mathematical trick going on here that we can make use of to drastically decrease both the number of instructions and the number of cycles.

A - B == -1 * (B - A)

That is, instead of subtracting left from right for the left column and right from left for the right column, we can just subtract once, pass the positive result to one column and the negative result to the other column.

Using this trick, I'm also able to eliminate an entire node.

As you can see, 201 cycles 5 nodes, 10 instructions.

So, starting with the top left node, we pull A into memory, subtract B, then pass it down. Middle left just passes it down again. Bottom left saves it to ACC, passes it down, negates it and passes it right. The top right node just reads in B and passes it left. The bottom right node just moves stuff from left to down.

Three of the five nodes are just there to move the values around.

Here's the source...

TOP RIGHT

MOV UP, LEFT

TOP LEFT

MOV UP, ACC
SUB RIGHT
MOV ACC, DOWN

MIDDLE LEFT

MOV UP, DOWN

BOTTOM LEFT

MOV UP, ACC
MOV ACC, DOWN
NEG
MOV ACC, RIGHT

BOTTOM RIGHT

MOV LEFT, DOWN

Answer 2

Nice find on the NEG by @nhgrif. That's really the key to this one.

Whenever, in TIS-100, you're using nodes just for transport, ask yourself what you're doing. In this puzzle, the middle nodes are only shunting data while the top nodes block I/O as they're cracking numbers. You can save quite some cycles by moving the SUB to the middle node and use the top two nodes for quickly reading the input and shunting it down.

The node at IN.B:

MOV UP, LEFT

At IN.A

MOV UP, DOWN
MOV RIGHT, DOWN

One below IN.A

MOV UP, ACC
SUB UP
MOV ACC, DOWN

Now feed this result to OUT.P and NEG it for use with OUT.N. Once again, don't use OUT.N for transport only.

Answer 3

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.