Microsoft Files For 3 Parallel Processing Patents

theodp writes "Microsoft may have been a Johnny-come-lately when it comes to parallel programming, but that's not stopping the software giant from trying to patent it. This week, the USPTO revealed that Microsoft has three additional parallel-processing patents pending — 1. Partitioning and Repartitioning for Data Parallel Operations, 2. Data Parallel Searching, and 3. Data Parallel Production and Consumption. Informing the USPTO that 'Software programs have been written to run sequentially since the beginning days of software development,' Microsoft adds there's been a '[recent] shift away from sequential execution toward parallel execution.' Before they grant the patents, let's hope the USPTO gets a second opinion on the novelty of Microsoft's parallel-processing patent claims."

Comments

Pain of Patents is in the reading

[phantomfive]

I can't imagine anyone making a living off of reading software patents. Every time I read them, I think to myself, "whoever those patent examiners are, they are not getting paid enough." The only way you could enjoy writing those things is if you liked giving people pain, and were dreaming of how much you actually were going to hurt the poor examiner.

After reading through the claims in the third patent, I honestly can't see how it is different than the producer/consumer program I wrote my Junior year. They seem to imply that it might be applied to a database, but I couldn't find where it actually specified it (of course the pain of what I was doing somewhat distracted me). Can anyone else see anything in there that is different?

The first patent looks kind of interesting, inasmuch as it seems like they are applying it to a database, and I know of no database that actually does a single query in parallel, but I'm not sure it would be any more efficient, because there is only one disk. Having two threads isn't going to speed anything up there, and might actually cause the disk to thrash.

Re:Pain of Patents is in the reading

[shutdown -p now]

The first patent looks kind of interesting, inasmuch as it seems like they are applying it to a database

I don't think so. From reading the claims, it seems to be quite obviously a patent for Parallel LINQ to me - it specifically covers all LINQ operators one by one. And PLINQ isn't for databases - it's for in-memory data. Essentially, it's just map/filter/fold/join on arbitrary sequences with automatic parallelization.

Though I don't see why it wouldn't be just as applicable to databases (which are, after all, just advanced implementations of the above).

I know of no database that actually does a single query in parallel, but I'm not sure it would be any more efficient, because there is only one disk.

Records aren't read from disk one-by-one - they are usually read in pages, and once in-memory, it's obviously faster to e.g. filter rows in parallel on as many cores as there are available. Doing it for a simple SELECT .. WHERE .. is trivial. The trick is to get it right for operations involving joins, grouping, and ordering, with arbitrary sequencing and possibly nesting. Which, if I understood correctly, is what the patent is about.

Anyway, for a shared-use RDBMS, it might be moot, because it usually has more than one query to process at any given time - and so it's easy to load-balance all cores just by assigning queries to them.

Re:Pain of Patents is in the reading

[KeithJM]

I know of no database that actually does a single query in parallel, but I'm not sure it would be any more efficient, because there is only one disk

There is more than one disk. Remember we're not running databases on your laptop. The first time I saw one table spread out over multiple disks it was an Informix database and the feature was called Fragmentation. I believe SQL Server calls it sharding. Once you do that, it's easy enough to do your queries in parallel. Informix not only let you roughly configure how many threads and how much memory to use for parallel queries, but it did all of this over 10 years ago. Here's a link to the relevant documation: http://docs.rinet.ru/InforSmes/ch20/ch20.htm#Heading4

Re:Pain of Patents is in the reading

[Dachannien]

The pay is fairly competitive (as government jobs go, at least) with industry jobs. Starting salaries are close to average, ranging from $50k to $70k, depending on your incoming level of experience/education, although you do have to live in the DC-VA-MD area, which can be fairly expensive (though not as bad as Manhattan or Silicon Valley, for instance). If you stay long enough, you can hit the federal salary cap (about $150k). It's also tough to beat government bennies. The question is whether you like the work and can deal with the production environment.

Examiners are responsible to get a certain number of "counts" per pay period. You get a count by sending out a first Office action for an application (on the merits - there are certain Office actions which don't count for this). You also get a count when an application is disposed of (abandoned, allowed, upon writing an Examiner's Answer when the applicant is appealing your decision, or upon the applicant filing a Request for Continued Examination).

The problem is that there are Office actions that don't earn you counts, but that still require a decent amount of work. Your second Office action on a case doesn't earn you a count, and if you screwed up the first one, you may not be able to make the second one "final" (after final, if you did your Office action correctly, the applicant is only able to appeal or file an RCE, so you usually get a count after a final action within 3 to 6 months).

What this amounts to is a fairly grueling workplace starting at about six months (once your "basic" training is mostly complete) to about 1.5 to 2 years, because in the interim, you're doing a lot of Office actions that don't earn you any counts yet. Once your pipeline gets full, i.e., all those extra actions you sent out are finally netting you some disposal counts, the workload tapers off, and if you're good at the job, you'll pretty much sail through and get your promotions and bonuses easily at that point. But in the meantime, you'll probably be working a lot of unpaid overtime to make production.

