Fetching the paper…

Reading the bibliography…

2017

Parallel Complexity of Forward and Backward Propagation

Naumov, Maxim

Original
PDF
Post on X

Understand

We show that the forward and backward propagation can be formulated as a solution of lower and upper triangular systems of equations.

For standard feedforward (FNNs) and recurrent neural networks (RNNs) the triangular systems are always block bi-diagonal, while for a general computation graph (directed acyclic graph) they can have a more complex triangular sparsity pattern.
We discuss direct and iterative parallel algorithms that can be used for their solution and interpreted as different ways of performing model parallelism.
Also, we show that for FNNs and RNNs with $k$ layers and $\tau$ time steps the backward propagation can be performed in parallel in O($\log k$) and O($\log k \log \tau$) steps, respectively.

Parallel Complexity of Forward and Backward Propagation · Around

Built on

R. W. Hockney
1965
Earlier work this paper cites.
B. L. Buzbee, G. H. Golub, and C. W. Nielson
1970
Earlier work this paper cites.
M. Spivak
1971
Earlier work this paper cites.
J. A. George
1973
Earlier work this paper cites.
H. S. Stone
1973
Earlier work this paper cites.
A. H. Sameh and R. P. Brent
1977
Earlier work this paper cites.
A. H. Sameh and D. J. Kuck
1978
Earlier work this paper cites.
D. P. O’Leary
1980
Earlier work this paper cites.
J. J. Dongarra and A. H. Sameh
1984
Earlier work this paper cites.
S. L. Johnsson
1985
Earlier work this paper cites.
D. E. Rumelhart, G. E. Hinton and R. J. Williams
1986
Earlier work this paper cites.
J. J. Dongarra and S. L. Johnsson
1987
Earlier work this paper cites.
R. W. Hockney and C. R. Jesshope
1988
Earlier work this paper cites.
O Egecioglu, C. K. Koc and A. J. Laub
1989
Earlier work this paper cites.

Similar

P. Werbos
1990
Cited alongside, same era.
F. L. Alvarado and R. Schreiber
1993
Cited alongside, same era.
R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst
1994
Cited alongside, same era.
C. Bishop
1995
Cited alongside, same era.
V. Simoncini and E. Gallopoulos
1996
Cited alongside, same era.
A. Greenbaum
1997
Cited alongside, same era.
P. Arbenz and M. Hegland
1998
Cited alongside, same era.

Then

M. Naumov, M. Manguoglu and A. Sameh
2010
Later among the works it cites.
Y. Zhang, J. Cohen and J. D. Owens
2010
Later among the works it cites.
U. Naumann
2012
Later among the works it cites.
M. Naumov
2012
Later among the works it cites.
J. Schmidhuber
2015
Later among the works it cites.
L. Bottou, F. E. Curtis and J. Nocedal
Original
2016
Later among the works it cites.
D. Das, S. Avancha, D. Mudigere, K. Vaidynathan, S. Sridharan, D. Kalamkar, B. Kaul and P. Dubey
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

R. A. Horn and C. R. Johnson

1999

Cited alongside, same era.

A. El Guennouni, K. Jbilou and H. Sadok

2003

Cited alongside, same era.

C. Bishop

2006

Cited alongside, same era.

E. Polizzi and A. H. Sameh

2006

Cited alongside, same era.

E. Polizzi and A. H. Sameh

2007

Cited alongside, same era.

2016

Later among the works it cites.

I. Goodfellow, Y. Bengio and A. Courville

2016

Later among the works it cites.

N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy and P. T. P. Tang

2016

Later among the works it cites.

A. Devarakonda, M. Naumov and M. Garland

2017

Closest in time.

P. Goyal, P. Dollar, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia and K. He

2017

Closest in time.

2017

Closest in time.

Y. You, Igor. Gitman and B. Ginsburg

2017

Closest in time.