On a Tool in Artificial Intelligence Research: An Associative Memory, Parallel Language, AMPPL-II

Al:lSTRACT

One of the remarkable things about human information processing is the way we store and retrieve information. The human associative memory is a device that has been only rather crudely approximated with computers in flexibility, selfmodifiability, and complexity of associations.

In this paper, we describe a computer language, AMPPL-II, which simulates a machine with an extensive, variable size associative memory and parallel processing capability. It was to be made fairly machine-independent and is, therefore, embedded in a high-level algebraic language. The version outlined here is built as an extension of SLIP (Symmetric List Processing Language), itself being

embedded in FORTRAN IV.

The expected range of applicability of 1\i'!PPL-II covers a rather wide area. Candidates in the non-numerical field are game playing, picture processing and image identification, encoding-decoding, simulation of cognitive behavior, multikey information retrieval, language analysis, sorting, merging, collating, query systems, and so on. Ntrrnerical applications would be matrix calculations, solution of partial differential equations, computation of auto- and cross­ correlation functions, signal correction,

etc.

Stimulated by this language, new computational techniques and algorithms nay, hopefully, be developed. These, on one hand, and technological advances, on the other, may render the hardware implementation of an AMPPL-like machine economical.

*N. V. F.

c:es1gned N-!PPL and is responsible for the mistakes contained in this paper. W. R. McK. implemented the language on the CDC 6400. Teiii Furugori's contribution to the latter is also acknowledged. Further, Peter Muller and Charles Bergenstock worked on an IDM 7044 implementation of l\HPPL-I.

ON A NE\<1 TOOL IN ARTIFICIAL INTELLIGENCE RESEJ',RCH,

AN ASSOCIJI.TE Hm!ORY, PARALLEL PROCESSING

LANGUAGE, NlPPL- I I.

by

Nicholas v. Findler and Wiley R, McKinzie*

Department of Computer Science State University of New York at Buffalo

KEY I'.'ORDS AND PliPl\SI:S

Associative memory, parallel processing, symbol manipulation, list processing, extension of algebraic languages, information structures.

CR CA'l'EGORIES

3.60, 3,69, 4.10, 4,22

I:JTROCUCTION

