A SCALABLE PARALLEL FORMULATION OF THE BACKPROPAGATION ALGORITHM FOR HYPERCUBES AND RELATED ARCHITECTURES

In this paper, we present a new technique for mapping the backpropagat ion algorithm on hypercubes and related architectures. A key component of this technique is a network partitioning scheme called checkerboar ding, Checkerboarding allows ns to replace the ail-to-all broadcast op eration performed by the commonly used vertical network partitioning s cheme, with operations that are much faster on the hypercubes and rela ted architectures. Checkerboarding can be combined with the pattern pa rtitioning technique to form a hybrid scheme that performs better than either one of these schemes. Theoretical analysis and experimental re sults on nCUBE(R) and CM5(R) show that our scheme performs better than the other schemes, for both uniform and nonuniform networks.