Browse Prior Art Database

Efficient Determination of Order and Parallelism of Build Events

IP.com Disclosure Number: IPCOM000113373D
Original Publication Date: 1994-Aug-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 6 page(s) / 149K

Publishing Venue

IBM

Related People

Bronchetti, SF: AUTHOR [+7]

Abstract

A method is described for determining from a build tree which of the contained objects are out of date and need to be rebuilt. The method then structures the objects to be built such that it can maximize the parallelism and distribution of those builds across multiple platforms.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 20% of the total text.

Efficient Determination of Order and Parallelism of Build Events

      A method is described for determining from a build tree which
of the contained objects are out of date and need to be rebuilt.  The
method then structures the objects to be built such that it can
maximize the parallelism and distribution of those builds across
multiple platforms.

Take the example noted below.
               A.exe
                  |
                  ---- A.o
                  |           |
                  |            --- A.c
                  |                     |
                  |                      --- Util.c
                  ---- B.o
                              |
                               --- B.c
                                        |
                                         --- Util.c

      The  algorithm hinges on the notion of "Build events" that link
two build objects together.   For example, when a  user  updates  the
file  Util.c,  the  build  events that connect Util.c to A.c and that
connect Util.c to B.c are updated to reflect the change.    They  are
also marked as needing to be rebuilt.

      Once  this  update  occurs,  a user can specify to build at any
stage in this tree.  For example, a user requests from A.exe to build
that object.  The algorithm proceeds as follows:

o   For  the  one  build event that connects A.exe with it's children
    nodes in the tree, the question is asked : "Are you up to date ?"
    In order to answer this, the build event forwards the request  to
    the objects to which it is connected.

o   Each  lowest  level  build  event  (determined by lack of further
    build events in its child branches) that is not  up  to  date  is
    added as a key (entry in the left column) to the table.

o   The recursion returns a level, with each build event connected to
    an  out-of-date  build  event also marking itself as being out of
    date.  Each build event that is now marked as out of date at this
    level of the tree is added to the table as a new  key  (entry  in
    the  left column) with the children build events added as entries
    in the right column.

o   This recursion continues until the Build event that initiated the
    whole recursion is reached.

o   Each row in the table that  has  no  right  entry  can  be  built
    immediately  in  parallel with any other row with no right entry.
    When complete, that row is either marked as done or removed  from
    the table.

o   When  a  build  of  one of those rows is complete, that object is
...