Browse Prior Art Database

Evaluating the Effectiveness of Task Partitioning

IP.com Disclosure Number: IPCOM000101965D
Original Publication Date: 1990-Sep-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 96K

Publishing Venue

IBM

Related People

Bardell, PH: AUTHOR [+2]

Abstract

Many design automation tasks exhibit a polynomial complexity in practice. This means that the time needed to execute the task grows according to some power p of the number of task elements. If N is the number of elements in the task, then the time to execute the task is proportional to Np . We denote this mathematically by saying that the task complexity is of the order O(Np).

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

Evaluating the Effectiveness of Task Partitioning

       Many design automation tasks exhibit a polynomial
complexity in practice.  This means that the time needed to execute
the task grows according to some power p of the number of task
elements.  If N is the number of elements in the task, then the time
to execute the task is proportional to Np .  We denote this
mathematically by saying that the task complexity is of the order
O(Np).

      Generally speaking, partitioning of a task into smaller
subtasks has the potential of reducing its execution time. Since
partitioning of a task into smaller subtasks will, most likely,
result in subtask overlap, there is a risk that a given partitioning
scheme will yield an increase of its overall execution time.  It is
important, therefore, to be able to determine whether or not a given
partitioning will actually result in a reduction of the task
execution time without actually executing it.

      The object of this disclosure is to devise an easy test that
will enable one to determine a priori whether or not a proposed
partitioning of a given task will result in any savings in its
execution time.  This test will save the elaborate step of actually
executing the task, and then realizing that no saving in execution
time was, in fact, encountered.

      It is assumed that the task executor is sequential in nature,
namely, it can only execute one task at a time.

                            (Image Omitted)

      Let T be a task that is composed of N elements.  The complexity
of the task is bounded by the polynomial kNp, where k is a given
constant, and p/1.  When p=1, the task is said to have a linear
complexity; when p=2 it is said to have a quadratic complexity, etc.
For the sake of simplicity let the execution time,  , be given by
      (1)          = kNp .

      Assume now that the task T of N elements is partitioned into a
set of subtasks Ti of Ni elements, 1=1,2,...,m.  The subtasks are not
necessarily disjoint, namely, some of the elements of Ti may also
appear in Ti, j/i.  Let  i be the execution time of subtask Ti .  The
overall time to execute the partitioned task is   m   i .  The
question is under
 i=1 what circumstances will the partitioned task execute in less
time than the original task, namely, under what conditions
      (2)       m...