> Reinventing the wheel is generally said to be something to be avoided, but there’s quite a bit to learn from actually doing it. It made me realize that I didn’t understand it as well as I could implement it from scratch.
I wrote a bitmap image library in C a few months ago and when I realized that I was in too deep I just kept going because I can never abandon a project I start.
I felt bad when I came out the other end because of all the time I spent on it that I could have spent doing other things and because I could have just taken a library off the shelf.
In doing the exercise I did realize that what appears to be a simple and straight forward image format, at first glance, is actually ambiguously defined and full of edge cases. There was no way for me to know that when I started.
> There was no way for me to know that when I started.
Any format/protocol/RFC that's been around for a significant amount of time is going to be bastardized and bent to solve people's problems. Right now I'm going through that with RTSP. I did my best to try to avoid writing my own client/server implementation because I knew that I would be taking on the responsibility to run down the quirks, but after some major vendor problems here we are =(
Just throwing this out there for folks new in their career: if it's been "a thing" for awhile you can almost guarantee that doing a full implementation against it is going to be time-consuming because of the quirks/edge-cases. If it's something common like handling bitmaps you can get ahead of your problem by reading open-source image libraries to get an idea of how much "edge-case support" you're going to have to dig through.
I just don't like forcing myself through "clean-room"/from-RFC/from-spec implementations unless I professionally have to - they're almost always painful and impossible to time-manage.
I like to call these discoveries as unknown unknowns. It’s when not only the answer/fact is not known, but even the existence of the question/fact is unknown.
In this case, not only the fact that the format is ambiguous (the answer), but also the fact that there exists something interesting/unusual about the format (the question).
For example, you could have learned the answer if you could have searched “is there something unusual about the format?”, or even “is the format actually ambiguous?”, but those ideas were not present!
This was an excellent read. Congrats to the team on getting their port of Xv6 up and running!
I had the opportunity to help with a project to port UNIX to a data general NOVA computer as an undergrad and the combination of "non toy" problems and results you can see is really fun. We didn't have to write the compiler though! That is an amazing part of this story too.
Given the availability of RISC-V descriptions and FPGA boards that will host it with memory, this sort of project should be within reach of anybody willing to invest about $150 in parts and a lot of labor. It would make for an interesting basis for a demo contest!
That's a current project for me right now. When I took computer architecture in university, it was fairly light on hard details about things like superscalar and out of order designs. Sure there's the concepts, but there are so many interesting problems it didn't cover.
E.g. how do you, at a hardware level, actually do the reservation stations for a out of order design. How do you actually implement a register file with enough read and write ports to satisfy such a design without taking up a whole die for it?
I know there are a few Linux capable soft-core RISC-V designs out there (VexRisc, etc.) and microcontroller class ones (PicoRV32, etc.). If my goal was implement a system and it needed one of those things, sure, I'd use an off the shelf one. But I really want to understand how the CPUs work, and the best way to do that is doing it myself without looking at the answer key.
Turns out register files are complicated and fascinating. I'd never come across "register file banking" in my architecture courses. Makes what I had to deal with in CUDA make a lot more sense now.
> We didn't have to write the compiler though! That is an amazing part of this story too.
As noted in the article, the compiler was written in OCaml. If you follow links, the compiler emits assembly which is then assembled by an assembler written in Python.
I think developing the compiler in a more productive language (certainly for writing compilers) than C greatly helped.
To be honest, I'm kinda jealous. I do have a general understanding of how a CPU works, and I do understand what preemptive multitasking operating systems do, but my understanding is mostly abstract. And, fwiw, I studied most of this by myself out of sheer curiosity.
I did graduate a university but the closest thing we had was using a custom CPU emulator, given by the teacher, to run programs, given by teacher, and tracing every step it takes. It was so tedious and boring (the thing ONLY accepted binary, too, hexadecimal would be too convenient I guess), I wrote my own emulator that took an assembly file as input and generated the paper as the output, you only had to add your name to it before printing and turning it in. It then took me 5 whole minutes to generate semester worth of those. Of course I got a passing grade. Still, no substantial understanding of CPU inner workings was gained during the process.
I was reading a book on early computing and I believe folks working on some of the original computers at MIT (?) would add their own instructions. They would just wire them in.
I’ve always wanted to do this. I helped my housemates implement a CPU with custom ISA in college (this was before FPGAs, so there were a lot of chips in that CPU) but that’s as close as I’ve gotten.
I kind of feel like you can do something like this in college, or after you retire, but nowhere in between. :)
Why not? I made my first Phone OS (RTOS) on 8051 and 256KB ROM in college 20 years ago. Then I worked on several projects and my skills improved. Then I designed a processor architecture, made C-like programming language, created a compiler, an IDE, created a mobile OS and want to build a hardware chip in my startup https://animationcpu.com/
I did a course like this while on exchange programme to UCSB! In the ECE 152B Digital Design Methodologies class, teams of 2 people had to design and build a CPU from scratch.
We had to choose all our own chips and wire them together by hand. We had an FPGA for the Control Unit, but had to design the bus, pipelining, stack, carry-borrow, all the way up to running a demonstration program.
We did that in teams of 2 people, with only 1 semester. I was broke, so we chose the cheapest chips (I built MUXes out of NANDs). I realised we couldn't finish on time. I wandered the hallways, saw a project poster from a previous year, took some photos, reverse-engineered and reimplemented their design. We didn't have the FPGA code, but knowing the breadboard layout helped enormously. A few more nights in the lab, working to exhaustion and sleeping under the desk, and we passed the class. If you think industrial espionage only happens in other countries, that taught me that it happens in the US too. Arguably we made enough changes that it wasn't total plagiarism, but it did help to have a known-working design to build on.
The most lasting memory of that project, though, was when it worked fine during debugging, but failed whenever we removed the test probes. We were using 2 breadboards, but no common GND. During programming, they were grounded together through the GND on the PC's USB port. Always check for a common ground!
Very cool. I once taught a class similar in spirit to this, although it was aimed at first-year undergraduates with only a basic knowledge of programming, squashed into a single quarter, and designed on the fly, so we only got partway through implementing a C compiler. Instead of writing a full C compiler ourselves, we considered "cross-compiling" one by taking one that compiled to bytecode, and writing an emulator for that in assembly, taking that to be our first "compiler" and then progressively bootstrapping from there to a better compiler until it became feasible to start writing (or porting) a C-based OS.
Indeed, while i was reading the blog post i had in my mind Wirth's Project Oberon which is also about implementing a custom CPU on FPGA and then a complete OS with its own compiler, tools, GUI, etc on it.
Jaw-droppingly impressive to have gone from nothing to a custom ISA, C compiler toolchain and a whole freaking OS with userland apps in six months!
My favorite detail was that having spent all this time on extra credit, they only managed to complete their primary task an hour before the presentation - an unmistakable mark of a true hacker if there ever was one.
They completed the primary task way before that. This was free time and they did it for fun. The fact that they re-implemented their initial task as a program in the OS itself was the cherry on top, to impress their teachers (and also to learn a heap load of stuff in the process).
WOW. that's all I have got to say. I wish my country's universities had such educational quality, help guiding students properly and would encourage students to work on such projects.
If you want to do the lite version of this there is a book called “From NAND to Tetris” that is an instructional book for a similar class and walks through doing much of the same thing. It helped me connect the dots between “I know how a transistor works” and “I know how assembly language works” that I have never learned otherwise. Even if you just skim the book without doing the project you will likely learn some things.
> Reinventing the wheel is generally said to be something to be avoided, but there’s quite a bit to learn from actually doing it. It made me realize that I didn’t understand it as well as I could implement it from scratch.
The paradox of any performance that seems effortless, is that tons of effort invariably went into producing that effect. Good going mate!
All the major toolchains work on Linux. I personally liked Pynq http://www.pynq.io/, it works fairly well and is beefy enough to do non-toy projects with it. For something totally barebones you can try https://www.latticesemi.com/Products/DevelopmentBoardsAndKit..., it has the advantage that it has a very nice open source tool flow available for it: http://www.clifford.at/icestorm/. I own both boards and I work professionally with EDA tools, honestly the biggest cliff is setting up tooling and processes around a given project. If you don't want to do everything from scratch you need to either rely on proprietary libraries, which will cost you a fortune and/or lock you into a very specific tool flow (Synopsis Designware libraries). The other alternative is to use one of the open source ecosystems like https://github.com/m-labs/migen or tooling around Chisel or various scattered libraries of open-source components which are often hard to get to work together, but also this requires a massive amount of time investment to just get the synthesis / simulation flow working.
The situation is slowly improving and there are various university research groups and corporations that have released larger amounts of open source code that one can use as a starting point:
On the hardware synthesis side some exciting developments are also happening, mostly driven by the desire of companies like Google to be vendor independent for their Deep learning accelerator designs and through funding by DARPA.
These days there is a low barrier of entry to create "own" CPU. Just get your favourite FPGA ecosystem, configure ready made core and off you go. Route manufacturer's reference design in Eagle or Kicad add your peripherals then send the design to JLCPCB or other fab and job done. There is plenty of good soldering tutorials on YT.
[+] [-] vegetablepotpie|5 years ago|reply
I wrote a bitmap image library in C a few months ago and when I realized that I was in too deep I just kept going because I can never abandon a project I start.
I felt bad when I came out the other end because of all the time I spent on it that I could have spent doing other things and because I could have just taken a library off the shelf.
In doing the exercise I did realize that what appears to be a simple and straight forward image format, at first glance, is actually ambiguously defined and full of edge cases. There was no way for me to know that when I started.
[+] [-] folkhack|5 years ago|reply
Any format/protocol/RFC that's been around for a significant amount of time is going to be bastardized and bent to solve people's problems. Right now I'm going through that with RTSP. I did my best to try to avoid writing my own client/server implementation because I knew that I would be taking on the responsibility to run down the quirks, but after some major vendor problems here we are =(
Just throwing this out there for folks new in their career: if it's been "a thing" for awhile you can almost guarantee that doing a full implementation against it is going to be time-consuming because of the quirks/edge-cases. If it's something common like handling bitmaps you can get ahead of your problem by reading open-source image libraries to get an idea of how much "edge-case support" you're going to have to dig through.
I just don't like forcing myself through "clean-room"/from-RFC/from-spec implementations unless I professionally have to - they're almost always painful and impossible to time-manage.
[+] [-] swiley|5 years ago|reply
But IMO you can learn a lot reinventing things badly and correct software has little business value anyway.
[+] [-] kovek|5 years ago|reply
In this case, not only the fact that the format is ambiguous (the answer), but also the fact that there exists something interesting/unusual about the format (the question).
For example, you could have learned the answer if you could have searched “is there something unusual about the format?”, or even “is the format actually ambiguous?”, but those ideas were not present!
Active mentors can help with this a lot.
[+] [-] ajsnigrutin|5 years ago|reply
[+] [-] ChuckMcM|5 years ago|reply
I had the opportunity to help with a project to port UNIX to a data general NOVA computer as an undergrad and the combination of "non toy" problems and results you can see is really fun. We didn't have to write the compiler though! That is an amazing part of this story too.
Given the availability of RISC-V descriptions and FPGA boards that will host it with memory, this sort of project should be within reach of anybody willing to invest about $150 in parts and a lot of labor. It would make for an interesting basis for a demo contest!
[+] [-] Teknoman117|5 years ago|reply
E.g. how do you, at a hardware level, actually do the reservation stations for a out of order design. How do you actually implement a register file with enough read and write ports to satisfy such a design without taking up a whole die for it?
I know there are a few Linux capable soft-core RISC-V designs out there (VexRisc, etc.) and microcontroller class ones (PicoRV32, etc.). If my goal was implement a system and it needed one of those things, sure, I'd use an off the shelf one. But I really want to understand how the CPUs work, and the best way to do that is doing it myself without looking at the answer key.
Turns out register files are complicated and fascinating. I'd never come across "register file banking" in my architecture courses. Makes what I had to deal with in CUDA make a lot more sense now.
[+] [-] sanxiyn|5 years ago|reply
As noted in the article, the compiler was written in OCaml. If you follow links, the compiler emits assembly which is then assembled by an assembler written in Python.
I think developing the compiler in a more productive language (certainly for writing compilers) than C greatly helped.
[+] [-] grishka|5 years ago|reply
I did graduate a university but the closest thing we had was using a custom CPU emulator, given by the teacher, to run programs, given by teacher, and tracing every step it takes. It was so tedious and boring (the thing ONLY accepted binary, too, hexadecimal would be too convenient I guess), I wrote my own emulator that took an assembly file as input and generated the paper as the output, you only had to add your name to it before printing and turning it in. It then took me 5 whole minutes to generate semester worth of those. Of course I got a passing grade. Still, no substantial understanding of CPU inner workings was gained during the process.
[+] [-] m463|5 years ago|reply
[+] [-] wrs|5 years ago|reply
I kind of feel like you can do something like this in college, or after you retire, but nowhere in between. :)
[+] [-] ellis0n|5 years ago|reply
[+] [-] peterburkimsher|5 years ago|reply
We had to choose all our own chips and wire them together by hand. We had an FPGA for the Control Unit, but had to design the bus, pipelining, stack, carry-borrow, all the way up to running a demonstration program.
We did that in teams of 2 people, with only 1 semester. I was broke, so we chose the cheapest chips (I built MUXes out of NANDs). I realised we couldn't finish on time. I wandered the hallways, saw a project poster from a previous year, took some photos, reverse-engineered and reimplemented their design. We didn't have the FPGA code, but knowing the breadboard layout helped enormously. A few more nights in the lab, working to exhaustion and sleeping under the desk, and we passed the class. If you think industrial espionage only happens in other countries, that taught me that it happens in the US too. Arguably we made enough changes that it wasn't total plagiarism, but it did help to have a known-working design to build on.
The most lasting memory of that project, though, was when it worked fine during debugging, but failed whenever we removed the test probes. We were using 2 breadboards, but no common GND. During programming, they were grounded together through the GND on the PC's USB port. Always check for a common ground!
[+] [-] saagarjha|5 years ago|reply
[+] [-] fancyfredbot|5 years ago|reply
[+] [-] badsectoracula|5 years ago|reply
[+] [-] duckfruit|5 years ago|reply
My favorite detail was that having spent all this time on extra credit, they only managed to complete their primary task an hour before the presentation - an unmistakable mark of a true hacker if there ever was one.
[+] [-] unnouinceput|5 years ago|reply
[+] [-] plastman|5 years ago|reply
[+] [-] fomine3|5 years ago|reply
[+] [-] notdan|5 years ago|reply
The Elements of Computing Systems: Building a Modern Computer from First Principles https://www.amazon.com/dp/0262640686/ref=cm_sw_r_cp_api_i_yH...
[+] [-] amcvitty|5 years ago|reply
I saw there’s a highly rated Coursera version too (I prefer books to videos so I haven’t looked at it)
[+] [-] shyam_joshi|5 years ago|reply
The paradox of any performance that seems effortless, is that tons of effort invariably went into producing that effect. Good going mate!
[+] [-] unionpivo|5 years ago|reply
I would prefer if tool chain works on linux ?
[+] [-] orbifold|5 years ago|reply
The situation is slowly improving and there are various university research groups and corporations that have released larger amounts of open source code that one can use as a starting point:
- https://github.com/openhwgroup/cva6 (mostly done by ETHZ people initially, also see https://github.com/pulp-platform/pulpino)
- https://github.com/chipsalliance/Cores-SweRV-EL2 (one of several high quality open-source RISC-V cores by Western Digital)
- https://github.com/chipsalliance/rocket-chip (UCB by initial creators of RISC-V)
- https://github.com/electronicvisions/nux (POWER based embedded processor, that we have used in several neuromorphic chip tapeouts (silicon proven))
On the tooling side one great thing that happened is that the verilator open source simulator has gained a lot of traction.
- https://github.com/verilator/verilator
On the hardware synthesis side some exciting developments are also happening, mostly driven by the desire of companies like Google to be vendor independent for their Deep learning accelerator designs and through funding by DARPA.
[+] [-] ncmncm|5 years ago|reply
[+] [-] nkozyra|5 years ago|reply
I see "cofee" written a bunch across the site is that some alternate spelling or just a typo?
[+] [-] poxwole|5 years ago|reply
[+] [-] known|5 years ago|reply
[+] [-] CyberRabbi|5 years ago|reply
[deleted]
[+] [-] varispeed|5 years ago|reply