Model Matching and SFMD Computation

Steven Rehfuss, Dan W. HammerstromNeurIPS 1995

Introduction

In sensory processing domains like computer vision and speech recognition, systems typically operate in two distinct phases. The first phase involves processing raw data (such as pixels or audio waves) using Data Parallelism—applying identical mathematical operations to every piece of data. This phase is highly optimized for SIMD (Single Instruction Multiple Data) architectures.

However, the second phase, Model Matching, presents a different challenge. Here, the system compares the processed data against various "models" (e.g., different words in a dictionary or objects in a visual database). Because these models have varying structures, the control flow logic differs from one model to the next. In a traditional SIMD setup, if one processor follows a specific code branch, all other processors must sit idle until that branch completes, creating a massive efficiency bottleneck known as the "Idle PE" (Processing Element) tax.

While MIMD (Multiple Instruction Multiple Data) architectures allow every processor to execute independently, they are expensive to build, difficult to program, and require complex explicit synchronization. To bridge this gap, this paper introduces Single Function Multiple Data (SFMD), a novel parallel computing model designed to offer the flexibility of MIMD with the hardware efficiency and simplicity of SIMD.

The SFMD Architecture

SFMD is proposed as an extension to existing SIMD architectures that already possess local addressing and local conditional execution capabilities. The core innovation of SFMD is shifting from instruction-level synchronization to block-level synchronization. By allowing processors to synchronize at the boundaries of loops and conditionals rather than at every single instruction, SFMD significantly speeds up model matching tasks.

To enable this, the authors introduce three new assembly-level constructs:

  1. distribute n: Instructs the processors to take the next n instructions, store them in a local buffer, and execute them independently.
  2. sync: Acts as a barrier where processors wait until all PEs have finished their local block of code.
  3. branch-local: Allows processors to perform their own loops and jumps entirely within their local code block.

From a hardware perspective, implementing SFMD requires adding a small "micro-sequencer"—comprising a program counter and a small instruction buffer—to each processing element. The authors calculate that this hardware addition would only consume about 3% to 11% of the chip area. As transistors continue to shrink, this minor silicon real estate trade-off becomes increasingly favorable, allowing PEs to act as independent computers for short bursts of time.

Evaluation and Results

Because SFMD is a proposed architectural model, the authors relied on algorithmic simulations rather than modern benchmark datasets to evaluate its performance. They focused on tasks that traditionally suffer under strict SIMD constraints:

  • Sparse Matrix Multiplication: The authors simulated synthetic matrices ranging from 256x256 to 2048x2048 with varying levels of sparsity (0.001 to 0.4). Because row lengths vary significantly in sparse matrices, SIMD processors often wait for the longest row to finish computing. SFMD achieved a speedup of 2.2x to 2.7x over SIMD for very sparse matrices.
Speedup of SFMD over SIMD for sparse matrices across varying levels of sparsity.
  • Interpretation Tree Search (ITS): Simulating a common computer vision task based on real-world parameters (involving 5,000 to 10,000 tree expansions), SFMD demonstrated speedups in the 2x to 4x range compared to SIMD.
  • Floating Point Emulation: The authors also estimated a 2x improvement for IEEE floating-point math emulation, a process that relies heavily on complex, data-dependent branching logic.

Ultimately, SFMD proves significantly easier to implement than MIMD because it avoids the overhead of explicit inter-processor communication during function execution. In SIMD, the cost of a branch is the sum of all possible paths; in SFMD, the cost is only the time of the longest path actually taken by any processor.

Key Insights and Limitations

A major conceptual takeaway from the paper is the distinction between Knowledge Parallelism and Data Parallelism. While traditional parallel computing focuses on distributing data, model matching requires distributing "knowledge" (the models themselves). SFMD is specifically tailored for this "distribute the knowledge, broadcast the data" paradigm. Furthermore, SFMD is highly compiler-friendly. It can be implemented as a compiler optimization for data-parallel languages like 'C', where the compiler automatically detects when a code block meets the constraints for SFMD execution.

Despite its advantages, SFMD has notable limitations:

  • Nested Loop Constraints: SFMD does not offer massive performance gains for nested loops unless the outer loop count is exceptionally large.
  • Communication Restrictions: Code executing within an SFMD block cannot reference global variables or communicate with other processors. This strictly limits SFMD to "embarrassingly parallel" sub-tasks.

Looking forward, the authors suggest that SFMD could eventually support a form of "highly synchronized pipeline parallelism." In this future state, different processors could execute entirely different tasks independently and then synchronize to share results in standard SIMD mode, further expanding the flexibility of the architecture.

Summary updated

BibTeX
@inproceedings{rehfuss1995model,
  author = {Steven Rehfuss and Dan W. Hammerstrom},
  title = {{Model Matching and SFMD Computation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
}
Figure