HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Inefficient differential converter

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
converterdifferentialinefficient

Problem

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?

Solution

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

Code Snippets

A - B == -1 * (B - A)
MOV UP, LEFT
MOV UP, ACC
SUB RIGHT
MOV ACC, DOWN
MOV UP, DOWN
MOV UP, ACC
MOV ACC, DOWN
NEG
MOV ACC, RIGHT

Context

StackExchange Code Review Q#98713, answer score: 8

Revisions (0)

No revisions yet.