Computing 10,000X more efficiently (2010) [pdf]

http://web.media.mit.edu/~bates/Summary_files/BatesTalk.pdf

by luu • 12 years ago

134 58 12 years ago

web.media.mit.edu

It would be nice to see where he is with this now - that was 2010 and it appears nothing has been written since about it.

ChuckMcM2• 12 years ago

An update from 2013 apparently : http://www.bdti.com/InsideDSP/2013/10/23/SingularComputing

hoilogoi• 12 years ago

It would be funny if a technology pioneered by "Singular Computing" were a primary contributor to reaching the Singularity.

ChuckMcM2• 12 years ago

This guy went on to found a company as I recall, which I think was then acquired. Its a pretty clever way to make fast floating point.

hershel2• 12 years ago

Who did squire them ?

IvanK_net• 12 years ago

This guy is totally stupid. I just read 4th slide.

1% error - what that means? Error in mantissa? Shorter mantissa? Simplified IEEE?

He writes O(5K) and presumes it to be "better" than 500K ... wtf? Does he know what O() means?

So, he basically "rounds" the values in images, mentions some recent technologies and says "if we had better engineers, we would have flying cars blah blah blah ...".

varelse7• 12 years ago

This design is utter computational tripe that completely ignores Amdahl's Law or any notion of data-parallelism.

His 1% error comes from relying on 7-bit logarithmic floating point used in a task-parallel manner. This is a non-starter for HPC. While most theoretical models certainly have 1% or greater underlying errors in accuracy, a 1% or worse error in precision is going to doom these algorithms to numerical instability without Herculean additional effort that would obliterate the computational advantage here.

Neural networks? See The Vanishing Gradient Problem.

Molecular dynamics? It's numerically unstable without 48-bit or better force accumulation as proven by D.E. Shaw.

NVIDIA, AMD, and Intel have invested a huge sum in manycore processors that are already too hard to program for most engineers. These processors are a cakewalk in comparison to what's proposed here.

