Title :
Synthesis of reliable application specific heterogeneous multiprocessors
Author :
Dasgupta, Aurobindo ; Karri, Ramesh
Author_Institution :
Dept. of Electr. & Comput. Eng., Massachusetts Univ., Amherst, MA, USA
fDate :
30 Apr-3 May 1995
Abstract :
We present a deterministic and provably optimal algorithm to synthesize real time, reliable multiprocessors using a heterogeneous library of N processors and L link types. For a series-parallel task graph consisting of M sub tasks and with a nested depth d, the worst-case complexity of the proposed algorithm is O(M(L+N)Nd). For tree-structured task graphs, on the other hand, the algorithm runs in O(M(L+N)) time, and is also asymptotically optimum
Keywords :
application specific integrated circuits; computational complexity; multiprocessing systems; parallel algorithms; parallel architectures; real-time systems; trees (mathematics); application specific heterogeneous multiprocessors; asymptotically optimum algorithm; heterogeneous library; nested depth; optimal algorithm; series-parallel task graph; tree-structured task graphs; worst-case complexity; Application software; Costs; Equations; Libraries; Mission critical systems; Multiprocessing systems; Reliability; Safety; Space missions; Tree graphs;
Conference_Titel :
Circuits and Systems, 1995. ISCAS '95., 1995 IEEE International Symposium on
Conference_Location :
Seattle, WA
Print_ISBN :
0-7803-2570-2
DOI :
10.1109/ISCAS.1995.520363
