Solving the Multicore Dilemma

For massively parallel systems, functional language compilers do not address the primary implementation challenges around software design. In fact, the C++ compilers for a number of supercomputers have functional language extensions but I have almost never seen those extensions used because they do not solve any of the problems parallel systems designers have.

To dispel one misconception, the reason it is simple to write massively parallel code in C++ is that the basic model is a single process locked to a single core with no context switching at all. It is all non-blocking, coroutine-esque, cooperative scheduling. Writing this type of code is exactly like old school single-process, interrupt-driven UNIX code from back in the day when no one did threading. Simple to write, simple to analyze. Analogues of this work well even on fine-grained systems.

The real parallelization challenge is often completely overlooked by people offering nominal solutions. While your application may only be composed of two algorithms and those algorithms are independently massively parallel, that does not imply that the algorithms are operating on identical representations of the underlying data model, something that is tacitly assumed most times. Representation transforms between algorithm steps inherently parallelize poorly.

A canonical example of this is the hash join algorithm. It is a two-stage algorithm, and both stages are obviously parallelizable, yet ad hoc hash joins parallelize very poorly in practice because it requires a representation transform.

In a sense, the real parallelism problem is a data structure problem. How do you design a single data structure such that all operators required for your algorithms and data models are both efficient and massively parallel? Using functional programming languages does not speak to that and it is the fundamental challenge regardless of the hardware.

For a while, I've been pondering how to solve the same problem. I also reached similar conclusions, that parallelism needs to be implicit at the language level. I've even been working on an implementation that will run on the JVM (it's all of a week old for writing code for it, but I've been documenting the how it works for months in my notebooks). The language is based around the idea of stream processing. By using type signatures, function calls can be parallelized based on how the are called.

As an example, given two functions, A(Item) and B(List[Item]), if you call them like:

    B << A << List[Item](x,y,z)

the A should be called once for each item in the list of x,y,z, the results of which are collected into a list and passed to B. If you add in a function C(Item) and call it like:

    B << C << A << List[Item](x,y,z)

then at any given point, A can be processing a list item, C can be processing a list item and the total results of C are being collected. Which leads into, what if it is order dependent?

    B << serial { A << List[Item](x,y,z) }

will guarantee that A is called serially and the order of the List (and results) is preserved.

I really shouldn't advertise the link to the language at all here, considering I have zero documentation and there's almost no comments in the current code, but I'm going to anyways, https://bitbucket.org/ismarc/muster . It currently will parse a single file, generate the AST and generate the symbol table. I'm working on a non-parallel interpreter right now, with the intention of using the interpreter to write the compiler so the language is fully exercised to work out any potential issues with it. And on a final note, I'm targeting the JVM mainly for existing libraries, but I'm open to discussions about it.

Maybe I'm wrong, but it seems to me that most of this guy's ideas are either a bit half-baked or simply flat out wrong.

Consider the argument for his proposed language being Turing complete on the flow manifesto page. He claims that this follows from the Böhm-Jacopini theorem. However the Böhm-Jacopini theorem requires variable assignment is allowed in the subprograms (which does not appear to be the case in flow), and without this the theorem does not hold, as this paper by Kozen demonstrates: www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf. Then he goes on to argue that order duality implies the existence of a selection operator in flow, which doesn't seem to make any sense.

I think it's telling that he has been working on this since 2010, yet has no decent proofs of his claims, nor any working implementation.

Since this thread is young and full of expertise, I'm going to ask a question about a nuance of Moore's Law that's been bugging me for a while. (I study CS and currently have very little background in physics and electrical engineering.)

Over the past few years I've read engineers talk about the manufacture and design of CPUs in terms of an XX nanometer processes, where XX is some ever smaller integer - presumably representing the density of transistors in the CPU, or something proportional to that.

But for many decades, we've known that there are fundamental physical limits of computation as-we-know-it with Moore's law predicting a smooth logarithmic curve until that point, doubling every 18 months.

My question is why does it have to be a smooth increase? Don't we have enough computation and understanding now to leapfrog straight to the physical limits using standard run-of-the-mill CPU architecture? After all we can manipulate individual atoms and I think we have transistors made of a just few atoms or less.

Why do we have to go through the 20 nanometer processes then presumably through the picometers until finally stopping at some point maybe in the femtometers (where the lengths of many atomic nuclei can be expressed in single digit integers). Development that Moore's Law presumably predicts will take multiple decades to reach.

Why can't we build processors using modern CPU paradigms on the atomic scale earlier? Is it mass-production issues? Or some physical bottlenecks? Do we need to continually develop ever slightly more dense processors at great expense slowly or can we skip the interval and develop straight at the atomic scale?

I just feel like at some point there should be step function straight to the physical limits of processors as-we-know-them. Why hasn't this happened?

Fortress, a programming language funded by DARPA and developed by Sun, aimed at solving this very issue by parallelizing core operations. For example, 'for' loops in the language are parallel operations that do not guarantee linear iteration. Unfortunately, development wound down this summer due to incompatibility with VM type systems.

