Heuristic42
Blog
Opengl
Meta
Rendering
2
comment
Oct 4 at 16:12
Matrices
Want to get millions of people to subscribe to your channel eco…
–
anonymous
comment
Sep 30 at 15:51
Matrices
Need a cost-effective way to reach millions? More Info: http:…
–
anonymous
comment
Sep 23 at 13:15
Matrices
[deleted]
–
anonymous
comment
Sep 21 at 3:52
Contributing
I kind of predicted what was bound to happen when my favourite …
–
anonymous
comment
Sep 6 at 22:21
Route contention when running docker and a VPN
Thank you for this. Between this and the overwriting of iptabl…
–
anonymous
comment
Sep 6 at 14:57
Making a real EMF Reader
Sorry for the random quoted text comments. I am one of those p…
–
anonymous
comment
Sep 6 at 14:48
Making a real EMF Reader
["ove! Play a tone with a buzzer and has 5 LEDs to show the “EM…
–
anonymous
comment
Sep 6 at 14:47
Making a real EMF Reader
["easure direction Measure the magnetic fie"](#q107-644-685)
–
anonymous
comment
Aug 20 at 14:01
Matrices
[deleted]
–
anonymous
comment
Aug 11 at 19:32
Matrices
[deleted]
–
anonymous
edited
Jun 8 at 19:29
Rethinking writing files with memory mapping and C++
This post introduces the motivation behind the [decodless C++ o…
–
admin
created
Jun 8 at 19:16
Rethinking writing files with memory mapping and C++
This post introduces the motivation behind the [decodless C++ o…
–
pknowles
comment
Jun 5 at 10:36
Contributing
just buy the newer model, still on amazon or ebay: https://www.…
–
anonymous
comment
Apr 19 at 8:24
Matrices
[deleted]
–
anonymous
comment
Apr 12 at 21:25
Matrices
[deleted]
–
anonymous
comment
Apr 5 at 6:43
Matrices
[deleted]
–
anonymous
comment
Mar 27 at 14:19
Matrices
[deleted]
–
anonymous
comment
Mar 25 at 1:59
Matrices
[deleted]
–
anonymous
comment
Mar 5 at 12:39
Matrices
[deleted]
–
anonymous
comment
Feb 7 at 2:45
Microsoft Natural Ergonomic 4000 Replacement
Thank you so much for sharing your thoughts here, it tells me e…
–
anonymous
comment
Jan 28 at 20:31
Microsoft Natural Ergonomic 4000 Replacement
Oh man, I feel this post. Not sure if you've seen the "new" new…
–
anonymous
comment
Jan 25 at 9:06
Matrices
[deleted]
–
anonymous
comment
Jan 20 at 0:11
Matrices
[deleted]
–
anonymous
reverted
Dec 21 '23
Route contention when running docker and a VPN
updating to latest
–
admin
…
View All
Log in
Prime Mover - Processor (final problem) [Spoilers!]
leave this field blank to prove your humanity
Article title
*
Article revisions must have a non-empty title
Article body
*
[Prime mover](https://store.steampowered.com/app/693700/Prime_Mover/) is a fun puzzle game. It's about designing circuit boards, or rather more about logic circuits. I'm a programmer and have no electrical enginnering training, so this was especially fun reinventing a few wheels. The final problem is to implement a very simple processor. This post broadly describes how I solved it. The problem is a significant jump in complexity and took me ~50 hours. Spoilers ahead! # The game Game mechanics compared to real circuits: - Rather than binary signals, numbers move along wires. ![enter image description here][1] - There is only one sensor and it can only tell whether a number is positive, negative or zero. ![enter image description here][2] - Board space is very limited. There is a way to nest circuits, but they only have 4 wires for input/output. ![enter image description here][3] # Processor - problem description As always it's very, *very* important to understand the problem first before trying to solve it. Of course I knew this beforehand. But don't think that stopped me wasting a bunch of time making the mistake anyway :) There are three input wires and one output wire. Input A contains the instructions. B and C contain constant data for the instructions: 1. **Move B to pos C** - Take the number from input B and store it in the register index given by input C. E.g. if B is 5 and C is 2, store 5 in the second register. 2. **Copy *B to pos C** - Take the value in the register at index given by B and store it in the register at index given by C. E.g. if B is 1 and C is 2, copy the value from the first register to the second. 3. **Add *B to *C** - Add the values in registers at index given by B and C, then store the result in C. 4. **Sub *B to *C** - Subtract the value in register B from C and store the result in C. 5. **Send *B to D, C times** - This is the output instruction. C is 2 in the last two problems. 6. **If *B is greater than 0, jump to relative instruction C in program** - Only jump if the value in register at index B is positive. The jump can be positive or negative. E.g. If C is -1, repeat the last instruction. If -2, go back to the second last instruction and continue from there. If C is 1, skip the next instruction. This is a real challenge to implement. A final instruction 0 will end the program and must reset the entire processor. That is, destroy all values in registers and any instruction memory. My big mistake was thinking the data was separate to the instructions, i.e. a jump instruction could rewind or skip some values in input A but B and C would have new data for those instructions. This is not the case. Values in A, B and C make groups of three and a jump affects all of them. Note that the last instruction 0 is an exception and does not contian B and C data. One last note. The processor only has 100,000 ticks to complete all programs! Seems like a lot compared to previous problems, but I overshot by ~10% before optimizing. # Possible shortcuts Based on the current input (Dec, 2020) the following can be useful shortcuts to take: - You only need 4 registers - The maximum jump is -5, so you only ever need to store 6 instructions. In fact the only values -5, -3, 2 and 3 are used. - There is never a negative jump that goes back further than a previous negative jump. - You don't need to handle subtracting negative numbers. # Design The processor starts with the inputs - numbers on A, B and C. It needs a way to perform different instructions based on the value of A. Some instructions require loading register values and sending them to other components. Some instructions produce new values which must feed back into registers. Only the output instruction needs to be sent to D. Finally, the jump instruction feeds back to affect the input instructions. There also needs to be some synchronization, so we don't start processing the next instruction before the last one finished etc. Clearly there's going to be some components and the instructions will dictate how data is transferred between them. I assume there are many ways to implement all of this, varying in how hard coded components are. Perhaps each A+B+C instruction could move on a big wire loop through all the components and each component would be able to read it when appropriate and know which step of the instruction. That sounds absurdly complicated so I decided to break up instructions and generate smaller and more primitive commands based on each instruction. This means that each instruction on A is more like a higher level assembly-like command and I would be generating machine code dynamically. Figuring out the right set of internal instructions, including necessary synchronization, was tricky but perhaps the most creative and rewarding part. To handle the jump instruction I would have a component on the A/B/C inputs that could be sent either a value to send the next instruction, or a value to jump forwards or backwards. The implementation of the latter I left for later. This was fed by a simple component that could also do an inline compare. To connect all the components together I chose to have a bus where I would first send an address number, followed by one data number. To send multiple bits of data I would need to re-send addresses, but this could be pipelined (send 4 numbers without waiting for any to finish). The image below shows the overall component layout and addresses. Note that the register and add/subtract outputs feed back into the synchonization compoennt. A special zero address is used to wait for and load values onto the bus as either an address or data. ![enter image description here][4] It's not a coincidence that this matches the board in the solution too: ![enter image description here][5] # Components ## Address router These were modules placed along the main bus. They would decrement the first number, the address, and if it were zero route subsequent data value to the component. Otherwise it would let the next data value pass through unaltered. I actually had another varient inside the instruction translation component, which routed instructions and their B/C constants to separate blocks that would do the translation for each. The difference was these operated in threes, routing two following numbers depending on the first. ## Translate This took most of my time but was probably the simplest. A/B/C instruction triplets were routed to hardwired circuits to generate various sub-instructions in the right order. Here's what it would need to send for each instruction. Most sub-instructions would be in pairs of (address, data) with the exception of 0 which would send the following value as an addres, then wait for and then load a data value from registers/add/subtract. Originally this could also load the value as an address, but there are no instructions that require this (after I realised B/C data is attached to A). **1 - Move B to pos C** - C (register address) - 1 (register store) - C - B (data) - 8 (jump address) - 1 (load next instruction) **2 - Copy *B to pos C** - B (register address) - 2 (register load) - C (register address) - 1 (register store) - 0 (data input after address, send *B as data to *C) - C - 8 (jump address) - 1 (load next instruction) **3 - Add *B to *C** - C (register address) - 2 (register load) - B (register address) - 2 (register load) - 0 (data input after address, send *C to add) - 5 (add address) - 0 (data input after address, send *B to add) -> outputs result - 5 (add address) - C (register address) - 1 (register store) - 8 (jump address) - 1 (load next instruction) --- do this early to save time - 0 (data input after address, send result to *C) - C **4 - Sub *B to *C** Same as Add, but with 6 for sub address. Both add and subtract took advantage of this and used the same generation circuit. **5 - Send *B to D, C times** - B (register address) - 2 (register load) - 7 (output address) - C (number of times to duplicate) - 0 (data input after address, send *B to output) - 7 - 8 (jump address) - 1 (load next instruction) **If *B is greater than 0, jump to relative instruction C in program** - B (register address) - 2 (register load) - 8 (jump address) - 2 (to offset if greater than zero) - 0 (data input after address, send condition *B) - 8 - 8 - C (jump to this instruction) - 8 - 1 (load next instruction) **End program (instruction 0)** This instruction clears the internal memory of the processor. - 1 (register 1) - 1 (clear) - 2 (register 2) - 1 (clear) - 3 (register 3) - 1 (clear) - 4 (register 4) - 1 (clear) - 8 (jump address) - 2 (to offset if greater than zero) - 8 - 1 (greater than zero) - 8 - 0 (jump to offset zero) ## Register - 1 to clear and be ready to store the next value - 2 to load the current value (sends it to Sync) ## Sync This component does a few things: - Adds a little delay between each sub-instruction - Keeps input from registers/add/subtract behind a gate until sub-instruction 0 - When a zero is encountered it sends the next sub-instruction value as an address and then the data input. The unexpected ordering of the 0 operation is required because input is needed as data. The address can't be sent first and then a zero as a special "read from the input" because it would be ambiguous with other real data values of zero. ## Compare - 1 is a passthrough to jump - simply load the next instruction - 2 is a compare and jump that expects two more values - The first is the compare value (no-op if it's zero or below) - The second is the value that is sent to jump if the first was positive. Custom synchronization here was added to make sure a 1 would not be passed through if a jump was in progress. Sadly this was timing based and the jump replay took a very long time. Program 4 was a big bottleneck. ## Jump This one isn't the work I'm most proud of. As I understand, a real processor would fetch instructions from some memory. Rather than keep an instruction counter I opted to feed the instruction translator with a stream. This meant I needed to keep a queue of 6 recent instructions that I could replay if needed. It also needed to keep groups of 3 (A/B/C). Rather than linearize the inputs I chose to duplicate the entire jump module three times. The same input would be sent to all three jump components. If this unit received a 1 it would send the next value to the translation component. The next value may be waiting after the replay feedback or on the input before the replay is recorded, which added some complexity. If the unit received a value greater than 1 it would skip that many values bar one. E.g. a 2 skips 1 value. However the skipped values would still be recorded for subsequent replay if needed. A subsequent 1 value would be sent to the jump unit after any skip happened to then run the following instruction. If the unit received a negative value it would replay that many instructions. It would actually discard any remaining instructions, but thankfully no program exposed this flaw. This was implemented with one queue along a single wire (the basic idea for the queue is shown in the image below, with the input on the left, release on the top and output on the right). When replaying I needed the *n* most recent items. Since the queue was FIFO and the most recent input would be at its tail I had to reverse the queue, take only the first *n* and then reverse the result. My reverse implementation was timing dependent and took aaaages. ![enter image description here][6] Finally, a special value was needed to empty and discard the queue when the program finishes. This almost came for free as "replay zero values" gives the same result. Because allowing positives, negatives and zero through logis is fiddly in prime mover I subtracted 1 from all replay values until they made their way into the inner-most circuits. # Programs For my own reference, it was incredibly helpful to copy out the programs to a spreadsheet, where A, B and C could be side by side. I could also write notes about what the expected output was. For debugging and optimizing performance I'd also keep the tick that they were processed at. As of Dec, 2020... ## Program 1 | A | B | C | |--:|--:|---:| | 1 | 5 | 1 | | 1 | 1 | 2 | | 1 | 0 | 3 | | 4 | 2 | 1 | | 3 | 2 | 3 | | 5 | 1 | 1 | | 5 | 3 | 1 | | 6 | 1 | -4 | | 0 | | | ## Program 2 | A | B | C | |--:|--:|---:| | 1 | 1 | 1 | | 1 | 1 | 2 | | 1 | 4 | 3 | | 1 | 2 | 4 | | 4 | 4 | 3 | | 3 | 1 | 2 | | 5 | 2 | 1 | | 3 | 2 | 1 | | 5 | 1 | 1 | | 6 | 3 | -5 | | 0 | | | ## Program 3 | A | B | C | |--:|--:|---:| | 1 | 5 | 1 | | 2 | 1 | 2 | | 2 | 2 | 3 | | 1 | 1 | 4 | | 4 | 4 | 1 | | 5 | 3 | 1 | | 3 | 2 | 3 | | 4 | 4 | 1 | | 5 | 3 | 1 | | 6 | 1 | -3 | | 5 | 1 | 1 | | 5 | 2 | 1 | | 5 | 3 | 1 | | 5 | 4 | 1 | | 0 | | | ## Program 4 | A | B | C | |--:|---:|---:| | 1 | 1 | 3 | | 1 | 0 | 2 | | 1 | 15 | 1 | | 3 | 3 | 1 | | 4 | 3 | 1 | | 6 | 1 | 3 | | 5 | 2 | 1 | | 6 | 3 | 2 | | 5 | 3 | 1 | | 6 | 1 | -5 | | 0 | | | Output D: 15 x 1s, 0 ## Program 5 | A | B | C | |--:|--:|--:| | 1 | 1 | 3 | | 1 | 8 | 2 | | 4 | 2 | 3 | | 5 | 3 | 2 | | 0 | | | ## Program 6 | A | B | C | |---|----|----| | 1 | 16 | 1 | | 5 | 1 | 1 | | 1 | 3 | 2 | | 5 | 2 | 1 | | 1 | 1 | 3 | | 1 | 0 | 4 | | 4 | 2 | 1 | | 3 | 3 | 4 | | 5 | 4 | 1 | | 6 | 1 | -3 | | 4 | 3 | 4 | | 2 | 4 | 1 | | 5 | 1 | 2 | | 0 | | | Output D: 16, 3, 1, 2, 3, 4, 5, 6, 5, 5 [1]: https://img.heuristic42.com/img/2a6024979e36.png [2]: https://img.heuristic42.com/img/88233a03c5a9.png [3]: https://img.heuristic42.com/img/33bdd01780ca.png [4]: https://img.heuristic42.com/img/76bf20425c10.png [5]: https://img.heuristic42.com/img/cfee70f4af80.png [6]: https://img.heuristic42.com/img/48f869c41373.png
Toggle Preview
Edit message
*
A description of the changes made
Discard Draft
Save Draft
leave this field blank to prove your humanity
Flag
the thing you clicked
for moderator attention.
Reason choice:
Spam, promoting, advertising without disclosure
Rude, inappropriate, generally offensive
Too arrogant or demeaning to others
Other
Reason:
The reason for raising the flag
Error