Optimal Algorithms for Synthesis of Reliable Application-Specific Heterogeneous Multiprocessors

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.