FLATS, A MACHINE FOR NUMERICAL, SYMBOLIC AND ASSOCIATIVE COMPUTING

1. Introduction

Numerical computation and symbolic formula mani­ pulation are the major practices in scientific computation. While numerical computation has a long history, computer-aided algebra or large scale formula manipulation has become practical only recently.

In this paper, we describe the architecture of FLATS, a machine which aims to efficiently run scientific computations. We consider Fortran (F) and Lisp (L) as major scientific programming languages for reasons:

• (i) Scientific numerical programs are written mostly in Fortran.
• (ii) Lisp is the major host language used for symbolic and algebraic systems such as REDUCE 1 and MACSYMA2. Moreover, Lisp has been used for writing a very large number
• of programs in the AI area.

Hence, high efficiency in running programs writ­ ten in 'F' and 'L' is considered a minimum re­ quirement, which is symbolized in the first two letters of 'FLATS'. 'A' in FLATS stands for associative capabilities; 'T' and 'S' stand for Table, Set and String which are the data types

used in FLATS.

Many efforts have been made to increase the speed of computations by introducing parallelism3· 4 ·5, in which we include the pipe line architecture as a specific implementation (of parallelism). Vectorized operations on floating and fixed point numbers of fixed bit length are recognized as a class computations suited for highly paral­ lel machines. It should be noted, however, that highly parallel algorithms are not known for or not applicable to certain computations. For example, take the Euclidian gcd algorithm. The gcd of two integers r 0 and r1, say, is obtained by successively computing the remainder sequence ro, r1, r2, r3 ·.· (ri is the remainder of ri_ 2

divided by ri-l) until it reaches the first zero

remainder rn z 0 with rn-l giving the gcd.

Parallel schemes faster than the Euchidian al­ gorithm are not known. Hence, for gcd, a ma­ chine equipped with a single sophisticated high speed remainder unit would do better than paral­ lel machines with hundreds of slower units. List processing, arbitrary precision integer arith­ meter, and variable precision floating point arithmetic are other examples of operations which are not suited for contemporary highly parallel machines. The objective of FLATS is to ef­ ficiently run those operations which are not suited for highly parallel machines.

FLATS is basically a single instruction stream machine and parallelism shall be pursued only to a limited extent such as advance control, paral­ lel hashing and parallel interpolation but it shall not incorporate parallel processor arrays .

FLATS may hence be regarded complementary to the highly parallel machine approach.

The numerical support to algebraic manipulation systems is indispensable since the process of al­ gebraic manipulation requ:l.res exact calculation of intermediate (and final) numerical coef­ ficients as opposed to approximations done by conventional fixed precision floating arithmetic.

Fur thermore, the results of the algebraic compu­ tat ion must often be given to numerical compu­ taion systems.

Func tional requirement for FLATS is therefore to incorporate the different characteristics of the two languages (F and L), e.g. compile-time vs. run- time data type checks, and static vs. dynamic storage allocation, into a single architecture, without impairing the efficiency of either one.

Bes ides the advanced numerical features, associ­ ative caEabilities have been found to be very powerful in efficiently carrying out basic opera­ tions in formula manipulation.

We first give in section 2 functional specifica­ tions of FLATS from users' point of view, and in sect ion 3 consider the implementation from archi­ tectural point of view.

2. FLATS from users' point of view

2.1 Overflow free and variable precision computing

We observe that most contemporary computer sys­ tems neither provide adequate means for handling (1) overflows, (2) precision higher than built­ in standard precisions, e.g. double or quadruple, nor (3) variable precision arithmetic. The de­ sign and implementations of some important class of algorithms 7·8·9 are hampered by the lack of the systematic support of these three features.

To remedy such defects, FLATS is provided with following means:

• Integers are treated with automatic multiple­ precision.
• Exponents and mantissas -of floating numbers are expressed in integers as stated above, hence practically no overflow would occur.
• A variable precision scheme 10 is adopted, in which precision is specified by a status word called an ASW (Arithmetic Status Word), which is part of the PSW (Program Status Word).

These features are made available to users in an extended FORTRAN called BFORT (Bignum Fortran).

2.2 Tabulative computing

Before high speed computers came into extensive use, look-up of mathematical tables was an es­ sential process of numerical calculation. This fact is in quite contrast to 'on-demand' comput­ ing prevalent today. To pursue further the speed-up of the present numerical computation, table look-up is becoming again a practical method, owing to the recent advances in memory fabrica tion technology. In FLATS, we provide following means for tabulative computing 11 ;

