Prioritizing non-dependent targets in parallel make

[tom honermann]

I'm working on optimizing our GNU make based build system to reduce 
build times.  Consider the
following dependencies with these run times for each target:

   A:       # 3 minutes
   B: C D   # 1 minutes
   C:       # 1 minutes
   D:       # 1 minutes
   E:       # 6 minutes

There are many valid orders in which the targets can be built.  When make
is invoked with the parallel execution (-j) option, the order in which the
non-dependent targets are scheduled has a significant impact on the total
run time.  Consider the following schedules for the above dependencies.
(View with a fixed width font if the tables don't line up properly)

+------+-------------+    +------+-------------+
| Time | Jobs (-j 2) |    | Time | Jobs (-j 2) |
+------+------+------+    +------+------+------+
|    0 |    A |    C |    |    0 |    A |    E |
|    1 |    A |    D |    |    1 |    A |    E |
|    2 |    A |    B |    |    2 |    A |    E |
|    3 |    E |      |    |    3 |    C |    E |
|    4 |    E |      |    |    4 |    D |    E |
|    5 |    E |      |    |    5 |    B |    E |
|    6 |    E |      |    |    6 |      |      |
|    7 |    E |      |    |    7 |      |      |
|    8 |    E |      |    |    8 |      |      |
+------+------+------+    +------+------+------+

The table on the left illustrates a worst-case schedule (9 minutes) and the
one on the right illustrates a best-case schedule (6 minutes).  The 
difference
in build times is 30%.

Clearly, make can't be expected to know how long each target will take to
complete, so any scheduling hints for make would have to be specified in
the Makefile (or learned from prior runs).  As far as I can tell, GNU make
doesn't have any features that enable the Makefile author to provide
scheduling hints.

I am interested to know what others have done to optimize their Makefiles
for parallel execution.  Has anyone worked on enhancements to GNU make that
would allow some targets to be prioritized over others (without introducing
strict dependencies)?

If no prior effort has been made to support target prioritization, I have a
few proposals for how such support might be added to GNU make.  I don't have
any insight into the effort required to implement these however.

GNU make has a syntax for order only prerequisites.  A similar extension
could be used to define relative priorities between targets.  The following
syntax would specify that the PRIORITY-PREREQUISITES should be started 
before
building TARGETS.  Naturally, specifying priority prerequisites would have
no effect in non-parallel make invocations.

   TARGETS : NORMAL-PREREQUISITES | ORDER-ONLY-PREREQUISITES ^ 
PRIORITY-PREREQUISITES

Alternatively, priority levels could be specified using a numeric system and
a syntax similar to the vpath directive.

   priority LEVEL TARGETS

For the dependency example above, the following directives would ensure an
optimal build schedule.  (for the priority directive example, lower numbers
have higher priorities, default priority is 0)

   C D B: ^ A E

   priority -1 A E

Comments?

Tom.