Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Paul Graham argues that:

It would be great if a startup could give us something of the old Moore's Law back, by writing software that could make a large number of CPUs look to the developer like one very fast CPU. ... The most ambitious is to try to do it automatically: to write a compiler that will parallelize our code for us. There's a name for this compiler, the sufficiently smart compiler, and it is a byword for impossibility. But is it really impossible?

Can someone provide a concrete example where a paralellizing compiler would solve a pain point? Web-apps don't appear to be a problem: just run a bunch of Node processes. Real-time raytracing isn't a problem: the programmers are writing multi-threaded, SIMD assembly language quite happily (indeed, some might complain if we make it easier!). The holy grail is to be able to accelerate any program, be it MySQL, Garage Band, or Quicken. I'm looking for a middle ground: is there a real-world problem that you have experienced where a "smart-enough" compiler would have provided a real benefit, i.e that someone would pay for?

A good answer is one where there is a process where the computer runs at 100% CPU on a single core for a painful period of time. That time might be 10 seconds, if the task is meant to be quick. It might be 500ms if the task is meant to be interactive. It might be 10 hours. Please describe such a problem.

Really, that's all I'm looking for: candidate areas for further investigation. (Hence, raytracing is off the list because all the low-hanging fruit have been feasted upon.)

I am not interested in why it cannot be done. There are a million people willing to point to the sound reasons why it cannot be done. Such answers are not useful.

share|improve this question
11  
Most problems are impossible to parrallelize. And that's it, the argument is moot. –  Coder Mar 20 '12 at 21:33
5  
Webapps and raytracing (which, BTW, is not what graphics cards do) are problems in the "embarrassingly parallel" class. –  Michael Borgwardt Mar 20 '12 at 22:11
4  
from recollection moore's law says nothing about the performance of software running on a chip so the trivial answer is that compiler advances do not effect moore's law at all –  jk. Mar 21 '12 at 12:03
2  
@jk FTA: "The last 10 years have reminded us what Moore's Law actually says. Till about 2002 you could safely misinterpret it as promising that clock speeds would double every 18 months. Actually what it says is that circuit densities will double every 18 months. It used to seem pedantic to point that out. Not any more. Intel can no longer give us faster CPUs, just more of them." –  jamie Mar 21 '12 at 14:54
3  
In Haskell you are able to annotate data that could be evaluated in parallel without causing non-determinism. This is possible because Haskell is pure and hence reordering computations cannot change the result. It is very difficult to decide what should be run in parallel; it's very easy to lose any gains due to excessive bookkeeping. Furthermore, it's only where the authors of programs have paid attention to data dependencies that they have been able to effectively parallelize their code. The sufficiently smart compiler would have to redesign your code in order to make significant gains. –  dan_waterworth Mar 21 '12 at 16:02
show 2 more comments

8 Answers

Scientific computing has many fields where programs can be parallelized, but not easily. One particular example is linear algebra, another fluid dynamics. Parallelizing compilers in these areas are the subject of active research.

share|improve this answer
add comment

Actually I did ray tracing for many years. Writing SIMD code is not the same as utilizing multiple cores. Compilers can now "vectorize" a lot of code that previously was done by hand and use the SIMD instructions. For my own efforts I went with OpenMP which allowed the outer loops to be run in parallel on many cores (doing ray per pixel stuff). This could be done automatically by a compiler if it did a LOT of analysis. It turns out that the parallel threads all access the data structures but do not modify them (no side effects), so with much analysis a compiler might decide that the loops could be run concurrently. That is not usually the case and when it is people will probably know it anyway.

Since people have a hard time making parallel programs, I suspect a general algorithm will be hard to find. The trivial cases already have simple tools to help.

From what I understand functional languages should be more parallelizable since they allegedly have no side effects and no state. That sounds like lots of things that could be run in parallel.

share|improve this answer
    
