concurrent builds

[wookietreiber]

Some revisions of the concurrent build process as explained in my last mail.

One problem with the algorithm I described is that the building blocks always should be smaller than the amount of computing cores available for building. If we only have a dual-core CPU a three-module block would be kind of troublesome. So now I'd like to present an event-based approach, which handles this better.

But first, lets tag our modules / dependency tree with a PSAFE tag: an asterisk (*) means it's not PSAFE, i.e. it can only use one core for building.

A
|--->B1
|    |--->C1*
|    |--->C2
|         |--->D
|--->B2*
|    |--->D
|--->[B3]
     |--->D

Now we can optimize our approach and see how building time can be improved. Lets say our imaginary CPU has six cores.

For our first building block {C1,D} we can now say that since C1 is not PSAFE but D is we give D all remaining 5 cores for building. So now we have:

1 core building C1
5 cores building D

Now imagine D being ready before C1: D being ready means we can now build B2, B3 and C2 with our 5 cores freed.

1 core still building C1
1 core building B2 (not PSAFE)
2 core building B3
2 core building C2

Now imagine (this would kinda be the best case) C1 and C2 finish, which means we can now build B1:

1 core still building B2
2 core still building B3
3 core building B1

Now we need to wait until all BX are ready and can assign all six cores to build A.


Best regards
Christian Krause aka wookietreiber


On Mon, Jan 17, 2011 at 02:01:41PM +0100, wookietreiber wrote:
> THE EXAMPLE:
> 
> A
> |--->B1
> |    |--->C1
> |    |--->C2
> |    |    |--->D
> |--->B2
> |    |--->D
> |--->[B3]
> |    |--->D
> 
> None of these modules are installed.
> The user wants to 'lin A' and intends to choose 'B3'.
> 
> CONCURRENT lin:
> 
> With concurrent lin, you have to use a different approach, because the whole dependency has to be known before any module can be built. This means, that ALL questions from CONFIGURE and DEPENDS of the whole dependency tree have to be asked and answered before any building starts, which can be done using the same depth-first algorithm as in non-concurrent lin.
> 
> This idea is kinda event-based: First we need to look at all the leaves of the tree. Leafs are those modules with no missing dependencies. Those are module 'C1' and three times module 'D' -- that is our first 'building block': {C1,D}, which can be built concurrently. Now to use our leaf-logic further, we remove all leafs from the tree:
> 
> A
> |--->B1
> |    |--->C2
> |--->B2
> |--->B3
> 
> Now again: take all leaves, C2, B2 and B3 and define the next building block {C2,B2,B3} and build them concurrently.
> 
> A
> |--->B1
> 
> The last two steps are rather simple: build only block {B1} and then only {A}.
> 
> Let us now compare the build order by using single-module building blocks for non-concurrent lin:
> non-concurrent: {C1},{D},{C2},{B2},{B3},{A}
> concurrent: {C1,D},{C2,B2,B3},{B1},{A}