I/O embedding in hypercubes Conference Paper uri icon

abstract

  • 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.

author list (cited authors)

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

publication date

  • December 1988