I'd ruled out raytracing for two reasons. First, as Michael Borgwardt observes, raytracing is "embarrassingly parallel". Secondly, raytracing is at the point where "optimizations" are more about algorithmic solutions (e.g. photon mapping). –  jamie Mar 21 '12 at 2:17
    
My point was that RT is easy and already has reasonable solutions. I did mention that it could automatically be done for RT if the compiler did the appropriate analysis. Any solution must handle the easy stuff at a minimum and must go beyond that to be a worthy product. –  phkahler Mar 21 '12 at 20:35
    
I disagree. My question asks for low-hanging fruit. I suggest that RT research has progressed way past the low-hanging fruit stage and well into the staggeringly hard-coded stage. I attended IEEE RT08 and most every presentation was quite specific. I'm not saying that the ideas presented could not be used by an automated system: I'm saying that the best minds are already engaged, and they're a high bar to beat. –  jamie Mar 21 '12 at 20:59
    
While the compilers do vectorization, AFAIK they do not automatically insert parallel code constructs via OpenMP for example - you have to do that by hand, but it's fairly easy for people. So I consider that low hanging fruit for a tool that does not exist yet. Once implemented and shown to work for RT, it might find use in other applications where people don't realize there is an opportunity to make things parallel. –  phkahler Mar 21 '12 at 21:08
    
So you are saying, if it works at all, it should easily be able to spot that RT is trivially parallelizable. I'm inclined to agree. –  jamie Mar 21 '12 at 21:37
add comment

The trouble is in the more mundane fields of computing for which the majority of programs are written:

  • calculating interest

  • adding sales tax to a bill

  • routing an e-mail

  • liking a picture of a puppy etc.

don't lend themselves to the type of parallel processing used for simulating a hydrogen bomb explosion, or, predicting the path of a hurricane.

For these types of tasks you need to run the logic sequentially to get the correct result. You can however run several individual tasks in parallel, to maximize hardware utilization. This has been common practice even before SMP machines were conceived, and, there is a vast amount of software out there dedicated to running several tasks in parallel from the ancient and venerable CICS, to java EE, and specialized servers like Apache and ASP for web serving.

There are several languages which have features/architectures to aid multi-threading and parallel execution going back to PL/1 recent notable examples are Erlang, Scala and Go.

share|improve this answer
    
Question asks for concrete examples where it would apply. Your answer provides general examples where it does not apply. –  jamie Mar 21 '12 at 2:04
add comment

Summary:

I don't think very many people can answer your query as there are some pretty big assumption hurdles present in it. I would recommend studying Functional Programming in general and Scala in particular to deeply understand the kinds of breakthroughs occurring which are strongly related to what it appears you desire.


Details:

To succinctly rephrase your question I think you may be asking:

Please tell me about a personal experience I have had where I worked on a problem using traditional single-threaded assumptions where I know that I would experience an improvement with a "magically parallelizing" compiler.

I think the challenge is the assumptions (many) required to jump from an existing assumed single-threaded code base to understanding all the different, complex and hard intricacies which are present to take the same program and accurately parallelize it via a compiler. This is a non-trivial jump, one that almost no-one can realistically make without having done both types of implementation.

Having said all of that, I do think there are some software engineering practices that might help you move closer to what you might be seeking. And what I sense you are seeking is to spend as little time as possible having to redesign your single-thread assumed code into something that can be easily parallelized. And that requires you become aware of several domains of work which will support this.

  1. You must pick a language which naturally supports the notion of parallel code.
  2. The language must also have libraries for which easily converting single-threaded code to be able to be multi-threaded is a simple class/method/function renaming.
  3. You need to ensure the language BY DEFAULT supports immutability, and then strongly practice immutability within all of your single-threaded assumed software design.

If you follow all three of these practices, you will find the complexity of moving between single-threaded assumed code and parallelizing it will be dramatically reduced. Absent any one of the three practices above, you will find the hurdles to moving from single-threaded to multi-threaded to be so complex as to be not worth the orders of magnitude of extra effort required. And it's even less likely a compiler can be written to make said jumps.

