Efficient Embeddings of Trees in Hypercubes

Abstract

THE BOOLEAN HYPERCUBE IS A PARTICULARLY VERSATILE NETWORK FOR PARALLEL COMPUTING. IT IS WELL KNOWN THAT MULTI-DIMENSIONAL GRID MACHINES CAN BE SIMULATED ON A HYPERCUBE WITH NO COMMUNICATIONS OVERHEAD. IN THIS PAPER WE SHOW THAT EVERY BOUNDED-DEGREE TREE CAN BE SIMULATED ON THE HYPERCUBE WITH CONSTANT COMMUNICATIONS OVERHEAD. OUR PROOF IN FACT SHOWS THAT EVERY BOUNDED-DEGREE GRAPH WITH AN 0(1)-SEPARATOR CAN BE EMBEDDED IN A HYPERCUBE OF THE SAME SIZE WITH DILATION AND CONGESTION BOTH 0(1). WE PROVE ALSO THAT NOT ALL BOUNDED-DEGREE GRAPHS CAN BE EFFICIENTLY EMBEDDED WITHIN THE HYPERCUBE.