There is an obvious interrelation between the level of complexity of the problems that are potentially solvable on computers, and the power of available software and hardware. Further develonment in programming syste[lS and langua0es enables us to attack problems that have so far been Lcyond the sphere of practicability. List processing and strinq manipulatino languages, for example, hn.ve opened up ne,.; vistas in many research fielrls, probably most significantly in Artifical Intelligence.

We describe in this paper an approach to Me~ory and information processing, radically ~ifferent froM those of the traditional von Neu~ann-type computers. An Associative Memory, Parallel Processing Language, l\MPPL-II*, is introduced, which sinulates a cor;1puter built in harC:Iware. (\·.'e point out that some of the facilities available in l\r1PPL-II would not he present in the engineer's implementation. However, they do not "cost" much in progranw.inq effort and in cor..putinq tirr.e, and they nay also be handy to have. h'e have, therefore, decided to inclu0e a few "non-generic"

features.)

* The first version, ru~PPL-I, was rerorted on in [1,2) and was i~plemented but not col",plctely < 1 ebur:rqed for the Im1 7044, The presently described language, running on the CDC 6400, has improved dynamic memory allocation facilities and more powerful instructions concerning Relations (cf. Section II/G).

It should be noted here that t here are ~any references in the literature to hardware and s oftware efforts that are aimed at oGjectives similar to ours here. The engineering activity can be divided into two, rather distinct cateq-ories. First, very expensive "black boxes" have Leen constructed and attached to special or general purpose computers to perform some of the functions \'/C shall discuss later. Second, small associative memory units have been included in com~uter systems for specific purposes , such as the paging operation wi th large- scale time­

shared machines.

l\ number of progra:nming systerrts have also been developed, most of them directed towards specific, sor:1e of them tm·1ards more general applications. vie only wish to single out here the work of Feld~an and Rovner [3,4,5], and of Dodd , Beach and I<ossol [6]. Their olJjectives are very similar to ours, although the respective techniques are different. Exrerience will sho\<1 which of these languages is more poHerful, easier to program anc1 debug in.

Excellent surveys, covering the field in question up to the middle of 1966, can be found in [7,8]. For the sake of completeness, we mention a few more , some left out of the above surveys, some of more recent vintage [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20].

I. SOML BASIC CONCEPTS

In contrast with conventional, wordoriented machines, computers \vith associative memories are contentaddressable. These terms refer to the interrelat1onship betHeen data as well as to the fact that a memory \·lOrd or words can be accessed by matching with a selectable field of a special word, rather than by an address. Parallel ~recessing, a related idea and dist1nct from multiprocessing , allows command sequences to be executed simultaneously over large

numbers of data sets .

It was intended to develop a language which incorporates, from the programmer's viewpoint, these facilities in addition to the previously available algebraic, list processing and string manipulating

facilities.

For understandable reasons, embedding seemed to be an economical and fairly efficient approach, which also achieves a reasonably high level of machine indenendence. The presently described version is an extension of SLIP, itself be ing embedded in FORTRAN IV. (The internal mechanism of SLIP had to be modified to a small extent but the user need not be nwarc of thi s fact.) There are only tv:o 7\_MPPL subpro<Jrams written in assembly language now. Converting often used subroutines and functions, currently coded in FOR7RAN , into assembly language would, of course, save considerable machine time Hith large programs.

Unlike the expensive and inflexible associative memories nresently built in hardware, the size of the Si mulated Associative :·1err.ory (S!'.'i) is determined by the programmer accorC::ing to his needs. In fact, he has to specify the ratio b7tween the sizes of Si'\!'1 and of the Ava1lable Space Li s t (AVSL) of SLIP at the beginning of his progra.rn. 'l'he sum of Sl\J'1 and .'\VSL e~uals the storage area left unused after the compilation of the F0RTPAN program.

The programmer can also b';lild into the program trap points , at 1-1h1ch a.part of SNI or AVSL is dynamically reass1gned to the other part if there is a need for it, i.e. if the. size of. one memory type decreases below a certain prespecified threshold value. Memory contraction, coupled with a specific form of garbage coliection, takes place in SJ'IN at this instance.

There is an efficient and fast flow of information between any two of the SAM, AVSL and FOP.TPJ\N memory.

It will be helpful in understanding the organization of l'"·1PPL-II if we consifier . the diagram in Fi~ure 1.

INSEPT FIGURE Z:\BOTJT HERE

The main block is the Memory Matrix, which consists of E. SJIJ 11 1-words*, each having 2n bit positions . The re are four special \vords, the short registers, each n bits lana. (On the CDC 6400, there are n=60 bits . in a word.) T\<10 of these serve as Argument Reg isters 1 and 2. The other two represent Mask Registers 1 and 2. There are also three long registers, vertical columns r bits in length and 1 bit in width. Two -of these are called Response Reaister 1 and Response Register 2. The thi;.d one is the Availability Register . (The role of the words FIRST and LAST in Figure 1 is explained later).

In the following, we shall briefly describe some of the operations used in k~PPL-II and discuss only two, the 'Search and Flag' and 'Set Relation', in detail.

word *As ,.,i 11 be seen later, every SA.t"1consists of two actual memory words.

?!CURE 1

II. OPERJ\'l'IONS IN NIPPL-II

(1) Memory Allocation:

As mentioned above, the initial subdivision of free core into SN1 and .IWSL can be <.lynamically modified during the execution of the program. Instructions are available to count the number of currently available SAM and AVSL cells, and to accomplish the transfer of free cells from one memory category to the other. At these points, and also at the tine of mass input into SM~ (see below), Inemory contraction and garbage collection in SN-1 takes place.

(2) Input-Output:

11ass input-output is obtained w·hen FOH'fMil arrays or SLIP lists are read into SN·l, and when designated SAN-words are loaded into FOETRlJ.'l arrays or SLIP lists. Also, wholesale clearing operations can be executed between any two specified SN-1addresses. (A Sl'~"l-adoress can be conceived of as the index of a one­ dimensional array.)

Individual words can be transferred between any two of the SN1, SLIP and

FORTRAN memories. Designated parts of S.i'\'1 can be printed in different modes.

Full words or specified configurations can be put into Argument and Hask Registers , and contents of the latter can also be into the FORTRAN memory. bit the the read

(3) Operations Registers: Concerning the Response

To the AM''lPL programmer, SAH appears to contain information in a manner that permits certain basic processes, including reading and \'lriting, to be carried out simultaneously in particular cells. These designated cells contain responding pieces of information and were selected by a previous 'Search and Flag' operation or were deliberately flagged by a srecial flagging instruction. The 'Search and Flag' operations locate and mark SNI-words accora1ng to various criteria. Subsequent processes may then be performed on these again and the results can represent Boolean combinations, AND's, OR's and NOT's of

consecutive searches.

'I'hc basis of comparison is usually* put into one of the Arqument Registers. '1'he search is carried out only over those fields of SJI.'I-words that are marked by bits '1 ' in the relevant !.'\ask P.eg ister. The success of a search is indicated by flaqs (bits '1') at the level of the corresnona1nq SN1-word in the relevant Respon.se Register. Those Sl'.t·l- words that have not been used or are no longer necessary are denoted by a tag (bit '1') in the Availability Register.

Two points shoult! be J'T1entioned here. In order to speed un the search processes in SM~, one-directional pointers link f lag9eC. sr,'l- v;ords (see Figure 2) anci, also, end markers indicate the address~s of the SM1-words first and last flagged 1n the two Response Registers (the contents of the FORT!\JI.N variables FIPS'l' and Ll'.S'f on Fi<Jure 1).

Two other FO?'l'PAN variables, I'0INT1 and P0It.;T2 contain the SM'-addresses of the last SNt-\'.rord searchP-d, whether successfully or otherwise, with reference to P.esponse Reqister 1 and Response Register 2, ~espectively. (Cf. the possible values of the argument \~ll!CH of the subroutine SERF'LG.)

The actual form of the major instruction performing the above described processes is where regardless of previous status of the Response Register, AND-ed with flaas in the other Response Register, OR-ed with flags in the other Response Register, NOT-ed and left in the same Response Register;

*If, for example, those numbers are seard1ect for that are greater than a given one. However, if the criterion of search is, for example, 'maximum' , the Argument Registers are ignored.

a certain SAM-adclressed

\ITOrd,

the first SN-1-'1--'0rd,

the next-after-P¢INT word,

the last SJIJ.,-word,

all SAM-words,

any single SAM-word;

• { IARG 2 i.e. the number of Argument Register; the relevant
• { IHASK 2 i.e. the number of Mask Register; the relevant
• I RESP {: i.e. the number of Response Register. the relevant

A few words of comment are needed here. Two subsequent 'Search and Flag' operati?ns with CRITER=GTEQ and LTEQ yield respons~ve words of values between given limits. NEXTHI can be performed by two subsequent searches with criteria GTEQ and t-HN , similarly NEXTL0 is done with criteria LTEQ and MAX. The value of one of NEXTHI and NEXTL0, that is nearer to the value in t~e Argument Register, yields NEXT. The cr~teria BITSHI and BITSL0 are useful in comparing non-numerical data and selecting the "most similar" or "least similar" pieces of information respectively. The number of matching bit~ can be found as the values of special FORTRAN variables. GRP0FM finds for example, misprints caused ' by transposition, missing and added characters. The character set can be represented by groups of 2-8 bits. Since the matching process ignores the position of the groups being matched, there are extra facilities to identify transposition errors. Also, the number of the matching groups is accessible.

There are safeguards to prevent a SAM-word of the wrong information mode (e.g. floating point number instead of alphabetic information) from becoming respondent if its contents happens to be the right bit configuration. A detailed description of this is to be found in [22].

Finally, it should be noted that there exist instructions to flag and unflag specified SAM-words, to count the number of flagged SAM-words, and to put the SAM-addresses of flagged words in a FORTRAN array or a SLIP list.

(4) Operations Concerning the Availability Register:

As mentioned before, a bit 1 in Availability Register· indicates that corresponding SAH-word is free. We this mark a 'tag', as distinct from 'flag' in the Response Registers. the the call the

There are instructions which tag and untag SAM-words, count the number of available SJIJ1-words, and which put the SAM-addresses of tagged words in a FORTRAN array or a SLIP list.

(5) Inter-Register Operations:

All the 16 logical operations possible are executable between any two of the short (Argument and ~1ask) Registers or between any two of the long (Response and Availability) Registers. Here the operands are the bit strings occupying the respective registers.

(6) Processes Regarding Relations:

Besides the 'Search operation, these processes significant in AMPPL-II. therefore, discuss them, and Flag' are the most lve shall, also, in some

detail.

Let us generalize the concept of an algebraic function and define a Relation (REL) between an Object (0BJ) and a Value (VAL)

Each of the above three entities can be single items or three kinds of lists. The first kind simply contains various equivalent names of the same item. (One can think of synonyms within the given context.) This is called the EQUIVALENT LIST . The second kind of list bears the names of a number of subunits any processing on which is always uniform. An example of these lists may he the students of a class, who always have the same teRcher, always stay in the same classroom, etc. Distinguishing ,processes, such as grading of individua l exams , are not to be carried out on the elements of so designated lists. Finally, the third kind of list has distinct and, in some respect, independent elements. An example of this could be the pieces of furniture in a certain room if one would like to, say, paint them to different colors.

Also, the programmer can define a Relation as an ordered set of other Relations. The combining connectives are:

· (concatenated), -(reverse).

Let us further def ine a reserved symbol SELF in orde r to be able to exc lude self-referencing in unwanted cases. Finally, the term on the left hand side of a 'concatenated ' s ymbol is considered to be in (Teutonic) genitive. The following examples should make this clear:

i.e. a parent is defined a father or mother;

i.e. the child is defined as the reverse of the parent;

i.e. the grandfather is defined as the father's or mother's father;

i.e. the husband is defined as a spouse but (and) not wife;

• (v) BROTHER=:>( (MOTHER/\FATHER)+ SON/\....,S.8LF

i. e . the brother is defined as the mother's and father's son but (and) not self; if we wish to include half-brothers as well, we can put

BROTHER=*< (i'!OTHER V FATHER) + SON) A -,SELF

i.e. the mother's or father's son but (and) not self.

As the system reads in these definitions from cards, it checks them in toto for circularity, which it does not accept, and puts them in a Polish prefix form on DEFINITION LISTs. The latter are sublists of the EQUIVALENT LISTs and therefore sub-sublists of the SLIP list C¢DEL. (See Figure 2). On the

INSERT FIGURE 2 ABOUT HERE

C¢DEL list, the members are either entity (Relation, Object, Value) names, each less than 11 characters long, or the names of the three kinds of sublists mentioned before. The machine address of an item on the C¢DEL list is called its Code Number. \'lhenever a new Relation is defined by the subroutine

SETREL (REL,¢BJ,VAL,K), the system sets up one (or more) Relation Descriptor word(s) in SAM, which contain(s), in the proper fields, the three code numbers representing the Relation, the Object and the Value. (See Figure 3). ~is an integer between 0 and

INSERT FIGURE 3 ABOUT HERE

7, and characterizes each of the three entities whether they represent a single item or non-distinct elements of a list, on one hand, or distinct elements of a list, on the other. In the latter case, as many Relation Descriptor words are established as the total number of combinations possible.

There are altogether seven basic questions a retrieval system for Relations can answer. These are as follows:

• (a) Is a particular relation, between a given object and value, true?
• (b) What is (are) the value(s) belonging to a given relation-object pair, if any ? REL (¢BJ)=?
• (c) What i s (are) the object(s) belonging to a given relation-value pair, if any? REL (?)=VAL
• (d) I<Jhat is (are ) the relation (s) that connect(s) a given object-value pair, if any? ?(0BJ)=VAL
• (e) belong (s) ?(?)=VAL What relation-object pair( s) to a given value, if any?
• (f) belong(s) ?(¢BJ)=? What relation-value pair(s) to a given object, if any?
• (g) Finally, what object-value pair(s) belong(s) to a given relation, if any? REL(?)=?

The answers are obtainable by using one simple instruction in every case.

Finally, instructions of of them creates we note t'l-m considerable power. more One

REL2(VAL) = ¢BJ

where the Object and Value are connected by

REL1 (y>!BJ) = VAL

REVREL (R.CL 1) = REL2

i.e. REL1 and REL2 are Reversed Relations. Examples of this are:

Note that always

REVREL(R~VREL(REL1)) = REL1

Another instruction finds ~. for which it is true that

A : B = C : X

where A, B, and C are any of the three entities,- RelatTon, Object, or Value; A, and C, on one hand, and B and X, on the other, are of the same type, and the third entity in the Relation Descriptor words containinq A, B and c, X is the same for both. ·(occurrences -of all possible combinations of A and B are considered.) Two examples should make this clear:

and An Exemplary Segment of the C0DEL List and Its Sublists

1 2 3 4 5 6

SN1-word as Relation Descriptor FIGURE 3

• (a) Suppose in Sam , we have Re lation Des criptor words standing f or

HO'ri!ER TONGUE OF (JEANNE ) FRI:NCH

I · MOTHER TOUGUE OF (JOSE) SPANISH

A B JEANNE , FRENCH,

c JOSE

the resulting X will be SPANISH since Jeanne's relation-to French is the same as that of Jos~'s to Spanish -- these are the mother tongues of the people in question.

(b) Let Sk~ now contain

UNCLES OF (JACK)

JOE, BILL, PETER

AUNTS OF (JACK) MARY, CARON

If

If A UNCLES OF B JOE, BILL, PETER C AUNTS OF

the resulting X will be the list 'VIi th HARY 1 CARON since JOE 1 BILL, PETER are the uncles of the same person whose aunts are HARY, CARON

(7) Parallel Operations over SAH:

Here, we briefly list some basic but high-level instructions that should be useful both in numerical and non-numerical applications:

A constant word in one of the Argument Registers can be added to, subtracted from, multiplied by, divided into, Boolean AND-ed and OR-ed with designated SAM-words through one of the ~1ask Registers.

The above operations can also be perforr.1ed between any two fields, and the Boolean NOT of any single field, of designated SN1-words.

Specified fields of designated SN1words can be cleared.

Designated SAM-words can be shifted to the left or to the right by specified number of places.

Single elements, vectors, planes, cofactors or all elements of an array can be flagged if the array >·Tas read into SAM according to the usual mapping order.

Vector addition, subtraction and scalar multiplication are single instructions.

Also, s ingle instructions yield the de terminant and the inverse of one, and the product of two, matrices.

III. AN OVERVIElv

We have tried to give a short outline of a new computer language. 'VJe, however, feel it is more than "just another language" it represents another philosophy of, another approach to, problem solving. After all, it is only the sequential design of the von Neumann­ type machines that has imposed upon the computing co~~unity the presently prevalent but often quite unnatural computational methods. Even using these conventional methods, N~PPL-II (a) should decrease the length of written programs and (b) should simplify the writing, debugging and understanding of programs. (It has very powerful diagnostic facilities.) There is, however, a significant trend, as can be seen in the referenced literature, to develop new algorithms and techniques that make use of content addressability and parallel processing, expose latent parallelism, and introduce computational redundancy. \.;'e hope AMPPL-II "VTill enhance this trend.

'VJe have had only limited programming experience with the language. The following, as yet incomplete, projects are representative examples:

1. a query system, which can be continually updated, dealing with complex kinship structures;
2. simulation of a learning and self-adapting organism in a hostile environment;
3. empirical proofs of conjectures in computational linguistics;
4. simulation of a demographical problem; and
5. scheduling classrooms, teachers and students.

We have found that, although one must pay a certain price in machine time and available memory, the programming ease achieved is quite significant. (The disk resident system consists of roughly 8k words for each SLIP and 1\MPPL-II. Only the needed subprograms are called into core.) In the INTRODUCTION, we listed a number of broad areas of application in whi ch AHPPL-II should prove useful. NOt,.l we can be more specific in terms of problem characteristics. We expect to save considerable programming effort in using the language whenever

• (i) data are to be addressed by a combination of various sets of reference properties,
• (ii) data above reference throughout the random manner, elements properties memory in satisfying the are scattered a sparse and
• (iii) data elements dynamically change their location in the memory as a consequence of the information processes acting on them,
• (iv) identical sequences of processes manipulate on distinct, non-interacting data elements,
• (v) the ratio between concurrently and serially executable processes is reasonably high.

These criteria of language applicability occur to some extent with practically every complex programming problem. The availability of a conventional algebraic language with the 1\MMPL-curn-SLIP package renders programming more efficient. ·

~1e intend to study in a later paper the numerous issues involved in using N1HPL-II in various fields. Here, we only wish to point to the fact that the proposed system, to an extent, is capable of simulating two distinct kinds of associative memory. In the exact associative memory, the informat1.on processes are performed on the basis of finding the intersection of several matching descriptors. Because of the non­ uniqueness of many associations and, also, because retrieval · requests may be incomplete, there can be several respondent pieces of information. However, ill-formulated and imprecise tasks cannot, in general, be solved, and there is no logical "interpolation" or "extrapolation".

On the other hand, in a non-exact associative memory these restrict1.ons do not apply. Associations connect statistically related entities, too. The measure · of "nearness" is an important concept. Various counting processes, the criteria of search for the most and least similar items (BITSI!I and BITSL¢) and matching groups of bits (GRP¢FM) represent steps in this direction. Biological systems, of course, incorporate both of the above described associative memories.