\section{Introduction}

\pretolerance=15000  \tolerance=15000
\def\thinspace{\thinspace}

      This is two papers in one, as reflected in the title:

      My original aim was to summarize the Kormendy \& Ho (2013) review of supermassive black hole (BH)
mass measurements and their use to investigate whether host galaxies are influenced by radiative or
kinetic feedback while BHs grow by accretion as active galactic nuclei (AGNs).

      However, other speakers at this conference (e.{\thinspace}g.,~Bureau 2019) echo published papers
that cast doubts on measurements of BH mass $M_\bullet$ scaling relations.  They claim that we are biased
toward high $M_\bullet$ because BH spheres of gravitational influence are small, so only the
highest-$M_\bullet$ BHs are preferentially discovered. I therefore added a demonstration that the BHs which
satisfy tight $M_\bullet$\thinspace--{\thinspace}host galaxy correlations{\thinspace}--{\thinspace}and {\it only} those BHs{\thinspace}--{\thinspace}are
discovered in classical bulges and ellipticals with no significant bias in favor of special,
compact galaxies with respect to fair samples that include more diffuse objects.  I was limited in how much detail
I could include in real time.  Here, Section 3 enlarges on the evidence that derived $M_\bullet$\thinspace--{\thinspace}host
galaxy correlations are not biased by selection effects.

      A point of casting doubt can be to introduce a new technique that comes~to~the~rescue.  Bureau (2019)
emphasizes that molecular gas kinematic measurements with ALMA, the Atacama Large Millimeter Array, can have
higher spatial resolution and certainly have different and better controlled measurement systematics than does
optical spectroscopy.  Also, measurements of nuclear megamaser disks are immune from optical atmospheric blurring.
They can find smaller BHs farther away.  In Section 4, I add to published BH scaling relations the new BH
detections{\thinspace}--{\thinspace}most of them from molecular gas kinematics{\thinspace}--{\thinspace}reported at this meeting.
I show that the molecular disk mass measurements define the same BH correlations as do stellar and ionized
gas dynamic measurements.  This is also true for BH masses derived from maser disk dynamics.

\vskip -26pt \null

\section{M{\lower 2pt \hbox{$\bullet$}} Measurements. I. Halo Dark Matter and Broad Emission Lines}

      Kormendy \& Ho (2013) review $M_\bullet$ measurements.  Two techniques require ``tweaks'':

      The state of the art for stellar dynamical $M_\bullet$ measurement is Schwarzschild (1979) orbit superposition
modeling.  This now includes the superposition of tens of thousands of stellar orbital density distributions and
the fitting of line-of-sight velocity distributions from two-dimensional spectroscopy.  Another improvement is the
addition of halo dark matter (DM) to dynamical models
(Gebhart \& Thomas 2009;
Schulze \& Gebhardt~2011;
Gebhardt et al.~2011;
Rusli et al.~2013).
Adding DM at large radii causes us to decrease the stellar mass-to-light ratio. Because we assume that
mass-to-light ratio is independent of radius, we decrease the mass-to-light ratio at small radii, too.  Then we
have to increase $M_\bullet$ in order to continue to explain high velocities there.  This proves to make a bigger
difference if the black hole sphere of influence is poorly resolved (Schulze \& Gebhardt 2011; Rusli et al.~2013).
It also tends to be more important for core-nonrotating-boxy ellipticals (see Kormendy et al.~2009 for a summary
of the division into core and coreless ellipticals).  These effects and the improvements in orbit sampling
increase our estimates of $M_\bullet$, in many cases by factors of $\sim$\ts2.
In particular, the BH in M{\thinspace}87 is found to have a mass of $M_\bullet = (6.2 \pm 0.4) \times 10^9$
$M_\odot$ (Gebhardt \& Thomas 2009; Gebhardt et al. 2011).

      This is 1.7 times larger than $M_\bullet = (3.6 \pm 1.0) \times 10^9$~$M_\odot$ given by Hubble Space
Telescope (HST) spectroscopy of the emission-line rotation curve $V(r)$
(Macchetto et al. 1997).  Similarly, the stellar-dynamic $M_\bullet$ is larger than the gas-dynamic estimate in NGC\ts3998.
In both cases and for several other galaxies with emission-line HST $M_\bullet$ measurements, the authors noted
that the emission line widths are comparable to the velocity amplitudes.  These widths were ignored in the analysis,
based on the assumption that gas clouds may have high internal velocity dispersions but may rotate around the
center at lower~$V(r)$.  This is dangerous:~Nobody makes stellar dynamical models ignoring~velocity~dispersions.
Now, we have independent confirmation of the M{\thinspace}87 BH mass from the Event Horizon Telscope collaboration
(2019), $M_\bullet$\thinspace=\thinspace(6.5\thinspace$\pm$\ts0.2\thinspace$\pm$0.7)\thinspace$\times$\thinspace$10^9$\thinspace$M_\odot$.
{\it Kormendy \& Ho 2013 omit from BH correlations nine $M_\bullet$ measurements that they conclude
are underestimated because broad emission-line widths were ignored.}  Caution:~these underestimated masses
are still included\thinspace--{\thinspace}and produce a bias\thinspace--{\thinspace}in many published derivations of BH correlations.

\vskip -26pt \null

\section{M{\lower 2pt \hbox{$\bullet$}} Measurements. II. Are Sample Selection Effects Important?}

      The answer is ``no'' for the classical bulges and ellipticals that satisfy tight
$M_\bullet$\thinspace--{\thinspace}host correlations but ``yes'' for pseudobulges and disks that do not satisfy such correlations.

      At this meeting, Bureau (2019) and others echo van den Bosch et al.~(2015) who conclude that BHs are discovered
only in ``the densest of galaxies, which [are] not representative of the galaxy population at large.  This is evident
from the distribution of host galaxy properties \dots~shown in [their] Figure 8.  It is striking how the host
galaxies trace out a very narrow locus in this parameter space.  This is most obvious in the luminosity--size panel,
where they lie along a narrow line, sampling preferentially the densest galaxies.  Note that the black hole
host galaxies are typically denser than the average (early-type) galaxies'' (see also van den Bosch 2016).

\vfill\eject

      Figure\ts1 shows projections of the fundamental plane correlations for  ellipticals and classical
bulges; $r_e$ vs.~$M_V$ is the bottom panel.  BH detections sample the complete range of parameters
for bulges and ellipticals.  We do not preferentially find~BHs in the most compact galaxies.  Contrast
unrelated spheroidal galaxies:~they are more diffuse.  In Figure 1, the scatter for the BH host galaxies
is actually smaller than the scatter for the

\begin{figure}[b]
\vspace*{-2.0 cm}
\begin{center}
\includegraphics[width=4.5in]{kormendy-fig1ss.ps}
\end{center}
\vspace*{-0.3 cm}
\caption{Parameter correlations for elliptical galaxies and classical bulges of disk galaxies (dark gray)
and for spheroidal galaxies (lighter gray).  The bottom panels show the effective radius~$r_e$ that
contains one-half of the $V$-band light and the effective surface brightness $\mu_e$ at $r_e$ as functions
of the total $V$-band absolute magnitude of the galaxy component.  The top panel shows the
Kormendy (1987) relation, $\mu_e$ versus $r_e$; this projection shows the fundamental plane nearly edge-on
and has especially small scatter.  Sources are given in the keys.  Galaxies in which supermassive black holes
are detected via spatially resolved stellar or gas dynamics are encoded in dark red for ellipticals and
dark brown for bulges.  This figure is adapted from Figure 16 of Kormendy \& Bender (2012), who provide
the references in the keys for Sph galaxies.}
\label{fig2}
\end{figure}

\newpage

