Parallelism

The unparser can run parallel. While the pure unparser can be easily parallelized, due to the complex behaviour of the formatter and the expression-unparser there is a large sequential part in the unparser that cannot be parallelized (or at least cannot be easily parallelized).

By default the unparser run sequential. If you want to run it parallel you have to set its EnableParallelProcessing property to true. You can also set the DegreeOfParallelism to adjust the parallelism (by default it equals to Environment.ProcessorCount).

Here are the results of unparsing a simple, large test file (30010 lines, 87022 words, 627198 characters, 567180 non-whitespace characters) using MiniPL.GrammarP (the numbers are rounded to one decimal digit):

DegreeOfParallelism	Time	Speedup	Efficiency
1 (sequential)	7.6 s	1.0	1.0
2	7.5 s	1.0	0.5
4	4.6 s	1.7	0.4
8	3.2 s	2.4	0.3

Speedup is defined with the following formula:

where:

• n is the DegreeOfParallelism
• T₁ is the execution time of the sequential part
• T_n is the execution time of parallel part with n as DegreeOfParallelism

Efficiency is defined with the following formula:

Ideal speedup would be S_n = n, this is when we reach the ideal efficiency which is E_n = 1. Due to the sequential part we do not reach the ideal values.

If we consider Amdahl's law:

where P is the proportion of the unparser that can be parallelized (thus 1-P is the sequential proportion), then it can be estimated that P = 2 / 3 (calculating with n = 8 and S_n = 2.4).

Using that estimated P we can estimate the speedup:

The best expected speedup is:

We can also estimate the efficiency if we calculate the efficiency by Amdahl's law:

Of course, due to the sequential part, the efficiency approaches zero as n increases.

If you are interested in how to reuse grammars, continue with Grammar Reuse.