Browse Prior Art Database

RESEARCH IN NATURAL LANGUAGE UNDERSTANDING (Report No. 6)

IP.com Disclosure Number: IPCOM000128808D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-19
Document File: 16 page(s) / 55K

Publishing Venue

Software Patent Institute

Related People

W.A. Woods: AUTHOR [+3]

Abstract

In various attempts to construct systems that automatically transform ordinary computer programs into programs that can capitalize on parallel execution, it is common to discover that the maximum effective parallelism that can be gained for a given program is quite limited (factors of 4 to 6 are not atypical). This is due to the fact that the potential parallelism that is exploited by such systems is essentially the parallel computation of subexpressions in an equation or the parallel evaluation of arguments to a function call. Such parallelism is limited to the number of subexpressions an equation has or the number of arguments in a function call, and these numbers are not. large. For computations that are typical of nondeterministic algorithms, however, the number of alternative computation paths that can be potentially followed in parallel can easily grow into the hundreds (or more). For many searches to find something satisfying a condition, one may find lists being scanned which are themselves hundreds long (even longer lists would be used if it - 1 - Report No. 4181 Bolt Beranek and Newman Inc. were not for the computational cost). Often, the condition to be tested involves a pattern match which could itself have a large number of alternative choices (e.g., when the pattern contains one or more substring variables). Hence, in this domain, it is not unreasonable to expect factors of potential parallelism in the hundreds (or even thousands for very large data bases).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

RESEARCH IN NATURAL LANGUAGE UNDERSTANDING

Quarterly Technical Progress Report No. 6

1 December 1978 - 28 February 1979

AHPA Order No. 3414 Contract No. N00014-77-C-0378

Program Code No. 8D30 Contract Expiration Date:

31 August 1979

""" " Name of Contractor: Short Title of Work Bolt Beranek and Newman Inc. Natural Language Understanding Effective Date of Contract: Principal Investigator: 1 September 1977 Dr. William
A. Woods (617) 491-1850, x4361 Amount of Contract: Scientific Officer: $712,572 Gordon D. Goldstein

Sponsored by Advanced Research Projects Agency ARPA Order No . 3414

This research was supported by the Advanced Research Projects Agency of the Department of Defense and was monitored by ONR under ~'"^ Contract No. N00014-77-C-0378.

Report No. Report No . 4181 Bolt Beranek and Newman Inc.

Parallel Algorithms for Real Time Knowledge Based Systems

W. A. Woods

1. Introduction

In various attempts to construct systems that automatically transform ordinary computer programs into programs that can capitalize on parallel execution, it is common to discover that the maximum effective parallelism that can be gained for a given program is quite limited (factors of 4 to 6 are not atypical). This is due to the fact that the potential parallelism that is exploited by such systems is essentially the parallel computation of subexpressions in an equation or the parallel evaluation of arguments to a function call. Such parallelism is limited to the number of subexpressions an equation has or the number of arguments in a function call, and these numbers are not. large.

For computations that are typical of nondeterministic algorithms, however, the number of alternative computation paths that can be potentially followed in parallel can easily grow into the hundreds (or more). For many searches to find something satisfying a condition, one may find lists being scanned which are themselves hundreds long (even longer lists would be used if it

- 1 - Report No. 4181 Bolt Beranek and Newman Inc.

were not for the computational cost). Often, the condition to be tested involves a pattern match which could itself have a large number of alternative choices (e.g., when the pattern contains

Bolt, Beranek & Newman, Inc. Page 1 Dec 31, 1979

Page 2 of 16

RESEARCH IN NATURAL LANGUAGE UNDERSTANDING (Report No. 6)

one or more substring variables). Hence, in this domain, it is not unreasonable to expect factors of potential parallelism in the hundreds (or even thousands for very large data bases).

Most successful parallel processing architectures have resulted from designing an architecture to support some specific class of algorithm which is known to be important and/or expensive for some useful class of problems. Examples are Fast Fourier Transforms (for signal processing applications) and Key retrieval for associative memory processors. The former has turned out to be immensely important for a...