Optimal parallel back-propagation schemes for mesh-connected and bus-connected multiprocessors

Optimal parallel schemes that minimize communication overhead for the backpropagation algorithm on neural networks (NNs) are proposed. A parallel computation framework of the backpropagation algorithm is discussed, and the lower-bound of communication overhead is provided. Optimal schemes for mesh-connected and bus-connected architectures based on this framework are proposed. The scheme for the mesh-connected architecture achieves the lower-bound of communication overhead. The scheme for the bus-connected architecture reduces it to the square-root order of the number of processors, while the conventional scheme requires a linear order overhead