And I am speaking from personal experience. I started a Java project in 2000 based on roughly the same reasoning you used above. It was an ANN/GA (Artificial Neural Network/Genetic Algorithm) distributed computing system to attempt to create a Go (game) AI. Go being quite a challenge, I started with Checkers first to ensure my system worked. For every hour of useful "single-threaded" work I did, I spent another 99 hours (no exaggeration) on technical tangents unrelated to the core goal. I eventually got my entire system working across 10 nodes. However, after having spent close to 2000 hours working on it, I was completely burned out on attempting to do the Go implementation.

I've since sat back and remained very interested in how I might be able to redo the 2,000 hours of work and reduce it to something on the order of 20-50 hours. I finally resorted to inventing my own language and libraries to see if I could solve it faster that way. Talk about a huge technical tangent, huh? :)

Right after I started generating my list of desirable requirements in 2010/Dec, a friend of mine asked me why I was doing all that work. And then he suggested I take a look at Clojure and Scala. I quickly read up on Clojure and didn't like how noisy/boilerplate-ish it felt coming from Java. I then read up on Scala. And I couldn't believe that it had over 60% of the kinds of features I wanted myself. I then purchased the newly released "Programming in Scala, 2nd Edition" and completely read the e-reader version before I got the physical copy.

I've spent all the time between then and now working very hard to grok Scala, Functional Programming and thinking exclusively in terms of immutability. It's been quite challenging to my decades of OO experience. However, I think I am finally rounding the corner on a couple of the core challenges...finally!

Will I use Scala (and Akka, Play and Scala-IDE) and completely re-create my AI system so I can continue on to my Go goal? I'm playing around with it now. I still have so much to learn and so much more confidence to gain before I'm able to code as quickly in Scala and it's libraries as I can in Java with its libraries.

Anyway, it seemed you wanted a personal story from which to draw your conclusions about the possible profitability of a "single-threaded assumed code based automagically parallelized" compiler. Hopefully, this helped.

share|improve this answer
    
Thank you for your answer. I think you summarized the question correctly, so I may need to clarify it. The rest of your answer is "why it can't be done". Believe me, if I had asked "why can't this be done" I'd get a million answers, and I'd vote up every one. But I didn't ask that. –  jamie Mar 21 '12 at 17:55
    
"Anyway, it seemed you wanted a personal story from which to draw your conclusions about the possible profitability of a "single-threaded assumed code based automagically parallelized" compiler." - no. Thanks. I do appreciate the effort you put into the answer, but its not what I asked and not what I wanted. –  jamie Mar 21 '12 at 18:10
    
If you could rework your answer to describe your problem, as opposed to describing your attempts to solve it, that would answer the question and be genuinely useful to me. If you would like to communicate to the world why the question is a fools-errand, perhaps you could ask your own question. –  jamie Mar 21 '12 at 18:21
    
@jamie Ah. I see. Well, my sub-problem was within a specific game, being able to more effectively distribute an alpha-beta-like search to make a better next-move generator for checkers which would then be upgraded to work with my Go implementation. All the checker's playing code was single threaded assumed with lots of mutation. I would have loved a compiler which could have analyzed my single-threaded assumed checkers playing code and adapted it to being highly parallel (i.e. use more threads, cores, processors, nodes). –  chaotic3quilibrium Mar 21 '12 at 20:12
    
@jamie Another domain that might be interesting to work with would be 3D game engine scripting languages; i.e. enabling NPCs to have have more organic like responses to their environment along the lines of the AI used in games like Black&White. There's plenty of need for all sorts of "better parallel algorithms" in the dynamic continuous world of gaming. –  chaotic3quilibrium Mar 21 '12 at 20:14
add comment

