Depth first build order for parallel builds

[Tom Varga]

Is there any way to force a depth first build order of tasks during parallel -n builds?

Please see my contrived example below where leaf0.file1 depend on leaf0.file0, leaf0.file2 depends on leaf0.file1 and so on.

In other words, each leaf has 10 file types that must be built in order based on dependencies.

This is actually a realistic EDA flow.

A non-parallel build does appear to build in a depth first order, ie:

.  leaf0.file0

.  leaf0.file1

.  leaf0.file2

...

However, turning on a parallel build with 'doit -n 2' now appears to build breadth first, ie:

.  leaf9.file0

.  leaf5.file0

.  leaf4.file0

.  leaf1.file0

...

What I'm hoping to see is:

.  leaf9.file0

.  leaf5.file0

.  leaf9.file1

.  leaf5.file1

...

This may seem like a silly requirement, but please imagine that every different file type target is built using a different (expensive) licensed EDA tool with a limited quantity of licenses.

Let's say we only have 2 licenses for each file type but we want to use -n 5 to build the tree more quickly.

In this case, the first 5 jobs would try to use a file0 license, so 3 would have to wait for licenses to become available.

But, once the first 2 jobs complete, I'd like to see doit start building file1 types and thus use a different license instead of firing off more file0 jobs which would have to wait for more file0 licenses to become available.

Again, this may seem trivial, but when I need to build 50K targets with -n 200, it does become a major limiter of throughput.

Anyway, how difficult would it be to give doit an option to force breadth first building of tasks during parallel builds?

If it appears possible, please consider adding this feature to doit.

Thanks again,

-Tom

NUM_LEAVES = 10

LEAF_LIST  = [ "leaf%s" % i for i in range(NUM_LEAVES) ]

NUM_TYPES  = 10

import os

def dir_exists(task):

    directory=task.targets[0]

    return (os.path.exists(directory) and os.path.isdir(directory))

def file_exists(task):

    filename=task.targets[0]

    return (os.path.exists(filename))

def task_tree():

    """create tree/"""

    return {

        'targets'  : ['tree'],

        'uptodate' : [dir_exists],

        'actions'  : ["mkdir -p tree"],

        }

def task_leaf_dirs():

    for leaf in LEAF_LIST:

        dirname  = "tree/%s" % leaf

        yield {

            'basename' : dirname,

            'targets'  : [dirname],

            'uptodate' : [dir_exists],

            'task_dep' : ['tree'],

            'actions'  : ["mkdir -p %s" % dirname],

            'doc'      : "create tree/%s" % leaf,

            }

def task_leaf_filetype():

    """create tree/leaf#/leaf#.file#"""

    for leaf in LEAF_LIST:

        for i in range(NUM_TYPES):

            filetype  = "file%d" % i

            directory = "tree/%s" % leaf

            basename  = "%s.%s" % (leaf, filetype)

            target    = "%s/%s" % (directory, basename)

            if i > 0:

                depend_basename = "%s.file%d" % (leaf, i-1)

                depend_filename = "tree/%s/%s" % (leaf, depend_basename)

                yield {

                    'basename'  : basename,

                    'targets'   : [target],

                    'task_dep'  : [directory],

                    'file_dep'  : [depend_filename],

                    'actions'   : ["date > %s ; sleep 1" % target],

                    'doc'       : "create %s" % target,

                    }

            else:

                yield {

                    'basename'  : basename,

                    'targets'   : [target],

                    'uptodate'  : [file_exists],

                    'task_dep'  : [directory],

                    'actions'   : ["date > %s ; sleep 1" % target],

                    'doc'       : "create %s" % target,

                    }

[Eduardo Schettino]

On Tue, Sep 9, 2014 at 11:33 PM, Tom Varga <tomv...@gmail.com> wrote:

Is there any way to force a depth first build order of tasks during parallel -n builds?

It is not correct to say that the build order is depth first nor breath first...

The execution order is the order the tasks were defined

(in your example you define them depth first).

The order using parallel build is the same as long as there is no contention
of tasks to be executed. Contention happens when a task selected to be executed

but it depends on another task that didnt finish its execution.

In case of contention a task is picked from a FIFO queue.

 

This may seem like a silly requirement, but please imagine that every different file type target is built using a different (expensive) licensed EDA tool with a limited quantity of licenses.

Let's say we only have 2 licenses for each file type but we want to use -n 5 to build the tree more quickly.

In this case, the first 5 jobs would try to use a file0 license, so 3 would have to wait for licenses to become available.

But, once the first 2 jobs complete, I'd like to see doit start building file1 types and thus use a different license instead of firing off more file0 jobs which would have to waist for more file0 licenses to become available.

Again, this may seem trivial, but when I need to build 50K targets with -n 200, it does become a major limiter of throughput.

Anyway, how difficult would it be to give doit an option to force breadth first building of tasks during parallel builds?

From your explanation, what you really need is a mechanism to control usage of limited resource.

doit has no support for this yet, or any other advanced scheduling mechanism.

doit only makes sure the dependencies are met.

 

If it appears possible, please consider adding this feature to doit.

You better scratch your own itch :D

regards,

  Eduardo