TORCH Testbed

TORCH (Testbed for Optimization Research)

TORCH is a broad testbed of computational reference kernels in the context of high-performance computing. The testbed provides a detailed problem specification, input generation scheme, verification scheme, and a functional reference implementation. With these assets, computer scientists may research a wide range of areas including algorithms, performance optimization, programming models, languages, compilers, and hardware/software co-design by unencumbering themselves from potentially decades-old implementations. This project is codified in two forms: a set of reference implementations, and a technical report describing the methodology and kernels.

Researchers

Dwarfs / Motifs

Previously researchers have attempted to categorize the styles of computation seen in scientific computing, and more broadly, in computing in general. Phil Colella suggested most computation within the scientific computing arena could be classified as one of his Seven Dwarfs of computing: Dense Linear Algebra, Sparse Linear Algebra, Computations on Structured Grids, Computations on Unstructured Grids, Spectral Methods, Particle Methods, and Monte Carlo. Researchers from UC Berkeley and LBNL took this concept and explored extending it to computing in general. The result was the Berkeley View's 13 Motifs. These motifs reused or clarified many of the original Dwarfs and added several new ones including: Map Reduce, Combinational Logic, Graph Traversals, Dynamic Programming, Backtrack/Branch-and-bound, Graphical Models, and Finite State Machines. Unfortunately, these methods use such broad strokes to describe and delineate motifs, they are of limited use to researchers wishing to improve performance or productivity. Conversely, the more pragmatic benchmark-based approach of simply collecting fixed-implementations of key applications or kernels optimized for existing architectures, languages, and programming models, greatly narrows the potential research. In this project, we explored an alternative that attempts to take the best of both worlds.

An Evolved Testbed

Problem Specification: For each kernel, we specify a domain-appropriate, high-level definition independent of architecture, languages, and programming model.
Scalable Input Generation: We defined and implemented a scalable problem generator for each problem. In some cases, this represents a prose description, and in others, a piece of code used to produce an input dataset.
Solution Verification: In conjunction with the input generation scheme, we strive to ensure the problem verification scheme is independent from the problem definition. That is, you don't have to have a correct implementation of the problem to verify another (more optimized) implemementation of the problem. Rather we use the underlying domain-specific mathematics in conjunction with the problem generator to produce problems that can easily be verified.
Solution Quality: The quality of a solution is a multifaceted and complex discussion. Quality can be measured in terms of performance, energy, time-to-solution, or productivity, among others.
Reference Implementation: To provide context as to how such kernels productively map to existing architectures, languages and programming models, we have included a sequential C implementation for each kernel.

Publications

A. Kaiser, S. Williams, K. Madduri, K. Ibrahim, D. Bailey, J. Demmel, E. Strohmaier, "TORCH Computational Reference Kernels: A Testbed for Computer Science Research", Lawrence Berkeley National Laboratory, Paper LBNL-4172E, 2010. Also, EECS Department, University of California at Berkeley, Technical Report UCB/EECS-2010-144, 2010. [pdf]
A. Kaiser, S. Williams, K. Madduri, K. Ibrahim, D. Bailey, J. Demmel, E. Strohmaier, "A Principled Kernel Testbed for Hardware/Software Co-Design Research", Proceedings of the 2nd USENIX Workshop on Hot Topics in Parallelism (HotPar), 2010.
E. Strohmaier, S. Williams , A. Kaiser, K. Madduri, K. Ibrahim, D. Bailey, J. Demmel, "A Kernel Testbed for Parallel Architecture, Language, and Performance Research", International Conference of Numerical Analysis and Applied Mathematics (ICNAAM), 2010.