An Efficient Parallel Substrate for Typed Feature Structures on Shared Memory Parallel Machines

Takashi Ninomiya, Kentaro Torisawa, Jun’ichi TsujiiCOLING 1998

TL;DR

This paper introduces PSTFS, a novel parallel substrate designed for efficient processing of Typed Feature Structures (TFSs) on shared-memory parallel machines. PSTFS enables the development of high-level parallel Natural Language Processing (NLP) systems by providing a flexible agent-based architecture that significantly speeds up complex tasks like HPSG parsing.

What Problem Does This Paper Address?

Developing real-time Natural Language Processing (NLP) systems has been a long-standing challenge. While sophisticated methodologies exist, their computational expense often makes them impractical for real-time applications. The advent of shared-memory parallel machines offers a potential solution, but requires efficient tools for developing parallel NLP systems. Programmers need a way to leverage parallel hardware without getting bogged down in low-level efficiency concerns. This paper addresses this by proposing PSTFS, a system that simplifies the creation of parallel NLP applications by abstracting away much of the complexity of parallel execution and communication for TFSs.

Methods

PSTFS is built upon an agent-based and object-oriented architecture, where computational agents communicate via messages containing TFSs. The system distinguishes between two types of agents:

  • Control Agents (CAs): These agents manage overall system control, including parallelism, and act as "masters" to CSAs. They are written in ABCL/f.
  • Constraint Solver Agents (CSAs): These agents perform the actual TFS manipulation and constraint solving, acting as "workers." They are primarily written in LiLFeS, a language supporting TFSs.

A key innovation is PSTFS's efficient communication scheme for TFSs. Instead of sending entire TFSs, messages often carry only IDs (pointers) to TFSs residing on a shared heap. This "demand-driven copying" mechanism reduces redundant data transfer. When a CSA needs to operate on a TFS, it copies the relevant data from the shared heap to its local heap. This approach ensures that TFSs remain unmodified by CAs, preventing anomalies when multiple agents access the same data. The CSA's execution mechanism is based on a modified abstract machine for TFSs (LiAM), designed for efficient handling of TFS operations like unification, which can be destructive.

Datasets

The paper evaluates PSTFS using two HPSG parsers on a corpus of 879 random sentences from the EDR Japanese corpus. The grammar used for the CKY-style parser is an underspecified Japanese HPSG grammar with 6 ID-schemata and 39 lexical entries. For the ALE-style parser, a sample HPSG grammar with 7 schemata and 62 lexical entries was used.

Key Insights and Ideas

  • Agent-based abstraction simplifies parallel NLP: By separating control (CAs) from computation (CSAs), PSTFS provides a clear and manageable way to build parallel NLP systems.
  • Demand-driven TFS copying is efficient: Passing TFS IDs instead of full structures significantly reduces communication overhead, especially for large TFSs.
  • Shared heap for inter-CSA communication: This mechanism, combined with local heaps for temporary computations, allows for efficient data sharing and processing among CSAs.
  • TFS immutability for CAs is crucial: Preventing CAs from modifying TFSs simplifies parallelism management and avoids race conditions.
  • PSTFS is practical and flexible: The ability to implement complex HPSG parsers with relatively concise code demonstrates the system's ease of use and effectiveness.

Key Results

The paper reports significant speedups for two parallel HPSG parsers implemented on PSTFS:

  • Parallel CKY-style HPSG Parser: Achieved a maximum speedup of 12.4 times and an average parsing time of 85 msec per sentence.
  • Chart-based Parallel HPSG Parser (ALE Grammar): Achieved a maximum speedup of 10.9 times and an average parsing time of 1776 msec per sentence for long sentences.

These results demonstrate that PSTFS can achieve near real-time performance even with computationally expensive formalisms like HPSG.

Limitations and Future Work

The authors acknowledge that the speedup is not perfectly proportional to the number of processors. Analysis of processor status logs reveals that many processors are frequently idle. They suggest that this idle time could be utilized for other tasks, such as semantic processing, or for parsing different sentences in a server-like application.

Future work includes exploring the use of their HPSG parser on PSTFS for applications like speech recognition, Natural Language Interfaces, and Speech Machine Translation. They also note that further investigation into optimizing the parallelism extraction within the parsing algorithms themselves could further improve performance.

Summary updated

BibTeX
@inproceedings{ninomiya1998efficient,
  author = {Takashi Ninomiya and Kentaro Torisawa and Jun’ichi Tsujii},
  title = {{An Efficient Parallel Substrate for Typed Feature Structures on Shared Memory Parallel Machines}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1998},
}
Figure