Which comes first: The architecture or the algorithm?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

There is a constant tension between the designers of algorithms and architectures. Each designs for the others previous generation. Several factors are making this an increasingly inadequate approach. On the hardware side, the growing disparity between the performance of memory and CPU has pushed many architectures to hierarchical memories that reward significant data reuse (and punish algorithms that use data items a small number of times). On the algorithmic side, at least for a large class of algorithms in scientific computing, the emphasis on increasingly efficient algorithms, measured by the amount of work (floating point operations) per solution value, has led to algorithms that touch data only a few times. Further, algorithmic techniques that lead to adaptive methods (computing only with as much data as is required to accurately represent the solution) often lead to irregular or unpredictable accesses to memory. While these trends in architectures and algorithms are away from each other, there are other trends in algorithms that provide both a degree of greater memory locality without sacrificing algorithmic optimality. These are hierarchical methods, such as multigrid and general domain decomposition. These hierarchical methods place some requirements on architectures; primarily that there be no distinguished collection of processes/threads in a computation. Another opportunity in algorithms is the potential for exploiting split-phase or two-step operations; most algorithms are designed under the assumption that parallel operations, such as a scan or reduction, are single step (blocking in MPI terms), but this is often not required. We conclude by noting that both algorithmic and architecture research can benefit from a more continuous dialog.

Original languageEnglish (US)
Title of host publicationProceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems
EditorsA. Veidenbaum, K. Joe
PublisherIEEE Comp Soc
Pages13
Number of pages1
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems - Maui, HI, USA
Duration: Oct 22 1997Oct 24 1997

Other

OtherProceedings of the 1997 International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems
CityMaui, HI, USA
Period10/22/9710/24/97

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Which comes first: The architecture or the algorithm?'. Together they form a unique fingerprint.

Cite this