OPTIMAL-ALGORITHMS FOR SYNTHESIS OF RELIABLE APPLICATION-SPECIFIC HETEROGENEOUS MULTIPROCESSORS

Fast and optimally-reliable application-specific multiprocessor-synthe sis is critical in system-level design, especially in medical, automot ive, space, and military applications. Previous work in multiprocessor -synthesis & task-allocation for performance & reliability requires ex ponential time, and therefore, is useful only for small examples, We p resent the first deterministic and provably-optimal algorithm (RELSYN- OPT) to synthesize real-time, reliable multiprocessors using a heterog eneous library of N processors and L link types. We prove that for a s eries-parallel graph with M subtasks and nested-depth d, the worst-cas e computational complexity of RELSYN-OPT is O(M .(L + N).(d)). For tre e-structured task graphs, RELSYN-OPT runs in O(M .(L + N)), and is asy mptotically optimum, RELSYN-OPT, because of its speed, applies to stat ic & dynamic task allocation for an ultra-reliable distributed process ing environment for which, until now, research has produced only subop timal heuristic solutions.