Partitioning of Polynomial Tasks: Test Generation, an Example

Jacob Savir, Paul H. Bardell

Research output: Contribution to journalArticlepeer-review


The objective of this paper is to analyze the circumstances under which a partitioning of a task with a polynomial complexity will result in an overall reduction of its execution time. It is assumed that the task executor is sequential in nature, namely, it can execute only one task at a time. Since partitioning of a task into smaller subtasks will, most probably, result in subtask overlap, there is a risk that a given partitioning scheme will yield an increase of its overall execution time. Formulas are derived to test the effectiveness of any proposed partitioning scheme. In the case of multiple partitioning options, the best one can be easily obtained. One of the possible tasks that this analysis is applicable to is the test generation of digital circuits with a uniprocessor.

Original languageEnglish (US)
Pages (from-to)1465-1468
Number of pages4
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
StatePublished - Nov 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Partitioning of Polynomial Tasks: Test Generation, an Example'. Together they form a unique fingerprint.

Cite this