Associative
Processing
Many information processing applications re-
quire users to reference
a
set of data elements,
associated with
a
common key, by the value of an
associated key (rather than by their physical loca-
tions within some storage structure). Examples of
data elements might include the selection of those
Rover cars sold after
1987
with air-conditioning or
those graduate software engineers with two years of
experience in Ada programming or those pixels cor-
responding to a particular intensity value in a com-
puter vision system or those facts and rules that are
related to a particular query in a knowledge-based
artificial intelligence system.
With traditional von Neumann computers, such
data access requires repeated (sequential) navigation
through some tree-structured (possibly complex)
indirect-addressing mechanism to unique storage
locations (where the sought data may or may not ex-
ist). This access method results in loss of accessing
efficiency and much redundant processing.
In contrast, with associative processing users ac-
cess the set
of
data elements in parallel by content
addressing and simple association linking. The ad-
dresses of such data have no logical significance and
only relevant data can be accessed. Moreover,
asso-
ciative processing avoids the additional overheads
of
sequentially transferring data to an external pro-
cessor by (parallel) in-situ processing.
Associative processing involves a particularly
flexible and naturally parallel form of symbolic
representation and manipulation of structured data
(sets, arrays, tables, trees, and graphs) processing.
Potential benefits include simplicity of expression,
storage capacity, and speed
of
execution over a wide
variety of nonnumerical and numerical information
processing applications.
multilayer thin-film ceramic, and silicon-on-silicon
superhybrids). ASP remains independent of
technology,
so
it can benefit from the inevitable im-
provement in microelectronics technology without
ar-
chitectural modification.
ASP
system architecture
As indicated in Figure
1,
an ASP system comprises a
dynamically reconfigurable parallel processing struc-
ture of communicating ASP substrings, each sup-
Table
1.
ASP
information processing applications.
Special-purpose applications
Nonnumerical information processing
Text processing, database management,
office systems, information management
Information (document) retrieval for infor-
mation, legal and patents services
Intelligent knowledge-based, or expert,
systems (medical, automotive systems)
Numerical information processing
Digital signal processing in aerospace,
military, telecommunications systems
Speech recognition in military, business,
automotive systems
Image-related processing
Computerized tomography for medical,
industrial, geophysical image recon-
struction
Image clarification, scene analysis, pattern
recognition in support of remote sensing
(for satellites and surveillance), artificial
vision (for robotics, automation)
Computerized image generation for
graphic arts and special television
effects and CAD/CAM (3D image
generation, associated database
management)
General-purpose applications
Vector processing for research modeling and
design simulation
Symbolic processing for compilation, transla-
tion, theorem proving
Artificial intelligence processing for fifth-
generation (declarative) support of pro-
gramming languages such as functional
(LISP) and logic-based (Prolog)
ported with an ASP data buffer (ADB), a controller,
and a data communications network.
ASP
substrings.
Each ASP substring comprises a
string of identical APES (associative processing ele-
ments), as shown in Figure
2.
Each APE connects to an
inter-APE communications network (which runs in
parallel with the APE string). All APES share common
bit-parallel data, activity, and control buses, and one
feedback line called Match Reply, or MR.
An
external
controller maintains the buses, feedback line, and Link
October
1988
11
Authorized licensed use limited to: NANJING UNIVERSITY OF POST AND TELECOMMUNICATIONS. Downloaded on May 23, 2009 at 00:54 from IEEE Xplore. Restrictions apply.