• (i) Tabulative computation of numerical func­ tions with a floating number argument such -1 r- X as x , ·x, e , sin x, log x and atan x.
• (ii) Associative tabulation for (sparse) integer and/or symbolic arguments.

Linear (or quadratic) interpolation shall be used for 24 bit (single length) mantissa and cubic interpolation for 48 bit (double length) man­ tissa. Namely f(x) is to be computed by f(x) ~ f(x 0 ) + f'(x 0 )6x + (l/2)f''(x0)6x 2 + (l/6)f''' (x0)6x3 where x = x0 + 6x and xo is the most significant 12 bit part of the 48 bit mantissa x and each term is assumed to be less than the

-12 previous term by a factor of 2 The coefficients f, f', f'' and f''' are tabulated (in ROM or RAM). This cubic interpolation can be made within time of two stages of multiplications by introducing parallelism:

Stage 1. Read the coefficient table and the table of cubes of the 12 bit (in precision) 6x3 and compute the 24 bit 6x 2 in parallel. (Table look up is assumed to be no slower than multi­ plication.)

Stage 2. Multiply and add in parallel.

-1 For computing the 48 bit inverse y · x , this scheme is faster than Newton iteration, which would consist of five stages of successive operations:

Stage 1. Read the 12 bit approximate inverse -1 Yo = x from table.

Stage 2,3. Two multiplications to get the 24 bit inverse Yl = (2-xyo)Yo·

Stage 4,5. Two multiplications to get the full 48 bit inverse y = (2-xyl)Yl·

When a function, say g with (sparse) integer or symbolic arguments, is computed in tabulation mode, the value v = g(i 1 , ... ,in) is tabulated

in a content addressed table (CAT), using the tuple (g, i 1 , ··· ,in) as a search key in the CAT. In the subsequent computations of g with the same values of the arguments, the value v is fetched immediately from the CAT. Associative tabulation effectively and automatically speeds up recursions by avoiding repetitive computation. For example, the notoriously slow (exponential time) recursive computation of the Fibonacci numbers:

procedure Fib[n] = [n<l -> 1;

T -> Fib[n-1] + Fib[n-2] ] is turned into a fast algorithm (linear time for the first evaluation and 0(1) time for the sub­ sequent evaluations).

2.3 Associative capabilities and built-in data types

Starting from the pioneering associative language LEAP12, a variety of associative language and architectures for the associative processing have been proposed and implemented.

We consider an AMT (Address mapping table) and an h-op hash table (Fig. 1) as the two basic entities for building associative data struc­ turesl3. We define an AMT as a mapping from bit patterns of fixed sizes (actually 32 bits/64 bits) into addresses (consecutive integers). An AMT may be regarded as a single-hit associative memory. A multi-hit associative scheme such as found in LEAP is to be dealt with by software, making use of arrays, linked-lists and AMT's. Table 1 gives the built-in data types in FLATS. The data types STR, INT, FLOAT, VECT (one di­ mensional array) are the same as in most other languages except that INT and FLOAT are of ar­ bitrarily high precision as stated in 2.1. PAIR is the same as in Standard Lisp14 .

The data types prefixed by H denote those types obtained by hashing (h-op). h-type objects are guaranteed to be unique by virtue of hashing. The Lisp concept of 'intern' corresponds to that of h-op with the following differences; that h-op does not allow remobl5 and that h-op can apply to all data types in FLATS, whereas intern op in Lisp 1.5 is applicable only to atomic symbols. h-type objects musL be read-only so as for the hashing search mechanism to work properly. Hence, HSTR objects are the same as atoms of Lisp; i.e. every different string of characters is represented as a unique pointer to a table called oblist in Lisp 1.5, or to name tables in assemblers and compilers. HINT and HPAIR objects are multi-precision integers and hashed lists, respectively. Equality check of two long integers of type HINT or two lists of type HPAIR is reduced to that of two pointers. HPAIR and HINT can be made by the shared linked list method as shown in Fig. 1.

Insertion, deletion and membership test of an AMT entry correspond to the same operations on a set. A 'set' created by h-op (represented by an AMT) is given6· 16 and shown in Fig. 1. In FLATS the hashed AMT (HAMT) is a synonym to 'set'.

A CAT consists of an AMT and RAM (random access memory, i.e. hardware term for VECT sharing the same addresses). A CAT can be hashed similarly to an AMT and the resultant data type is called HCAT.

