High Performance Natural Language Processing on Semantic Network Array Processor

Hiroaki Kitano, Dan I. Moldovan, Seungho Cha

Introduction

In the early 1990s, the field of Artificial Intelligence faced a significant hurdle: the performance bottlenecks of traditional symbolic Natural Language Processing (NLP). This paper explores a pioneering solution—specialized "connectionist" hardware designed to achieve the speeds necessary for real-time applications.

The Computational Challenge

The primary goal of the era was real-time speech-to-speech translation. However, traditional NLP relied heavily on "unification," a process of merging complex data structures to ensure grammatical agreement. Unification is computationally expensive and notoriously difficult to parallelize. For systems intended to handle simultaneous interpretation or massive text volumes (millions of sentences per hour), serial, rule-heavy processing was insufficient. The researchers sought a way to perform deep linguistic analysis—handling ambiguity and complex syntax—at human-interaction speeds.

The DMSNAP Approach: Hardware-Software Co-Design

The authors proposed DMSNAP, an NLP system running on the Semantic Network Array Processor (SNAP). This approach moved away from treating parsing as a logical proof, instead framing it as a memory search within a semantic network.

Hardware Architecture

The SNAP hardware is a highly parallel machine featuring 160 processing elements (DSPs) arranged in a modified hypercube. It is optimized for "marker passing," where small information units (markers) traverse a network of nodes. By microcoding marker-propagation instructions directly into the hardware, the system bypasses the overhead associated with general-purpose CPUs.

The SNAP-1 system architecture, showing the hardware and software environments alongside the physical design.

Memory-Based NLP and Finite Message Passing

DMSNAP utilizes a "finite message passing" model. Unlike previous parallel models that struggled with complex, unbounded "feature structures," DMSNAP passes only bit-vectors, addresses, and numeric values. This simplification allows for high-speed hardware execution.

The system's "secret sauce" is the Syntactic Constraint Network (SCN), which replaces traditional unification. The SCN uses a finite-state network to enforce grammatical rules through node activation and inhibition.

A semantic network representation in DMSNAP, illustrating concept nodes and their relationships for a sample sentence.

Experimental Setup

The system was evaluated using the ATR Conference Registration Domain, which includes a vocabulary of 450 words and 329 sentences. At the time of the study, the physical SNAP hardware was under assembly, so performance was estimated using an instruction-level accurate SNAP simulator running on a SUN 3/280 workstation.

Performance and Insights

The results demonstrated that specialized hardware could achieve remarkable efficiency:

  • Parsing Speed: Sentences were processed in just 0.55 to 1.65 milliseconds.
  • Throughput: Theoretical estimates suggest the system could parse over 3 million sentences per hour.
  • Sublinear Scaling: Crucially, processing time grew sublinearly with network size. Guided marker passing ensures that adding knowledge does not proportionally slow the system.
  • Robustness: Unlike rigid unification systems that fail on minor errors, DMSNAP uses a cost-based approach to find the "best fit" interpretation, mirroring human linguistic flexibility.

Performance Summary

Sentence Example Length (words) Time at 10 MHz (ms)
"He is at..." 4 0.65
"He said that..." 10 1.50
"Juntae solved..." 7 1.65

Conclusion

DMSNAP represents a masterclass in hardware-software co-design. By tailoring a processor to the specific logic of semantic networks, the researchers achieved performance gains that far outpaced the general-purpose hardware of the time. While modern AI has shifted toward commodity hardware like GPUs, this work remains a fascinating example of how specialized architecture can break through fundamental computational barriers.

Summary updated

BibTeX
@inproceedings{kitano1991high,
  author = {Hiroaki Kitano and Dan I. Moldovan and Seungho Cha},
  title = {{High Performance Natural Language Processing on Semantic Network Array Processor}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure