Show HN: Online challenge: Build a CPU from scratch

by sergex • 8 years ago

143 60 8 years ago

sergex22• 8 years ago

This is an attempt to make an educational online game, where the mission is to build a microprocessor starting from simple logic gates.

Hopefully it is both fun and challenging, while at the same time educational about some of the fundamental principles of how a CPU works.

It still lack some explanatory texts, but is should be playable as it is.

It is inspired by the first chapters of the brilliant Nand2tetris course (and I have gotten permission to use the same general CPU design). My hope is this is more accessible since it is web-based and does not require any text-based coding or CS background.

harperlee• 8 years ago

FYI: I'm not able to drag components from the toolbox in mobile chrome.

sergex22• 8 years ago

I'm sorry, it does not work with touch yet.

pro_zac2• 8 years ago

This is great! I've been reading up on low level logic during long builds at work. Any chance you could add a clear all button?

sergex22• 8 years ago

You mean for just wiping all components from the canvas? That should be possible.

chrisparton19912• 8 years ago

This is really neat, good job!

This reminded me of "Code" by Charles Petzold, which I saw you reference in the About page. As a software engineer with an interest (but no professional training) in hardware design, I think it's useful and interesting to have at least a basic understanding of how a CPU handles logic.

Can I ask what library (if any) you used for the canvas interactions? I'm looking for something similar for a project of my own.

sergex22• 8 years ago

Thank you. I'm using Angular, but no library beyond that. I was looking for a library for the diagram, but didn't find anything that suited my needs, so it is just custom code. I would like to find a library which could draw nicer arrows at least, since the diagram currently gets pretty confusing when there are many connections.

AnthonBerg• 8 years ago

My fiancee is starting computer science this fall. I'm already using this to teach fundamentals. Thank you!!

olavk2• 8 years ago

Great to hear. I would love to hear feedback from someone without CS background.

ganashaw• 8 years ago

I can't figure out why this isn't accepted as an answer for latch? Admittedly there's probably something simpler, but this seems to adhere to spec.. https://i.imgur.com/mnePQc7.png

sergex22• 8 years ago

The design does not seem to fully adhere to the spec. If you have output 0 and both w and d is 0, and then set d=1, then output changes to 1. But output should only change when w=1. Admittedly the specification is not very clearly written.

Neeek• 8 years ago

In the full adder level, shouldn't the input/output table in the specification read 01 for the h/l on row 3? Had me a little confused trying to get my head around how the adder works.

I'm really enjoying the whole thing though, great work!

sergex22• 8 years ago

Thank you. You are correct, this is a bug. Thank for pointing it out. Fixed now.

ackfoo• 8 years ago

I had more fun with this than I expected to. The only problem is that I got to the Full Adder level, then clicked on "About" and when I went back, my progress was not saved. It would be nice to have a way of saving and a way of showing how I built each component.

sergex22• 8 years ago

Yes that is annoying. Also all progress is lost if you leave the page. I am considering saving the state in local storage so you can return to the page and continue where you left of. Also a great suggestion to save previous levels so you can go back and review them.

n4r92• 8 years ago

This is fun. Reminds me a lot of Euclid the Game: http://eu.jugregator.org/Level1/

Would be awesome if you compare your answer to the "best" solution, i.e. which uses the minimum number of components (or even the minimum number of nand gates!)

sergex22• 8 years ago

Great idea! I don't know the optimal solutions, only that each task can be solved. Perhaps someone smarter than me can prove that a certain solution is optimal. But I could record the solutions provided and show if someone else have solved the task with fewer components or less nand-gates.

It would also be cool to show the overall cost in nand-gates or even transistors. And to be able to show the solutions decomposed into only transistors and wires.

Didn't know Euclid the Game, but it seems very cool and close to what I wanted to achieve.

n4r92• 8 years ago

I'd be happy to have a crack at the optimality part. The first few are obvious but it gets quite interesting. Email my username at protonmail.com if you're interested =]

meta_AU• 8 years ago

If you have a look at any Zachtronics games you can see one way of doing it. It is just a leaderboard represented as a histogram. A separate one for instructions, cycles, etc. No need to know the best, just keep track of what other people have achieved.

jakear2• 8 years ago

Gate count is interesting from a "how much would this const to make" perspective, but I think minimum clock cycle time is a more interesting metric, as that will show how fast you can run the thing. Maybe a two dimensional plot? It would be very interesting to have a worldwide "leaderboards" section with a dot on the plot for every entry, and a link to see how they did it.

gsaga2• 8 years ago

The level on subtraction doesn't mention how negative numbers are handled at all.

sergex22• 8 years ago

Thank you for noticing this error. I will add the necessary information.

barrystaes2• 8 years ago

Really nice! Ideas for features i missed: Reset button. Way to see diagram of previous components. Level goal text is not equal to whats shown left. Possibly mislabeled C in full adder level. Hint option to show the count of needed components.

sergex22• 8 years ago

Thanks for the suggestions, much appreciated.

Reset for clearing all components off the canvas, or for resetting the input signals and state? Or both?

fbomb• 8 years ago

Holy crap! this brings back memories. I actually did this many years ago with real logic gates, eventually ending up with a 4-bit CPU that could address an entire 16 nybbles of RAM. That was so much fun!

sergex22• 8 years ago

I would love to be able to get as close as possible to the "feel" of working with actual physical components.

dzolvd• 8 years ago

