Monday, September 10, 2007

Is Erlang a Parallel Language? Simple Answer: No

All Multicore Related Articles
All Erlang Related Articles

In a recent article, Fady Younan wrote “We have to realize that the world is going towards parallel processing even we don't accept Erlang as a language I think it will take place in the next decade”. I am not entirely sure what Fady is saying here. Is he saying that Erlang will be accepted as the de facto parallel language in the next decade? If so, I beg to differ. A true parallel language must handle fine-grain parallel processing. Erlang is anything but fine grain. A true parallel language will have no trouble initializing a collection of variables simultaneously. Can Erlang be used to implement a parallel QuickSort module on a multi-core system that is faster than the single-core sequential implementation? I doubt it.

The point that I am driving at is that, if the computing world is going toward massive parallelism (Tilera and others are already talking about the coming of 1000-core CPUs), in order to take full advantage of all those cores, we need a parallel programming model that scales up linearly, up to the elementary operation level. Unless there are as many processes/threads running as the number of available processors (cores), Erlang’s lightweight concurrent processes are not fine enough to take advantage of a huge number of processors. As soon as the number of processes falls below the number of available cores, performance suffers. The best way to take full advantage of massive parallelism is to increase the number of processes by shrinking their size down to elementary operations such as, addition, subtraction, etc… At that point, the model is fully parallel (parallelism is implicit) and sequential order is explicit and signal-based. Indeed, why limit asynchronous signaling to lightweight processes? Why should elementary operations be excluded? I know, some may think that asynchronous signaling at the operation level would be too slow. Sure, this is true, but only because current CPUs are designed and optimized for the algorithm. There is a way to design a multicore MIMD CPU to handle fine-grain parallelism at the operation level that does not incur any performance penalty. (see How to Solve the Parallel Programming Crisis)

One of my bones of contention with concurrent languages like Erlang is that they don’t encourage multicore designers (AMD, Intel, Tilera, etc…) to create architectures for fine grain parallelism in an MIMD environment. In fact, they discourage it. That’s too bad, in my opinion, because the market wants super fast, auto-scalable, fine-grain parallel computers and applications. And what the market wants, the market will get. You can bet on it.

See Also:

Erlang Is Not the Solution
How to Solve the Parallel Programming Crisis
Parallel Programming, Math and the Curse of the Algorithm

The Age of Crappy Concurrency: Erlang, Tilera, Intel, AMD, IBM, Freescale, etc…
Half a Century of Crappy Computing
Parallel Computers and the Algorithm: Square Peg vs. Round Hole

3 comments:

Ulf Wiger said...

You get no argument from the Erlang crowd. Erlang was never designed to be a fine-grain parallel language. Indeed, one of the languages used in the experiments that led to Erlang was Parlog, but the fine-grain parallelism was found to be impractical for telecom programming.

The concurrency granularity in Erlang is great for modeling applications such as control systems, web services, etc. Erlang-based applications are shipping today on multicore, using around 10,000 processes per machine. Erlang supports millions of concurrent processes today, so I think it will be a while before the number of cores on a chip becomes too large for Erlang programmers. It's not likely that this will have any major impact on mainstream CPU design, though, so I think you needen't worry.

When it comes to exploiting fine-grain parallelism, I think there are some opportunities in Erlang, but languages like Haskell will most likely have greater potential in this regard, since the compiler has more information to work with.

Louis Savain said...

Indeed, one of the languages used in the experiments that led to Erlang was Parlog, but the fine-grain parallelism was found to be impractical for telecom programming.

No doubt that it was, and still is, impractical. I do not fault Erlang for doing the best that can be done with current CPU technology. But I do have a problem with Erlang's advocates promoting it as the language of our parallel future. The lack of fine-grain parallel support is just one of several shortcomings that I find unacceptable. One of the problems that is absolutely inexcusable, in my opinion, is the inability to enforce deterministic timing, an absolute must for rock-solid reliability. The only way this can be done is by adopting a model that requires that all processes have equal execution durations. And the only way you can do that is with fine-grain parallelism where every elementary process can be made to execute within one system cycle.

Erlang supports millions of concurrent processes today, so I think it will be a while before the number of cores on a chip becomes too large for Erlang programmers.

Yeah, I am sure that Erlang is well suited for all sorts of large scale concurrent applications. However, you are overlooking the fact that there are many instances where an application may have millions of small communicating entities that must be executed simultaneously but are too small to be efficiently encapsulated in Erlang's processes (or any type of algorithmic threads) without incurring a severe performance penalty. I am thinking of applications like large neural networks (AI) and simulations. I happen to conduct experiments in spiking neural networks and I would never consider using Erlang's processes to encapsulate one of my elementary cells.

Ulf Wiger said...

you are overlooking the fact that there are many instances where an application may have millions of small communicating entities that must be executed simultaneously but are too small to be efficiently encapsulated in Erlang's processes

Not at all. That happens to be another niche than that which Erlang was designed for. While it would be nice to have a tool that fits all problems, I'm not going to hold my breath. For one thing, you seem to be after programs that are provably correct, but in our field of applications, we couldn't even begin to formulate the necessary proof criteria - the requirements are much too fuzzy. Thus, the "robustness in the presence of software failures" idea. Different problems call for different approaches.