What is "embarrassing" about an embarrassingly parallel problem?

Suppose you have a lot of work to be done, and want to get it done much faster, so you hire 100 workers. If the work is 100 separate jobs that don't depend on each other, and they all take the same amount of time and can be easily parceled out to the workers, then you'll get it done about 100 times faster. This is so easy that it is called embarrassingly parallel.

Source

And from your own Wikipedia source:

is one for which little or no effort is required to separate the problem into a number of parallel tasks. This is often the case where there exists no dependency (or communication) between those parallel tasks.

It says it right there, it requires no effort.

From what I gather, it is considered embarrassing because it is easy.

Definition of embarrass:

verb [with object]

1cause (someone) to feel awkward, self-conscious, or ashamed: she wouldn’t embarrass either of them by making a scene

(be embarrassed) be caused financial difficulties: he would be embarrassed by estate duty

2 archaic hamper or impede (a person or action): the state of the rivers will embarrass the enemy

archaic make difficult or intricate; complicate: I do not apprehend that this case will be embarrassed by that decision

(Source)

---

Edit for OP

The etymology of embarrass:

1670s, "perplex, throw into doubt," from Fr. embarrasser (16c.), lit. "to block," from embarras "obstacle," from It. imbarrazzo, from imbarrare "to bar," from in- "into, upon" (see in- (2)) + V.L. *barra "bar." Meaning "hamper, hinder" is from 1680s. Meaning "make (someone) feel awkward" first recorded 1828. Original sense preserved in embarras de richesse (1751), from French (1726): the condition of having more wealth than one knows what to do with. Related: Embarrassing; embarrassingly.

I'd like to focus more on the last part:

the condition of having more wealth than one knows what do do with

When you have an embarrassingly parallel problem, you are saying you have many identical but separate subtasks to deal with

An example is a cryptographic brute force attack, in which the algorithm is to independently try billions of random inputs until one works.

this example is from your own question

---

For the other answer, a synonym of easy is simple.

If you Google either "embarrassingly simple question" or "embarassingly simple answer" you will find thousands of people asking questions which they're sure have answers so simple they will be intensely embarrassed to have raised the question in the first place.

Furthermore, most people to whom a problem with an "embarrassingly simple answer" is posed are themselves embarrassed, doubly: it is on the one hand socially embarrassing to have to point out to the questioner how stupid his question is, and on the other professionally embarrassing to be asked to bring one's extraordinary skill and expertise to bear on so trivial a matter.

I imagine that this conventional usage is carried over to "embarrassingly parallel problems" -- these are problems with an "embarrassingly simple answer".

This usage may derive from the idiom an embarrassment of riches: “An abundance or overabundance of something; too much of a good thing.” Wiktionary shows, for the etymology of the phrase, “from John Ozell's 1738 translation of a French play, L'Embarras des richesses (1726) by Léonor Jean Christine Soulas d'Allainval.”

For embarrassingly parallel problems, the number of subproblems that could be handled in parallel (if enough processors were available) is often a large multiple of the number of processors; ie there are vastly more subproblems than processors, and parallelization of them is no worry, in contrast to more-common problems constrained by Amdahl's law.

As noted in OED 1 and in etymonline's entry for verb embarrass:

from 1670s, “perplex, throw into doubt,” from Fr. embarrasser (16c.), lit. “to block,” from embarras “obstacle,” from It. imbarrazzo, from imbarrare “to bar,” from in- “into, upon” (see in- (2)) + V.L. *barra “bar.” Meaning “hamper, hinder” is from 1680s. Meaning “make (someone) feel awkward” first recorded 1828. Original sense preserved in embarras de richesse (1751), from French (1726): the condition of having more wealth than one knows what to do with.

It is from the latter sense, “more wealth [ie, parallelism] than one knows what to do with” that embarrass was first used in the term embarrassingly parallel. Some definitions on the web place undue emphasis on ease of parallelization of such problems (1), but more important features include “minimal communication between runs” and “little to no effort for load balancing” (2). Embarrassingly parallel problems need not be easy to parallelize; indeed, parallelization may be difficult:

The embarrassingly parallel gravitational lens application of Section 7.4 was frustrating for the developers as it needed software support not available at the time on the Mark III. Suitable software ... had been developed on the Mark II to support graphics ray tracing as briefly discussed in Section 14.1. Thus, the calculation is embarrassingly parallel, but a distributed database is essentially needed to support the calculation of each ray. This was not available in CrOS III at the time of the calculations described in Section 7.4. (3)

As StoneyB said, the word embarrassing is used here in the same context as embarrassingly simple.

The underlying notion is that the problem is so easy to solve, you'd be embarrassed to be lauded in public with credit for solving it. In other words, the accomplishment is so elementary, no kudos are warranted.

I checked a few dictionaries, and found one meaning that seemed closely aligned with this usage of the word:

To the point of embarrassment; to an extreme or bewildering degree

So, embarrassingly parallelizable essentially means extremely parallelizable; it's a figure of speech, no one expects the coders will really blush when the program works.

As a side note, it's interesting how the Wordnik entry for embarrassingly includes this sample usage on the right-hand side:

“Quite a few (almost all?) problems in that domain are what can be called embarrassingly parallel - be it Structural Mechanics, Fluid dynamics, or Virtual Modeling.”

Embarrassed, as Souta and others have pointed out, can also mean 'perplexed' or 'in difficulties'; this was the original sense (see Etymology of "embarrass"?), and is still used in certain contexts. So being financially embarrassed does not imply anything about your emotions, and an embarrassing pleading to a lawyer means only a document to which no factual answer can be given.

It may be that your 'embarrassingly parallel' problems are so parallel that they become impossible to deal with normally; there is no point devising an algorithm for the process of trying every possible password in succession.

It means your blisteringly fast solution is not clever at all, all you did was throw more microchips at it.

Graphics processing units are where I first heard the term. They get faster and faster every year, but only because of ever increasing transistor counts and basically coloring more pixels in in parallel ever year, as opposed to finding a generally faster way to color pixels (algorithmically).

The embarrassment involved is that, in the early days of the concept of parallel processing, computer science specialists put a great deal of thought and effort into creating generalized solutions which took into account what might happen if one parallel chunk needed information from another parallel chunk and then another and another and so on. Then, when machines capable of parallel processing became readily available, it turned out they were mostly used for problems that are inherently parallel and do not depend on any of the other tasks going on at the same time. All that effort, how embarrassing. I am not one of the computer scientists that did all that work so I can't say this is the origin of the phrase with certainty. But I read many of these papers and worried that it would be so difficult to get real benefits out of parallel machines. Now I write programs routinely that use embarrassingly parallel processes to evaluate weather forecasts from what are called ensembles of weather forecast model results, because the results of one ensemble member can be processed without any information from all the other members. And considering all the worry from reading those professional papers, I am embarrassed.

Imagine you are a world-class tennis player and you find yourself playing a ten-year-old who is about as good as you expect. You don't even lose a single point, of course. Wouldn't you be embarrassed? Embarrassingly parallel problems are like that. You don't have to use any clever techniques, you just divide up the work and rake in the time savings.