These data types, especially the hashed types, have been found to be very useful· in polynomial manipulation. For example, take a polynomial P c 3AX2 + 4BY3, where AX2 and BY 3 are term identifiers; and 3 and 4 are coefficients. There are many (non-unique) ways to represent a term identifier in list forms owing to the commutative nature of multiplication. AX 2 , for example, is represented in a list form ((A 1) (X 2)) and ((X 2) (A 1)) corresponding to AX 2 and x2A respectively. The HCAT representation {A:l, X:2} is unique (AX2 and X2A are represent ed by a pointer to a unique HCAT structure). In this case, P is represented uniquely by nested HCAT's as

P · {{A:l,X:2}:3, {B:l,Y:3}:4}.

A FLATS FORTRAN program for multiplying poly­ nomials in the HCAT normal form can be written in 9 lines:

FUNCTION CATMULT (P,Q) C = MKCAT(O) SWEEP 1, P, TP=KEY, FP=VAL SWEEP 1, Q, TQ=KEY, FQ=VAL T = H(CATADD(TP, TQ)) C(T) = C(T) + FP*FQ CATMULT = H(C) RETURN END

Here SWEEP is similar to DO in FORTRAN; SWEEP scans all the occurrences of keys in the speci­ fied GAT's P and Q. Function H corresponds to h-op above mentioned. This program would give the best known time complexity for multiplying multi-variate polynomials6.

3. FLATS from architects' point of view

3.1 Tagged architecture

A practical solution for efficient detection of the built-in data types given in 2.3 is a tagged architecture!0· 17 Table 2 gives tags to be used in FLATS.

Take numerical computation for example. Arith­ metic operations on small numbers tagged as "sint" (short integer) or "afloat" (short float­ ing number) are to be made with standard hardware at high speed, while those on tagged "big" num­ bers are to be trapped and handled by micro­ programming. Since "sint" or "afloat" numbers are likely to appear with high probability in most programs, the slow down factor due to the "big" numbers is very small.

Bit-loss, a common objection against tagbit(s), can be remedied by using a specific exponent value as a 'trapping tag'. In the case of 7-bit exponent -64 ~ p ~ 63 FLOAT representation, p · -64, +63, +62 are used as the tags to denote data types-other than "sfloat" with the mantissa part having different meanings given in table 2. The effective bit loss is only log2(123/128) · -0.06 bits in this scheme.

3.2 Hashing Hardware

AMT's can be implemented either by using CAM

(content addressable memory) chips or by hashing. In a previous paper 18 , we presented a hardware hashing scheme which makes use of parallel read­ out mechanism of memory. A parallel hashing hardward consists of multiple RAM banks, hash address sequence generators and a hashing con­ trol unit. A single comparator is attached to every RAM bank (cf. Fig. 2) in the parallel hashing hardware, whereas in CAM chip such as Intel 3104 a comparator is attached to every memory cell. Even at a chip level, a CAM re­ quires several times more gates than a RAM chip. Hence total number of gates required for realiz-· ation of CAM is greater by at least one order of magnitude than that for the hash table, with no significant speed gain over parallel hashing: The items in the hash table are searched in average 0(1) memory cycle (a quantity independent of the number of items entered in the hash t able), in comparison with strict 0(1) used to search items entered in CAM. Since we are i nterested in the overall efficiency in our intended applications, it is more advantageous to invest the resource on enlargement of RAM memory than on still expensive CAM chips, More­ over, h-op of complex types such as AMT, CAT and VECT cannot be performed with CAM's.

Fi gure 2 shows the schematic diagram of the par­ a llel bank hashing hardware of FLATS. Hashing is essentially the cycle (hash probe cycle) of (i) hash address generations, (ii) memory accesses, (iii) key comparisons and (iv) judge­ ment of termination based on the comparisons. The hash tables, (i.e. AMT's and CAT's and an h-op table), are taken in main memory consisting of J banks. In a simple parallel hashing scheme with J banks, a single hash address generator and J comparators are used . together with some auxiliary hash sequence control circuits. To hand le key deletion, detectors of reserved words for denoting empty and deleted states are provid­ ed in each bank.

Assuming that the operations {i) - (iv) are performed in a single memory cycle, the perform­ ance of parallel hashing is given in number of memory cycles used until the completion of the probe cycles. Figure 3 shows that the average number of memory cycles in a successful search . (f i nding a key in the table) in the worst case19 We presume the worst average performance in the per formance evaluation when key deletion and in­ sert ion are repeated alternately. It shows that the basic hash operations can be performed in a time comparable to an indirect addressing oper­ ations, e.g. for J = 16 and the load factor of a hash table a= 0.9. Note that the hashing hard­ ware handles a fixed length key at a time. For handling variable length strings, arbitrarily long integers and lists, a shared linked list above mentioned is used with the parallel hashing hardware.

