Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems

2024

Read Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14441.txt.

Introduction

Quentin Stout gives optimal fine-grained algorithms for matrix multiplication and graph problems under the limits of classical physics in three-dimensional space. Each bit needs a minimum volume, and signals travel at bounded speed. Those two facts set a floor on how fast an n by n matrix product can run on any machine built in 3-space.

Stout shows the floor can be met with a three-dimensional mesh of processors, though the constants are far too large for real use. For matrices not over a ring, a larger mesh gives a slightly slower set time. Path and maze problems gain from 3-space tricks as well, while flat chips gain nothing, since there the classic systolic designs are already optimal.

Catalog record

YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14441

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems Abstract Obeying constraints imposed by classical physics, we give optimal fine-grained algorithms for matrix multiplication and problems involving graphs and mazes, where all calculations are done in 3-dimensional space. We assume that whatever the technology is, a bit requires a minimum volume and communication travels at a bounded speed. These imply that multiplying n × n n\times n matrices takes Ω ⁡ ( n 2 / 3 ) \Omega(n^{2/3}) time, and we show that this can be achieved by a fine-grained 3-d mesh of n 2 n^{2} processors. While the constants are impractically large, this is asymptotically faster than parallel implementations of Strassen’s algorithm, while the lower bound shows that some claims about parallelizing faster serial algorithms are impossible in 3-space. If the matrices are not over a ring then multiplication can be done in Θ ⁡ ( n 3 / 4 ) \Theta(n^{3/4}) time by expanding to a mesh larger than the input. In 2-d (such as the surface of a chip) this approach is useless and Θ ⁡ ( n ) \Theta(n) systolic algorithms are optimal even when the matrices are over a ring. Similarly, for path and maze problems there are approaches useful in 3-d but not 2-d. Quentin F. Stout Computer Science and Engineering, University of Michigan Keywords: 3-dimensional mesh-connected computer, fine-grained, physical constraints, matrix multiplication, graph, maze 1 Introduction We are interested in understanding the algorithmic differences in fine-grained parallel computing for computation in 3-dimensional space vs. the extensively studied 2-dimensional space used in VLSI, and for a few of the differences between medium-grained systems vs. fine-grained ones. Whatever the technology being used, we assume that a word of data takes a unit volume or area, respectively, and, for fixed energy takes unit time to move a unit distance. These limits are imposed by classical (non-quantum) physics, and imply that the basic mesh-connected computer is the densest packing of computation. This is in contrast to PRAM models that ignore the physical implications of increasing the memory and treat the communication time as being constant no matter what the distance. It is also in contrast to serial computer models where it is assumed that the time to access RAM is independent of problem size, and in contrast to medium or large-grained distributed memory parallelism models which make the RAM assumption on a board and typically make a PRAM-like assumption of constant time communication time between boards. Throughout, our computer is a 3-dimensional mesh (2-d meshes will also be discussed), with each processor connected to the 6 adjacent processors. The processing will be done in non-overlapping subcubes. Each time step is actually split into two smaller time steps, one for every processor to pass information to its neighbors, if it has any communication to do, and the other to do its processing as a member of a subcube (if it is in an active subcube). The time to move a word of information from one processor to another is proportional to the L_{1} distance between them if a shortest path is used, and more generally is linear in the length of the path. One aspect of the mesh model is that while communication is relatively slow, it eliminates the volume or area of wires to increase the bandwidth from one subcube to another. An algorithm which increases the number of long wires as n increases will increase the total volume. This was recognized as a serious issue in VLSI layout where typically the space increase was considered, making many of the wires longer, while the increased time to travel on a wire was occasionally, though not always, ignored. The space increase alone made some desirable configurations vastly inferior than if wires had zero area [ 46 ] since it required chips that had more area than the area needed to do the operations between words. An important example is the binary hypercube [ 23 ] : A hypercube, which is a popular interconnection network for parallel computers, requires considerably more area — \Theta(n^{2}) . What causes a hypercube to occupy so much area? Although the size of a vertex grows slowly with the number of vertices in a hypercube, most of the area of a hypercube layout is devoted to wires. Here n is the number vertices, not the number of rows or columns in the matrices considered in this paper, hence for our purposes the area is \Theta(n^{4}) Largely motivated by VLSI, there is extensive literature on algorithms for the fine-grained 2-dimensional mesh (see [ 22 , 26 , 46 ] ). A few fine-grained algorithms, and questions, for the 3-dimensional mesh had appeared, such as for sorting [ 43 ] (including finding the optimal high-order coefficient of time [ 18 , 41 ] ), oblivious routing [ 15 ] , connected component labeling of graphs [ 39 ] , and reachability in mazes [ 4 , 27 , 38 ] , but overall there are far fewer algorithms than for 2-d. However, interest in 3-dimensional computing is mounting due to its potential for faster and more energy efficient data movement [ 30 , 44 ] . It lowers the communication diameter and increases the bisection bandwidth, fundamental lower bounds for many problems. It was an important step towards reaching exascale [ 5 , 6 , 17 ] , and now must be used to reach zetascale. One saying is that “flops are free”, meaning that the time and energy required to move data on a chip from L2 cache to the floating point units are greater than doing a few calculations. Further, moving from RAM onto the chip is far more costly in time and energy. 3-d systems can simultaneously reduce time and energy. In the ‘80s there was theoretical work on embedding 2-d circuits into 3-d layouts, using the 3rd dimension to make denser devices on the base layer, with wiring in the higher layers. In some cases devices were allowed to be on higher layers as well. When the 3rd dimension could have the same extent as the others, with results such as Leighton and Rosenberg’s theorem that the smallest volume of a 3-dimensional layout of an N-device circuit is no more than \sqrt{NA} , where A is the smallest area of a 2-d layout [ 21 ] . Another result is that every small-degree N vertex graph can be laid out in a 3-dimensional grid with volume \Theta(N^{3/2}) and wire-length \Theta(N^{1/2}) [ 31 ] , in contrast to the 2-d bounds of area \Theta(N^{2}) and wire length \Theta(N) [ 20 ] . These results depend on having the third dimension grow as a power of N . All of these 3-d embeddings can be used in our model, but we are more interested in developing algorithmic techniques. This raises questions as to what algorithmic opportunities appear when moving from 2 to 3 dimensions. Some are trivial extensions and quite straightforward. For example, algorithms for sorting [ 43 ] and component labeling of a graph given its edges [ 39 ] easily extend to all dimensions, with the time going from \Theta(\sqrt{n}) on 2-d meshes to \Theta(\sqrt[d]{n}) in d-dimensional meshes of n processors with

Read the complete text