What is "embarrassing" about an embarrassingly parallel problem?

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)

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

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.