The Relationship between Architectures and Example-Retrieval Times

Eiichiro Sumita, Naoya Nisiyama, Hitoshi IidaAAAI 1994

Abstract

Example-Retrieval (ER) represents a significant computational bottleneck in Example-Based Machine Translation (EBMT), often accounting for up to 80% of total processing time. This paper evaluates the performance of ER across serial, MIMD, and SIMD architectures. By benchmarking two retrieval algorithms—basic and index-based—against a database of 100,000 examples, we demonstrate that SIMD architectures are uniquely capable of meeting the sub-millisecond latency requirements of real-time speech-to-speech translation systems.

Introduction

In the early 1990s, Natural Language Processing (NLP) shifted toward Example-Based Approaches (EBA). Instead of relying solely on complex rules, these systems translate by identifying the most similar previously recorded examples in a massive database. While this improves coverage and accuracy, it introduces a substantial computational "tax" in the form of Example-Retrieval (ER). To identify the best match, the system must calculate the semantic distance between an input and every entry in a database that may exceed 100,000 examples. On the serial hardware of the era, this process was far too slow for real-time applications like interpreting telephony. This study investigates which hardware architectures—Serial, MIMD (Multiple Instruction, Multiple Data), or SIMD (Single Instruction, Multiple Data)—can effectively handle this load.

Methods

The authors evaluated two primary retrieval algorithms across three hardware architectures:

  1. Basic Retrieval: An exhaustive search that calculates semantic distance for every example.
  2. Index-Based Retrieval: A faster variant that uses hashing and thesaurus codes to prune the search space, skipping calculations for examples that are clearly not a match.

The core of the retrieval is a semantic distance measure based on a three-layered thesaurus hierarchy (Ohno & Hamanishi, 1984). Distance is calculated by comparing "thesaurus codes" (numerical representations of word meanings) rather than raw strings.

Examples of semantic distance calculations based on thesaurus hierarchy conditions.

The dataset consisted of 100,000 Japanese noun phrases of the form "A no B" (e.g., "Tokyo no ginko") collected from the ASAHI newspaper. Typical sentence lengths were estimated from the ATR dialogue database to determine the number of ER calls required per sentence.

Results and Discussion

The primary performance goal was to retrieve from 100,000 examples in under 1 millisecond. The architectures tested included a high-performance serial workstation (DEC alpha/7000), a MIMD multiprocessor (KSR1 with 80 processors), and a SIMD massively parallel machine (MP-2 with 8,000 processors).

Performance comparison of Serial, MIMD, and SIMD architectures as the number of examples increases.

As shown in the performance comparison, serial machines are efficient for small datasets but scale poorly; even with indexing, the DEC alpha/7000 required ~100ms for 100,000 examples. MIMD architectures achieved ~20ms, but were limited by the communication overhead of the "merge" step, where results from different processors are combined.

SIMD architectures proved to be the "natural" fit for this task. Because the distance calculation is identical for every example in the database, ER is embarrassingly parallel. The SIMD machine (MP-2) successfully hit the 1ms target by broadcasting the input to thousands of processors simultaneously. While serial machines win at very small scales due to zero parallelization overhead, SIMD provides the highest throughput per dollar for large-scale semantic similarity searches.

Conclusion

While SIMD is optimal for retrieval, other NLP tasks like parsing may be better suited for MIMD architectures. Future EBMT systems should likely be heterogeneous to balance these diverse needs. Key limitations for future research include the potential bottleneck of data movement between specialized retrieval engines and general controllers, and the sensitivity of SIMD advantages to the complexity of the retrieval algorithm.

Summary updated

BibTeX
@inproceedings{sumita1994relationship,
  author = {Eiichiro Sumita and Naoya Nisiyama and Hitoshi Iida},
  title = {{The Relationship between Architectures and Example-Retrieval Times}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure