LISP Machine NK3 and Measurement of Its Performance

1. INTRODUCTION

LISP is the most popular programming language in the research area of artificial intelligence. We have used LISP to develop natural language under­ standing systems and some problem solving systems. The most complicated systems among these is a programming language for natural language analysis called PLATON[NAGAO 1975], which is an extended version of Wood's ATN parser. It has the ability of pattern matching to check the applicabilities of the grammar rules. This makes the definition of a grammar very clear and easy to understand. However, because the pattern matching operation is very time consuming, it took a long time to analyze a sentence. The more poweful analysis we wish, the bigger the programs become, and require both a huge free cell area and high ex­ ecution speed.

On thP. other hand, for natural language under­ standing systems the more flexible control struc­ tures are required than the recursive one the ordinary LISP systems provide. The idea of the 'society of experts'[HEWITT 1977] is also very important in natural language understanding sys­ tems. Implementing such a co-routine environment by an ordinary LISP may decrease the efficiency considerably. It is desirable that the hardware system supports such mechanisms.

From the above reasons, we decided, in 1975, to construct a special hardware system which can directly execute LISP codes. The LISP machine which we have developed is called NK3 and equipped with various hardwares such as a specially design­ ed hardware stack. We have completed the hard­ ware of NK3 and implemented the interpreter of LISP1.5 on it. We are now developping more soph­ isticated LISP interpreter, compiler, and micro coded instructions for the machine step by step in evolutional approaches. We have measured the performance of the machine from various view points: how often the data transfer between the hardware stack and the main memory occurs, how frequent each micro coded instruction is used etc. Based on these measurements, we are improving the constructions of the interpreter, compiler and micro coded instructions.

2. ARCHITECTURE OF LISP MACHINE_ NK3

Fig.l shows the overall architecture of the LISP

machine NK3. NK3 is a micro-program machine. Micro-programs are stored in WCS(writable control store), and the macro-programs and LISP cells are stored in the main memory. The machine has three data buses, ordinary registers, ALU and some other functions. Special care is taken in the archi­ tecture to realize rapid transfer of the pointer information in the system. Automatic manage­ ment of the stack areas and the guarantee of the high speed, flexible automatic pushing down and popping up operations are the other important design issues of the system. Some typical fea­ tures of NK3 are the followings.

(i) Writable Control Store (4 kw, 42 bit/word)

This contains micro-programs of most built-in functions and most parts of the interpreter.

(ii) Main Memory (512kB, 800nsec)

The main memory is of the mini-computer INTERDATA 8/32 and is shared by NK3. Because of this memory sharing the access speed to the memory from NK3 takes about 2 pseconds, which is very slow. The input/output operations of NK3 are performed by INTERDATA 8/32. Since the OS is also shared, NK3 does not need to have any general facilities such as the file management.

(iii) Hardware Stack (16 words, 32 bits/word)

The top part of the stack is stored in these reg­ isters. The popping-up and pushing-down operat­ ions are generally performed in ordinary LISP programs alternately. Long consecutive popping ( pushing) operations are rare. In such a situation, the usual double buffering technique is inadequate. It causes frequent data transfer. To avoid this, we have adopted quadruple buffering for the hard­ ware stack. The hardware stack is divided into four blocks, each of which consists of four words. By transferring data from/to the main memory asyn­ chronously with the CPU by the unit of four words, the hardware stack is guaranteed to contain always at least four words of the stack and four word spaces for the push-down information. Special circuits are provided to detect the errors such as stack overflow and underflow. The data transfer is done by burst DMA mode independently with the LISP program. Any part of the main memory can be assigned to be the stack area, and any number of areas can be reserved for different stacks in the memory to realize co-routine environments. Some special instructions are prepared to switch the active stack from the current one to the other etc. Because frequent switching among stacks is expected to occur, it is not reasonable to have a larger hardware stack than the present one. It will cause a data transfer of large amount, when the active stack is changed.

We have measured how often the consecutive popping and pushing operations occur in the usual execut­ ion, and how often the data transfer is performed between the hardware stack and the memory (See Table 1).

Table 1. Stack Operations and Data Trensfer

