coarse-grained is synonymous with task-level parallelism. For example, the Map phase in MapReduce is a set of coarse-grained tasks. In MapReduce it is matched to the long latency file and I/O operators and since you have millions of files this is a very nice division of labor, and a very coarse-grained division.

Embarrassingly parallel tasks are tasks that have no inter-dependencies, that is, they are completely 'unconnected'. A perfect example is a pixel shader in a GPU. Each pixel of a triangle needs to be colored and that calculation can be done independently from the other pixels in the triangle. Such a task can be coarse-grained or fine-grained. For example, Renderman shaders can run for hours on a single pixel, where as a flat-shaded triangle has a single interpolation calculation to determine the color.

Coarse-grained and embarrassing are terms that do not refer in any way to the same concept. As Theodore pointed out, embarrassingly parallel tasks do not have dependencies (for instance, there is no need to communicate data among them in a message-passing setting). Coarse-grained and fine-grained are terms that, instead, are strictly related to the grain size of the problem when you partition it into a number of tasks (i.e.: the grain size is the amount of data per process). It is worth noting here that coarse-grained tasks are not necessarily associated to task-level parallelism: they may associated, as well, to data parallelism, in which you first partition (using domain decomposition techniques) the data to be processed by your application among the available cores, and then associate to each tasks the operations to be applied on the data.

Coarse and fine-grained decompositions only differs in the amount of data assigned to each core. For instance, if your problem is summing in parallel the element of two vectors component-wise, let's assume that the problem size is n, i.e. the dimension of each vector is n. Now if you have n processes (each running on a distinct core), you may assign one component per core in your decomposition, leading to a fine-grained decomposition. If you have p cores with p

The classification depends on the amount of synchronization -- often communication, so I'll use it to illustrate -- that is needed between the tasks running in parallel. If you need a formalism, consider the time a task spends actually computing divided by the time it spends communicating -- its computation/communication ratio. An embarrassingly parallel task is completely independent, requires no task-to-task communication to complete its parts of the computation, so its computing/communication ratio is infinity. A coarse-grained parallel task requires some communication to complete its part of the computation, so its computation/communication ratio is relatively high, but not infinite. (A fine-grained parallel task requires a substantial amount of communication to complete its part, relative to the amount of computing it does, so its computation/communication ratio is relatively low, perhaps approaching 1.)

So if your Monte Carlo simulation tasks run independently, with no synchronization with their peer tasks from start to finish, they are embarrassingly parallel. If they require some modest amount of synchronization with their peers during their execution, they are coarse-grained.

Thank you so much, colleagues! Be safe and sound!

I think you better classify using the computation to communication ratio as a metric. Above a certain level (> 10, > 100, the size of the tasks is not so important. With large systems, you might need to take into account latencies as well. Latency then expressed in number of bytes that can be communicated to/from the task in that interval.

Remember as well. Software is modelling. The world we model is parallel by nature. So design parallel. Grouping concurrent tasks (to reach the computation/communication ratio) is sequentialisation and needs to be seen as an optimisation step.