ACM SIGPLAN Notices · 1997 · 39 citations · 17 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersComputer ArchitectureMatrix ComputationMemory HierarchyMemory Hierarchy DesignMemory Hierarchy OptimizationMemory Subsystem DesignParallel Numerical Linear AlgebraBlocked AlgorithmsMatrix MultiplicationMemory Access LocalityMemory Hierarchy AlgorithmsMemory Hierarchy AnalysisMemory Hierarchy PerformanceParallel Matrix ComputationParallel Matrix Multiplication
An elementary, machine-independent, recursive algorithm for matrix multiplication C+=A*B provides implicit blocking at every level of the memory hierarchy and tests out faster than classically optimrd code, tracking hand-coded BLAS3 routines. Proof of concept is demonstrated by racing the in-place algorithm against manufacturer's hand-tuned BLAS3 routines; it can win.The recursive code bifurcates naturally at the top level into independent block-oriented processes, that each writes to a disjoint and contiguous region of memory. Experience has shown that the indexing vastly improves the patterns of memory access at all levels of the memory hierarchy, independently of the sizes of caches or pages and without ad hoc programming. It also exposed a weakness in SGI's C compilers that merrily unroll loops for the super-scalar R8000 processor, but do not analogously unfold the base cases of the most elementary recursions. Such deficiencies might deter future programmers from using this rich class of recursive algorithms.
17
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
David Culler, Richard M. Karp, David A. Patterson et al. · Communications of the ACM · 1996 · 286 citations · Full text
A gentle introduction to Haskell
Paul Hudak, Joseph H. Fasel · ACM SIGPLAN Notices · 1992 · 209 citations · Full text