I'm surprised that the author did not mention join lists in his discussion of parallelizable functional program structure. A join list is either empty, a single element, or contains two join lists. In a normal list, you recur on a list that is only one smaller. In a join list, each recursion passes half of the list to a new processor.

The switch to easy parallelization will require data structures that do not guarantee linear iteration but gain scalability "for free." In my experience, this is easy to add to lisp dialects, but difficult to implement and use in imperative languages.

May I make a small, unrelated suggestion if the OP is the blog owner? Smaller logo. Took me a full half-minute to figure out that I should scroll down. Took up my entire screen, and thought I was supposed to click something special to see the content.

/rant

A colleague of mine remarked that one of the things that bothered him about Go (and uC++, and to some extent, VHDL for that matter) was how much the languages resembled traditional imperative languages (like C). In particular, it was the cases where these languages did something that was different from C (i.e., "different from what the user expected") that caused him the most pain.

If the Flow language can figure out how to deal with this expectation, I think there might be something here.

While I agree with him in theory, I doubt this will work in practice.

I very much doubt that a compiler will be able to choose appropriate parallelization schemes at runtime without hints from the user, Big-O approximation will probably be insufficient in an annoying number of cases and very hard for the compiler to implement. IO will require monads or that DAG turns into a linked list. I also find it very telling that he doesn't show what that DAG looks like for loops or recursive functions.

I did not understand everything in the article, but if Haskell has solved all these problems already, why isn't everyone jumping ship en masse to functional programming? Surely there must be a better reason than "It's too hard for programmers"?

He overlooks a lot of related work on data flow languages. Also, 1) and 3) remind me of I-structures (http://dl.acm.org/citation.cfm?id=69562).

Otherwise he seems to have described asynchronous message-passing style, except with convoluted programming language concepts. But Microsoft already has a compiler that statically analyzes message passing in large programs; look up the Singularity operating system. [TL;DR: Message-passing microkernel; everything runs in supervisor mode; safety is checked statically at compile-time.]

Unordered collections is just too lax to be useful: for example, multiplication of 100 matrices can be nicely parallelized because multiplication is associative, but not commutative. So you'd probably end up defining write-once locations ("boxes") that contain (ordered) vectors of elements and use that for communication. So, back to I-structures.

So, basically, just another mash-up of old ideas.

I'll never forget this exchange I had with a CS professor:

Me: ... but, in the future, everyone will learn how to program. Neal: no, in the future, no one will need to know how to program.

I suspect Neal was right, though I dislike the idea strongly.

Anyhow, machines will probably prove to be smarter with such details. So accountants can likely just shift the cost to another column. (Sorry to anyone who can conceivably be replaced by a robot.)

Not to sound like such a douche: parallelism, concurrency, distributed process; can raw human "wet" computing ever pretend to compete with clean binary process in such gambles?

To claim this is a 'dilemma' is to ignore the increasingly common types of workloads that companies need to run, and the amazing technology stacks that have been created to run them. Namely, horizontally scalable systems on commodity hardware with linear performance vs node count.

Software is eating the world, and as the speed and availability of the network continues to improve dramatically, computing workloads will continue to centralize, and companies will serve their massive user bases with wimpy cores at a massive scale.

Amdahl's Law says that "the speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program."

So while you have a hard limit trying to improve performance of a single function through parallelization, there is no upper limit on running multiple instances of the same function to respond to multiple concurrent and independent requests.

Individual cores need only to be fast enough such that the latency of a single request/response is acceptable. After that, any increase single-core performance requires a commensurate increase in the complexity of the scheduler, leading to rapidly diminishing returns, not to mention significantly lowering 'Responses per kWh'.

The fundamental shift toward multi-core processors may have been necessary due to physics, but not coincidentally (I think) it's also exactly the architecture you want if you are trying to serve large numbers of requests over a network.

The difficulty I have with his manifesto is that he proposes many ideas that sound quite similar to existing ideas (e.g. graph reduction model of computing, dataflow execution models, dataflow languages), but there isn't a direct comparison: I can't tell if this is a remix of older ideas (nothing wrong with that necessarily), or if there is some additional idea he has that mean the language would be a major advance over past work. It's just difficult to know what to make of it.

Identifying parallelism is important, and the Flow project sounds cool. However it's by no means the only thing we have to do to solve the multicore conundrum. It turns out that there's a lot more to worry about in a cluster or a GPU than just the number and nature of their cores.

Just a problem statement and initial idea which isn't that new, but could be interesting if he actually implements it.

There have been many failed systems that hinged on "sufficiently smart compilers". Some have been thread-parallel machines (like the Tera MTA, shipped 1998) and some have been VLIW/MIMD, like Multflow (shipped 1987). And Itanium.

Nicely written article - clarified some points for me.

Isn't the wait for the unordered collection to be "finalized" a huge bottleneck, though. I can see this working nicely for low level parallelisation but not so well for more traditional producer/consumer threads or I/O operations.

from the science prospective: after LAPACK and friends are rewritten into functional languages, maybe some people will be willing to switch from FORTRAN... but i doubt it.

There will always be a monkey banging the drum for fantastical soft solutions, and then there are rocket scientists who will deliver the hard solution.

Would that you could see over the horizon.