Title :
The difficulty of finding good embeddings of program graphs onto the OPAM architecture
Author :
Ramamurthy, Badrinath ; Krishnamoorthy, Mukkai S.
Author_Institution :
Dept. of Comput. Sci., Indian Inst. of Technol., Kharagpur, India
Abstract :
We describe a problem that arises in mapping process graphs onto a certain communication architecture. The problem is called bounded p contractability. We have shown in earlier work that the problem is NP complete. We present two results: the first is a result on a corresponding approximation problem and the second is a heuristic for the problem based on local search. The heuristic is compared with an existing heuristic for the problem
Keywords :
computational complexity; graph theory; optical interconnections; parallel architectures; search problems; NP complete; OPAM architecture; Optical Parallel Architecture Model; approximation problem; bounded p contractability; communication architecture; heuristic; local search; process graphs; program graph embedding; Communication switching; Computer architecture; Computer science; High speed optical techniques; Optical interconnections; Optical switches; Parallel architectures;
Conference_Titel :
Massively Parallel Processing Using Optical Interconnections, 1995., Proceedings of the Second International Conference on
Conference_Location :
San Antonio, TX
Print_ISBN :
0-8186-7101-7
DOI :
10.1109/MPPOI.1995.528636
