KEK NODAL System

© 1985 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transucrioni011NuclearScience.Vol. NS-32,No. 5, October 1985

207 1

KEK NODAL SYSTEM S. Kurokawa, A. Akiyama, T. Katoh. E. Kikutani, H. Koiso, and K. Oide National Laboratory for High Energy Physics (KEK) y Oho-machi. Tsukuba-gun, Ibaraki-ken. 305 Japan M. Shinomoto, N. Kurihara. Omika Works, Hitachi, Hitachi-shi, Ibaraki-ken.

NODAL Conversation

Abstract The KEK NODAL system, which is based on the NODAL devised at the CERN SPS, works on an optical-fiber token ring network of twenty-four minicomputers (Hitachi HIDIC 80's) to control the TRISTAN accelerator now being constructed at KEK. KEK NODAL complex, retains main features of the original NODAL: the interthe multi-computer programming preting scheme, In addition, it and the data-module concept. facility, has the following characteristics: (1) fast execution due to the compiler-interpreter method, (2) a multiediting computer file system, (3) a full-screen and (4) a dynamic linkage scheme of data facility, The structure of the KEK modules and NODAL functions. NODAL system under PMS, a real-time multitasking operating system of HIDIC 80, is described; the NODAL file system is also explained. Introduction NODAL' was devised at the CERN SPS as an interpretive language for accelerator control and has been Today, NODAL or NODALused there more than ten years. like languages are also used at the CERN CPS, at DESY. At KEK we have at Rutherford Appleton Laboratory. language for the adopted NODAL' as the control TRISTAN', an electron-positron colliding beam facility The KEK NODAL system works on now being constructed. the optical-fiber token ring network' of twenty-four HIDIC 80's made by Hitachi, Ltd. HIDIC 80 is a 16-bit minicomputer with the computing power of 1 Mips. One of the most prominent features of NODAL is its The syntax of NODAL allows a multi-computer facility. program to be expressed as a number of separate parts which can be executed on different computers in the network. For the detail see reference 1. The KEK version of NODAL has been enhanced the original NODALat the foIlowing points: (1) speedup of execution by the compiler-interpreter method, (2) a multi-computer file system, (3) a full-screen editing facility, and (4) a dynamic linkage scheme of data modules functions.

over

and

In this paper, we explain the structure of the KEK NODAL under the operating system of the minicomputers and the structure of the file system. The explanation of the network system is given elsewhere.4 Structure Operating

of KEK NODAL

System

A real-time multitasking operating system, PMS, is A task under PMS is a used in the KEK NODAL system. unit of the smallest activity working on a computer and processuch as programs, a central shares resources, an auxiliary memory, a main memory, sing unit, input-output

devices,

etc.

and K. Abe Ltd. 319-12 Japan Monitor

Tasks

To each terminal connected to HIDIC 80's, corresponds a set of NODAL conversation monitor tasks which support NODAL program development. The main functions of these tasks are: (1) supporting the full-screen editing (2) lexical and syntax analysis.

facility,

and

The full-screen editing facility of the KEK NODAL uses the cursor control capability of DEC VTlOO, which is a standard video terminal of the KEK NODAL system. Auser can edit his program, by moving a cursor on the screen, inserting, deleting, or changing characters. A source program typed by a user is lexically and syntactically analyzed and converted to intermediate codes, line by line. The intermediate codes are stored in the working area, while the source program is stored on the disk for the later use, since we cannot reconstruct the source program from the intermediate codes in the KEK NODAL. NODAL Interpreter

Tasks

The NODAL interpreter task interprets intermediate codes at run time. Note that not a NODALprogram but a NODAL interpreter itself works as a task under PMS. Three types

of NODAL interpreter

tasks

exist:

(1) The terminal interpreter task is executed when an immediate NODAL command is typed by a user. If the typed command is RUN, it interprets the NODAL program in the working area; if the command is RUN file name, it loads the NODAL program first from the disk into the working area and begins the interpretation. This kind of interpreter tasks corresponds to each terminal connected to the computer. The user can interrupt the task by pressing the BREAK key, (2) The remote execution interpretertaskinterprets NODAL programs transferred from other computers one of the EXEC. IMEX or EXEC-P commands. (3) The real-time interpreter task computer timer, CAMAC modules, timing system.

by

is activated by the or the accelerator

Working Area NODAL lines (the word 'line' means the intermediate codes for one line of NODAL source program), variables, defined functions, and related information are stored in the working area. This area is composed of five subareas: the control table, the bit-map table, the hashing table, the code.variable.defined-function area, and the stack, as shown in Fig. 1. The control table contains various pointers such as the stack pointer, the pointer to the list of lines, etc. This area also includes several flags and counters.

0018-9499/85/1ooO-2071$01.00~ 1985IEEE

2072

The code.variable.defined-function area is divided into cells of8-word units. Each bit of the words in the bit-map area shows whether the corresponding unit is occupied or not. When some free units are necessary (for example, a new variable is created), the interpreter searches them consulting the bit-map table. The cell structure is adopted to obviate the accumulation of garbage. Time for the garbage collection is harmful for real-time application. The stack area stores internal local variables of the interpreter. This area starts at the bottom of the working area and grows upwards, although the maximum size is limited to 2 kwords.

0

64h Shared PMS etc. I I91

LS#O I

t

8

t

2

t

3

t

*I

t

4

t

a)

