Communication (data movement) often dominates a computation's runtime and energy costs, motivating organizing an algorithm's operations to minimize communication. We study communication costs of a class of algorithms including many-body and matrix/tensor computations and, more generally, loop nests operating on array variables subscripted by linear functions of the loop iteration vector. We use this algebraic relationship between variables and operations to derive communication lower bounds for these algorithms. We also discuss communication-optimal implementations that attain these bounds.

Skip to main contentclear all Search tipsRefine Results Back to Results From: To: Apply Sort By: Relevance A-Z By Title Z-A By Title A-Z By Author Z-A By Author Date Ascending Date Descending

# Your search: "author:"Knight, Nicholas""

3 results

No filters applied

## filters applied

## Type of Work

Article (2) Book (0) Theses (1) Multimedia (0)

## Peer Review

Peer-reviewed only (3)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (3) UC Davis (0) UC Irvine (0) UCLA (0) UC Merced (0) UC Riverside (0) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (0) Lawrence Berkeley National Laboratory (2) UC Agriculture & Natural Resources (0)

## Department

## Journal

## Discipline

## Reuse License

## Scholarly Works (3 results)

Recent Work (2013)

The movement of data (communication) between levels of a memory hierarchy, or
between parallel processors on a network, can greatly dominate the cost of
computation, so algorithms that minimize communication are of interest.
Motivated by this, attainable lower bounds for the amount of communication
required by algorithms were established by several groups for a variety of
algorithms, including matrix computations. Prior work of
Ballard-Demmel-Holtz-Schwartz relied on a geometric inequality of Loomis and
Whitney for this purpose. In this paper the general theory of discrete
multilinear Holder-Brascamp-Lieb (HBL) inequalities is used to establish
communication lower bounds for a much wider class of algorithms. In some cases,
algorithms are presented which attain these lower bounds.
Several contributions are made to the theory of HBL inequalities proper. The
optimal constant in such an inequality for torsion-free Abelian groups is shown
to equal one whenever it is finite. Bennett-Carbery-Christ-Tao had
characterized the tuples of exponents for which such an inequality is valid as
the convex polyhedron defined by a certain finite list of inequalities. The
problem of constructing an algorithm to decide whether a given inequality is on
this list, is shown to be equivalent to Hilbert's Tenth Problem over the
rationals, which remains open. Nonetheless, an algorithm which computes the
polyhedron itself is constructed.

Recent Work (2019)

H\"older-Brascamp-Lieb inequalities provide upper bounds for a class of
multilinear expressions, in terms of $L^p$ norms of the functions involved.
They have been extensively studied for functions defined on Euclidean spaces.
Bennett-Carbery-Christ-Tao have initiated the study of these inequalities for
discrete Abelian groups and, in terms of suitable data, have characterized the
set of all tuples of exponents for which such an inequality holds for specified
data, as the convex polyhedron defined by a particular finite set of affine
inequalities.
In this paper we advance the theory of such inequalities for torsion-free
discrete Abelian groups in three respects. The optimal constant in any such
inequality is shown to equal $1$ whenever it is finite. An algorithm that
computes the admissible polyhedron of exponents is developed. It is shown that
nonetheless, existence of an algorithm that computes the full list of
inequalities in the Bennett-Carbery-Christ-Tao description of the admissible
polyhedron for all data, is equivalent to an affirmative solution of Hilbert's
Tenth Problem over the rationals. That problem remains open.
Applications to computer science will be explored in a forthcoming companion
paper.