Optimal Algorithms for Synthesis of Reliable Application-Specific Heterogeneous Multiprocessors

Aurobindo Dasgupta, Ramesh Karri

Research output: Contribution to journalArticlepeer-review


Fast and optimally-reliable application-specific multiprocessor-synthesis is critical in system-level design, especially in medical, automotive, space, and military applications. Previous work in multiprocessor-synthesis & task-allocation for performance & reliability requires exponential time, and therefore, is useful only for small examples. We present the first deterministic and provably-optimal algorithm (RELSYN-OPT) to synthesize real-time, reliable multiprocessors using a heterogeneous library of N processors and L link types. We prove that for a series-parallel graph with M subtasks and nested-depth d, the worst-case computational complexity of RELSYN-OPT is O(M·(L+N)·Nd). For tree-structured task graphs, RELSYN-OPT runs in O(M·(L+N)), and is asymptotically optimum. RELSYN-OPT, because of its speed, applies to static & dynamic task allocation for an ultra-reliable distributed processing environment for which, until now, research has produced only suboptimal heuristic solutions.

Original languageEnglish (US)
Pages (from-to)603-613
Number of pages11
JournalIEEE Transactions on Reliability
Issue number4
StatePublished - Dec 1995


  • Heterogeneous multiprocessor system
  • task allocation

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal Algorithms for Synthesis of Reliable Application-Specific Heterogeneous Multiprocessors'. Together they form a unique fingerprint.

Cite this