I/O embedding in hypercubes Conference Paper uri icon


  • Multiprocessor systems based on the hypercube or binary n-cube topology use I/O processors to handle the data transfer between the processors and the outside world or the host. A method of embedding the I/O processors in such a system is proposed. The method is shown to require far fewer links than the earlier methods. The method achieves a higher I/O adjacency, and as a result, higher degree of tolerance of I/O failures. Necessary and sufficient conditions to obtain such an embedding are derived. A generalization of the problem to k-regular network is presented and necessary conditions for I/O embedding in such network are derived. It is shown that embedding in a general k-regular network is NP-complete. An algorithm for finding a minimal embedding in a k-regular network is presented.

published proceedings

  • Proceedings of the International Conference on Parallel Processing

author list (cited authors)

  • Reddy, A., Banerjee, P., & Abraham, S. G.

complete list of authors

  • Reddy, ALN||Banerjee, P||Abraham, SG

publication date

  • December 1988