ROUTING AND BROADCASTING ON INCOMPLETE AND GRAY CODE INCOMPLETE HYPERCUBES

Abstract

We propose new deadlock-free routing and broadcasting algorithms for incomplete hypercube network that have optimal communication and computation time. Broadcasting algorithm may run on one-port communication model of hypercube and is suitable for both the asynchronous (MIMD, or distributed) and synchronous (SIMD, or parallel) hypercube models. Routing and broadcasting procedures have optimal distance paths between any two nodes. We then introduce a new model of computation, Gray code incomplete hypercube (GCIH), which is an interval of nodes of hypercube in Gray code order, and obtain similar results for the new model.

KEY WORDS:

• Hypercubes
• incomplete hypercubes
• routing
• broadcasting
• data communication
• Gray code
• asynchronous and synchronous hypercube models

C.R. CATEGORIES:

• C.1.2
• F.1.2
• F.2.2

Additional information

Notes on contributors

IVAN STOJMENOVIĆ

This research was supported by the Natural Sciences and Engineering Research Council of Canada