The Lexra/MIPS Story | Hacker News Reader

The Lexra/MIPS Story

probell.com

130 pointsluu48 comments

Given the discussion of patents and instruction sets, you may be interested in the work of David Patterson and his student Tony Chen in tracking prior at of all RISC-V instructions http://www.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-6....

I think this is why humans fail. I think we'd be much further along if the kind of short term mindset driven by short term business goals outlined in this article were the exception instead of the rule. Patents in software and hardware design should not exist at all given the mathematical and physical underpinning of both disciplines.

There is creativity involved and the original inventors should get due credit but not to the point of being able to sue an equally good competitor with equally good inventors into oblivion. Everyone is worse off because of what happened here.

There isn't some abstract mathematical truth at issue in the MIPS patents, but a clever way of doing unaligned loans in an otherwise word-oriented machine.

And the value of the patent isn't "giving inventors credit" but instead enabling a particular sort of business model: the R&D-only company. None of the companies discussed in the article: MIPS, Lexra, and ARM, would exist without IP protection. They'd never make any money if companies could just copy their designs for free. The only viable model would be to vertically integrate and build complete processors like Intel does. And that probably would've made it impossible to build up the rich ecosystem of compatible cores that you see with ARM.

The issue is that given two hardware engineers both of them would have come up with the same clever design. In fact I'm almost certain this could be posed as a constraint satisfaction problem and I could even get a SAT solver to come up with the same design. The mathematical constraints basically force the design. So I disagree with you. It is indeed an abstract truth. The foundations are axiomatic. There are only so many theorems (clever tricks) you can come up with given the foundation. The law overstepped because of fundamental misunderstandings of how the engineering, theory, and practice are combined in something like software and hardware design.

I also did not say there shouldn't be limited forms of protection to enable the license based business model but being able to outmaneuver your competitor legally instead of through proper design and engineering is why progress is hampered and why the patent model is fundamentally broken.

But they didn't. Berkeley RISC predates MIPS and simply punts on the issue of unaligned loads. Other contemporary designs handled them in microcode.

That's fine. Plenty of mathematical theories still have theorems left to prove. It still doesn't change the fundamental and theoretical nature of the discipline. I'm trying to drive the point home that much of hardware and software design is a lot like "a^2 + b^2 = c^2" and patents in that context don't make sense.

In my opinion, you have to distinguish between situations where you use math to evaluate particular points in a design space, and situations where there is a correct solution that follows directly from the math. Most things in software are not examples of the former. They're just different points in a design space of solutions, just like with any other engineering field. The MIPS unaligned load instructions are an example of that. Just one way to do things. Not even a particular good way, considering that they've long been out of patent protection and nobody has implemented them in another architecture.

I have little problem with protection for how MIPS handles unaligned loads; I have a huge problem with the mere existence of that patent making it financially untenable for Lexra to defend an implementation of the same instructions with a trap, something that I hope we can all agree is unfortunate.

