Title :
A heuristic approach for embedding communication patterns in an interconnection cached parallel processing network
Author :
Gupta, Vipul ; Schenfeld, Eugen
Author_Institution :
Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
Abstract :
The problem of identifying whether a graph has a bounded l-contraction for a given integer l is known to be NP-complete for l>2. The authors describe a heuristic approach based on simulated annealing to approximate the solution of this problem. Performance results of their algorithm on graphs representing classical topologies (e.g. trees, grids, hypercubes and cube connected cycles), are presented as well
Keywords :
computational complexity; heuristic programming; hypercube networks; simulated annealing; NP-complete; bounded l-contraction; cube connected cycles; embedding communication patterns; grids; heuristic approach; hypercubes; interconnection cached parallel processing network; simulated annealing; trees; Communication switching; Computer science; Multiprocessor interconnection networks; National electric code; Network topology; Parallel algorithms; Parallel processing; Routing; Switches; Throughput;
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
DOI :
10.1109/IPPS.1993.262895