\noindent galaxies that define the fundamental plane, both toward compactness (small $r_e$ and bright $\mu_e$) and
toward diffuseness (large $r_e$ and faint $\mu_e$).  The reason is that the BH hosts tend to be relatively
nearby and are studied more accurately (e.{\thinspace}g., in Kormendy et al.~2009, where many sources of photometry are
combined) than the more heterogeneous data on more distant ellipticals and bulges.  The fundamental plane
is well known to have small intrinsic scatter perpendicular to the plane (e.{\thinspace}g., J\o rgensen et al.~1996).
That's why BH hosts ``trace out a very narrow locus in [$r_e$\thinspace--\thinspace$M_V$] space''
(van den Bosch's words).

      Shankar et al.~(2016) also worry about $M_\bullet$ bias:~``We confirm that
the majority of black hole hosts have significantly higher velocity dispersions $\sigma$ than local galaxies
of similar stellar mass.  We use Monte Carlo simulations to illustrate the effect on black hole scaling
relations if this bias arises from the requirement that the black hole sphere of influence must be resolved
to measure black hole masses with spatially resolved kinematics.  We find that this selection effect artificially
increases the normalization of the $M_\bullet$\thinspace--\thinspace$\sigma$ relation by a factor of at least $\sim$3; the
bias for the $M_\bullet$\thinspace--\thinspace$M_{\rm bulge}$ relation is even larger.''

      Figure 2 shows the Faber-Jackson (1976) correlation between $\sigma$ and absolute magnitude from
Kormendy \& Bender (2013).  I use this because the galaxies are relatively nearby and well studied;
e.{\thinspace}g., HST was used to look for cores.  BH hosts tend to be high in luminosity; we do not search for BHs
in distant, tiny ellipticals for which we know we don't have sufficient spatial resolution.  But the $\sigma$
{\it scatter} is fairly sampled at least at $M_V > -22$.  The BH host at $M_V \simeq -18$ and $\sigma \simeq 170$
km s$^{-1}$ is NGC 4486B; this is one of the ``BH monsters'' that lie far above the BH correlations in Figure 3.
At $M_V < -22$, the core ellipticals that are known to be BH hosts do have slightly higher $\sigma$ than the
\phantom{000000000000}

\begin{figure}[b]
\vspace*{-2.2 cm}
\begin{center}
 \includegraphics[width=5.2in]{kormendy-fig2.eps}
\end{center}
\vspace*{-0.3 cm}
\caption{Faber-Jackson (1976) correlations for ellipticals with and without a ``core'', i.{\thinspace}e.,
a break in the density profile near the center from a steep outer profile to a shallow inner cusp.
Total $V$-band absolute magnitudes and velocity dispersions are from Lauer et al.~(2007) with corrections
from Kormendy et al.~(2009) and Kormendy \& Bender (2013).  This figure is from the latter paper,
here labeling galaxies that have BH detections from spatially resolved near-central dynamics.  The lines
are symmetric least-squares fits (Tremaine et al.~2002) to the core galaxies (solid line with gray shading)
and the coreless galaxies (dashed line with lighter shading of 1-$\sigma$ fit uncertainties).  The kink at
$\sigma \simeq 250$ km s$^{-1}$ was also emphasized by Lauer et al.~(2007).}
\label{fig1}
\end{figure}

\newpage

\noindent galaxies that are not known to be BH hosts.  However, {\it the reason is not that we looked for BHs and failed.
If that were the case, then Shankar's criticism would be valid.}  Rather, these are (e.{\thinspace}g., more distant)
galaxies that have not been searched for BHs.  The BH correlations in Figure 3 do not show a kink at $M_K \simeq -25$
corresponding to $M_V \simeq -22$ as would be the case if $M_\bullet$ values were fairly sampled at $M_V > -22$
but, at $M_V < -22$, were overestimated by an ``even larger'' factor than ``at least $\sim$3'' as Shankar suggests.

      Note in Figure 2 that coreless ellipticals have the well known $L_V$\thinspace$\propto$\thinspace$\sigma^4$
correlation, whereas core ellipticals have an $L_V$\thinspace$\propto$\thinspace$\sigma^8$
correlation.  These are understood to result, respectively, from ``wet'' major mergers with cold gas dissipation
and central starbursts and dissipationless, ``dry'' mergers in which $\sigma$ grows only slowly with
luminosity $L_V$.

      Shankar and van den Bosch believe that typical galaxies are more diffuse than BH hosts
because they compare to large samples of galaxies measured by the Sloan Digital Sky Survey.
These must mainly be far away, so spectroscopic apertures sample large radii that include
outward $\sigma$ decreases and{\thinspace}--{\thinspace}more importantly\thinspace--{\thinspace}galaxy disks.  Also, they do not
make bulge-disk decompositions but rather include galaxy disks and pseudobulges in single measurements of
$r_e$, $\mu_e$, and $\sigma$.  Pseudobulges and disks are fluffier than classical bulges and ellipticals.
They do not participate in BH{\thinspace}--{\thinspace}host correlations (Section 5).

\vskip -25pt \null

\section{M{\lower 2pt \hbox{$\bullet$}} -- Host Galaxy Correlations for Classical Bulges and Ellipticals}

      Figure 3 shows the correlations of $M_\bullet$ with the $K$-band luminosity and
the velocity dispersion of the host bulge measured outside the BH sphere of influence.   The intrinsic scatter is
essentially the same for both correlations, respectively, 0.30 and 0.28 dex.  Using

\vfill

\begin{figure}[b]
\vspace*{-2.2 cm}
\begin{center}
\special{psfile=kormendy-fig3-left.eps  hoffset=-20 voffset=-56 hscale=36.5 vscale=36.5}
\special{psfile=kormendy-fig3-right.eps hoffset=181 voffset=-56 hscale=36.5 vscale=36.5}
\end{center}
\vspace*{-0.0 cm}
\caption{Correlations of BH mass with ({\it left}) $K$-band luminosity and
absolute magnitude and ({\it right}) velocity dispersion of the host elliptical galaxy or classical bulge.
This is Figure~17~of Kormendy \& Ho (2013) with six galaxies added (see the key).  Lines and shaded 1-$\sigma$
uncertainties are symmetric least-squares fits to the Kormendy \& Ho sample. The fits omit BH monsters that
have BH mass fractions of $>$\thinspace10\thinspace\% (two lightly shaded~points).  Important: this figure omits
pseudobulges and major mergers in progress.  Pseudobulges show no tight $M_\bullet$\thinspace--{\thinspace}host
correlations.  Mergers in progress also do not participate in these correlations: they have undermassive BHs.
Only classical bulges and ellipticals as shown here participate in tight $M_\bullet$ correlations that
are suggestive of BH\thinspace--{\thinspace}host coevolution. Figures 1 and 2 show that these objects
fairly sample the fundamental plane correlations. We see no signs that the detected BH masses are biased
by sample selection.  And the new BH detections mostly added at this meeting ({\it key}) extend and are consistent
with the $M_\bullet$\thinspace--{\thinspace}host correlations.}
\label{fig1}
\end{figure}

\newpage

\noindent mass-to-light ratios to convert $L_K$ to bulge stellar mass $M_{\rm bulge}$ (Figure 4, bottom left),
\vskip -12pt
$$
\quad{{M_\bullet} \over {10^9~M_\odot}} = \biggl(0.49^{+0.06}_{-0.05}\biggr)\
                                           \biggl({{M_{\rm bulge}} \over
                                                  {10^{11}{\thinspace}M_{\odot}}}\biggr)^{1.17 \pm 0.08};~
                           {\rm intrinsic~scatter} = 0.28~{\rm dex}. \eqno{(1)}
$$
\vskip -5pt
The canonical BH-to-bulge mass ratio,
$M_\bullet/M_{\rm bulge} = 0.49^{+0.06}_{-0.05}$\thinspace\% at $M_{\rm bulge} = 10^{11}$\thinspace$M_\odot$,
is 2--4 times larger than previous values, because (1) we omit pseudobulges; they do not satisfy
$M_\bullet$ correlations; (2) we omit galaxies with $M_\bullet$ measurements based on ionized gas dynamics that
do not account for broad emission-line widths; (3) we omit mergers~in progress:~Kormendy \& Ho show that
these have undermassive black holes, in part because progenitor disks have undermassive BHs.  And (4) many
BH masses were revised upward when halo DM and more complete orbit sampling were added to dynamical models.

      To further address possible bias in deriving BH{\thinspace}--{\thinspace}host correlations, I add
six new BH mass measurements to Figure\ts3, five of them reported at this meeting.  They are identified in the key;
NGC\ts1380 (Tsukui 2019);
NGC\ts383, NGC\ts404, and NGC\ts4697 (Bureau 2019),
NGC\ts6958 (Thater 2019), and
Holm 15A (Mehrgan et al.~2019).

      Bureau's measurement in NGC\ts4697 of $M_\bullet = 1.39^{+0.07}_{-0.03} \times 10^8$ $M_\odot$ via an
ALMA molecular gas rotation curve (scaled to distance 12.54 Mpc as in Kormendy \& Ho 2013) is slightly smaller
than but consistent with $M_\bullet = 2.02^{+0.51}_{-0.50} \times 10^8$ $M_\odot$ from stellar dynamics.
The same appears true of NGC\ts6958 (all new $M_\bullet$ measurements reported at this meeting are preliminary).
If differences persist between ALMA-derived and stellar dynamical $M_\bullet$ measurements,
this may point to a systematic error in one or both techniques.  If the problem is stellar dynamics, then a
likely culprit is the assumption that $M/L$ is independent of radius.  Allowing stellar $M/L$ to increase
toward galaxy centers may decrease BH mass estimates by a few tens of percents (McConnell et al.~2013).

      All new galaxies except Holm 15A were measured using molecular gas rotation~curves.
Bureau (2019) emphasizes that they have different systematics from other $M_\bullet$ machinery.
Despite his concerns about biases, they are consistent with the Figure 3 correlations.

      Agreement between stellar dynamics, ionized gas dynamics, megamaser dynamics, and ALMA-based
molecular gas dynamics supports our conclusion (Kormendy \& Ho 2013) that the BH{\thinspace}--{\thinspace}host
bulge correlations are robust.  The discussion of Section 3 further reassures us that biased BH samples
do not significantly affect the derived correlations.

      \underline{Important:} This conclusion applies only to $M_\bullet$ correlations for classical bulges and
ellipticals.  Section 5 reviews the evidence that $M_\bullet$ shows no such strong correlations with pseudobulges,
disks, or dark matter halos. BH searches in such objects have frequently yielded only $M_\bullet$ upper limits.  The
BH masses observed in these components almost certainly are upper envelopes of BH mass distributions that
extend to lower masses.

      \underline{Returning to astrophysical conclusions:} Figure 3 adds the biggest BH discovered so far in
the nearby Universe, $M_\bullet = (4.0 \pm 0.8) \times 10^{\rm 10}$ $M_\odot$ in Holm 15A, the giant elliptical
with the largest known core (Mehrgan et al.~2019).  It extends the $M_\bullet$\thinspace--\thinspace$L_{K,\rm bulge}$
correlation toward larger luminosities and strengthens an important conclusion that has become evident as
we find more giant BHs.  As concluded by Kormendy \& Ho (2013) and as seen also by McConnell et al. (2011),
the $M_\bullet$\thinspace--\thinspace$\sigma$ correlation ``saturates'' at $\sigma \sim 250$~km~s$^{-1}$.  For velocity
dispersions higher than this value, $\sigma$ grows slowly or not at all as $M_\bullet$ increases.  Figure\ts2
indicates why: Core galaxies are remnants of dry mergers in which $\sigma$ grows only slowly while $M_{\rm bulge}$
and $M_\bullet$ grow rapidly in successive mergers. If the Faber-Jackson relation has a kink at $M_V \sim -22$
and $\sigma \sim 250$ km s$^{-1}$, then $M_\bullet$\thinspace--\thinspace$L$~and $M_\bullet$\thinspace--\thinspace$\sigma$ cannot both be
straight lines in Figure\ts3, without a kink.  Holm 15A and other giant ellipticals define a single, straight
correlation between $\log{M_\bullet}$ and $\log{L}$ or $\log{M_{\rm bulge}}$ (Equation 1).  The more famous
$M_\bullet$\thinspace--\thinspace$\sigma$ correlation has a kink at large $M_\bullet$~and~$\sigma$.  This possibility was
foreseen by Lauer et al.~(2007).

\section{M{\lower 2pt \hbox{$\bullet$}} Does Not Correlate with Pseudobulges, Disks, or Dark Matter}

      Figure 4 repeats the $M_\bullet$ correlations with $K$-band luminosity and velocity dispersion
of the host classical bulge and elliptical and adds the correlation with bulge stellar mass derived using
mass-to-light ratios zeropointed to SAURON dynamical models (Cappellari et al.~2006; Williams et al.~2009).
Pseudobulges are added in light blue shading.  They demonstrate the result (references in Figure 4 key) that
BH masses do not correlate tightly enough with pseudobulges to be suggestive of BH-host
coevolution.  Since coevolution generally involves feedback that controls star formation, it is worth
emphasizing that pseudobulges are {\it not\/} quenched in their star formation.  Rather, they form stars very
vigorously, at least as vigorously as their associated disks
(Kormendy \& Kennicutt 2004;
Fisher 2006;
Fisher et al. 2009).

      Recognition of pseudobulges as distinct from elliptical-galaxy-like classical bulges is part of a
picture of the slow, ``secular'' evolution of disk galaxies that complements our picture of
hierarchical clustering (Kormendy 1993; Kormendy \& Kennicutt 2004; Kormendy 2013 provide reviews).
Prototypical examples occur in the globally oval disk galaxies NGC\ts1068 (Figure\ts4), NGC\ts4151, and
especially NGC\ts4736.  Bars and oval disks transport disk angular momentum outward and rearrange disk
gas into outer rings (NGC\ts1068 shows an example), inner rings that encircle the ends of bars, and gas
that falls toward the center.  There, high gas densities drive strong star formation as described \phantom{00000}

\begin{figure}[b]
\vspace*{-2.2 cm}
\begin{center}
\includegraphics[width=5.3in]{kormendy-fig4ss.ps}
\end{center}
\vspace*{-0.15 cm}
\caption{Powerpoint slide showing the correlations (or lack of correlations) of BH mass~$M_\bullet$~with
({\it left}) $K$-band luminosity and stellar mass and ({\it right}) velocity dispersion of the host elliptical,
classical bulge, or pseudobulge.  Classical bulges and ellipticals participate~in~tight correlations
with intrinsic scatter $\sim$\ts0.28 dex.  {\it Pseudobulge BHs ({lightly shaded}) show no significant correlation
with their hosts.}  This is Figure~21~of Kormendy \& Ho (2013) adding references and a Sloan Digital Sky Survey
$gri$ color image of the Seyfert galaxy NGC{\thinspace}1068, a prototypical unbarred but oval (R)SAb galaxy with a
pseudobulge.  Another such galaxy is the Seyfert NGC{\thinspace}4151.}
\label{fig1}
\end{figure}

\newpage

\noindent by the Schmidt (1959)\thinspace--{\thinspace}Kennicutt (1998a,{\thinspace}b) law.  The result is to make both ring types
visible in starlight and to build, near the center, a compact stellar component that was grown slowly out of the disk,
not assembled rapidly via galaxy mergers.  These high-density centers were misidentified as classical bulges by early
morphologists
(e. g., Hubble 1936;
de Vaucouleurs 1959;
Sandage 1961)
and so are called ``fake bulges'' or ``pseudobulges''.  They recognizably remember their disky origin --
they are flatter than classical bulges, often as flat as their outer disks;
they are more rotationally supported, i.{\thinspace}e., $V/\sigma$ is larger than in classical bulges;
they often show spiral structure and nuclear bars that can only be sustained in flat, cold disks, and (except in S0s)
they show vigorous star formation.  Central components in BH disk galaxies were classified as classical or pseudo
before the BH correlations were derived.  It is a success of the secular evolution picture that classical and
pseudo bulges then prove to correlate differently with their BHs.  Many of these BHs are actively accreting AGNs
(e.{\thinspace}g., NGC\ts1068 and NGC\ts4151).  This is part of the evidence that feedback from AGNs
does not quench the star formation or otherwise influence the evolution of galaxy disks.

      A further indication that BHs do not affect disk evolution is the observation that BH masses
do not correlate with the $K$-band luminosities and hence the stellar masses of disks.  This is shown in
Figure 5.  Not surprisingly, for disk galaxies with BH discoveries, $M_\bullet$ correlates less well with
total galaxy luminosity and stellar mass than it does with classical bulge properties.

\begin{figure}[b]
\vspace*{-2.2 cm}
\begin{center}
\includegraphics[width=4.2in]{kormendy-fig5ss.ps}
\end{center}
\vspace*{-0.15 cm}
\caption{BH mass vs.~$K$-band absolute magnitude of the host disk (Figure 22 of Kormendy \& Ho 2013).
Solid symbols represent BH detections; open symbols are for BH mass upper limits.
BH masses do not correlate with properties of their host disks.  At M$_{K,{\rm disk}} \simeq -21 \pm 1$,
BH masses range from detections with $M_\bullet \simeq 10^9$\thinspace$M_\odot$ to the upper limit of 1500 $M_\odot$ in
M{\thinspace}33 (Gebhardt et al. 2001; Merritt et al. 2001).}
\label{fig1}
\end{figure}

\newpage

      Finally,{\thinspace\ts}$M_\bullet${\thinspace\ts}does{\thinspace}not{\thinspace}correlate{\thinspace}with{\thinspace}DM{\thinspace}halos{\thinspace}beyond{\thinspace}the{\thinspace}correlation{\thinspace}implied{\thinspace}by{\thinspace}Figure\ts3.
This result is unpopular with galaxy formation theorists, especially numerical modelers who add baryon physics
to simulations of DM hierarchical clustering.  DM mass $M_{\rm DM}$ is arguably the most fundamental parameter
associated with a galaxy, and it would have been convenient if it controlled galaxy evolution partly via AGN feedback.
Unfortunately, this is not the case, as suggested already by the fact that dwarf ellipticals such as M{\thinspace}32 participate
in tight $M_\bullet$ correlations whereas giant disks such as M{\thinspace}101 do not.

      Ferrarese (2002) and Baes et~al.~(2003) suggested that $M_\bullet$ {\it does} correlate with $M_{\rm DM}$.
Their conclusions seem to reflect the conspiracy that baryons and DM are arranged~so $V(r)$ is featureless
even though baryons dominate at small $r$ and DM dominates at large~$r$.

      Kormendy \& Bender (2011) and Kormendy \& Ho (2013) present seven arguments against the hypothesis that $M_\bullet$
correlates fundamentally with $M_{\rm DM}$.  One is illustrated in Figure\ts6.  The correlation of galaxy stellar
mass $M_*$ with DM mass $M_{\rm DM}$ is complicated.  The ratio $M_*/M_{\rm DM}$ is largest at $M_{\rm DM} \equiv M_{\rm crit} = 10^{12}$ $M_\odot$,
the critical mass above which galaxies can gravitationally hold onto large amounts of hot, X-ray-emitting gas.
This keeps baryons increasingly suspended in hot gas\thinspace--{\thinspace}not stars\thinspace--{\thinspace}in bigger galaxies, accounting
for the decrease in $M_*/M_{\rm DM}$ at larger $M_{\rm DM}$.  The decrease in $M_*/M_{\rm DM}$ at $M_{\rm DM} \ll
10^{12}$ $M_\odot$ is believed to result from more supernova-driven baryon ejection in smaller galaxies.  As a result,
the correlation of $M_\bullet$ with $M_{\rm DM}$ must be very different at $M_{\rm DM} \ll 10^{12}$ $M_\odot$ and
at $M_{\rm DM} \gg 10^{12}$ $M_\odot$.  But the correlation of $M_\bullet$ with $M_* \equiv M_{\rm bulge}$
is continuous across $M_{\rm DM} = 10^{12}$ $M_\odot$.  Thus Equation 1 appears to be the fundamental~correlation.

\begin{figure}[b]
\vspace*{-2.2 cm}
\begin{center}
\includegraphics[width=4.9in]{kormendy-fig6ss.ps}
\end{center}
\vspace*{-0.2 cm}
\caption{Powerpoint slide illustrating one argument why we conclude (Kormendy \& Bender 2011;
Kormendy \& Ho 2013) that $M_\bullet$ does not correlate with dark matter (DM) halos beyond
the known correlation with the masses of classical bulges and ellipticals.  The correlation (inset) of
$M_\bullet$ with {\it stellar} masses $M_*$ of bulges and ellipticals is continuous across the
dark matter transition mass $M_{\rm DM} \simeq 10^{12}$ $M_\odot$, but the
correlation of stellar mass $M_*$ (or $M_*/M_{\rm DM}$ as illustrated here from Behroozi
et al. 2013) changes slope sharply at $M_{\rm DM} \simeq 10^{12}$ $M_\odot$.  Therefore the
correlation of $M_\bullet$ with $M_{\rm DM}$ must be different at $M_{\rm DM} \gg 10^{12}$
$M_\odot$ and at $M_{\rm DM} \ll 10^{12}$~$M_\odot$.  Arrows point to these different correlations.
The references in the key are not included here.}
\label{fig1}
\end{figure}

\newpage

\section{Four Regimes of BH -- Host Galaxy Coevolution}

\def$_>\atop{^\sim}$} \def\lapprox{$_<\atop{^\sim}${$_>\atop{^\sim}$} \def\lapprox{$_<\atop{^\sim}$}

      This review concentrates on the demographics of BHs discovered via spatially resolved stellar
or gas dynamics in and near the sphere-of-influence radius of the BH.  BHs in classical bulges and
ellipticals are typically discovered using spatial resolution $_>\atop{^\sim}$} \def\lapprox{$_<\atop{^\sim}$ 4 times the radius of the
BH sphere of influence (Kormendy \& Ho 2013, Figure 1).  This was true even for the BHs discovered
using ground-based spectroscopy before HST became available.  Most of these BHs could still
have been discovered if they were several times less massive.  But they weren't. The conclusion that
$M_\bullet$ correlates tightly with the luminosity, stellar mass, and velocity dispersion of host classical
bulges and ellipticals is robust.

      On the other hand, $M_\bullet$ is found not to correlate with any other structural component in
galaxies -- not pseudobulges, not disks, and not dark matter halos.  This, together with other evidence
reviewed in Kormendy \& Ho (2013), allows us to refine our picture of when BHs do and when they do not coevolve
with their hosts.  We suggest that there are four distinct regimes of coevolution. Quoting from our review:

``(1) Local, secular, episodic, and stochastic feeding of small BHs in largely bulgeless galaxies
involves too little energy to result~in~coevolution.''

``(2) Global feeding in major, wet galaxy mergers rapidly grows giant BHs in
short-duration, quasar-like events whose energy feedback does affect galaxy evolution.
The resulting hosts are classical bulges and coreless-rotating-disky ellipticals.''

``(3) After these AGN phases and at the highest galaxy masses, maintenance-mode BH feedback into X-ray-emitting
gas has the primarily negative effect of helping to keep baryons locked up in hot gas and thereby keeping
galaxy formation from going to completion.  This happens in giant, core-nonrotating-boxy ellipticals.
Their properties, including tight correlations between $M_\bullet$ and core parameters [Kormendy \&
Bender 2009], support the conclusion that core ellipticals form by dissipationless major mergers.
They inherit coevolution effects from smaller progenitor galaxies.''

``(4) Independent of any feedback physics, in BH growth modes 2 and 3, the averaging that results
from successive mergers plays a major role in decreasing the scatter in $M_\bullet$ correlations
from the large values observed in bulgeless and pseudobulge galaxies to the small values observed in giant
elliptical galaxies'' (Peng 2007; Gaskell 2010; Hirschmann et al.~2010; Jahnke \& Macci\`o 2011).
It is no accident that pseudobulge BH masses range from the largest
$M_\bullet$ observed in ellipticals of similar mass down to much smaller masses.  Mergers convert
pseudobulges into classical bulges and ellipticals, adding new stars in starbursts, merging the
progenitor BHs, and in general growing the resulting BHs further by gas accretion.

\vskip -27pt

\centerline{\null}

\section{Conclusions}

Figure 7 lists astrophysical conclusions of this paper, echoing Kormendy \& Ho (2013).

I also emphasize the practical conclusion of this paper:

Selection effects do not invalidate the $M_\bullet$ correlations shown here
and in Kormendy \& Ho (2013).  Only classical bulges and elliptical galaxies
participate in tight correlations of $M_\bullet$ with the stellar mass and velocity dispersion
of the host (intrinsic~scatter~$\simeq$~0.28~dex).  Classical bulges and
ellipticals are well sampled over the complete range of their masses; objects with
BH detections sample essentially completely the tight fundamental plane correlations of their hosts.
In contrast, BH searches frequently fail for pseudobulges and disks: the BHs that we detect in these objects
are very likely to be the high-$M_\bullet$ part of a scatter that extends to
lower $M_\bullet$ masses.  Thus our picture of disk secular evolution (Kormendy 1993;
Kormendy \& Kennicutt 2004; Kormendy 2013) is an indispensible part of our understanding
of how BHs do and do not coevolve with their host galaxies.

\newpage

\centerline{\null} \vskip 3.55truein

\special{psfile=kormendy-fig7ss.ps hoffset=8 voffset=-10 hscale=61 vscale=61}

\centerline{{\bf Figure 7.}~Powerpoint slide of astrophysical conclusions of this paper.}

\vskip 10pt
\noindent {\bf Acknowledgments}
\vskip 5pt

      It is a pleasure to thank Ralf Bender and Luis Ho for many years of very enjoyable and fruitful
collaboration.  I thank Scott Tremaine for helpful comments on this work.  And I am grateful to Ralf Bender
and the Max Planck Institute for Extraterrestrial Physics and to Juntai Shen, the Shanghai Astronomical Observatory,
and Shanghai Jiao Tong University for my financial support to attend IAU Symposium 353.

\vskip 10pt
\noindent {\bf References}
\vskip 5pt

\frenchspacing
\def\noindent  \hangindent=1.0truecm{\noindent  \hangindent=1.0truecm}

\noindent  \hangindent=1.0truecm Baes, M., Buyle, P., Hau, G. K. T., \& Dejonghe, H. 2003, MNRAS, 341, L44

\noindent  \hangindent=1.0truecm Baggett, W. E., Baggett, S. M., \& Anderson, K. S. J. 1998, AJ, 116, 1626

\noindent  \hangindent=1.0truecm Behroozi, P. S., Wechsler, R. H., \& Conroy, C. 2013, ApJ, 770, 57

\noindent  \hangindent=1.0truecm Bender, R., Burstein, D., \& Faber, S. M. 1992, ApJ, 399, 462

\noindent  \hangindent=1.0truecm Bureau, M. 2019, paper presented at IAU Symposium 353, Galactic Dynamics in the Era of Large Surveys,
     posted at {\tt https://pan.cstcloud.cn/s/OaHRZGsQTgs}

\noindent  \hangindent=1.0truecm Cappellari, M., Bacon, R., Bureau, M., et al. 2006, MNRAS, 366, 1126

\noindent  \hangindent=1.0truecm de Vaucouleurs, G. 1959, Handbuch der Physik, 53, 275

\noindent  \hangindent=1.0truecm Event Horizon Telescope Collaboration 2019, ApJ, 875, L6

\noindent  \hangindent=1.0truecm Faber, S. M., \& Jackson, R. E. 1976, ApJ, 204, 668

\noindent  \hangindent=1.0truecm Ferrarese, L. 2002, ApJ, 578, 90

\noindent  \hangindent=1.0truecm Fisher, D. B. 2006, ApJ, 642, L17

\noindent  \hangindent=1.0truecm Fisher, D. B., \& Drory, N. 2008, AJ, 136, 773

\noindent  \hangindent=1.0truecm Fisher, D. B., Drory, N., \& Fabricius, M. H. 2009, ApJ, 697, 630

\noindent  \hangindent=1.0truecm Gaskell, C. M. 2010, in The First Stars and Galaxies: Challenges for the Next Decade,
     ed. D. J. Whalen et al. (Melville, NY: AIP), 261

\noindent  \hangindent=1.0truecm Gavazzi, G., Franzetti, P., Scodeggio, M., Boselli, A., \& Pierini, D. 2000, A\&A, 361, 863

\noindent  \hangindent=1.0truecm Gebhardt, K., Adams, J., Richstone, D., et al. 2011, ApJ, 729, 119

\noindent  \hangindent=1.0truecm Gebhardt, K., Lauer, T. R., Kormendy, J., et al. 2001, AJ, 122, 2469

\noindent  \hangindent=1.0truecm Gebhardt, K., \& Thomas, J. 2009, ApJ, 700, 1690

\noindent  \hangindent=1.0truecm Greene, J. E., Peng, C. Y., Kim, M., et al. 2010, ApJ, 721, 26

\noindent  \hangindent=1.0truecm Hirschmann, M., Khochfar, S., Burkert, A., et al. 2010, MNRAS, 407, 1016

\noindent  \hangindent=1.0truecm Hopkins, P. F., Hernquist, L., Cox, T. J., et al. 2006, ApJS, 163, 1

\noindent  \hangindent=1.0truecm Hu, J. 2008, MNRAS, 386, 2242

\noindent  \hangindent=1.0truecm Hubble, E. P. 1936, The Realm of the Nebulae (New Haven: Yale University Press)

\noindent  \hangindent=1.0truecm Jahnke, K., \& Macci\`o, A. V. 2011, ApJ, 734, 92

\noindent  \hangindent=1.0truecm J\o rgensen, I., Franx, M., \& Kj\ae rgaard, P. 1996, MNRAS, 280, 167

\noindent  \hangindent=1.0truecm Kennicutt, R. C. 1998a, ApJ, 498, 541

\noindent  \hangindent=1.0truecm Kennicutt, R. C. 1998b, ARA\&A, 36, 189

\noindent  \hangindent=1.0truecm Kormendy, J. 1987, ApJ, 218, 333

\noindent  \hangindent=1.0truecm Kormendy, J. 1993, in IAU Symposium 153, Galactic Bulges, ed. H. Dejonghe \&
     H. J. Habing (Dordrecht: Kluwer), 209

\noindent  \hangindent=1.0truecm Kormendy, J. 2013, in XXIII Canary Islands Winter School of Astrophysics,
     Secular Evolution of Galaxies, ed. J. Falc\'on-Barroso \& J. H. Knapen
     (Cambridge: Cambridge University Press), 1 (arXiv:1311.2609)

\noindent  \hangindent=1.0truecm Kormendy, J., \& Bender, R. 2009, ApJ, 691, L142

\noindent  \hangindent=1.0truecm Kormendy, J., \& Bender, R. 2011, Nature, 469, 377

\noindent  \hangindent=1.0truecm Kormendy, J., \& Bender, R. 2012, ApJS, 198, 2

\noindent  \hangindent=1.0truecm Kormendy, J., \& Bender, R. 2013, ApJ, 769, L5

\noindent  \hangindent=1.0truecm Kormendy, J., Bender, R., \& Cornell, M. E. 2011, Nature, 469, 374

\noindent  \hangindent=1.0truecm Kormendy, J., Fisher, D. B., Cornell, M. E., \& Bender, R. 2009, ApJS, 182, 216

\noindent  \hangindent=1.0truecm Kormendy, J., \& Ho, L. C. 2013, ARA\&A, 51, 511

\noindent  \hangindent=1.0truecm Kormendy, J., \& Kennicutt, R. C. 2004, ARA\&A, 42, 603

\noindent  \hangindent=1.0truecm Lauer, T. R., Faber, S. M., Richstone, D., et al. 2007, ApJ, 662, 808

\noindent  \hangindent=1.0truecm Macchetto, F., Marconi, A., Axon, D. J., et al. 1997, ApJ, 489, 579

\noindent  \hangindent=1.0truecm McConnell, N. J., Chen, S.-F. S., Ma, C.-P., et al. 2013, ApJ, 768, L21

\noindent  \hangindent=1.0truecm McConnell, N. J., Ma, C.-P., Gebhardt, K., et al. 2011, Nature, 480, 215

\noindent  \hangindent=1.0truecm Mehrgan, K., Thomas. J., Saglia, R., et al.~2019, submitted to ApJ (arXiv:1907.10608)

\noindent  \hangindent=1.0truecm Merritt, D., Ferrarese, L., \& Joseph, C. L. 2001, Science, 293, 1116

\noindent  \hangindent=1.0truecm Peng, C. Y. 2007, ApJ, 671, 1098

\noindent  \hangindent=1.0truecm Rusli, S. P., Thomas, J., Saglia, R. P., et al. 2013, AJ, 146, 45

\noindent  \hangindent=1.0truecm Sandage, A. 1961, The Hubble Atlas of Galaxies (Washington:~Carnegie Institution of Washington)

\noindent  \hangindent=1.0truecm Schmidt, M. 1959, ApJ, 129, 243

\noindent  \hangindent=1.0truecm Schulze, A., \& Gebhardt, K. 2011, ApJ, 729, 21

\noindent  \hangindent=1.0truecm Schwarzschild, M. 1979, ApJ, 232, 236

\noindent  \hangindent=1.0truecm Shankar, F., Bernardi, M., Sheth, R. K. et al. 2016, MNRAS, 460, 3119

\noindent  \hangindent=1.0truecm Thater, S. 2019, paper presented at IAU Symposium 353, Galactic Dynamics in the Era of Large Surveys,
     posted at {\tt https://pan.cstcloud.cn/s/OaHRZGsQTgs}

\noindent  \hangindent=1.0truecm Tremaine, S., Gebhardt, K., Bender, R., et al. 2002, ApJ, 574, 740

\noindent  \hangindent=1.0truecm Tsukui, T. 2019, paper preented at IAU Symposium 353, Galactic Dynamics in the Era of Large Surveys,
     posted at {\tt https://pan.cstcloud.cn/s/OaHRZGsQTgs}

\noindent  \hangindent=1.0truecm van den Bosch, R. C. E. 2016, ApJ, 831, 134

\noindent  \hangindent=1.0truecm van den Bosch, R. C. E., Gebhardt, K., G\"ultekin, K., Y\i ld\i r\i m, A.,
     \& Walsh, J. E. 2015, ApJS, 218, 10

\noindent  \hangindent=1.0truecm Williams, M. J., Bureau, M., \& Cappellari, M. 2009, MNRAS, 400, 1665

\end{document}


\section{Introduction}

Advance in computational sciences, engineering, medicine and other
computational disciplines often relies on simulation results to drop in faster,
even though researchers continuously increase the problem size or detail.
There are other important driving factors behind progress such as improved
models or numerical techniques.
Yet, speed and size are omnipresent desirable characteristics and
requirements.
To suit them, the community relies on the improvement of two tools:
their computer hardware and their software.
Improvement here means speed.

Computers are becoming faster.
The Top-500 list \cite{Webpage:Top500} documents their impressive evolution.
In many manuscripts, the speed growth is attributed towards Moore's law; which
is not in line with the original statement from \cite{Moore:65:Law}.
What is however true is that the growth---though maybe with a reduced constant
before the exponential---of Moore's law does and continues to hold for
computers' potential capabilities.

Parallelism is key to make computers faster
\cite{Asanovic:2006:LandscapeOfParallelComputing}.
Starting from around 2004, computers stagnated in frequency or even
reduced it \cite{Sutter:05:FreeLunchIsOver}.
This is due to physical (quantum) effects introducing nondeterministic
effects, i.e.~errors in a deterministic view of the world, energy
envelopes, manufacturing constraints, and so forth.
All effectively forbid
vendors to increase the frequency or to shrink the dies aggressively.
Shrinking allows us to work at lower voltages which in turn
creates freedom to increase the speed.
Once these upscaling techniques are not an option anymore, we can still
increase the number of compute units.
This yields more powerful computers despite the fact that individual compute
components do not speed up.

The seminal, popular science report ``The Free Lunch Is Over: A Fundamental Turn
Toward Concurrency in Software'' \cite{Sutter:05:FreeLunchIsOver} documents this
insight as well as its consequences:
software has to be made ready for parallelism, too.
A second seminal paper is the SCaLeS report championed by David E.~Keyes
\cite[pp.~32]{Scales:03:Scales} which contains content similar to an algorithmic version of Moore's Law:
The report highlights that the dramatic growth of performance and capabilities
on the hardware side over the last decades is matched by improvements on the
algorithm side.
The manuscript's introductory example from linear algebra showcases this by the
transition from direct Gauss Elimination into full multigrid \cite{Trottenberg:01:Multigrid} which
yields a gain in compute efficiency equivalent to 35 years of hardware evolution.
More examples along these lines exist.

If we cast statements on algorithmic improvements into statements on performance
without machine context, we run risk to make an error very similar to the
misinterpretation of Moore's law as performance statement.
Improvements on the hardware side and on the algorithm side are not
orthogonal:
In the present paper, we sketch nuances of the growth of hardware parallelism
and highlight that the sole focus on an increase of concurrency\footnote{
 In the tradition of \cite{Lamport:78:Concurrency}, we use concurrency as a
 theoretical concept that highlights that two control flows in hardware or in
 code run independently, can be merged into each other in any order, or may be
 executed in parallel, i.e.~it is the term parallelism that denotes that things
 happen at the same time.
}
on the software side falls short, as data movements quickly become a
limiting factor (Section~\ref{section:co-design}).
As a consequence, programmers of high-end software have to familiarise
themselves with communication-avoiding techniques.
In Section~\ref{section:terminology}, we attempt to classify
communication-avoiding techniques and claim that the phrase has to be weakened
and generalised to include many more techniques than the traditional
communication-avoiding tool set from linear algebra.
Consult \cite{Demmel:2013:CA} for a comprehensive overview over the latter.
Only a generalisation and, hence, an expansion of our toolset
accommodates the pressing needs imposed on us by the hardware
evolution.
The two sections \ref{section:strong} and \ref{section:weak} give examples for
communication-avoiding techniques in line with this generalised notion.
The examples allow us to conclude (Section~\ref{section:conclusion})
which next steps might be required to tackle the
challenges around communication in data-intense computing.

\section{One-way co-design}
\label{section:co-design}

Reports and roadmaps predict that the exascale wall will be climbed
through an increase of parallelism on the hardware side
\cite{Asanovic:2006:LandscapeOfParallelComputing,Dongarra:14:ApplMathExascaleComputing}.
There are different levels of parallelism.

First, vendors increase the parallelism through the widening of vector
registers---AVX512 is an example---or lockstepped hardware threads as we find
them in GPGPUs.
Parallelism on this level materialises in code which performs basic arithmetic
operations on small, fully populated vectors or vector segments.
NVIDIA calls its cores streaming multiprocessors (SMs) which work with many
sets (warps) of hardware threads per core which are swapped quickly.
This original SIMT's (single instruction multiple threads)
\cite{Lindholm:2008:CUDA} concept is conceptionally
close to vectorisation.
Its swapping idea materialises hardware concurrency hiding
latency and bandwidth constraints.

Second, vendors increase the core count per processor.
Intel might have abandoned their own manycore product line, but we see
mainstream supercomputers nevertheless host already 20 or more cores
per processor.
Different to vector registers, multicores run independently of each
other, i.e.~each executes its own instructions.
GPGPUs in general operate with lower physical core/SM counts.
As NVIDIA however supports higher thread divergence, i.e.~allows multiple
threads ran simultaneously to run different code branches and to synchronise
with a subset of other threads, the SIMT paradigm moves closer to multicore
parallelism.
Cores and SMs are connected to each other through a shared memory.
One core thus can read data written by another core.

Finally, supercomputers connect multiple of these multicore devices (nodes) with
each other.
Nodes do not share data spaces but communicate with each other
through messages.
Alternatively, new hardware in the market, such as NVLink,
joins distributed memory logically into large shared spaces and thus pushes
multi-node or multi-device architectures logically into the multicore domain.

Recent hardware generations exhibit a fast growth of concurrency on the vector
and multicore level, while the number of nodes seems to stagnate.
One reason for this are data movements which are subject of the subsequent
sections:
If it is already expensive and problematic to transfer data between
memory and vector registers as well as in-between cores, it is even more
challenging to transfer data over long distances via messages.

In a co-design fashion, the tremdendous increase in concurrency on the hardware
side forces developers to rewrite their codes such that they are capabable of
exploiting this \cite{Sutter:05:FreeLunchIsOver}.
The different hardware levels here require different programming efforts.
An increase in vectorisation parallelism forces programmers to phrase
algorithms in terms of small vectors.
These vectors are treated as dense, i.e.~vector units on a chip manipulate vectors agnostic of their content.
An increase in core counts requires programmers to decompose algorithms into
fine-granular activities (tasks).
This allows a runtime system to deploy tasks among the cores and, hence,
to keep them busy.
An increase in node counts requires programmers to decompose data spaces into
larger regions and to design codes such that the effort to keep these
distributed data spaces consistent remains limited.
If we formalise the induced communication as graph, the graph has to be as
sparse as possible.
In linear algebra, this corresponds to the need for sparse matrices.

Co-design the other way round is harder to find.
Algorithms rarely guide the hardware design \cite{Russell:2016:CoDesign}, and special-purpose
chips materialising particular algorithms are not found that often in mainstream
HPC.
Recently however, we witness an influence the other way round:
In-hardware security algorithms (encryption) become part of chips,
FPGAs---software-programm\-able hardware---gain momentum, and GPUs start to
become equipped with special-purpose silicon;
tensor cores and raycasting/-tracing entities are the prime examples.
The economic success of GPGPUs as a whole has, to some degree, to be attributed
towards machine learning algorithms.
One may interpret this as algorithm-to-hardware co-design.
We however prefer a different interpretation:

\subsection{Changing optimality metrics: over-vectorisation and task
decomposition}
Many sophisticated, efficient algorithms reduce
the concurrency:
In traditional computer science,
an algorithm is efficient if it requires fewer computations than a na\"ive,
competing approach.
Many computations---preferable of the same type---however tend to yield a high
concurrency, while very few calculations, in the ``worst case'' with tight
data dependecies, cannot make use of a parallel machine.
Sometimes, simpler is faster.

Some sophisticated codes thus combine the best algorithm on one scale with a
simpler variant with higher concurrency on another scale.
Examples for such hybrids that support our efficiency-vs-concurrency claim are
block-structured sparse matrix algorithms that use full matrix algorithms for subblocks
\cite{Ltaeif:19:HierarchicalAlgorithms},
linear algebra subroutines which switch to dense or sparse implementations
depending on the number of non-zeros and their pattern \cite{Breuer:2014:SustainedPetflow},
particle dynamics codes that use a grid
to administer the cut-off radius which is so coarse that it always hosts a
reasonable number of molecules
\cite{Eckhardt:15:SPHCompression,Schaller:16:Swift,Weinzierl:15:PIC}, or
multigrid codes that rely on algebraic multigrid for coarse resolutions and
employ geometric multigrid with rediscretisation on finer levels
\cite{Rudi:15:ExtremeScaleImplicitSolver,Weinzierl:17:BoxMG}.
Neural networks often are an extreme case:
Conceptually, they are significantly simpler than known approaches to minimise
cost functions describing how well a network represents a training or test data
set, respectively.
Their success in fitting strongly
overparameterised ansatz functions stems from massive data plus unprecedented concurrency; typically
subject to gradient descent, i.e.~a relatively basic algorithmic approach.

Besides the aforementioned revisit of ``less effective'' algorithms
which allow us to exploit (vector) concurrency and thus effectively
reduce the time-to-solution, the decomposition of our algorithms into finer and finer
tasks is the second important code design trend in large-scale computing.
The latter technique uncovers fine-granular concurrency and
is often followed by a rearrangement of these tasks such that the machine of choice is exploited
better.
The rise of task systems---Threading Building Blocks, Cilk, Charm++,
StarPU, and others---documents the popularity of the latter approach.
Developers have to carefully balance task decomposition against vectorisation
efficiency:
Too small tasks fail to keep the vectorising codes busy.
Too big tasks lack the required level of concurrency.
Both dimensions benefit from homogeneous, non-hierarchical, uniform
workload which can be split relatively straightforwardly
\cite{Asanovic:2006:LandscapeOfParallelComputing}.
Eventually, both benefit from hybrids.

The paradigm shift to construct hybrids exploiting less
efficient algorithms than theoretically known results from an update of our cost
model, i.e.~our understanding what induces high or low runtimes respectively.
New cost models are rarely introduced explicitly.
Most of the time we alter them implicitly in our minds and support the outcomes
through experimental studies.
Yet, the punchline remains the same:
The delicate balance between high concurrency vs.~parallelisation overhead
in some cases outweights classic operation count-based cost models.
\emph{The paradigm shift on the hardware side has recalibrated and changed the
correlation of floating point operation counts (FLOP numbers) to performance.}

\subsection{Vertical and horizonal communication constraints}
A second challenge rises in the shadow of hardware concurrency growth:
The architectures become ill-balanced w.r.t.~data delivery.
While the cores with their vector registers can yield an impressive number of
computations per second and while there are many cores, we struggle to feed them
with data
\cite{Dongarra:14:ApplMathExascaleComputing,Higham:2017:News,Higham:2019:SqueezingMatrix,Laguna:2019:GPUMixer,Lam:2016:ShadowValueAnalysis,Langou:2006:IterativeRefinement}.

\begin{figure}
 \begin{center}
  \includegraphics[width=0.6\textwidth]{vertical-and-horizontal-data-flow.pdf}
 \end{center}
 \vspace{-0.4cm}
 \caption{
  Schematic illustration of vertical and horizontal data flow in a conventional
  supercomputer consisting of multiple nodes where each node hosts multicore cores which in turn employ
  vector registers. The cores access the main memory through a cascade of cache
  levels, while the nodes communicate with each other through an interconnect.
  \label{figure:vertical-and-horizontal-data-flow}
 }
\end{figure}

There is a \emph{vertical data movement challenge}
(Fig.~\ref{figure:vertical-and-horizontal-data-flow}):
Cores can process data which is by a magnitude larger than what a standard main
memory can deliver.
One hardware workaround here is to introduce caches, i.e.~intermediate memories
in-between the main memory and the compute units.
They are small yet can hold hot data, i.e.~data that is frequently or soon used.
An alternative to caching is the use of massive oversubscription:
Whenever a core runs into a situation where the computations of one
thread require data which is not yet brought into the chip's registers, it
``suspends'' the execution and instead progresses another ``warp'' of (vector)
operations from a different thread.
In the meantime, the required data can be brought in.
The latter technique is used in GPGPUs.
As sketched above, such chips logically can be interpreted as a set of cores
where only one core is active (and thus requires compute resources) at a
time, while the others prepare for their next move.

Intel introduces a new cache level with its Optane technology
\cite{Boyandin:18:OptaneInMemoryDB,Charrier:19:EnergyAndDeepMemory,Kudryavtsev:17:NUMAOptane}.
Optane effectively renders the main memory into a further cache---either
implicitly managed by the company or explicitly managed by user codes---and
introduces a huge yet relatively slow main memory.
Intel furthermore abandons the idea of inclusive caching with the
Intel\textregistered\ Xeon\textregistered\ Scalable processor (Skylake).
Without inclusive caching, the probability increases that cache misses on a
small, close cache induce large runtime penalties: the missed data
is not backed up by the subsequent cache level.
If caches become (relatively) slower, it hurts even more.
On the GPGPU side, NVIDIA weakens the strict lockstepping in warps.
This allows users to run codes with a larger thread divergence, yet harms the
GPGPU's efficiency if used heavily.
The vertical challenge gains weight.

There is an additional \emph{horizontal dimension to the data movement
challenge} (Fig.~\ref{figure:vertical-and-horizontal-data-flow}):
Data movement penalties gain weight as vendors integrate more and
more cores into one chip.
Cache levels have to be split or shared between more and more compute
units and to keep their content consistent requires increasing effort
manifesting in runtime penalties (NUMA).
On the inter-node level, interconnects remain to be by magnitudes slower than
memory.
This also holds for processor-accelerator connections.

Both vertical and horizontal data movement constraints imply that efficiency
gains resulting from over-vectorisation and task decomposition run risk to
become obsolete.
The fastest compute instruction sequence, i.e.~source code, is of no value if
the processing units can not be fed with data.
The hardware evolution makes it mandatory that codes avoid communication along
all hardware dimensions.

\section{Terminology}
\label{section:terminology}

Communication-avoiding (CA) algorithms are not new.
One of the most important papers stems from 2013, e.g.,
\cite{Demmel:2013:CA} and reviews a vast number of CA techniques from
linear algebra.
We identify here six dimensions along which we can classify CA techniques:

\begin{enumerate}[leftmargin=*]
  \item
In the tradition of refactoring \cite{Fowler:99:Refactoring},
communication-avoiding modifications always have to be semantics-preserving,
i.e.~the outcome of an algorithm subject to a communication-avoiding technique has to
remain the same.
In scientific computing, ``the same'' usually means ``reasonably close to
machine precision''.
This implies that a communication-avoiding technique may not introduce
any numerical instability for the input data of interest, but we may classify
techniques into {\bf stability-preserving} and {\bf stable for data of
interest}.
  \item
We consider both data movements in-between nodes and within a
computer, i.e.~between chip and
caches, caches and main memory, memory and accelerator, as communication.
This is, our notion of communication comprises {\bf intra-node and inter-node
communication}.
  The phrase communication-avoiding thus includes cache optimisation techniques
  \cite{Kowarschik:03:CacheTechniquesOverview}.
  As novel hardware blurs the distinction between intra-node and inter-node
  (through remote memory access or distributed shared memory for example), we
  may characterise techniques rather by means whether they address problems of
  {\bf horizontal or vertical information flow}:
Horizontal circumscribes challenges that arise from the growth of
concurrency such as increasing node and core counts but also wider vector
registers.
Vertical techniques tackle challenges that arise from the fact that information
typically is spread out, i.e.~resides on different memory levels,
memory segments, devices.
  \item
Though papers traditionally motivate a communication-avoiding technique through
one application and demonstrate the impact of their ideas by means of one
application, we can distinguish {\bf application-specific from generic}
approaches. The latter techniques apply directly to many different areas.
  \item
  There are two extremes of CA code changes:
  Techniques can {\bf preserve the exact algorithmic steps per datum}.
  If we work in
  this regime, we are restricted to a re-orchestration of operations over all data, but
  the path how this outcome had
  been computed is preserved per datum. We are notably not allowed to change the
  algorithm that led to a particular result.
On the other side of the spectrum are techniques and algorithms which
{\bf change the algorithm's behaviour} or even the algorithm itself, i.e.~they
change how results are obtained.
There are many approaches in-between; in particular approaches which weakly
preserve the behaviour, i.e.~yield different pathways towards the results only
in some cases.
The in-the-middle regime comprises for example code modififcations
which materialise in altered iteration counts, required operations, and so
forth but stick to the same algorithmic blueprint.
  \item Some CA techniques are {\bf strictly monotonous} in a sense that they
  always reduce the communication. Others pay off asymptotically for large,
  characteristic data sets yet not for each individual choice.
  \item
Finally, many (application) scientists are not motivated by
communication-avoiding per se, but start to investigate CA techniques as
they suffer from communication penalties.
  From their point of view, it makes sense to
  distinguish {\bf strong communication-avoiding} techniques from
  {\bf weak communication avoiding} techniques.
  Strong means that communication is eliminated compared to a na\"ive baseline
  implementation.
  In the weak sense, a communication-avoiding technique primarily eliminates its
  negative impact---it might not reduce the actual communication.
  Such techniques are {\bf communication-flaw-avoiding}.
\end{enumerate}

\section{Communication-avoiding techniques in a strong sense}
\label{section:strong}

\input{classification-table-strong}

\subsection{Volume reduction}
Volume reduction is the most obvious communication-avoiding technique.
A classic example is Gaussian Elimination which reorders entries such that
the number of fill-ins is reduced \cite{Demmel:2013:CA}.
Today, such algorithms are integral part of all major direct solver packages.
Algorithmic steps are permuted such that
zero entries in a data structure are not overwritten with non-zero data.
Consequently, follow-up later steps which would otherwise have to
eliminate non-zero entries can be skipped.
Yet, this is not the prime goal from a data point of view.
The prime target besides a sparsification of the execution/task graph is to
avoid a temporary blow-up of the used data structures.
The observation behind this technique is that an intelligent permutation of
computations early in the algorithm's run implies that we don't have to
store large temporary data.

If this fails, a second technique is the
replacement of temporary data/variables with recomputations.
Results are not stored persistently and thus don't have to be held or
communicated.
Instead, we compute results on-the-fly again whenever we need them.
This technique trades memory for computations.
It is thus particularly attractive if we suffer from horizontal communication
flaws.

If it is not possible to avoid temporary data storage or data usage, precision
reduction becomes popular
\cite{Dickov:14:InfinibandCompression,Kuhn:2016:DCC,Laguna:2019:GPUMixer,Langou:2006:IterativeRefinement,Lindstrom:06:FastFloatingPointCompression}.
Machine learning pushes the introduction of precision reduction
\cite{Higham:2019:SqueezingMatrix}, but it is natural to exploit new native
hardware formats with reduced memory footprint in scientific computations, too.
Such a switch yields massive memory footprint reductions though might proof to
be problematic for the stability of the computations.
Therefore, we currently witness massive investments into research around
algorithms which combine different precisions without compromising on the output
quality \cite{Higham:2017:News}, or tools which guide the developers through the
zoo of novel precisions.

Our own work sticks to standard IEEE precision for all computations, but
translates all data into hierarchical representations prior to their storage
\cite{Bungartz:10:Precompiler,Eckhardt:15:SPHCompression,Weinzierl:17:BoxMG}.
An on-the-fly analysis of the data yields how many significant bits (bits that
hold information) are held per variable.
We then cut down the data after a suitable
number of bytes without loosing information before we stream them out of the
core.
After the compressed, low footprint data is loaded again, we convert it back
into a native precision.
Other papers propose similar storage schemes which store only few bits per datum
relative to a (predicted) reference value
\cite{Ratanaworabhan:06:LosslessCompression}.

For integer data or sparse records holding lots of zeroes,
run-length encoding has proven to be particularly useful.
In its simplest case, it eliminates long sequences of zeroes for the price
of additional header flags in a data stream \cite{Schreiber:13:Sfc-based}.
In particular for modern high-level programming languages, it is a CA technique
to eliminate the omnipresent padding and thus to squeeze out bytes without
semantics from the data
\cite{Bungartz:10:Precompiler}.

\subsection{Synchronisation elimination}
Volume reduction tackles bandwidth penalties.
Modern architectures however suffer from limited bandwidth and
high latency.
Latency notably causes problems whenever an algorithm synchronises various
compute units too often.
It is non-trivial to avoid synchronisation and typically impossible to
eliminate it completely, as algorithms synchronise to keep their distributed
states consistent.

Overlapping data spaces and running calculations redundantly tackles the
synchronisation challenge.
It is a tool classic in stencil-based linear algebra.
The idea is to revisit the data decomposition.
Let the data be decomposed into chunks such that each core or node can run its
evaluations independently of the other compute units on its chunk.
We achieve this by augmenting the data chunk with halos, i.e.~with copies from
the other chunks such that the calculation itself does not need any data
transfer.
After the computation, these halos are updated, as other compute units likely
have changed their value.
We can now analyse our data access needs and make the halos bigger such that we
can do two calculations in a row.
This typically requires us to run some calculations within the (larger) halos,
too:
we ``mirror'' some calculations done on other chunks.
The approach can be recursively extended.
Within the overlaps, we run redundant calculations, but this
redundancy is designed such that the redundant computations allow the
algorithm to immediately run a subsequent calculation without the need to
synchronise.
We reduce the synchronisation frequency; though at the price of an increased
data volume.
Increased data overlaps are a valid label for this technique.
The CA flavour however is emphasised once we highlight that the technique
involves loop unrolling of the outer algorithm loop and synchronises only once
per unrolled loop body.
$s$-step  Krylov methods are close to this concept
though they give up on some data consistency \cite{Ghysels:13:HideLatency}.

A radical alternative to enlarged halos which also reduces the synchronisation
is anarchic programming \cite{Wolfson:2019:AsynchronousJacobi}.
We drop the consistency considerations that led to enlarged data spaces and
ignore whether incoming information (data updates) from other entities have
already arrived.
Loops on data chunks continue to iterate, knowing that eventually another code
part will feed them with the required input data.
Such an anarchic paradigm requires the underlying algorithm to be robust
w.r.t.~inconsistent input data.
Elliptic problems seem to suit this requirement.

\subsection{Single-touch and single-load semantics}
Whenever data volume or latency pose problems, these
problems are amplified if information has to be communicated multiple times.
We rarely find distributed memory codes that exchange messages multiple times.
It happens however frequently that data is moved through the caches multiple
times (capacity misses) or that codes swap data to and from the
GPGPU due to their limited memory capacity.

The optimisation of algorithms towards particular cache architectures is
well-under\-stood.
Key ingredient here is typically proper tiling (chunkification) such that
tiles/chunks fit into the respective caches, and the attempt to increase the
spatial and temporal locality of data accesses
\cite{Kowarschik:03:CacheTechniquesOverview}.
Algorithms or loops, respectively, that
read (array) data multiple times are reordered such that data that are required
briefly after each other are close in the main memory, and such that data that
are required at one point are re-used again briefly thereafter.
We adapt the data access pattern of an algorithm and the data storage to each
other.
Sophisticated cache blocking techniques
\cite{Kowarschik:03:CacheTechniquesOverview,Saxena:2017:CacheAwareDD} exploit that most memory is
organised in pages/blocks/lines, i.e.~architectures do not exchange single entities of data but always transfer whole segments of memory---a
built-in message agglomeration.
They make the chunk sizes match particular cache sizes.

Clever data access and data storage reordering reduces multiple loads into
caches.
An extreme case of such clever reordering is the total serialisation of an
algorithm \cite{Weinzierl:11:Peano}.
Data are reordered such that the algorithm does not require any
indirect memory accesses anymore, but reads all data in as stream and holds
data temporarily only in stacks, streams or small arrays.
As a consequence, an algorithm becomes inherently cache-optimal (cache
oblivious)---the probability that the head of a stack remains in a cache is
always very high as long as the number of stacks remains small---and avoids
communication over the memory interconnects.

Data ordering and operation orchestration go hand in hand.
On the orchestration side, task fusion is the most important single-touch
optimisation \cite{Charrier:2019:StopTalkingToMe}.
Task fusion reorders operations (tasks) such that two tasks that access the same
piece of data are evaluated directly after another.
One might thus (logically) fuse the two pieces of codes into one big task.
If tasks operate on a reasonably small amount of data, we may assume that all
data are held in fast caches after the termination of the first task.
Task fusion is the task language's counterpart to loop fusion on arrays from a
CA point of view.

\subsection{Localisation}
Bandwidth and latency problems require different actions.
Quantitatively, these problems are affected by the number of participating
entities:
the more partners involved in communication, the harder the challenge.
In many cases, a reasonably small number of communication partners makes
communication flaws hide behind runtime noise.
If problems however do arise, it is sometimes only few communication partners
that cause delays on all other entities.
In such cases, it is reasonable to break up many-to-many data exchange
(collectives).
Rather than global data exchange, we localise data flow.
Such a sparsification of the data exchange graph can be done a priori by
analysing data dependencies.
In multiscale algorithms for example, it might be sufficient to let a
computation depend only on a certain subregion of one scale rather than the
whole level of one scale \cite{Mitchell:2019:AMG-DD}.
Sparse collectives have been proposed for MPI
\cite{Hoefler:09:SparseCollectives}, though one can always implement such sparse
graphs via tailored MPI (sub-)communicators.

Instead of a static localisation, we have studied algorithms which localise the
data exchange graph dynamically \cite{Weinzierl:15:PIC}.
The concept here is that we query the algorithm for predictions where
collectives actually transfer information.
If collectives exchange data along a sparse communication graph (many entries
are zero, e.g.), it is again reasonable to replace the collective with a set of
point-to-point operations.

\section{Communication-avoiding techniques in a weak sense}
\label{section:weak}

\input{classification-table-weak}

\subsection{Data movement hiding}
The hardware's organisation into levels (vertical) and nodes
(horizontal) introduces hardware asynchronicity since the entities can move around
data independently and, in particular, while core components compute.
This allows us to hide data movement cost.
Hiding is an example of a weaker interpretation of CA, as the
communication is not literally avoided yet negative impact is.

On the distributed memory side, non-blocking data exchange means that we trigger
data transfer for a particular memory region, continue to compute, and later
check whether the transfer has completed.
This is a rather old feature in MPI, though still sometimes challenging to
use/realise
\cite{Hoefler:08:SacrificeThread,Sergent:2018:OverlapCommunicationComputation,Wittmann:13:AsynchMPI}.
Within a node, all caches today have built-in prediction features to
transfer data from and to caches.
This also holds for new deep memory
\cite{Boyandin:18:OptaneInMemoryDB,Charrier:19:EnergyAndDeepMemory,Kudryavtsev:17:NUMAOptane}.
Agnostic of the exact caching strategies, least recently used
(LRU) seems to describe most cache behaviour reasonably.
LRU describes reactive cache behaviour:
the ``oldest'' data is removed from the cache if space is required.
Explicit prefetching can guide the caching as it triggers
data movements ahead of time.
It hands a pro-active technique over to developers.

\subsection{Synchronisation hiding}

Optimism is a powerful communication-avoiding technique to hide
synchronisation.
Optimistic algorithms synchronise program parts, but the receiver side does
not wait for the synchronisation input.
Instead, it optimistically assumes what information will drop in.
If this assumption turns out to be wrong later during the computation, the
receiver side either rolls back and redoes its computations with the actual
values \cite{Charrier:2019:StopTalkingToMe} or takes the actual data into account at the earliest
next opportunity.
If rollbacks are required, optimistic codes' runtime might deteriorate unless
we can immediately stop all calculations once invalidating data drops in.

Pipelining \cite{Ghysels:13:HideLatency,Ghysels:14:HideSynchronisation}
applies the data overlap idea to the control flow.
Its idea is that we bring all the computations forward that feed
into computations on another compute entity.
In turn, we receive data early that we need locally to determine results
required in later stages.
Data required for the follow-up step is already ``in the pipeline'' while we
continue to compute.
To construct the required level of concurrency,
pipelining is often combined with redundant calculations.
Entities exchange data feeding into critical calculations early, but
each rank then computes the results independently from the others.
Both pipelining and increased overlaps from Section
\ref{section:strong} contradict CA's objective to keep the memory footprint
small.
Many approaches relying on redundant computations furthermore become sensitive
to stability issues.

\subsection{Homogenisation}
Computers tend to be underequipped with memory access speed and with network
speed.
Yet, memory controllers and network cards  usually are sufficiently fast to
handle a few cores or nodes, respectively.
Service requests from everybody at once however make them struggle.
A weak communication-avoiding technique to address this flaw is
to homogenise bandwidth and network requests over time:
we sprinkle communication steps over the actual execution.
In particular, we break up codes written in in terms of compute
phases vs.~communication phases which take turns and make many (smaller)
communication steps interrupt the computation.
On the node, the same pattern implies that we carefully orchestrate all tasks
such that compute-intense tasks and memory-intense tasks take turns
\cite{Charrier:2019:Enclave,Charrier:2019:StopTalkingToMe}.
The goal here is to ensure that some compute facilities (cores) exploit all
available memory bandwidth, while the others spend the majority of their time in
actual computations and do not interfere.

\section{Conclusion}
\label{section:conclusion}

Communication-avoiding techniques have to become omnipresent if the current
hardware evolution trend endures.
The present collection of CA techniques is a rather arbitrary set inspired by
the author's own work and selected examples known to the author.
It is certainly not comprehensive.
The present classification expresses the author's personal opinion.
It is likely neither waterproof nor comprehensive either.
Yet, the present collection plus its classification can be a starting point to
think about CA techniques in a systematic way covering whole application
landscapes.
Eventually, a concerted push by the whole community is required to establish a more
complete catalogue of these techniques similar to design patterns
\cite{Gamma:94:DesignPatterns}.
This way, future generations of scientists will be able to rely on a
well-documented and formalised knowledge base.
Without such an effort, we run risk to be left behind with hardware that we cannot
(efficiently) use.

An inherent obstacle towards the adoption of communication-avoiding techniques
is the fact that they often require large code refactorings or even rewrites
(cmp.~preserve characterisation in Section \ref{section:terminology}); at a time
where researchers advocate to switch to black-box software building blocks to make software development more mature, efficient and sustainable.
Machine learning serves as prime example for the latter.
It champions the usage of established software frameworks
within multiple research projects.
Our discussion highlights however that a na\"ive assembly of software blocks
representing an algorithm's steps (data-flow paradigm) might be an ill-fit to
future machines:
If we complete one computing step, dump or stream the outcome into the next
algorithmic phase, and then continue, we will struggle to use
communication-avoiding techniques.

It is almost sarcastic that the discipline that pushed us into petascale, linear
algebra, and the discipline which drove the hardware development
towards the pre-exascale era, i.e.~machine learning, are kind of agnostic or
even ``contraproductive'' towards this particular challenge flavour.
One reason for the success of large-scale linear algebra packages is
without a doubt their clear encapsulation.
Data transfer is a challenge picked up within the software, but the API is not
designed towards CA\footnote{The author is well-aware that PETSc, e.g., offers a
matrix-free usage mode. Yet, it seems not to be the most popular way to use
the software within complex PDE discretisations; at least the author is not
aware of extended documentation and examples how to integrate it into an
application landscape outside of the PETSc sanctum.}.
One reason for the success of machine learning frameworks is the fact that we
can use them almost as black-box.
This implies that users tend to realise a data pipeline architecture where data
transfer is not a high priority design quality criterion.
The visualisation community in contrast is well-aware of this rising
challenge---mainly due to the large IO penalties computers already face---and
pushes in-situ postprocessing and software that is made for in-situ processing.
The computing community either has to follow or establish usable
refactoring techniques \cite{Fowler:99:Refactoring} such that developers can
start from black-box units and then refactor towards CA.

Finally, it is important for the scientific computing community to continue to
push vendors towards real co-design.
At the moment, engineering constraints and economic interest (machine learning)
seem to steer the direction into which our hardware evolves.
While this evolution stimulates the development of communication-avoiding
techniques and thus stimulates an area of research, it is important to challenge
vendors over and over again.
Would it not be possible to build better-balanced systems?