Yes, but these problems are few and far between in the world of line-of-business apps.

My problem was solved by manually implementing a threaded solution. I had a location and many resources, and I had to calculate the time it would take for each resource to get to the location. Performing the calculations in parallel was trivial, but offered the opportunity to reduce the overall time taken from n (resources) to 1.

Of course, as the problem was trivial to implement (push each resource to a queue, which were popped by a thread pool to calculate with a simple semaphore to wait for all the resources to complete), a smart compiler wouldn't have offered much help. There is OpenMP that offers the kind of smart compilation with just a couple of pragmas, or functional programming constructs that make this kind of task-splitting easy.

share|improve this answer
add comment

Is there a real-world problem that you have experienced where a "smart-enough" compiler would have provided a real benefit, i.e that someone would pay for?

At a previous employer, I worked in a group that wrote software for residential building energy simulation. Basically, each simulation run uses the past 20 years of weather (the datasets include hourly weather measurements at various airports around the world) for a building at the location and orientation of the building. This allows the user to determine which changes in insulation, heating or other things would make the biggest bang for the buck for their particular situation.

From a previous question of mine:

Individual tasks for offloading the simulation would be

- packaging a file (about 5Mb),
- uploading it to our servers,
- decomposing the package into individual simulations (each run takes about 30-120 seconds and is totally parallelizable), the number of simulations is a function of the number of options selected by the user (insulation, building orientation, etc) and the worst case of selecting every possible option would result in about 1E50 simulations. Running 100 to ~1E5 simulations isn't unknown, but the majority of users will run less than 10.
- reassembling the completed simulations and downloading the now much larger file.

Source
The budget cuts did indeed come and I'm no longer there, so the question over at scicomp is moot.

An architect/engineer running a large number of simulations to determine the effective energy consumption for a housing development (and most effective insulation/heating/cooling schemes for houses at various orientations) could easily spend a couple weeks on an 8 core machine with all the various combinations. Or, it could be parallelized and run in a couple of minutes on the 42,440 core cluster (downloading the results might take a day).

share|improve this answer
add comment

make a large number of CPUs look to the developer like one very fast CPU

Generally speaking, that is just not possible. Currently compilers already parallelize code as much as possible, using for example OpenMP. However, without developers extensively changing code to take advantage of multiprocessing, automatic improvements are limited.

SIMD gains traction GPGPU, this however requires writing software from ground up to take advantage of it. It's not possible to take generic program and convert it to vectorial version.

There are massively parallel distributed algorithms like map-reduce, which indeed are perfectly scalable. But again, you cannot just take generic program or service and automatically convert it into map-reduce. Also map-reduce is not about being fast, it's about processing vast amounts of data within reasonable time.

You cannot really accelerate RDBMS (like MySQL) using massive parallelism. Adding more slaves doesn't help scaling writes, adding masters introduces need of two-phase commits, which make it even slower (more on that here). You can replace it with massively parallel no-SQL storage, but that again isn't automatic, you need to change your code significantly and you loose at least part of ACID.

share|improve this answer
    
I asked for concrete examples where it might be useful. You answered with "generally speaking" opinion of why it doesn't. Again, I have a long line of people waiting their turn to tell me why its impossible. I didn't ask "Why is Paul Graham wrong?". –  jamie Mar 21 '12 at 17:57
    
Specific example where what is useful? An idea that cannot be made true? Or where OpenMP is already useful? –  vartec Mar 21 '12 at 23:43
add comment

What about video transcoding? That is a very CPU hungry operation, and even though there are some multithreaded encoders, the majority are single threaded and are not so quick.

It's a big enough problem that people make and buy expensive hardware to do it for the cpu.

share|improve this answer
    
No one uses CPU for that anymore. It's been done via GPU processing for quite a few years now. Nvidia PureVideo, ATI AVIVO, Windows DXVA etc. –  vartec Mar 21 '12 at 23:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.