ACM SIGPLAN Notices · 2001 · 11 citations · 22 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresParallel ComputingHardware AccelerationMatrix ComputationMemory Hierarchy OptimizationNumerical Linear AlgebraParallel Numerical Linear AlgebraHierarchical Memory ArchitectureMatrix MultiplicationParallel Divide And ConquerParallel Matrix ComputationParallel Matrix MultiplicationParallel Matrix-vector MultiplicationSparse Matrix ComputationTwo-dimensional Arrays
The uniform representation of 2-dimensional arrays serially in Morton order (or {\eee} order) supports both their iterative scan with cartesian indices and their divide-and-conquer manipulation as quaternary trees. This data structure is important because it relaxes serious problems of locality and latency, and the tree helps to schedule multi-processing. Results here show how it facilitates algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment. We have built a rudimentary C-to-C translator that implements matrices in Morton-order from source that presumes a row-major implementation. Early performance from LAPACK's reference implementation of \texttt{dgesv} (linear solver), and all its supporting routines (including \texttt{dgemm} matrix-multiplication) form a successful research demonstration. Its performance predicts improvements from new algebra in back-end optimizers. We also present results from a more stylish \texttt{dgemm} algorithm that takes better advantage of this representation. With only routine back-end optimizations inserted by hand (unfolding the base case and passing arguments in registers), we achieve machine performance exceeding that of the manufacturer-crafted {\tt dgemm} running at 67% of peak flops. And the same code performs similarly on several machines. Together, these results show how existing codes and future block-recursive algorithms can work well together on this matrix representation. Locality is key to future performance, and the new representation has a remarkable impact.
22
The Art of Computer Programming
W.J. Worlton · Nuclear Science and Engineering · 1968 · 2.3K citations
A Transformation System for Developing Recursive Programs
R. M. Burstall, John Darlington · Journal of the ACM · 1977 · 1.3K citations · Full text
An effective way to represent quadtrees
Irene Gargantini · Communications of the ACM · 1982 · 639 citations · Full text