Fast Database Emerges from MIT Class, GPUs and Student’s Invention • Hacker News Board

Re: Fast Database Emerges from MIT Class, GPUs and Student’s Invention

#41

Post by corresation » Wed, Apr 24, 2013, 12:18 AM UTC

Someone wrote: post #40

corresation wrote: post #37

Fantastic project, and this absolutely sounds like an embarrassingly parallel processing task. To the original itch, so to speak- "Then he plotted the Islamist indicators from 40 million tweets, ranging from August 2011 through March 2012, against 5,000 political districts from the Egyptian census." So the core problem is that you have 5,000 non-overlapping polygons and you want to determine from an x,y which they fa…

Let's assume a naive approach. Also, assume each point falls within a polygon. For every point to test, you need, on average, to test half the polygons. Testing a point against a polygon means testing the point against, on average, about half the polygon's edges. Each of those tests takes a multiplication, an addition, and a comparison. That's 4E7 points times 2500 polygons times, at least, 1.5 edges. Total: 1.5E11 m…

It really is a fascinating sounding problem and I'd really like to see the source data (regions and points), if I'm understanding the problem right, to discern alternative approaches.

Re: Fast Database Emerges from MIT Class, GPUs and Student’s Invention

#42

Post by im3w1l » Tue, Apr 30, 2013, 4:25 PM UTC

Groxx wrote: post #39

im3w1l wrote: post #38

Why are CPU's built like CPU's and not like GPU's? I mean this running things on the GPU business clearly means that the CPU does not meet the needs of programmers adequately. Shoehorning things to run on the GPU seems to me a dirty hack, indicating that there is an underlying problem that could and should be addressed in a better way.

Because most consumer software is not as insanely parallel as doing millions (billions?) of isolated lookups. If you ran most applications on the GPU, you'd see something like a 1000x slowdown because you're only able to use a single path (instead of hundreds / thousands at a time), and each path is way way slower than your average CPU.

>Because most consumer software is not as insanely parallel as doing millions (billions?) of isolated lookups.

I think this is more due to tradition than due to necessity. But I have no hard data and sources for this.

Re: Fast Database Emerges from MIT Class, GPUs and Student’s Invention

#43

Post by Groxx » Tue, Apr 30, 2013, 6:53 PM UTC

im3w1l wrote: post #42

Groxx wrote: post #39

Earlier quoted context omitted.

Because most consumer software is not as insanely parallel as doing millions (billions?) of isolated lookups. If you ran most applications on the GPU, you'd see something like a 1000x slowdown because you're only able to use a single path (instead of hundreds / thousands at a time), and each path is way way slower than your average CPU.

>Because most consumer software is not as insanely parallel as doing millions (billions?) of isolated lookups. I think this is more due to tradition than due to necessity. But I have no hard data and sources for this.

I doubt this is so. Lots of consumer software ends up being I/O bound, not CPU bound - even if they were completely rewritten to be crazy-parallel, you wouldn't notice. Good portions of games could probably be parallelized significantly more than they are, but they're quite a bit different than most software, so that's not very indicative.

Then there's stuff like parsing data. Lots of times data is context-sensitive - that "" could be a tag, or it could be wrapped in ]]>. Without reading through it in order, you can only make certain assumptions. Some of this can be redone in a more parallel-friendly way, some of it is not so much - if it's encrypted or compressed, you're probably forced to pre-process it sequentially, or lose some of the quality of the security / compression.

For those (and think of how much crypto and compression there is in consumer stuff! Every SSL web endpoint, secure wifi connection, zipped file...), a powerful-core CPU or a custom piece of hardware (that only does a few algorithms) is your only option.

Re: Fast Database Emerges from MIT Class, GPUs and Student’s Invention

#44

Post by im3w1l » Wed, May 01, 2013, 10:20 AM UTC

Groxx wrote: post #43

im3w1l wrote: post #42

Earlier quoted context omitted.

>Because most consumer software is not as insanely parallel as doing millions (billions?) of isolated lookups. I think this is more due to tradition than due to necessity. But I have no hard data and sources for this.

I doubt this is so. Lots of consumer software ends up being I/O bound, not CPU bound - even if they were completely rewritten to be crazy-parallel, you wouldn't notice. Good portions of games could probably be parallelized significantly more than they are, but they're quite a bit different than most software, so that's not very indicative. Then there's stuff like parsing data. Lots of times data is context-sensitive…

>I doubt this is so. Lots of consumer software ends up being I/O bound, not CPU bound - even if they were completely rewritten to be crazy-parallel, you wouldn't notice.

So for these programs it wouldn't matter either way.

>Then there's stuff like parsing data

How many states can you be in exactly? You can be in a CDATA, you can be in a quoted attribute, you can be in a tag, you can be between tags. Most other states are very local such as ampersand declarator ( &l ) , tagname started ( I suppose you are right about compresssion and crypto.