Are there any concrete examples of where a paralellizing compiler would provide a value-adding benefit?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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.

Answer 8

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.