[neilc]

And there are also enough 'prominent examples' for impure imperative languages. For instance, OpenMP makes parallelizing some loops in C/C++ a walk in the park, and I have parallelized some of my programs by adding only a few pragmas.

I'm curious -- were the programs that were easily parallelized with OpenMP largely data parallel to begin with? I haven't used OpenMP extensively, but I'd suspect that the ease of parallelizing a program with OpenMP probably varies inversely with the amount of explicit coordination/synchronization/update of shared state that the program requires.

[microtonal]

Mostly, yes. This particular program evaluates effectiveness of features given an existing log-linear model. So, you can evaluate the effectiveness of features in parallel. For each feature, you can also partition the training data, process the the data in parallel, and apply a reduction step[1].

But 'map' in MapReduce is also a typical data-parallel task.

[1] In practice, there is a trade-off: the vectors are usually so large for the average training set, that you do not really want to copy them for memory-efficiency, so the mapping and reduction are interleaved, requiring some locking.