Finally, even if you did find a task amenable to this architecture (and I'd admit there may be some computer vision tasks that might work here), where's the data bus that could keep it fed? We're already communication-limited with GPUs for a lot of tasks. Why do we even need such a wacky architecture?

thisisdave3• 12 years ago

Neural networks? See The Vanishing Gradient Problem.

For what it's worth, Geoff Hinton and others have had a lot of success in the last few years by intentionally injecting noise into their neural network computations. The best-known example is [0], but he's also had some success just adding noise to the calculation of the gradient in good old sigmoid MLPs--even reducing the information content of the gradient below a single bit in some cases.

Going back further, stochastic gradient descent and other algorithms have shown for decades that trading accuracy for speed can be very desirable for neural network computations.

[0] http://arxiv.org/pdf/1207.0580.pdf

jblow2• 12 years ago

Computational approximation has been shipped en masse very successfully.

You mention GPUs but did you know that GPUs already do a lot of approximate math, for example, fast reciprocal and fast reciprocal square root?

You mention how approximation must be impossible in all these applications (because REASONS) but all methods that numerically integrate some desired function are doing refined approximation anyway. If you have another source of error, that lives inside the integration step, it may be fine so long as your refinement is still able to bring the error to zero as the number of steps increases.

Your diagnosis of "utter computational tripe" and the accompanying vitriol seem completely inappropriate.

Houshalter3• 12 years ago

Neural networks? See The Vanishing Gradient Problem.

Only on deep networks. And as another comment mentioned, NNs can withstand and even benefit from noise.

There are numerous ways around it was well. You could just run the network several times (probably in parallel) and average the results together. Same with most of the other problems. It does defeat the purpose a little bit, but it would still retain most of the speed up. You could train multiple networks and average them together (also very successful even in deterministic nets.) Perhaps the network itself could be made more redundant or error tolerant.

Hell if the thing is as fast as promised, you could even do genetic algorithms and get reasonable performance.

slashcom• 12 years ago

Shit HN Says: the adjunct professor at CMU who's designing floating point hardware for processors is "totally stupid."

I'm guessing he intentionally underspecified for his audience, and if asked, could tell you in excruciating detail what 1% error means.

But skimming the patent [1], it seems that there's sometimes an error in a mathematical operation, measured as the computed value minus the expected value. The result doesn't seem surprising if you read how he defined addition in his hardware.

[1] http://www.google.com/patents/US8150902

jblow2• 12 years ago

O() is colloquially used to mean "approximately", among people who do actually know what O() means.

pointernil• 12 years ago

I understand the speed and energy efficiency of the proposed design can only be reached with specially designed hardware, but couldn't some of the expected effects be achieved on existing cpu-core-hardware designs by using the lower precision requirements?

Also this could be nice code golf idea: solve algorithm xyz only with a strictly limited cpu instruction set, which could be chosen to be those operations which are very quick resp. very energy efficient on a target platform...

trhway• 12 years ago

specifically it would be interesting to compare GPU (instead of classic CPU) vs. proposed imprecise approach

squigs25• 12 years ago

I think human brains are probably wired for speed over accuracy too. This might have a lot of potential in machine learning and eventually AI, where information processing speed is often more important than accuracy.

daenz• 12 years ago

If you believe in evolution and natural selection, then your functionality is just fast and accurate enough to keep you from dying before mating. That's as good as the optimization gets, except by random accident.

lkbm• 12 years ago

My genes are more likely to be passed on for multiple generations if I survive long enough to mate AND care for my children. If thy die at age five, my mating did nothing.

mistercow• 12 years ago

then your functionality is just fast and accurate enough to keep you from dying before mating

Approximately. And locally.

russell• 12 years ago

I believe that the theory of evolution by sexual selection is far more important. Same guy, a refinement on his original theory. In that case optimization can take many different forms. Parents arraigning marriages of children or reverence for grandmothers. Or for that matter, the old boy's explanation of peacock feathers.

nooron• 12 years ago

If you find this topic interesting, Robert Nozick's "Invariances: The Structure of the Objective World" explores how this fact should affect epistemology and ethics.

It's a tough book but it's worth your time.

acd• 12 years ago

There is probably an efficiency reason the human brain has 85 000 000 000(85 billion) neurons that operate with lossy compression operate in parallel drawing less than 20W of power.

varelse7• 12 years ago

Each neuron in the human brain has ~10^4 connections to nearby neurons. This makes it an insanely data-parallel computer. This PoS is a task parallel nightmare.

byerley• 12 years ago

Probably more relevant is the greatly reduced clock speed (ignoring that the brain doesn't so much have a centralized clock - neurons only fire at <1k Hz compared to the ~2k Ghz processors used in clusters).

The technology also seems somewhat incomparable. The purely chemical signal processing at the synaptic cleft presumably saves a lot of power.

agumonkey• 12 years ago

maybe it's more a throughput thing, if the brain is massively parallel, it's a giant pipeline with many things in flight all the time

ced• 12 years ago

Off-topic: if an integral is an approximation of a physical process, then that process is an approximation of the integral. I.e. we could in principle have a "chip" running a miniature lab experiment (like water flowing) with sensors that would output "an approximate solution of the Navier-Stokes equations". Numerical analysts would then write new versions of their algorithms assuming "an efficient hardware solution of N-S". Has this concept ever been used anywhere? I guess quantum computing would qualify.

thisisdave3• 12 years ago

Yes, but it's been largely displaced by digital computation: http://en.wikipedia.org/wiki/Analog_computer

hcarvalhoalves• 12 years ago

I.e. we could in principle have a "chip" running a miniature lab experiment (like water flowing)

It looks like this is a thing:

http://en.wikipedia.org/wiki/Fluidics

http://en.wikipedia.org/wiki/Water_integrator

http://en.wikipedia.org/wiki/MONIAC_Computer

anigbrowl• 12 years ago

Analog computers used to be a thing. If you want to get into this now it's actually a good time, thanks to the resurgence in modular synthesizers, which are just analog computation optimized for audio ranges. You can easily find modules specifically for math operations and so forth.

smoyer2• 12 years ago

We used to use a carefully biased diode in the feedback loop of an op-amp to create logarithmic signals. I was expecting the article to dispense with digital electronics (in the core of the machine) and use tuned physical properties to actually do the calculations.

What a disappointment that the first few slides imply such a break-through and then we find that the research is simply about reducing precision to the minimum needed. And it's patented? (rolls eyes)

foxhill2• 12 years ago

it's patented? 16 bit floats have been a thing for a long time.. :/

edit: never mind. somehow convinced myself that this was just 16 bit floating point arithmetic. it is not.

foxhill2• 12 years ago

you'd have to write a solver for this special hardware, which may see your performance disappear. double precision is usually required for N-S solvers. accounting for errors means injecting noise and averaging (probably) over multiple iterations.

to get 64 bits of precision where only 16 bits are available would be.. tricky.

that said, with 1M PEs on a chip.. i'd definitely give it a go.

source: GPU+CFD are my thing.

edit: seems there is even less than 16 bits of precision available..

dfc2• 12 years ago

Can anyone explain what page eleven, "Tomography," is supposed to mean? The example on the previous page seemed straight forward, when I got to page eleven I had no idea what I was looking at.

vladtaltos• 12 years ago

radon transform is used to produce tomography images. just take a look at the wikipedia page... s/he's talking about that...

dfc2• 12 years ago

I guess(??) I could have been clearer.

I understand what tomography is. I am curious how to interpret the three images and the differences. What does this page demonstrate to the reader? To me they look almost exactly the same. The one big difference is that the original has the the intersecting arrows. (I am also not really sure what the arrows are supposed to convey.)

hershel2• 12 years ago

Singluar computing have built a chip based on this tech, and deployed in a military UAV. It enabled tracking of objects(which ws impossible before due to power constraints), at 6400x the performance/power of other best known methods.

http://www.defensetechbriefs.com/component/content/article/1...

http://proceedings.spiedigitallibrary.org/proceeding.aspx?ar...

From the paper: "The hardware is designed to perform high dynamic range arithmetic with roughly 1% error per operation. Singular has developed and studied varied algorithms for producing high quality results despite the approximate hardware. These studies use a perfect simulation of the accelerator’s arithmetic. Tasks that have been explored include summing thousands of numbers without accumulating error, k-nearest neighbor classification (KNN), foreground/background separation using Gaussian mixture models, iterative reconstruction tomography, deblurring using the Richardson-Lucy deconvolution algorithm, FFTs, radar processing, neural net learning, and other tasks. Most of these algorithms need slight adaptations to prevent cumulative effects of the 1% error, but with those adaptations all perform as desired."

samstave• 12 years ago

And these are precisely the things, which we know little, that the NSA may be exploiting with extreme effectiveness that scares the shit out of me.

I recall an article from 2005 that described a system that could track BULLETS IN MID FLIGHT over a vast swath, in-the DARK, which provided detailed view in all ballistics in a fighting theater....

m_darkTemplar• 12 years ago

It's probably not of much use to the NSA where breaking encryption requires precise math that will fail quickly if operations are off by 1%.

valarauca1• 12 years ago

This topic was already discussed albeit satirically in another publication. Namely the, "The Slow Winter."[1] Which while comedic makes good points about hardware architecture.

[1] https://www.usenix.org/system/files/1309_14-17_mickens.pdf

GFK_of_xmaspast2• 12 years ago

1% error is, in some sort of half-assed sense, comparable to a signal-to-noise ratio of -40dB which strikes me as a lot of noise to be adding to a problem.

throwaway_yy2Di• 12 years ago

I think this guy successfully patented half-precision floating point. No really, look:

http://www.google.com/patents/US8150902

What a troll!

jejones3141• 12 years ago

Reminds me of Albert Edgar and Samuel Lee's paper in CACM in 1979, "FOCUS Microcomputer Number System".

fenollp• 12 years ago

This HW is a lot like [the Parallella's](http://www.parallella.org/)

Computing 10,000X more efficiently (2010) [pdf]

Related Stories