The production system is why the turnover at the USPTO is so high. Most examiners who leave cite it as the biggest factor in their decision to quit. Not coincidentally, most examiners leave within their first two years. If it were fun like programming games or something, then people would probably grin and bear it, but it's kind of not. You'll learn a lot about the technology (or "art") you're examining in, but most of this learning will come from searching the prior art rather than from reading the applications you're examining, because attorneys (most of whom have a basic science or engineering background) write most of these things (and frequently, they are mediocre translations from Japanese or Korean), and the legal aspects make the obfuscations practiced by the attorneys into an artform.

Still, some people like it, and they stay at the USPTO until they retire. I haven't figured out why yet.

Re:Pain of Patents is in the reading

[Anonymous Coward]

I know of no database that actually does a single query in parallel, but I'm not sure it would be any more efficient, because there is only one disk.

Many Databases (Teradata, DB2, Oracle and even Microsoft - leaving out startups like Greenplum, AsterData etc.) have parallel queries to allow execution of a single query by many processes/threads simultaneously. Research on this began in the 80s (DeWitt's Gamma for e.g.) so there are many well understood techniques. And really, saying databases only have one disk is a little bit of a stretch. Many (maybe most) commercial database implementations will use many disks for a single database

Re:pffff

[Anonymous Coward]

Try programming in linux for one day and then throw parallel processing into it.

Linux isn't a programming language. And if you think Microsfot is "light years" ahead of everyone else, you're severely misinformed.

Re:pffff

[Hillview]

I may be wrong, but I believe the article was referring to the fact that parallel processing has been around since before Microsoft existed. Of course, Following the Links and perhaps a little research of your own will provide further insight.

Re:pffff

[Cyberax]

"Try programming in linux for one day and then throw parallel processing into it. then throw in some data."

Funny, but I do this every day. Say, does Windows support zero-copy Infiniband links? How about MPI performance? How about fire&forget clustered processes?

Re:pffff

[shutdown -p now]

I think that GP was referring to some stuff that isn't out of beta yet:

Parallel LINQ (for .NET)
Parallel Patterns Library (for native C++)

Obviously, this stuff didn't have a chance to have any significant effect yet, and won't until first stable versions are released.

Can you spell "MapReduce" Microsoft?

[itsybitsy]

Strange I was just researching MapReduce online when this slashdot posting appeared.

http://www.cs.vu.nl/~ralf/MapReduce/paper.pdf
http://cnx.org/content/m20644/latest/
http://en.wikipedia.org/wiki/MapReduce
http://en.wikipedia.org/wiki/Google_File_System

Patent examiners need to get their heads examined.

Patents, a strange concept anyhow to have a government imposed monopoly. Revoke your governments power to have patents. That should take care of the pesky problem. Prior art helps too.

Re:pffff

[K. S. Kyosuke]

You keep hearing, but you not watching? A preview of Data Parallel Haskell is a part of GHC 6.10. I guess they just need more time, people and/or money - the scope of their project seems to be much broader. Oh, and BTW, the `par` operator has been a part of GHC for quite some time. The very idea, though, is much older, and as the link claims, in 1996, a language with these features had been already in use for three years.

Microsoft is only doing here something they are good ate: shrink-wrapping a technology for the average consumer. I would argue that many developers *can* be classified as consumers. While there is nothing inherently bad with this, it is does not exactly made these patent applications right, either.

Re:pffff

[Cyberax]

PureMPI is _slow_, it's managed and it can't work with raw links.

Windows does _not_ support process migration, clustering services is a different beast (comparable to JBoss Clustering - http://www.jboss.org/jbossclustering/ ).

Also, Windows has no good clustered filesystems (like OCFS2 in Linux). And no analogs of DRBD.

So you can use Windows for parallel processing, but Linux is almost(?) always better for HPC.

Re:Rules of the Game

[hubert.lepicki]

As a software developer and small player in this market i must agree. I don't use Microsoft's products, nor I make living from selling/using them, but that doesn't change the fact you can't criticize Microsoft for playing the rules of the game.

However, what you can blame Microsoft for is not trying to change the rules. They seem to be happy with things the way they are. I won't bring quotes from Bill Gates from past saying software patents is stupid, just go and google it.

The same applies to IBM and other big vendors, possibly with the exception of Sun and Novell (but go and figure out how these two ended up...).

These companies lobby very successfully in favor of software patents. They act together, as a team. They profit from their actions and other companies suffer. I can't think of different way of naming it than a CARTEL.

They are doing this different way than other cartels do. They are not fixing prices, but use law system to enforce their privileged positions and make life of other companies much more difficult and - most important - expensive. This means their products are also more expensive, and here is real intention of having software patents system in place - not to allow new players to enter the game. This is a cartel, but I don't know if EU/US governments will ever realize it.

Some kind of timewarp.

[Anonymous Coward]

Having worked at Teradata, where Parallel Data Processing is the life and breath, how does Microsoft expect to add 'data' in front of parallel processing and expect to own it? Teradata's prior art begins in '79. I'm not sure, but wasn't Microsoft incorporated after that?

Really. Can't the Patent Office bill applicants with actual, putative and stupidity costs to stop such bullshit filings?