A proposal for a more efficient parallel verrou_dd

[HadrienG2]

Currently, verrou_dd processes configurations in order, and only allows itself to perform multiple runs of a configuration in parallel. This has two problems:

• If you need less runs than your CPU has cores, you can't fully leverage your CPU time.
• As each run determines whether it is useful to do the next run or not, parallel run processing may not be very efficient because it hampers early exit.

Here is an alternate algorithm proposal:

Parameters:

NUM_PROCS = Maximal number of processes in flight
NRUNS = Maximal number of runs per configuration

Main thread:

Set up a pool of NUM_PROCS processes which listen to a FIFO queue of cancellable tasks (IIRC python's stdlib has something for this built-in)
For each schedule (set of configurations)
    For each run (1 to NRUNS)
        For each configuration:
            Schedule a run of the active configuration to be executed
    Wait for any of the runs in flight to complete or be canceled (out-of-order, select-style):
        If the run was a success and was the last run associated with this configuration...
            Mark the configuration as successful
            Print a log message indicating that this configuration is successful.
        If the run was a failure
            Cancel all other runs associated with this configuration.
            Mark the configuration as failing
            Print a log message indicating that this configuration is failing
    Once all runs have executed or have been canceled, do some error checking and determine next schedule

I think this algorithm is pretty good, because since the executor is FIFO and we schedule the first run of each configuration, then the second run of each configuration, and so on, multiple runs will only actually execute in parallel when the CPU has nothing better to do. Therefore, we reach a good compromise between keeping the CPU busy and avoiding potentially wasted work.

One thing which is lost with respect to the current algorithm is that no message will be printed when a configuration starts to be tested, only when verrou_dd is done testing a configuration. Also, configurations will be printed out of order, but I don't think this is a big deal (they were hardly identifiable anyhow).

[lathuili]

I agree with you : this naive parallelism is not satisfactory.

With the actual ddmax, when you reach a success you can exit of the loop of independent : "For each schedule". So it is not obvious that to switch configuration loop and the run loop will help to get the first success configuration.

As we want to leave ddmax and use an other algorithm rddmin which perform iteratively ddmin search, we wont' spent to much time on ddmax parallelism.

[HadrienG2]

You are right that in this case, it may be better to investigate how to make rddmin fast instead :)

[lathuili]

V3.2.1 implements parallelism in dichotomy part of rddmin algorithm. Let me known if it is not sufficient.