3.3 Hardware support for list processing

The hardware mechanisms essential to the speed­ up of Lisp are following;

1. run time data type checking,
2. hardware stack,
3. high memory bandwidth
4. segmented memory space with automatic bound­ ary checking for arrays etc., and
5. (S) instructions for Lisp primitives, such as car, cdr, cons and atom.

Note that the tagged architecture given in 3.1 is a solution to point (1).

As for point {2), we incorporate in FLATS both general (global) register and stack frame machine architecture. The basic op codes consist of four 8 bit fields as (op, r1, r2, r3), where r1, r2, r3 are register addresses each specifying either one of 128 global registers or one of 128 registers on the current stack frame. While the global registers are used to hold global entities, the stack registers are used for local entries and for (recursive) subroutine linkage,

In contrast to the two register address oper­ ations, r 1: · op(rl, r2) notably used in IBM 360/370, three register address operations r3: = op(rl, r2) are used in FLATS. The three register scheme would greatly reduce the number of register to register transfer operations. For example, while no register to register transfers are needed in the three register scheme for the following codes

a:=add(x,y);

b:=sub(x,y);

c:=mul(x,y);

d:adiv(x,y); ,

SO% of the corresponding codes would be register to register transfers in the two register scheme as in

a:=x; a;=add(a,y);

b:=x; b:=sub(b,y);

c:·x; c:=mul(c,y);

d:=x; d:=div(d,y);.

The unit of memory banking used in hashing is actually taken to be the bit width of a single list cell (64 bits). Expansion of memory to in­ crease the degree of parallelism (i.e. to in­ crease J) will speed up hashing operations as shown in Fig. 3; this does not imply the require­ ment of higher memory bandwidth sinte the com­ parators are provided in the memory units.

Need for segmentation is clear since the main memory is conceptually divided into several seg­ ments; AMT's, CAT's, arrays, list areas, program space and so on.

Fundamental Lisp primitives given above are ex­ ecuted in a single memory cycle. In fact, when run-time data type check is made by hardware, car and cdr instructions are equivalent to simple load operations. Complex Lisp primitives such as member and reverse are microprogrammed.

Furthermore, by virtue of the hashing hardware, operations on property lists and the oblist which rely on linear search in most Li~p systems are performed more efficiently in FLATS.

3.4 Hardware garbage collector

Dynamic storage allocation of variable length segments of memory in FLATS requires a com­ pactifying garbage collection scheme. The most time-consuming process in compactifying garbage collection schemes 20 ' 21 is pointer adjustment. FLATS is to incorporate the pointer adjustment hardware given in Fig. 5.

The pointer q in Q register is to be adjusted to be q' = q - ~q. where ~q is the total number of inactive cells in the memor~ block between base qo and q. A bit table of 2 width is set up in the memory local to the hardware. The bit table is marked by a garbage collector: '1' in the m -th bit position in columnnw corresponds to the inactive cell at qo + w2 + m in the main memory. Therefore ~q is obtained by counting l's bntween the base qo and q. The column (q - qo)/ 2 of the offset table contains the cumulative bit count E. The adjustment can be done in a main memory cycle when fast memory for the offset table and the bit table is used.

4. Concluding Remarks

At a users' level, FLATS is a machine both for numerical processing and for formula manipula­ tion. Instead of devising yet another language, we provide the facilities in the framework of existing languages, Fortran and Lisp (REDUCE is to be used for the user interface language). New compilers for Fortran and Lisp are under development, which incorporate the facilities for associative processing and overflow free and variable precision arithmetic, at the same time to accept programs written in Lisp and Fortran, which have been accumulated in libra­ ries of scientific application packages. The underlying techniques include hardware hashing~ tag mechanism, and hardware list processing (including hardware garbage collection). Con­ current garbage collection is not considered, since FLATS is not intended to be used for real time applications. FLAT is to be used as a back-end processor to a conventional computer system; hence the average performance, i.e. throughput, is a more important factor than responsiveness. For the same reason, hashing is best suited for the associative ~recessing dis­ cussed.

The associative capabilities of FLATS would also be suited for some operations for data base man­ agement.

Implementation of unified memory management of secondary and main memories using virtual tapes 22 is under consideration.

Substantial amount of software for FLATS has already been written and has been running under a FLATS simulator. Architectural design of FLATS is an outcome of the experiences with the develop· ment of the software system HLISP?·l6 REDUCE is now running under HLISP system and are used for various applications. A version of BFORT men­ tioned before which translates the extended Fortran into HLISP has already been running.