same! We actually built an 8-bit cpu, and while debugging some very strange, seemingly random bit flips, learned why you coil wires.

Robin_Message• 8 years ago

I can't see why my instruction decoder is failing: https://imgur.com/a/PCgkQhb

Otherwise, it's fun, although the node connections are fiddly! Maybe allow dragging from either end? Or snapping together.

Edit to add: and on the next level, the m flag doesn't exist. So, will stop there, but fun!

sergex22• 8 years ago

You need to special case "target a", it should be 1 in case bit 15 is 0. The error reporting could definitely be improved. It should probably display the exact mismatch, something like "with input XXX connector Y was 0 but was expected to be 1". Otherwise it gets to tedious to debug.

The m issue is a bug in the spec, thanks for discovering it.

Thank you for the feedback, it is much appreciated.

barrystaes2• 8 years ago

As for debugging, why not just put checkboxes in the input-output lookup table(s) shown on the left. And highlight the currently input line + mark wrong outputs. I think that would be intuitive.

To further build on this; If there is an intermediate state, show its pins in the diagram like output and input. If the table becomes wide, perhaps show it on the bottom. Perhaps let users add a "debug probe" from the toolbox that becomes a column in that table.

Streetwalrus2• 8 years ago

I've looked through the code a bit, I think your assembler is actually buggy. The expected results for the tests are correct, however the encoded instructions that you're feeding to the decoder are not. For example, A=1 should be 0x89F8, but you're encoding it as 0x8FE0. This causes the tests to fail despite the logic being correct.

Angostura• 8 years ago

Looks as if we have hugged it to death

wlxiong• 8 years ago

I always want to read The Elements of Computing Systems, but never finish it. Playing this game for a few minutes let me pick up the book again.

frafra• 8 years ago

Will it be released under an opensource license? It would be nice to try to improve, especially because it is an educational tool.

zerr• 8 years ago

That's certainly easier compared to that Build a standard conforming C++ compiler along with std libs from scratch challenge, awhile ago.

tgb• 8 years ago

Love the game. What's a good solution to the increment gate? My answer worked but seemed way too complicated.

sergex22• 8 years ago

Thanks! A possible solution [spoiler alert!] is inv(add(inv(input), inv(0)) where inv(0) is an inverter without any input.

By the way I suppose the subtraction component should be available in this task. This would make is simpler. I had trouble deciding if increment should be before or after subtraction.

r3dey3• 8 years ago

I'm enjoying this; but it looks like a few of the levels might be out of order. In State Selector uses Decoder in the library but it is before decoder. Then in the Arithmetics the "Bus" comes into play before it's described (I forget exactly which ones are out of order)

sergex22• 8 years ago

Doh, you are correct about selector - the decoder should no be available here (and is not needed). And the bus definitely needs an introduction.

Boxxed• 8 years ago

Cool! Very similar to MHRD -- give that a look if this is your thing.

https://store.steampowered.com/app/576030/MHRD/

notafraudster• 8 years ago

I had a lot of fun with MHRD but I hope the developer some day updates it to not be a sluggish Java implementation. The puzzle of working through all the levels was a fun throwback to my processor design courses 15 years ago, but the unresponsive typing in the IDE was a little less so.

DonaldFisk• 8 years ago

The usual convention for logic gates is to draw them so that information flows from left to right (or, less usually, top to bottom) and they're connected in the direction of information flow. Is there any reason why these conventions aren't followed here?

sergex22• 8 years ago

No, just ignorance on my part. I would be easy to flip input and output though.

Djvacto• 8 years ago

I'm not a huge fan of the fact that when I want to drag a component, if I initiate the click&drag on the little "i" information button, it lets me drag the component but when I release it snaps back to the previous location and opens the info.

Perhaps a toggle for the info boxes on components?

Overall, I love this though.

billpg• 8 years ago

Feedback....

I wanted to send a bit into two separate components and I was looking for some sort of "hub" object. It wasn't clear (to me) that you could connect many lines to a single node.

Removing lines takes a lot of clicking.

Is my design the best possible? Rather than just being told my design fits the requirements, I'd like to be told that I could have done it with one less component and offer to try again.

sergex22• 8 years ago

Yeah I'm unsure how to clearly communicate how the connectors work.

imtringued• 8 years ago

There is a very annoying bug that causes a component to get stuck (output triangles disappear) and if you try to move it a copy is created.

sergex22• 8 years ago

May I ask about browser/platform and what you did to make this happen? I am not able to reproduce the issue.

farzadb82• 8 years ago

This is really awesome. I just killed about an hour playing it part way through.

I was saddened by the fact that I lost progress when I left the page. It would be nice if progress could be save via cookies or something.

One other thing that would be nice is the ability to offer hints. These could even be just an external link to relevant material on wikipedia or equivalent.

gsaga2• 8 years ago

In the chapter on RAM, it says we can index upto 64KB of memory in a 16 bit architecture. Shouldn't it be '128K words of memory', since we can index '2 words' with a single bit.

sergex22• 8 years ago

You are correct, the text is wrong. It should be 128KB, not 64KB. A word is two bytes (on a 16-bit architecture) so we can address 64K words which is 128KB. (I think you mixed up byte and word in your comment, but I understand what you meant.)

The explanatory text for the level does not really define neither "byte" or "word", so beside fixing the error it also need more details. (But I want to avoid going down the rabbit hole of explaining that bytes can have different sizes than 8 and so on)

Show HN: Online challenge: Build a CPU from scratch

Related Stories