  Krylov subspace methods are among the most efficient solvers for large scale
linear algebra problems. Nevertheless, classic Krylov subspace algorithms do
not scale well on massively parallel hardware due to synchronization
bottlenecks. Communication-hiding pipelined Krylov subspace methods offer
increased parallel scalability by overlapping the time-consuming global
communication phase with computations such as spmvs, hence reducing the impact
of the global synchronization and avoiding processor idling. One of the first
published methods in this class is the pipelined Conjugate Gradient method
(p-CG). However, on large numbers of processors the communication phase may
take much longer than the computation of a single spmv. This work extends the
pipelined CG method to deeper pipelines, denoted as p(l)-CG, which allows
further scaling when the global communication phase is the dominant
time-consuming factor. By overlapping the global all-to-all reduction phase in
each CG iteration with the next l spmvs (deep pipelining), the method hides
communication latency behind additional computational work. The p(l)-CG
algorithm is derived from similar principles as the existing p(l)-GMRES method
and by exploiting operator symmetry. The p(l)-CG method is also compared to
other Krylov subspace methods, including the closely related classic CG and
D-Lanczos methods and the pipelined CG method by Ghysels et al.. By analyzing
the maximal accuracy attainable by the p(l)-CG method it is shown that the
pipelining technique induces a trade-off between performance and numerical
stability. A preconditioned version of the algorithm is also proposed and
storage requirements and performance estimates are discussed. Experimental
results demonstrate the possible performance gains and the attainable accuracy
of deeper pipelined CG for solving large scale symmetric linear systems.