t

5

WR .15)

Iosk HOi

NR

Rlunc datamod

7 I;“;

1101

171

/tl

t1

~I:/

t

dm table 112 /

6

7

Fig.

code

variable area

df

stack

WR ~(101~--by

2 Organization of the memory into togiATTOWS mean that the same ca 1 spaces. is shared by Several physical memory WR, NR, The letters togica 1 spaces. and R stand for the words, ‘working ‘non-resident’, and ‘resident’, area’, Numbers between parenrespectively. theses mean the memory size in kwoTds.

,

resident , non-resident commands commands

+

m

intermediate

code

101).941variable Fig.

Assignment

1 Structure

function (df i

a

defined

cl

unoccupied

of

the working

3rd-level

1 St-level 2nd-level r-QYI-----h--

non-resident functions ’

area.

non-resident data modules’

of Memory

$ DO

The 192-kword physical memory on HIDIC 80 is organized into nine logical spaces (LS's) whose maximum size is 64 kwords (see Fig. 2). LS#Ois the space for the operating system, LS#l is that for the subsystem of NODAL, and LS#~ is the linkers and loaders work. space on which compilers, LS#2, LS#3 and LS#4 are the spaces where the NODAL interpreter tasks work. On LS#5, LS#~ and LS#7 corresponding working areas for the interpreter tasks on LS#2, LS#3 and LS#4 exist, respectively. The remote execution interpreter tasks run on LS#2, the interpreter task for the first NODAL terminal runs on LS#3, and that for the second terminal runs on interpreter tasks run either on LS#4. The real-time LS#3 or LS#4, sharing the same logical spaces with the terminal interpreters.

EVAL

Fig.

3 Overlay preter

I I

of the NODAL inter-

structure task.

resident ones. Resident subroutines are loaded permanently on one of the following areas on LS#2: the resident subroutine area, the resident function area, subrouor the resident data-module area. Non-resident tines (that is non-resident data modules and nonresident functions) are loaded onto the third level area of the NODAL interpreter task from the disk. Speedup of NODAL Interpreter

The NODAL interpreter tasks are non-resident and run on the non-resident task areas (10 kwords) on LS#2, to this rather LS#3 or LS#4. In order to fit itself When structure. small area, the task has the overlay the interpreter is activated, the root of the task and the resident NODAL commands are loaded on the first and the second level of the overlay area, respectively. Non-resident NODAL commands are loaded at the third when necessary, from the disk (see Fig. 3). level,

The fast execution speed of the KEX NODAL is achieved by the adoption of the intermediate codes, the use of hashing for variable search, and the use of cache tables for lines and functions.

Subroutine resources for the interpreter tasks are of two kinds: the resident subroutines and the non-

This program is converted to the following 23-word long intermediate codes in the hexadecimal form:

An example below illustrates is converted to the intermediate Source:

FOR 1=1,100.2;

how a source program codes:

SET AA=I+l

2073 F301 4900 F104 4180 0000 F104 47c8 0000 F104 4280 0000 1518 ~302 4141 mol 4900 F104 4180 0000 0200 0900 0600 0007 The meaning of the above codes are: (variable I) (real 1.0) (real 100.0) (real 2.0) (FOR) (variable AA) (read variable I) (real 1.0) (add) (store) (FOR end) (end of line)

The file area on the disk is divided into blocks, the size of which are 2 kwords for program files, and 51.2 words for data files. These blocks have their sequential numbers and the numbers of the bl&ks occupied by a file are contained in an index (the size is 64 words for a program file, and 256 words for a data file). The index also holds the name, the section and the name of the owner, the date of update or creation of the file, etc.

This shows that constants are converted to the floating-point format from ASCII strings, commands are resolved into subcommands which are represented by the number codes, and the codes are arranged in the reverse-Polish order.

When a new file is created or data are appended to an existing file, the file must get new blocks. This procedure is done according to the record-area bit-map table which contains the status of each block (whether it is occupied or not).

The penalty we must pay for the adoption of the intermediate-code scheme is that some commands consume long execution time, because these commands need the compilation to the intermediate codes at run time. An example of such commands is SDO, which is followed by a string containing a NODAL source program as the command body.

The indexes for the same type of files occupy a continuous region on the disk. This area is divided into two parts: the primary area and the overflow area. The indexes for the program files in the primary area are arranged in a4 x m matrix, whereas the indexes in the overflow area are arranged in a 1 x n vector: the total number of indexes is 4 x m + n . The index of a file whose hash value is k (13&m) is stored in the kth line of the primary area; the hash value is calculated by the use of section and file name as the key. When the k-th line becomes fully occupied, an unoccupied index is searched in the overflow area. For data files, the number of the rows of the primary matrix is two ; the rest is the same as program files.

Search time for variables is reduced by the hashing which appear in a NODAL program are method. Variables connected to one of sixteen lists according to its hash value calculated from the variable name. The average number of variables in a list becomes l/16 as small as This makes the search the total number of variables. fast since time needed is roughly proportional to the number of variables in a list. When the interpreter encounters a line number or a function, it first searches them in cache tables in the working area. Since these cache table contain the pointers to the recently used lines and functions, time for the search of the frequently used items is reduced. Dynamic Linkage

of Functions

and Data Modules

The names, the addresses of the load modules, the numbers and types of the parameters of functions and data modules are contained in a special table. When the NODAL interpreter calls a function or a data in this table and module, it searches the name first We can compile, link and load a new gets the address. function or a new data module independently of the rest of the NODAL system: the only necessary procedure for registering these function and data module to the NODAL system is to set relevant parameters to this table. NODAL File File

System

Reference

Two types of files exist in the KEK NODAL system: The file NODAL program files and NODAL data files. reference consists of four parts: the computer name, the section name of the owner of the file, the file the file type. name, and the extension which identifies An example is shown below: DVO/CO.EXAflPL.N

where DVO is the computer name, CO is the section name, EXAMPL is the file name, and N denotes a program file. The computer name is optional; if it is omitted, the file on the current computer is assumed. The extension for a data file is the character D. The file system of the KEK NODAL has the multiAny file on any computer can be computer facility. accessed uniformly through the network. File

Index

File

Access

The procedure reading a file:

of

file

access

is illustrated

for

(1) Calculate

the hash value k using the section and file name as the key. (2) Search the index which contains the same section and file name as the key in the k-th line of the read the file accordIf it exists, primary area. ing to the contents of the index. continue (3) If the search in the primary area fails, the search in the overflow area. If the corresponding index is found, read the file according to the index. in the overflow area, then no (4) If the search fails file exists which has the same section and file name as the key. Acknowledgements We wish to thank Professor Y. Kimura and Professor_. We G. Horikoshi for their support during the work. also acknowledge the cooperation of the members of the TRISTAN controls group in constructing the TRISTAN control system; the KKK NODAL system is a part of it. References

Cl1 M.C. Crowley-Milling

and G.C. Shering, System at the SPS", CHRN 78-08.

"The NODAL

PI A. Akiyama,

et al., "Computer Control System of TRISTAN", Proceedings of the Europhysics Conference, Computing in Accelerator Design and Operation, Berlin, September 1983, in Lecture Note in Physics 215. Springer-Verlag 1984. pp. 367-371.

and G. Horikoshi. "Status of KEK c31 T. Nishikawa TRISTAN Project", IEEE Trans. Nucl. Sci. 30 (1983) 1983. et al., c41 H. Koiso. Computer Network", conference.

"Performance contributed

of the TRISTAN paper to this