8 ms·
MMIX 2009: A RISC computer for the third millennium (2011)
- du_bing 9y agoI find Knuth's idea fascinating. The fashionable languages come and go, but facts about how machine works does not change much, probably will not in the future.
- meanderer 9y agoQuantum computers could work in very different ways, though.
- soberhoff 9y agoSo do cars. Neither have any bearing on TAOCP.
- harry8 9y agoCars don't do much in the way of general purpose data transforms for you. In my day we had computational complexity, and we LiKED it! So say all of us who claim Knuth as our homeboy if quantum computers ever work better switched on than off...
- lokedhs 9y ago> Cars don't do much in the way of general purpose data transforms for you. And neither does quantum computers.
- userbinator 9y agoI would disagree: just compare MIX with MMIX. MIX is a 6-bit/2-digit hybrid binary/decimal sign-magnitude machine, typical of 50s-60s machines. MMIX is a 64-bit binary big-endian RISC with 256 windowed registers that resembles a hybrid of SPARC and MIPS, with all the traits of that 90s "RISC dream" that never really went anywhere. If he were to design it today, it would probably look more like a mix of x86 and ARM.
- masklinn 9y ago> If he were to design it today, it would probably look more like a mix of x86 and ARM. Why bother basing a new architecture on x86 when it's generally considered the worst ISA in history (with some boosting TI's TMS9900 instead)? x86's advantage is basically its continuous dominance and compatibility with itself which managed to thwart even its original designer's attempt to displace it[0], but you won't get that by basing a new incompatible ISA upon it, so there's really no point in doing so. [0] Linus made that point reasonably clearly in a 2016 PCWorld interview: http://www.pcworld.com/article/3129300/linux/why-linux-pioneer-linus-torvalds-prefers-x86-over-arm.html http://www.pcworld.com/article/3129300/linux/why-linux-pione... > What matters is all the infrastructure around the instruction set, and x86 has all that infrastructure... at a lot of different levels > I’ve been personally pretty disappointed with ARM as a hardware platform, not as an instruction set […] As a hardware platform, it is still not very pleasant to deal with. And this is a lesson he learned: while originally interested in the Acorn Archimedes (which wasn't a great success) he went with the Sinclair QL (which outright failed) and… > Finland wasn’t the center of the universe back then, after that, I learned my lesson: never ever go buy into something that doesn’t have infrastructure.
- CalChris 9y agoIf I were designing something today, something clean, I'd give a really good look at just cleaning up x86_64. AMD64 did some of that. What is RISC-V but a cleaned up RISC, omitting the architectural mistakes of previous RISCs (branch delay slot (MIPS), register windows (RISC-1), tagged integers (SPARC), ...). It has a place. A cleaned up x86 would definitely have a place. The idea of parsing a CISC instruction and translating+caching the result as a micro-op has worked, flat out worked. Worst ISA in history? I think not. Most successful ISA in history. Still, Intel really needs to do what ARM has done. Clean up their act. Itanium was changing their act. It kinda reminds me of the scene in Spinal Tap where they introduced the new direction. Intel just needs to get rid of their cruft, seriously needs to get rid of their cruft because ARM is a threat and ARMv8 is a weapon. The x86 tax helps prevent competitors in their space (as per their threats to Microsoft) but ARM isn't in their space; they're next door.
- kruhft 9y agoAnd we have all the source code for the optimized algorithms...every...single...one. https://www.amazon.ca/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043/ref=sr_1_2?ie=UTF8&qid=1497021908&sr=8-2&keywords=the+art+of+computer+programming https://www.amazon.ca/Computer-Programming-Volumes-1-4A-Boxe....
- hvidgaard 9y agoAnyone know the status of vol 4 and "ultimate edition" of vol 1-3?
- beefsack 9y agoLast paragraph of the page. > All of the MIX programs in Volumes 1--3 will need to be rewritten in MMIX, before I finish the ``ultimate'' edition of those volumes that I plan to write after Volume 5 is completed. The current target date for the ultimate volumes is the year 2020, so there is plenty of time to do the conversion. But I think it will be an instructive undertaking if different groups of students from around the world try to do the necessary translations first, perhaps in friendly competitions, long before I get into the act.
- hvidgaard 9y agoThat was said 8 years ago, I hoped someone had something more recent.
- davidtgoldblatt 9y agoAll the volume 4A listings are in MMIX, and there's "The MMIX Supplement" by Martin Ruckert, redoing the first three volumes in MMIX, which I believe is regarded as the authoritative edition. As to the ultimate versions (or even finishing until volume 5): not to be morbid, but the date there has been continually pushed back, and Dr. Knuth is not a young man.
- mci 9y agoVol 4A was published in 2011: https://www.amazon.com/Art-Computer-Programming-Combinatorial-Algorithms/dp/0201038048/ https://www.amazon.com/Art-Computer-Programming-Combinatoria... Vol 4B was partially published in fascicles: https://www.amazon.com/Art-Computer-Programming-Fascicle-Preliminaries/dp/0134671791/ https://www.amazon.com/Art-Computer-Programming-Fascicle-Pre... and https://www.amazon.com/Art-Computer-Programming-Fascicle-Satisfiability/dp/0134397606/ https://www.amazon.com/Art-Computer-Programming-Fascicle-Sat... Instead of the ultimate edition of vols 1-3, so far we've got a "patch" by Martin Ruckert who coordinated the volunteers: https://www.amazon.com/MMIX-Supplement-Computer-Programming-Volumes/dp/0133992314/ https://www.amazon.com/MMIX-Supplement-Computer-Programming-...
- plinkplonk 9y ago" The original MIX computer ran fine without an operating system. You could bootstrap it with punched cards or paper tape and do everything yourself. But nowadays such power is no longer in the hands of ordinary users. The MMIX hardware, like all other computing machines made today, relies on an operating system to get jobs started in their own address spaces and to provide I/O capabilities. Whenever anybody has asked if I will be writing a book about operating systems, my reply has always been ``Nix.'' Therefore the name of MMIX's operating system, NNIX, should come as no surprise. From time to time I will necessarily have to refer to things that NNIX does for its users, but I have no intention of building NNIX myself. Life is too short. It would be wonderful if some expert in operating system design became inspired to write a book that explains exactly how to construct a nice, clean NNIX kernel for an MMIX chip. The MMIX fascicle includes a level-50 exercise that asks a highly motivated reader to ``Write a book about operating systems, which includes a complete design of an NNIX kernel for the MMIX architecture.'' Other alternatives are also possible; for example, somebody at the Free Software Foundation might decide to come up with an alternative system called GNNIX. "
- masklinn 9y ago> " The original MIX computer ran fine without an operating system. You could bootstrap it with punched cards or paper tape and do everything yourself. But nowadays such power is no longer in the hands of ordinary users. The MMIX hardware, like all other computing machines made today, relies on an operating system to get jobs started in their own address spaces and to provide I/O capabilities. Unikernels come back to that, to an extent, what there is of the OS is part of the application, and IO capabilities are provided by libraries linked into the unikernel application. As always, the issue is having IO drivers for the hardware in a form which can be used.
- kazinator 9y agoSee: SYNC SWYM in last opcode row. :)
- wolfgke 9y agoAnd GET TRIP next. :-)
- pubby 9y agoMMIX was such a stupid idea by an otherwise genius person. So much effort and knowledge was put into TAOCP and yet it's wasted on the vast amount of people who aren't interested in learning a fantasy assembly language. I can't really fault Knuth for the original MIX. I mean, it _was_ written in the 1960s; a time when programming languages barely existed. But by 2009 it should be clear to everyone that C derivatives are here to stay, and that assembly programmers are dying off. Creating yet _another_ fantasy assembly language in the year 2009 was just stubborn and dumb.
- ianai 9y agoThat's like, just your opinion, man. There's always going to be that lowest level before 1s and 0s. (I say this as I'm curious if this assumption of mine is actually out of date at this point.)
- AstralStorm 9y agoNot really, and the hardware is getting more complex all the time. A modern CPU is like a probabilistic OS nowadays...
- wyager 9y agoOn many modern CPUs, the assembly language that compilers use and subsequent generated machine code isn't even the lowest level representation used by the CPU. Many desktop-class processors rewrite incoming instructions into a simpler microcode instruction set more easily handled by the OOOE hardware.
- brett40324 9y agoOP contains a lengthy section titled "Why have a machine language?" Toward the end of Knuth's answer is: "Therefore I will continue to use English as the high-level language in TAOCP, and I will continue to use a low-level language to indicate how machines actually compute. Readers who only want to see algorithms that are already packaged in a plug-in way, using a trendy language, should buy other people's books.
- 9y ago
- faragon 9y agoThe 2009 figure is not the year, but a result (the PDF [1] has the Copyright set in 1999) (Cray I + IBM 801 + RISC II + Clipper C300 + AMD 29K + Motorola 88K + IBM 601 + Intel i960 + Alpha 21164 + POWER 2 + MIPS R4000 + Hitahi SuperH4 + StrongARM 110 + Sparc 64) / 14 = 28126 / 14 = 2009 [1] http://mmix.cs.hm.edu/doc/fasc1.pdf#page=7&zoom=auto,-250,562 http://mmix.cs.hm.edu/doc/fasc1.pdf#page=7&zoom=auto,-250,56...
- Jabbles 9y agoRead the next sentence :)
- technomalogical 9y agoTIL deep linking URL syntax for PDFs in Chrome, thanks!
- faragon 9y ago"The same number may also be obtained in a simpler way by taking Roman numerals."
- unwind 9y agoThe names of the machine's primitive data types are interesting, and refreshing if you're tired of the more well-known ones. These are the load instructions, for reading data from memory: Load a Byte LDB $X,$Y,$Z Load a Wyde (2Byte) LDW $X,$Y,$Z Load a Tetra (4Byte) LDT $X,$Y,$Z Load an Octa (8Byte) LDO $X,$Y,$Z I thought the "wyde" in the instruction set reference was a typo, until I saw that it was used all over the place. :) I guess it's better (less ambiguous) than "word", "long", "double word", and so on.
- cjdrake 9y ago"Two bytes makes one wyde." Can't remember where I heard/read that, but it's classic Knuth humor :).
- andrewbinstock 9y agoIf you're interested in designing a RISC processor in software, Knuth's full book on MMIX is an interesting and complete read. I am not referring to the short version published as part of Volume 1 the revised TAOCP, but the full exposition in his book from Springer-Verlang. [1] There he explains the CPU, the memory management, the instruction pipeline. And he builds the assembler for the machine. He worked with David Patterson (of MIPS fame) on the architecture. As to the implementation, Knuth once commented that the coding of the instruction pipeline for MMIX was the hardest programming he'd ever done. Cool stuff! [1] http://www.springer.com/gb/book/9783540669388 http://www.springer.com/gb/book/9783540669388
- harry8 9y agoThe issue i have with Sedgwick, cormen et al is they ignore hardware. Is Knuth really better? How is the cache heirachy different in MMIX as compared MIX?
- Jtsummers 9y agoWhat hardware should they base their book on? Would it be universally applicable? Should they drop down to assembly level (as Knuth has) or stick to some higher level language? Their choice of using a pseudocode allows the algorithms they discuss to be accurately and completely specified, while leaving the implementations up to specific platform (hardware and language) developers and users.
- deleted 9y ago[deleted]
- hackermailman 9y agoVolume 4a there's a dozen or so mentions and examples of writing cache-friendly code. CS:APP 3/e is another book that gives general advice for writing cache friendly code. In fact CS:APP the chapters you can read side by side with TAOCP series: floating point, arithmetic operations, bit shifting, optimizations, boolean logic ect are in both books with TAOCP going much more into detail of course. I used the TAOCP chapter on bitwise ops in 4a to finish my CS:APP datalab assignment that was giving me problems.
- Koshkin 9y agoHow do RISC architecture designers deal with the problem of low code density when modern chip technology makes RAM access considerably slower than anything that happens inside the CPU? One answer could be to have a huge instruction cache, but I doubt that it is economically possible.
- 0xcde4c3db 9y agoAs far as I know, the two major approaches are 1) Caches 2) Supporting a "compressed" variant of the instruction set (ARM Thumb, MIPS16, RISC-V Compressed). This can be put together by using the same field for target and destination registers, shrinking the set of named registers, making shifts and conditions into explicit instructions instead of fields (for ARM), and similar tweaks.
- deepnotderp 9y agoA number of things. The biggest one is probably compressed instruction sets, which even x86 "CISC" processors use. For example, RISC-V and Thumb use this in their processors and they're a big boon. Also, I think that you've been lied to about the relative code density of RISC vs CISC. CISC is only about ~50% more dense than RISC in the best cases, unless you're talking about polynomial evaluation on VAX or something crazy like that.
- Symmetry 9y agoIf you're willing to be a bit impure like 64-bit ARM is you can get code density about equivalent to what you'd see in x86-64.
- kruhft 9y agoI've always wanted to implement the MMIX processor using this: http://github.com/burtonsamograd/anser http://github.com/burtonsamograd/anser
- lallysingh 9y agoSo is there any work on making an FPGA implementation of this?