ASSOCIATIVE COMPUTING ERRATA
The following comments are in reference to the discussion of ASC
in ASSOCIATIVE COMPUTING (Plenum Publishing, 1992).
1) MEMORY ALLOCATION
The ASC memory allocation scheme has been modified slightly
to better support the simulation of an associative SIMD machine on
a PC. In particular, array memory addresses are allocated when the
variables are declared. There are only local busy/idle flags. One
for each association. There is no global allocation. Reads and
allocates update the local bi only. Initially, the scope is set
to all TRUE.
NOTE: If a program takes a very long time to execute, it may
be due to a non-restricted scope. For example,
read aa[$] bb[$] in dd[$];
cc[$] = aa[$] + bb[$];
Since read does not set scope, all aa's and bb's in the parallel
memory are being added, not just the ones read in. Using
read aa[$] bb[$] in dd[$];
setscope dd[$]
cc[$] = aa[$] + bb[$];
endsetscope;
will resolve the problem.
A diagram of memory allocation follows. Given data:
1 2
3 4
5 6
7 8
9 10
and the program:
int parallel aa[$], b[$], c[$], d[$], e[$];
logical parallel bi1[$], bi2[$];
associate aa[$], b[$], c[$] with bi1[$];
associate d[$], e[$] with bi2[$];
read aa[$] b[$] in bi1[$];
read d[$] e[$] in bi2[$];
allocate xx in bi1[$];
c[xx] = 11;
endallocate xx;
the array memory will contain
aa[$] b[$] c[$] d[$] e[$] bi1[$] bi2[$] scope
---------------------------------------- ---
| 1 | 2 | | | | 1 | 0 | |1|
| 3 | 4 | | | | 1 | 0 | |1|
| | | | 5 | 6 | 0 | 1 | |1|
| | | | 7 | 8 | 0 | 1 | |1|
| | | | 9 | 10 | 0 | 1 | |1|
| | | 11 | | | 1 | 0 | |1|
| | | | | | 0 | 0 | |1|
---------------------------------------- ---
In order to use defvar for arrays, it is necessary to
understand how multidimensional arrays are allocated. When arrays
are allocated, say aa[$,5], the base address of the array is the
address of the array at aa[$,0]. But arrays are allocated from
left to right (lower addresses to higher). When defvaring to
fields, it is necessary to determine their alignment in terms of
their base address. The defvars given in Figure 5-27 on page 144
will not work for this implementation. The diagram below shows the
alignments and gives the proper defvars.
defvar (rittok, tokchr+40);
defvar (leftok, tokchr+32);
int parallel tokchr:8[$,6], rittok:40[$], leftok:40[$];
-------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 |
-------------------------------------
^ ^ ^
tokchr base +32 +40
-------------------------------
| |
-------------------------------
^
rittok base
-------------------------------
| |
-------------------------------
^
leftok base
This case is complicated by the fact that rittok and leftok are
smaller than the equivalenced field for arrays equivalenced to full
fields, define the array in terms of the field, thus
defvar(exbits, expon);
card parallel expon:7[$], exbits:1[$,7];
See Suites58,58a and 70 (Suites 14, 52, 56, 64 and suiteio also
have defvars).
2) COMPARISON OF CHARACTERS
Character variables default to a size of 8 bits. Thus in
Figure 4-2, the declaration should be
char parallel county:48[$];
When scalar character variables and parallel character
variables are to be compared, they must be of the same size. But
laterals default to the size of the string, so an intermediary
scalar must be used if the parallel variable is not the same size
as the string. Thus in Figure 5-18(See suite59), the proper code
is:
char parallel dsid[$], atom:32[$];
char scalar acary:32;
acary = "A";
get xx in dsid[$] .eq. "a" .and. atom[$] .eq. acary
Mixed compares (i.e. scalar with parallel) are limited to 48 bits.
3) NOT IMPLEMENTED
A number of items mentioned in the book are not implemented
in this release of the emulator. They are:
3.1 The exit statements.
3.2 Data structure insertion operator (p.130). However, insertion
can be implemented by the user using the code in Figure 5-18.
3.3
The nxtdex and prvdex functions. However, the sibdex function
may be used to calculate these functions as illustrated in
Suite56.
3.4 The scst functions (p. 141). Instead, the templates must be
read in from a data file.
3.5 The .cmp. function (p. 177,178 and Figure 7-7).
3.6 The AND constructs (Chapter 7).
3.7 The scsize function. However, scin8 calculates the structure
code sizes automatically and stores them in the right hand
field of a 8 character structure code field. See below:
0 1 2 3 4 5 6 7
---------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | |size
---------------------------------
Suite60 gives an algorithm which can be used for the 4 bit
scin structure code fields.
4) CORRECTIONS TO FIGURES
4.1 Since the figures were generated, two changes have impacted
many of the figures. "A" and "sum" are now reserved words.
Therefore, in all figures which include ASC code, variable
names "a" and "sum" should be changed to "aa" and "summ."
Figures 3-10, 3-11, 3-12 are examples.
4.2 Figure 3-3, p. 75. "index scalar" is not a valid variable
type.
4.3 Figure 3-12, p. 81. The modified figure reflects that "a" and
"sum" are reserved words, and the fact that the "if" statement
is a parallel if and that the else portion is therefore
executed causing aa[xx] value to be set to 21.
Items Items
aa[$] b[$] c[$] aa[$] b[$] c[$]
--------------- ---------------
| 1 | 17 | 0 | | 1 | 17 | 0 |
| 2 | 13 | 0 | | 13 | 13 | 0 |
Before | 2 | 8 | 1 | After | 21 | 8 | 1 |
| 3 | 11 | 1 | | 3 | 11 | 1 |
| 2 | 9 | 0 | | 5 | 9 | 0 |
| 4 | 67 | 0 | | 4 | 67 | 0 |
--------------- ---------------
summ = 0 summ = 21
summ = 0;
while xx in aa[$] .eq. 2 summ = summ + b[xx];
if c[xx] .eq. 1 .and. aa[$] .eq. 2 then
aa[$] = 5;
else
aa[xx] = summ;
endif;
endwhile xx;
4.4 Figure 3-13. p. 82. The line of code with the count function
should be:
i = count(them[$]) + i;
and the i result should be 6 not 5.
4.5 Figure 3-20. p. 86. The first line should be:
if w[$] .eq. 2 .and. q[$] then
4.6 Figure 3-25. p. 88. The constant specifications are shown as
'x'hex_number, 'o'oct_number and 'b'bin_number.
They should be shown as
X'hex_number', O'oct_number' and B'bin_number'.
See suite57.
4.7 Figure 3-28. p. 90. The last line of code should be:
if their size[$] .ne. 15 then
See suite55.
4.8 Figure 3-29. p. 90. The last "for statement" should be:
for each in a[$] .gt. 5
4.9 Figure 3-33. p. 93. The keyword "readnl" should be "readln."
4.10 Figure 4-1, p. 102. Uses floating point.
4.11 Figure 4-2, p. 103. See Memory Allocation above.
4.12 Figure 4-6, p. 125.
4.12.1 i should run from -1 to 1, not 1 to -1.
4.12.2 Must include out[$] on the right hand side of the
assignment in the lines marked "b". See suite63.
out[$,j] = out[$,j] + weights[xx,0]*inn[$+i,j-1] +
weights[xx,1]*inn[$+i, j] +
weights[xx,2]*inn[$+i,j+1];
4.12.3 xx[$] is not declared.
4.12.4 See the convolve.asc file for a working example.
4.13 Figure 4-10, p. 110. variable "globalbi" should be defined
as follows:
logical parallel globalbi[$];
4.14 Figure 4-11, p. 112. The node on the far right of the figure
labeled 11, should have a "+" (addition) symbol in it, not a
"*" (multiplication) symbol.
4.15 Figure 4-13, p. 113. The values in the "dest" fields should
be:
dest dest
flda fldb
1 2
0 3
0 4
0 5
0 6
4 7
3 0
8 0
6 0
9 0
0 9
0 8
10 10
0 0
This reflects the fact that array indices start at 0, and that
0 is used as the "no entry" marker. Accordingly, the values
in the fields had to be incremented by one which is then
subtracted during the distribution code in Figure 4-16, p.
115. 15. Figure 4-14, p. 114. The lines marked "a" should
be:
while zz in (flaga[$] .and. .not. consa[$]) .or.
(flagb[$] .and. .not. consb[$])
4.16 Figure 4-16, p. 115. The figure should be:
/* distribute results */
for xx in yy[$]
if desta[xx] .gt. 0 then
setscope mask[$,desta[xx]-1]
fielda[$] = fieldc[xx];
flaga[$] = 1;
flagc[$] = 0;
endsetscope;
endif;
if destb[xx] .gt. 0 then
setscope mask[$,destb[xx]-1]
fieldb[$] = fieldc[xx];
flagb[$] = 1;
flagc[$] = 0;
endsetscope;
endif;
endfor xx;
4.17 Figure 4-23, p. 122. Lines 6 and 7 of Figure 4-23 should be
switched.
4.18 Figure 5-18, p.137.
until j .ge. delta
should be
until j .ge. scsize[$]
4.19 Figure 6-17, p. 171.
4.19.1 The "stack" statement approximately in the middle
of the figure should read:
stack xx[$] yy[$] zz[$] pats[$] then
qq[$] = zz[$];
endstack;
4.19.2 The variable "att_value" should be "variable_va"
from Figure 6-14, p. 169.
4.19.3 In the three logical parallel expressions lines
labeled with "a" "c" and "d" should include
"rule_id[$]" in addition to "pattern_id[$].
4.19.4 The fourth line from the bottom should be removed.
4.19.5 The answer of the engine is in "result[$]."
4.20 Figure 7-7, p. 179. the comparisons should be:
tsta[$] .cmp(cmpa[$]). a .and.
tstb[$] .cmp(cmpb[$]). b .and.
tstc[$] .cmp(cmpc[$]). c
(This feature has not yet been implemented.)
5) I/O STATEMENTS - See suiteio and Section 8.2
5.1 The open statement shown in Figure 4-6, must use a double
assignment, i.e.
handle[0],handle[1] = open(...);
However, only handle[0] is used in the read, print or message.
See suiteio.asc.
5.2 A message statement may have an optional handle, i.e.
msg (handle[0]) "This is legal";
5.3 Scin8 now includes a line number field. That is the line
number of the atoms is calculated at run time and is stored
in the specified field. i.e.
scin8(atom[$], sc[$], bi[$], linenum[$]);
5.4 The "contiguously" function is not implemented. The read
statement will automatically use contiguous rows, provided
there have been no "releases," so normally, contiguously is
not needed.
5.5 When you open a file, a *.OT file is also opened. All output
is written to the *.OT file. When the file is closed, if the
*.OT file has been written to, the input file is switched to
*.bak and the *.OT file is switched to the original input
file. THEREFORE, if you output to a file, what ever was in
the original file will be lost upon closing (actually saved
in *.bak, but if the program is executed more than once, the
previous *.bak will be overwritten).
To APPEND to a file,
open the file,
read the file,
output the file,
then output the new (append) data.
6) APPENDIX
6.1 "Sum" should be added to the list of reserved words.
6.2 The "equal" relational operator is "==" not "=".
7) TYPOs
7.1 First line on p. 123, "MMP" should be "MPP."
7.2 Bottom of p. 7, feature 1 should read:
"massively parallel searching achieved by shared active
memory logic referred to as PEs, so that searching can
be used as an alternative to addressing."
7.3 The "and" in the third sentence from the bottom is the and
construct and should be in bold type.
7.4 The reference to Fig. 5-1 in the middle of the page should be
removed.
7.5 There is a line missing between the bottom of p. 80 and the
beginning of p. 81. The sentence that begins at the bottom
should read: "These are of two types and they are placed in
the loop where the exit is desired." Figure 3-13 shows the
format of a loop statement and an example.4.
8) NEW ASC FEATURES
8.1 Double assignment. The PC version of ASC is based on 16 bit
words. Certain basic operations such as Open require 32 bit
data. In ASC, two 16 bits words can be assigned with a single
statement to accomplish this. See 5.1 above.
8.2 I/O statements. The "standard" read and print I/O statements
have been augmented with two new statements (input and
output), and some new options.
8.2.1 OUTPUT - similar to print, but i) emulator only, ii)
without a header, and iii) uses dump - i.e. It does
not use the IOSTACK and therefore is faster. The
print command generates a header. If the output data
is to be read back in, the header gets in the way.
See Suite 67 and 68. An example:
output aa[$] bb[$] in bi[$];
Output treats commas differently than other io
statements. If commas (spaces) are used in the
statement to seperate variables, then commas (spaces)
are used to seperate the values in the output.
For example, if dump1 contains 1, dump2 contains 2
and dump3 contains 3, then:
output "Dump1,2,3=" dump1, dump2 dump3;
will produce
Dump1,2,3= 1, 2 3
8.2.2 SORTED BY - The output "sorted by" option produces
output sorted by a specified expression. Normally
the data is output in the random internal order.
The ordering is numerical from lowest to highest.
A char field can be used, but the ordering will
still be numeric on the char field. The syntax
allows the "sorted by" option to be an expression.
See Suite 67. An example is:
output aa[$] bb[$] in bi[$] sorted by cc[$]*dd[$];
8.2.3 INPUT - similar to read, but i) emulator only, ii)
without a header, and iii) uses dimp - i.e. It does
not use the IOSTACK and therefore is faster. INPUT
has two forms. The first form
input aa[$] bb[$] in bi[$];
is parallel, the second form
input xx yy;
is scalar (suite68). You can not mix scalar and
parallel in one statement. But files with mixed
parallel and scalar sections can be read by the
appropriate sequence of parallel and scalar INPUT
statements. However, if the statements are "out of
sequence" the results are unpredictable.
You can use the scalar version to control execution,
i.e.
msg "Press enter to continue.";
input ans;
8.2.4 LEXICON options - input can be used with a lexicon,
see the USING option in "Noun phrases" below. See
suites 67 and 68.
8.2.5 IN SILENCE. NOT IMPLEMENTED - The read "in silence"
option prevents read from requesting data (similar
to INPUT above). When a READ is executed, a request
for data is sent to the standard i/o device (i.e.
the terminal). This can become annoying. The "in
silence" option prevents the request from being
generated. An example statement is:
read aa[$] bb[$] cc[$] in bi[$] in silence;
8.3 Noun phrases. Noun phrases are in the development phase
(See suite68). Noun phrases require a lexicon. The lexicon
is an inverted list of the values in the fields (i.e. the
values in the lexicon specified what field they are in). Thus
to use:
if THE BIG OLD OBJECT then ....
The adjectives in the noun phrase are compiled into a search
of the lexicon for the field that contains them. It is then
searched for the adjective. The _adj intermediate code does
this. The lexicon can be specified in two ways. It can be
pre-generated and input directly, or it can be generated when
the values are read in using a "input .. using ..." statement.
For example, in
input size[$] age[$] object[$] in text[$] using lex[$];
lex[$] is for the pre_generated option which is not yet
implemented. For now lex[$] is a dummy field, the fields
needed for the second option are generated internally. The
last word in a noun phrase is the noun. The noun is a field
name. The "with" form is for a pre-define lexicon. It has
not been implemented yet. Also need a way of saving the
current lexicon.
8.4 Formatted variables (emulator version). The output statements
automatically determines the size of the fields of the
variables. This can lead to "jagged" tables. Formatting
information can be added to a variable definition to override
the automatic formatting. The formatting information is in
standard C form, it is quoted and immediately follows the
variable definition. See suite67. For example:
int parallel second[$] "%6d", third[$] "%5.2f";
The format is output only, input is always free format.
8.5 Date data conversion. Two new scalar functions, encode and
decode have been added. Encode converts an integer field into
an ASCII charter field. If the field is longer than a word
(currently 16 bits), it converts it in word size chunks. Thus
00e50001001d will be partitioned into 00e5 0001 001d and
converted into 3934 3031 3239. An integer is assume to be
right adjusted and the char field is left adjusted. Note that
if a date consists of a year field (16 bits), a month field
(16 bits), and a day field (16 bits), then e5(hex) is
converted into "94", 1(hex) is converted into "01", and
id(hex) is converted into "29". If year, month and day are
equivalenced to h_date, and date contains 00e50001001d, then
c_date = encode(h_date);
will produce "940129" in c_date. Decode is the inverse
transformation. See suite62. That is,
h_date = decode(c_date);
will convert "940129" in c_date into "00e50001001d" in h_date.
If hport is a 64 bit hex parallel variable and date_n is a 64
bit char scalar variable, then you can write:
date_n = encode(hport[xx]);
and
if decode(date_n) .eq. hport[$] then
8.6 The Release statement. When memory is no longer needed, it can
be returned to idle memory by using the release statement as
shown below:
release xx[$] from bi[$];
9) Misc.
9.1 Anonymous index variable - the pronoun "each" can be used as
an anonymous index variable in conjunction with the other
pronouns. For example (suite55),
for each value[$] .gt. 5
if its size .gt. 17 then
...
else
...
endif;
endfor each;
"Each" does not need to be declared. If several nested
statements are used, conventional index variables are normally
easier to understand.
9.2 Sum function. In addition to a count() function which counts
the number of responders in a logical field, the sum()
function will sum the values of all active responders in a
field.
9.3 The exp and sqrt functions have been added (suite61). Both
functions take integer and real arguments. Parallel and
scalar variables may be used. They return real values. For
example:
int parallel arg1[$];
real parallel resa[$], arg2[$];
resa[$]=sqrt(arg1[$]);
resa[$]=sqrt(arg2[$]);
resa[$]=exp(arg1[$]);
resa[$]=exp(arg2[$]);
9.4 The expotentiation operator ** has been added (suite61). It
accepts integer and real operands. It converts integers to
reals and the result is always a real. For example (given
above declarations):
resa[$] = arg1[$]**arg2[$];
9.5 Two trig functions have been added - sine and cosine. The
syntax is sin(aa[$]) and cos(aa[$]). See suite61.
9.6 Suite62 illustrates subroutine calls.
9.7 Suite64 illustrates char to integer conversions.
9.8 Mindex, maxdex, nthdex, minval, maxval and nthval are in
suite57.
9.9 Stackwhile is in suites 65 and 66.
9.10 The modulo operator % has been added, i.e. 5%3=2
9.11 The c based pseudo-random number generator, rand, has been
added. It is reseeded by the time of day on every startup.
It is a scalar integer function, thus
num = rand() % 24;
will produce a random number between 0 and 23.