So if you’ve been following along you know I completed a prototype for the 4×1 multiplexer. This was done on a breadboard and there was no thought put into compactness. I just wanted to see if it worked.
But compactness is a requirement of the actual design. I want to make sure that for each bit of the ALU (one bit per board) the overall connection distance between all the relays is minimized. If you saw any of the prototype videos you’d notice that there are a lot of wires connecting things and the wires go everywhere. I want to minimize that mess.
The final location of the multiplexer was arbitrarily decided by me to be on the right side of the board and fit in 2 columns of 10 relays each. On the left side of the board would be the adder and the gates (another 2 columns of 10). But that’s it. That’s all I came up with. I figured the placement of the relays would simply show itself as I played around. So it was time to start playing with the actual location of the multiplexer relays.
I spent about 2 hours drawing up ideas and started to get really frustrated. Sometimes I’d come up with something but there would be one wire that had to jump over a bunch or relays to make a connection. If I moved that one, then another long connection crept up. Moving again, same problem. There’s 20 interconnecting parts here that could be swapped around and rotated. It was also a factor that for some pins of the relay I was using I could connect to one side or another. How to optimize that?
Finally I thought of something : “hey! I’m a software engineer, this could be done with a computer!”. So I decided to start writing a program to help solve my problem. But then I started to think that with 20 relays and rotation and pins on either side that the number of possible combinations was in the billions (or more). So I needed some algorithmic solution of some kind.
Should I do research? Well, I did ask a friend for his ideas but it’s a really hard problem once you really start getting down into the details and he was too busy to get into it too deeply. I looked in a few books and checked the web but finally I gave up and started plugging away. After about 30-40 hours of coding I came up with something that works pretty good. It could be a lot better but for now I’m happy with it.
How does it work? I’ll explain maybe later but a simple overview is :
I came up with a metric to keep track of progress. I called it totalDistance and it was simply the sum of the distances of all the connections in the circuit. A connection distance is calculated by the following : Each relay can have connections on its right or its left side. The connection distances based on the 4 possible horizontal connections between 2 relays (call the left one 1 and the right one 2) there are 4 connections : 1L->2L (distance 1), 1R->2L (distance 0), 1L->2R (distance 2),1R->2R (distance 1) . From there I would also add 1 for each vertical space apart they were and 1 for each horizontal space they were apart.
Once I had the metric in place I could try different things. I first tried randomly placing and rotating relays, keeping track of the best ones. Then I came up with a way to swap relays around, then I came up with a way to rotate them, etc. All the while keeping track of my totalDistance.
To give you an idea, I started with a tD of about 85. After having my current code running for a day or so I got it down to 15.
Here is the output of the 15 version.
Note that there is a small bug in the program that I need to fix where the graphical output of connections on the left side of the relays have their arrows backwards but the locations and rotations (the ones with I are inverted/rotated) are correct.
This is a java program and if you want to play with it yourself I hosted it on github here. (note you will need another project of mine as well).
Maybe if you really are curious I can build an executable but for now you non techies will have to be happy just browsing the code..