What is “embarrassing” about an embarrassingly parallel problem?

Question

In computer science, a problem that is obviously decomposable into many identical but separate subtasks is called embarrassingly parallel.

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

But why are they called embarrassingly parallel problems? The usual meaning of "embarrassing" doesn't seem to apply here. Wiktionary:

causing embarrassment; makes you feel shy or ashamed; leading to a feeling of uncomfortable self-consciousness

Is high parallelism not a good thing, since it allows you to achieve arbitrary speeds just by scaling up the number of parallel processes? So what is "embarrassingly" supposed to mean here?

Answer 1

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)

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.