Take the 2-minute tour ×
English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. It's 100% free, no registration required.

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?

share|improve this question
    
"But why are they called embarrassingly parallel problems?": The answer should come from programmersSE. Voting to close as too localized. –  Kris Sep 25 '12 at 5:10
1  
@Kris: I think this is an English question, not a programming question. The question is, essentially, why is an easy-to-solve problem labeled with a word that connotes shyness, or uncomfortable self-consciousness? The more I think about it, I think it's one of the more interesting English language questions we've had here for some time. –  J.R. Sep 25 '12 at 7:11
1  
@J.R. When it is the domain experts who adopted a term for the phenomenon, why would the language pundits speculate as to what was on their minds? We are opening a debate. Why not ask those who know the etymology/ rationale? stackoverflow.com/questions/806569/… –  Kris Sep 25 '12 at 10:01
1  
@J.R. That question on SO also gives an into why these problems are obviously 'embarrassingly parallel' pl take a look. –  Kris Sep 25 '12 at 10:06
1  
@Kris: I took a look; I still think this question has merit on an English forum. –  J.R. Sep 25 '12 at 10:25
add comment

6 Answers 6

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)

share|improve this answer
    
That embarrassment of riches is an apt example, though overabundance is not the reason. –  Kris Sep 25 '12 at 10:09
    
@Kris, is so; see edit –  jwpat7 Sep 25 '12 at 16:24
add comment

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

share|improve this answer
    
+1 Almost there, wish you explained better. –  Kris Sep 25 '12 at 10:08
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
+1 Good catch. Embarrassingly is more flexible than it might seem at first glance. –  MετάEd Sep 30 '12 at 2:25
add comment

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.

share|improve this answer
    
But how does being easy make something embarrassing? –  Mechanical snail Sep 25 '12 at 1:13
    
@Mechanicalsnail I added in the etymology and hopefully how it ties in with what you're asking –  Souta Sep 25 '12 at 1:43
    
@Mechanicalsnail The best I can say is "The parallel problem is so easy to separate the problem into tons of tasks, it's embarrassing." "Oh hey! Why not just call it that?" "Okay, it's an embarrassingly parallel problem!" –  Souta Sep 25 '12 at 1:58
1  
-1 You have obviously missed the point as to why embarrassingly parallel? –  Kris Sep 25 '12 at 10:08
    
@Kris Embarrassingly so. –  Souta Sep 25 '12 at 12:33
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.