Except that Lexra didn't implement unaligned loads at all. According to the post, MIPS considered the mere possibility that you could handle unaligned loads through an OS-level trap that emulated the load - not even in microcode - to infringe their patent and managed to shake up several of Lexra's customers that way. (This is another flaw of patent law. In order for something to count as prior art it has to be identical to the claimed technology, but the same requirement doesn't apply to infringement claims.)

I too think we will eventually come up with something better than capitalism. But until we figure out what that would be, I don't know that throwing out parts of the existing system helps much, even if those are parts we happen to not like.

In particular, R&D is expensive. If patents in hardware don't exist, it's going to be much harder for investors to justify putting in the tens or hundreds of millions of dollars that it takes to start a modern tech company. No patents mean that investment in innovation makes much less sense for startups and small companies, because larger players can use their larger resources and deeper relationships to copy that innovation and crush the innovators.

Another way to look at it: sure, the current system has bad outcomes. But so did the previous system, one without patents. That's why we invented patents in the first place. If you want to persuade people to change, it's not enough to say, "patents bad". You have to propose an alternative and say why the total outcomes under your system are substantially better than the total outcomes under the status quo.

Honestly I think software/hardware patents wouldn't be nearly so problematic if patents expired sooner, say a few years instead of 20. Twenty years is way more than what's needed for the R&D to be profitable.

I have nothing against capitalism but it's a little ironic you bring up patents and capitalism in the same paragraph since patents are almost the antithesis of free form market capitalism. The equivalent in a purely capitalist system I believe is a trade secret which is different from a patent. Companies can have trade secrets but they can't sue each other over them. In fact I think that's the crux of the problem. There is no such thing as a trade secret in software and hardware. As soon as there is an existence proof equivalent implementations are sure to follow.

This goes back to what I've been arguing in this thread. The design space is very limited and the mathematical, physical, axiomatic nature of the field means there are only so many things you can actually design and implement and as soon as it is implemented everyone else can trace back the design to first principles.

As for R&D. Many of the best innovation in computers came from publicly funded projects. So I don't think the commercial nature of modern computing is actually helping anything. We had a system that worked and it was replaced by what we have now. I could just point people to historical precedent but we all know how well that works.

> Companies can have trade secrets but they can't sue each other over them.

Slight nit-pick: they actually can, when a company acquires knowledge of another's trade secrets through underhanded means.

> equivalent in a purely capitalist system

I was using "capitalism" by its common meaning. I understand there are fantasy versions of capitalism that might be different.

> Many of the best innovation in computers came from publicly funded projects. So I don't think the commercial nature of modern computing is actually helping anything.

Basic innovation is wildly different than commercialization. I'm a big fan of publicly funded basic research. But going from a scientific discovery to a commercially usable technology is a) often very expensive, and b) not something that academia is good at.

Personally, I think commercial investment helps quite a bit. Look at the wave of mobile hardware innovation we've seen in the decade since the iPhone came out. That took tens of billions of R&D dollars, and investors and shareholders don't put up that kind of money without expecting to get it back.

No fantasy necessary. In any version of capitalism government enforced monopoly for an idea and implementation is basically not capitalism whether it is fantastical or practical. Most modern democracies have not had any version of capitalism for a long time. The US economic system is more socialist than anything else really.

I also was not arguing for replacing one system with another since that never works out. The new thing ends up being as bad as the old thing but slightly different. I'm arguing for more stringent requirements for patents and higher bars for suing someone based on patent infringement claims. That already goes a long way towards preventing patent abuse.

> shareholders don't put up that kind of money without expecting to get it back.

Therein lies the problem and what I mean by "short term business thinking". MIPS investors could have settled for getting back much less money for their investment but instead they chose the greedy approach and we collectively ended up worse off.

> Most modern democracies have not had any version of capitalism for a long time.

You seem to have an unconventional definition of the word. Again, I am using the common definition: https://en.wikipedia.org/wiki/Capitalism

That said, I'm actually fine with a higher bar for patents.

> MIPS investors could have settled for getting back much less money for their investment but instead they chose the greedy approach and we collectively ended up worse off.

Could you show your math here? I can't find any evidence that MIPS in this incarnation actually returned money to investors. When SGI spun it out, it looks like its market cap was somewhere north of $300m. Eventually it was bought for $100m. I can't find any record of a dividend in between.

I also am not sure you understand how venture capital works. As an asset class, VC doesn't do much better than other investments. The absurdly great hits (e.g., Google) pay for the 80% of companies that don't make it. Without taking the very big payouts on the few successes, it's not clear to me who would put money into VC funds. A lot of their money comes from pension funds, school endowments and the like; those people have long-term obligations to meet. So how do you propose to maintain significant levels of venture funding if it returns "much less money" than it does now?

In that case the whole thing is even sadder. If the venture was doomed from the start they didn't need to bring down everyone else with them.

You seem to think there needs to be a solution to this that somehow maintains the status quo of VC funded ventures. I personally don't. You're welcome to come up with a solution. I'm not the one to brainstorm it with.

Do you understand that Lexra only existed because they were drafting off of work done by MIPS? Without MIPS, there would have been no Lexra to bring down. Both companies only existed because of venture funding and patents.

And MIPS of course wasn't "doomed from the start". The nature of investment is that there are no sure things. Many good bets don't pay off.

I don't particularly care about VC. I care a lot about investment in technological innovation. Your initial claim was that "we'd be much further along" without patents and greed. I'm saying that I don't think that's the case, because patents and greed are two parts of the mechanism by which we move further along.

If you have an alternative that will actually get us "further along", I'm all ears. Feel free to tell us how you'd achieve similar or greater levels of funding in a better world, preferably with some actual numbers. But without that, it sounds like you're just carping.

The biggest issues of the case to me were that MIPS believed that hardware patents cover software emulation and (even assuming that the first case is true) that Lexra could somehow be held responsible for software companies choosing to infringe. It's like holding a car manufacturer responsible because a driver decided to head into oncoming traffic.

I don't understand why these cases weren't immediately thrown out as the garbage they were. MIPS wasn't a mega-corp like Samsung or Apple which can bring lots of pressure on the system. Why did the court make such a boneheaded decision on appeal?

It seems the biggest issue is that you can patent "unaligned loads" in a way that covers both a hardware instruction and software fault handler.

These are very different things. The software fault handler doesn't even do unaligned loads, naturally.

As I understand it, patents cover results and not so much mechanisms. It's just that people tend to listen the intermediate results in such detail as to appear that they cover mechanisms.

Which is, of course, fucking insane, but nobody seems to want to act on that.

If it covers results, what about the virtual ISAs that allow you to load data from any address of a byte-adressed memory and their implementations include optimizations?

The patent doesn't cover the result of an unaligned load. It covers the specific mechanism of doing an unaligned load using two instructions and a shifter to get the two pieces into the right place in the target register. You can read the claims here: https://www.google.com/patents/US4814976.

That the court considered a software implementation of this to also be in violation again underscores how nutzo that is.

All patent appeals go to a special Court of Appeals for the Federal Circuit that is stuffed with IP lawyers and is extremely pro-patents. Their caselaw is filled with numerous nonsensical decisions. Only in the past 10 years has SCOTUS been giving them the equivalent of a spanking, repeatedly taking up patent cases to dismantle the CAFC's decisions.

The Oracle v Google trial ended up there thanks to the patent claims Oracle raised. If you've read their decision in that case it doesn't matter if you believe APIs should be copyrighted... the decision is incompetently written on its face.

> Why did the court make such a boneheaded decision on appeal?

The appeal was never decided. The patent was invalidated at the USPTO. That decision was appealed. Meanwhile, MIPS got a favorable trial ruling, and the whole thing settled before the Federal Circuit heard the appeal.

This is interesting for those of us interesting in squeezing what we can out of older nodes for lower, dev costs or verifiability. Their CPU's did quite a bit for push-button synthesis. The Stream processor linked had impressive capabilities for 130nm. I'm bookmarking it in case it is useful in future.

I was thinking the I.P. might still be useful depending on acquirer until I saw the name: MIPS Technologies Inc. (sighs) I doubt they'll play ball. So, now I think of using its tricks in a RISC-V CPU instead. ;)

In the end, patents only ensure that good things go down the toilet. Why do companies continue making them?

Same reason nations stockpile nuclear weapons.

There is a serious social movement in society against nuclear armament/for nuclear disarmament (in Germany at the beginning of the 80th this even lead to the founding of a completely new party). On the other hand there is no strong social movement against patents.

Sure there is, but it's quite reasonably smaller and/or less visible than a social movement standing against a fundamental existential threat.

Computer Organization and Design by Patterson and Hennessy is still sitting on my shelf, saved from my computer engineering classes at UIUC. It's probably the closest thing I have to a definitive source on the hard limits faced in processor design. IMHO since I graduated in 1999 there has been almost no innovation in processor cores, and in fairness, maybe there couldn’t have been (as the limits were well understood by then).

Instead the industry opted to go with smaller and smaller features which led to skyscraper interconnects that act as much like transmission lines as wires, with deep pipelines and large areas of the chip devoted to branch prediction, large percentages of chip area devoted to cache, niche processing units like GPUs on-chip rather than general purpose DSP for multiprocessing, obfuscated microcode rather than RISC, just layers and layers of cruft that were driven more by demands for single-threaded performance and low power consumption than innovation for its own sake.

So it shouldn’t be any real surprise that Moore’s law died somewhere around 2005, give or take. Computers today are still the 3 MHz they were then, transistor counts have gone up but real-world performance has increased mostly due to faster DDR and SSD, not faster cores. To get an idea of how far behind CPUs have fallen, just look at the throughput of any video card vs, say, a Core i7. We’re talking 3 orders of magnitude better performance for GPUs, about what a decade and a half of compounded transistor count for a multicore architecture would predict.

So it saddens me that there never really were other competitors to CISC for consumers. I wonder if something like an ARM or AMD with a MIPS instruction set aiming for more cores like the Teraflops or Kilocore that ran OpenGL (and TensorFlow and other AI libs had they existed) natively might have done for computing back in the day. But it was a strange time in history after the Dot Bomb. The carpet got pulled out of research at a time when it was perhaps needed most. Everyone had to pull themselves up by their bootstraps and we all became entrepreneurs instead of engineers.

Maybe that’s a good thing, maybe it’s not, I don’t really know. But I do know that we’ve had about a 15 year setback in computing and we are roaming the desert of informal methods on some kind of walkabout or vision quest to see where it’s all headed. Personally, I don’t see any future here if we don’t fix the fundamental problems in patents and intellectual property. It’s fun and everything to be hip about technology but at the end of the day someone has to push the state of the art forward.

I know precisely what I want: as many general purpose cores as possible running as fast as possible with a self-organizing interconnect to as many other computers as possible so I can run the simulations I thought we’d be running by now. I want a stream to that computer, no fancy libraries in my way, no proprietary OS. I want to program it with MATLAB, Erlang, Go, Clojure Haskell, Scala, etc etc etc. I don’t want CUDA, I don’t want to have to lease time from the cloud, I don’t want to have to depend on the largess of billion dollar companies’ research programs to innovate in AI. I may have forgotten the details of how to achieve these things but I haven’t forgotten the original dream of ever-cheaper transistors giving every person access to a supercomputer and eventually R2D2. We’ve scaled data but we simply haven’t scaled processing.

My understanding is that processing power stopped increasing because of heat limitations. Although, there may lie another engineering problem waiting to be solved.

The problem with simple high-performance RISC (and to even larger extent VLIW) designs is that invariably micro architecture details are going to leak into instruction set, either explicitly (branch delay slots, instruction combinations that do not handle hazards, weird memory models) or implicitly in form of micro architecture specific performance traps.

And main thing that seems to be required for general purpose computing is binary compatibility, which can be done almost for free on CISC designs while it makes RISC designs into complex nests of special cases.

Micro architectures that are not designed to directly execute user code (GPUs and such) do not have this problem and thus can do anything that makes the hardware go fast regardless of whether the resulting ISA looks sensible and whether it can be implemented in any other way (eg. drop pipeline stalls and forwarding paths, have separate register set for each execution unit...).

Another thing that limits general purpose CPUs is multitasking as it requires context-switches to be reasonably cheap, which means reasonably small and accessible architectural state (ie. not hundreds of architectural registers).

It sounds horrible that we should compromise potential performance (including per watt and per transistor) by giving up on (micro)architectural flexibility. Why should branch delay slots, instruction combinations that do not handle hazards and weird memory models matter in an era in which something like IBM's TIMI could be used for compatibility if you need it, and native ISA accessed if you don't or if you have your own toolchain?

That seems to be caused by market forces. Customers expect CPU's that are backward compatible by themselves and do not depend on few tens of MB worth of binary blobs for backward compatibility, microcode of modern x86 CPUs does not count as such blob as it's essentially invisible (it can be patched, but the CPU still looks like x86 when you don't load any blobs into it). (edit: it's also probably immaterial whether such blobs are or are not opensource)

Also, TIMI is probably not good example of how to implement high performance ISA abstraction as it's about abstraction first and performance second. Transmeta's x86 CPUs and things like HP Dynamo have better approach to this problem.

Theoretically, if Mill isn't vaporware, its plan is to distribute binaries in a format independent of certain hardware implementation details, and have a "specializer" in the BIOS or kernel to compile from the generic instruction set to the machine-specific instruction set on demand, reordering operations and grouping them into instructions, inserting delays, and spilling belt (register) contents to on-chip RAM where necessary.

Essentially, the idea is to move all the CISC stuff out to software, and do VLIW internally. That could possibly help?

My feeling is that processor development essentially came to a halt because the fruits of Moore's law were being used to design an ever "better" core that looked for all the world like a single core sequential machine. Was compiler technology holding back the hardware?

I think the best way forward is to tightly integrate simple rigidly multi-threaded processors (where the stages of the pipeline ARE the threads - barrel processing) into the memory itself. Screw all the caching, interconnect, branch prediction, etc. - what has is done for us lately?

> Screw all the caching, interconnect, branch prediction, etc. - what has is done for us lately?

What have the Romans ever done for us?

- caching: better performance; performance critical code is mostly memory constrained (your CPU is waiting for stuff), so huge caches are huuuge. I think "cache-friendly" code is one of the most important features in code for modern HW.

- branch prediction: again, performance; low-level code is filled with branches that check for mostly unlikely, but nevertheless critical events; if I am correct modern designs go many miles to achieve a high prediction-score

However I agree with you that a different approach might be a good idea that is maybe more useful for modern languages.

> [...] is to tightly integrate simple rigidly multi-threaded processors [...]

AFAIK this has been tried, but the "integrating" or connecting is far from trivial. I've read about a newish design called the Mill (it was on HN some years ago) and it sounded really interesting. Actually, I have to check how far they progressed, last time it was still not production ready and in simulation stage.

//edit: http://millcomputing.com

> We’re talking 3 orders of magnitude better performance for GPUs, about what a decade and a half of compounded transistor count for a multicore architecture would predict.

> I wonder if something like an ARM or AMD with a MIPS instruction set aiming for more cores like the Teraflops or Kilocore that ran OpenGL (and TensorFlow and other AI libs had they existed) natively might have done for computing back in the day.

Intel tried to replace the GPU by lots of cores in the Larrabee project. This project was not as successful as imagined. It was realigned and the result is the Xeon Phi.

Agreed about moore's law - but you mean ghz rather than MHz, right?

Right, meant to say 3 GHz, sorry about that!

> An instruction set is a language of commands given to a machine. Nobody can patent, copyright, or otherwise own a language or an instruction set.

This is wrong. Intel owns patents which protect the Itanium ISA. Non-Intel Itanium implementations would infringe on the patents, not that anyone would want to make one.

Intel also has patents on many x86_64 extensions and AMD has patents on x86_64 itself. I believe MMX expired recently, so a Pentium III level CPU could be implemented without infringing on ISA patents.

Hitachi still has patents on SH4 (though they expire this year). IBM has patents on POWER8. Oracle and Fujitsu have patents on SPARC. etc.

Incidentally, I believe HP also owns some of the Itanium patents.

I'd love to see a detailed write-up on how an ISA is protected. I've never really understood what protects the x86 instruction set. I'd always assumed there were patents covering implementation details which would make an effective implementation extremely difficult.

Can you really patent a list of instructions?

Intel's ISA is protected by fear of its army of lawyers, something from which no small company could (financially) survive a head on attack.

I worked on an x86 clone 20 years back, we analysed Intel's patents in depth to make sure we were safe, the biug one for us was Intel's segmentation/MMU patent - they essentially had patented segmentation followed by (unrelated) mmu processing - there was obvious prior art (cough 360, cough) but that's a bit of crap shoot, I came up with a brilliant way around this, only to discover a patent from someone else in the process of doing an x86 clone (Exponential I think). In the end we conflated our segmentation hardware and our TLBs effectively bypassing the core of Intel's patent

You can't patent a list of instructions, you can copyright a bunch of mnemnomics

That's really interesting thanks! I wonder if the army of lawyers protection also holds for ARM. Or perhaps there licenses are cheap enough that people don't care.

The article explains:

> Though you can not patent an instruction set, you can patent machines and methods that are necessary to implement a particular unusual instruction that is part of the instruction set. That legally blocks competitors from creating a fully compatible clone of your processor.

The author is making a very clear and correct distinction.

It continues:

> There are four instructions in the MIPS-I instruction set that were protected by one US patent, 4,814,976. These instructions, lwl, lwr, swl, and swr are known as the unaligned load and store instructions.

Reply on news.ycombinator.com