The bench marck problem here is the theorem prov­ er based on 'resolution principle' [ChQng 1973]. From this table, one can see more than 84% of stack operations are effectively carried out with­ out any data transfer.

(iv) Transfer Table (1 kw, 15 bit/word)

The interpreter frequently checks the data types of the cells and determines the jump position in the program. The data types of cells are express­ ed in the tag parts of the memory words(Fig. 2). The Transfer Table is used by micro-prc·grams to determine the jump position directly from the des­ cription of the tag parts.

(v) Micro-Instructions

There are six types of micro-instructions. Those types are (1) Arithmetic and Logical operations, (2) Conditional Jumps, (3) Emit operations, (4) Transfer Table operations, (5) Patch operations, and (6) Shift ·operations. By Patch operations, we can patch arbitrary portions of L-Bus data and R-Bus data together. Combining this operation with the Shift operations enables us to manipulat e the tag information efficiently. The format of the type 4 instruction is shown in Fig. 3.

Tl1is instrution extracts the portion of the bus data (specified by ES - Extraction Source (R-Bus or L-Bus), EP- Extraction Position, and EL­ Extraction Length), and adds it to TO (Table Off-

set). If the result is within SL (Search Length), it refers to the Transfer Table to determine the jump position. Other­ wise, the instruc­ tion has no effect (See Fig. 4). This type of instruc­ tion is very use­ ful for carrying out 'multi-way jump' in micro-pro­ grams, based on the tag information.

Fi~. 4 Transfer Operation

3. HIGH LEVEL MACRO INSTRUCTIONS

NK3 is essentially a micro programmable computer which is equipped with various special hardwares. Therefore, in order to make the execution effi­ cient, we should devise macro instructions which utilize these special hardwares well and are suit­ able for LISP operations. At present, most of built-in fuctions of LISP can be executed by sin­ gle macro instructions. Moreover, some of them operates directly on the top of stack. Because of the hardware stack, these instructions are executed very fast.

A set of special macro instructions which facili­ tate the writing of LISP interpreters is provided. These are the parts of 'the interpreter which con­ ceptually perform single tasks. For example, searching the value of a variable from the A-list, jumping to the appropriate locations in Eval or Apply according to the types of the arguments and so on are performed by single instructions. The instruction HASH is another example of high level macro instructions. The hashing operation on the atom's print-name is carried out by this instruc­ tion. It is very time consuming by the ordinary program to identify all the input character strings with the atoms already in the system. The HASH instruction performs this task very efficiently.

Some other special instructions have been devised to manipulate the hardware stack for implementing flexible control mechanisms directly. The instruc­ tions EXCHange and INITialize are the examples. The EXCH and INIT enables us to implement co-rou­ tine environments. Because NK3 is equipped with a single hardware stack, only one of the co-rou­ tines can be active at a time and the stack information for the routine is stored in the hardware stack. The EXCH is used to exchange the content of the hardware stack, in order to activate an­ other co-routine in place of the current one. The older context will be appropriately saved. The instruction INIT is for invoking a new co­ routine. It initializes a stack area and reserves a certain amount of memory area for that routine.

4. PERFORMANCE EVALUATION

We have written a LISP interpreter for LISP 1.5 by using the macro instructions described in 3, and have measured the performance and the effec­ tiveness of these instructins. We are still seek­ ing much more efficient set of macro instructions for LISP. Up to present we have experienced a drastic improvement of the execution times, for example two to three times, by setting up a good instruction set. On the other hand, another trial is in progress, which makes the macro in­ structions as big as possible in their functions. The limit in this direction is that the stack op­ rations cannot be realized by micro programs. Because of this weak point, the interpreter as a whole cannot be realized by micro instructions only.

We also compared the execution speed of NK3 with some other LISP systems on big and small comput­ ers. The bench mark problems were a sorting pro­ gram, a theorem prover, and some other typical LISP programs. The performance of NK3 might be judged as : it has a half of the power of very large machines (i.e. Ml90), and has several times of the power of small computer versions of LISP. If NK3 can use the main memory exclusively with­ out sharing with INTERDATA 8/32, and if the stack mechanism can be utilized freely from micro-pro­ grams, the execution speed will improve drasti­ cally. These may be the main improvement to be taken soon.