LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 Ittor no. 293-300 cop. 2 CENTRAL CIRCULATION AND BOOKSTACKS The person borrowing this material is re- sponsible for its renewal or return before the Latest Date stamped below. You may be charged a minimum fee of $75.00 for each non-returned or lost item. Theft, mutilation, or defacement of library materials can be causei for student disciplinary action. All materials owned by the University of Illinois Library are the property of the State of Illinois and are protected by Article 16B of Illinois Criminal law and Procedure. TO RENEW, CALL (217) 333-8400. University of Illinois Library at Urbana-Champaign JUN2 81999 FE s o i An When renewing by phone, below previous due date. write new due date L162 Digitized by the Internet Archive in 2013 http://archive.org/details/controlstatement298wilh * I* 8« -.■!'. yo't Report No. 298 y^UOUi CONTROL STATEMENT SYNTAX AND SEMANTICS OF A LANGUAGE FOR PARALLEL PROCESSORS by Robert B. Wilhelmson January 13, 1969 THE LIBRARY OF THE FEB 2 1959 * !i eg Hi 13! ;! ' Report No. 298 CONTROL STATEMENT SYNTAX AND SEMANTICS OF A LANGUAGE FOR PARALLEL PROCESSORS* by Robert B. Wilhelmson January 13, 19^9 Department of Computer Science University of Illinois Urbana, Illinois 6l801 This work was supported in part by the Advanced Research Projects Agency as administered by the Rome Air Development Center under Contract No. US AF 30(60Z)klUk and submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science, February, 19^9. Xll ACKNOWLEDCMENT The author would like to express his appreciation to his adviser, Dr. D. Kuck, for his suggestions and criticisms in the course of the study. The author is also indebted to his co-workers, Paul Budnik, Yoichi Muraoka, and Norma Abel, for their criticisms and suggestions. Thanks are also extended to the many who have helped prepare the final manuscript. IV ABSTRACT A description of the control statement features of TRANQUIL, a language for describing algorithms in terms of parallel constructs, and their implementation in a compiler for the parallel array com- puter ILLIAC IV is given. This includes descriptions of the revised ALGOL loop specification, simultaneous execution specification, and set specification; and the implementation of the storage and use of sets as well as use of the control unit registers. The concept of parallelism in a language is discussed and the problems of automatic translation of a serial to a parallel language "brought out. TABLE OF CONTENTS Page 1. PARALLELISM IN REVIEW 1 1.1 Parallel Concepts 1 1.2 Explicit Parallelism 2 1.3 Implicit Parallelism 6 2. TRANQUIL CONTROL STATEMENTS 9 2.1 An Introduction to TRANQUIL and ILLIAC IV 9 2.2 TRANQUIL Control Statement Manual 11 2.2.1 Introduction 11 2.2.2 Set Definitions, Declarations, and Operations 11 2.2.2.1 Defining Sets 11 2.2.2.1.1 List Sets 12 2.2.2.1.2 Comparison Sets Ik 2.2.2.1.3 Set Ordering Definition . 15 2. 2. 2.1. k Set Operations 15 2.2.2.2 Set Declarations 16 2.2.3 Sequential Control: The SEQ , Statement ... 17 2.2.4 Simultaneous Control: The SIM Function and the S IM Statement 20 2.2.5 Nested SEQ and SIM Statements 23 2.2.6 If Clauses 2k 2.2.7 Label and Switch Declarations 26 2.2.8 Designational Expressions and GO TO Statements 27 2.2.9 Statements and Block Structure 27 2.3 Comparison with Other Languages 28 2.3.1 ALGOL 28 2.3-2 MADCAP 28 2.3.3 APL 29 VI Page 3- COMPILER IMPLEMENTATION OF CONTROL STATEMENTS 32 3.1 Introduction 32 3.2 The Allocation and Use of CU Storage 3k 3.2.1 CU Structure and Instructions 3^ 3.2.2 An Implemented Solution 35 3.2.3 Use of the Procedures 39 3.2.3.1 INTEGER PROCEDURE GETLDB 39 3.2.3.2 INTEGER PROCEDURE GETCAR 1+2 3.2.3.3 INTEGER PROCEDURE CSPUSH kk 3. 2. 3.1+ PROCEDURE CSPOP 1+5 3.2.3.5 PROCEDURE MOVETOCS 1+6 3.2.3-6 PROCEDURE MOVETOMEM 1+6 3.2.3.7 FREELDB 1+7 3.2.3.8 FREECAR 1+7 3.2.3.9 INTEGER PROCEDURE GETBIT 1+7 3.2.3-10 INTEGER PROCEDURE FREEBIT 47 3.3 The Storage and Use of Sets 1+7 3-3.1 Introduction 1+7 3.3.2 Set Storage Tables 1+8 3.3.3 A Set Storage Scheme 50 3.3.4 Increment, Mode, and Explicit Storage Forms and Their Use 53 3-3-5 Index Set Usage in S E fls and SJ J^s 57 3.3.6 Mode Pattern-Explicit Word Conversion .... 60 1+. CONCLUSIONS AND SUGGESTIONS 62 APPENDIX A. METALANGUAGE FOR SPECIFYING SYNTAX 63 B. TRANQUIL SET AND CONTROL STATEMENT SYNTAX 65 B.l Statements 65 B.2 Control Statements 65 Vll Page B.3 Sets 66 B.3'1 Declarations 66 B.3« 2 Definitions 66 B.3» 3 Set Assignment Statements 67 B.k Switch and Label Declarations 68 B.5 Designational Expressions ..... 68 B.6 IF Clauses 68 B-7 Global Operators 68 C. AN INTUITIVE LOOK --- THE TRANSLATION OF FORTRAN INTO TRANQUIL 69 CI Essential Ordering 69 C2 Translation Decisions 71 D. A SAMPLE TRANQUIL PROGRAM 76 E. GENERAL FLOW CHARTS FOR THE TRANQUIL COMPILER .... 77 LIST OF REFERENCES 79 Vlll LIST OF FIGURES Figure Page 1. The identifier table 33 2. The division of the LDB 35 3- CU allocation pointer system 37 h. Mode patterns and explicit values for increment sets . . 5h 5« General PE and CU picture for line 10 of the problem in Appendix D where 1 = 2 55 1. PARALLELISM IN REVIEW 1.1 Parallel Concepts Today the use of the term parallelism in the field of computer science can, unless clarified, result in confused thinking due to its possible use in referring to a variety of concepts. In the early years of computer development the term became associated with the simultaneous handling of input-output processes and processor computations. This simultaneous capability reduces processor idle time; however, it is often the case that it cannot be used because of the serial nature of input-output requests and computation. The introduction of the parallel concept known as multiprogramming was directed in part to overcoming this problem by allowing several programs to share a processor during their execution stage. The implementation of this concept requires efficient and balanced handling of input-output processes, memory allocation, scheduling, and queue ing. Without careful planning the time gained can easily be offset by the time lost. An aid in this regard is the use of re-entrant code; i.e., code that can be used on demand, and not when some other user is finished with it. From the hardware perspective emerges yet another parallel concept, the utilization of a fixed number of processors in what is called a multiprocessing system. The implementation of this concept has been most successful when the processors are associated with certain tasks (thus lifting the burden off a single unit) or when programs are allocated to processors on a one-to-one "basis. However, their use for executing sections of a program that are data independ- ent over a series of operations has not been very successful. To accomplish this requires the ability to specify in or decide from a language on the level of FORTRAN or ALGOL this independence [1, 2, 3, k, 5, 6> 7, 8, 9, 10, 11]. In the former case the problem centers around attempting to denote parallel operations in serial form and in the latter the task of algorithmically rethinking in parallel a program that is specified serially is unsolved. Another parallel concept concerning hardware is the use of a large number of processing elements under a single control unit. Each processing element responds to a given operation simultaneously with the others unless it is disabled. A system using this concept is called an array processing system and the ILLIAC IV computer falls into this category. This type of system can be designed using one large memory or individual processing element memories with the problem of scheduling memory use or of moving information between separate memories occurring, respectively. 1.2 Explicit Parallelism In writing a program it is at times clear to the programmer that several statements or sections of his code are independent of one another and thus can be executed simultaneously. The concepts of FORK and JOIN were introduced to allow the programmer to specify when this occurs. Opler [ 3] presented these concepts for use in a multipro- cessing environment "by a single program in terms of the instructions DO TOGETHER and HOLD . These instructions are coupled with appropriate labels to specify the parallel paths and are to be used with the following rules : (1) variables common to several parallel paths cannot be altered from within these paths, (2) procedure calls from parallel paths in the same range must be made only to re-enterable code, (3) branching into or out of the range of a DO TOGETHER or in between parallel paths is forbidden, (k) logical decisions in parallel paths should set switches for later interrogation, and (5) DO TOGETHER ' s may be nested. Several months after the appearance of Opler' s paper Anderson [k] suggested several extensions to ALGOL in a similar manner and noted that the FORK and JOIN notation could be used not only in multiprocessing systems but also in multiprogramming systems to designate independent segments of the same program so that while one waits for an I/O transaction another can be in execution. He introduced five delimiters in his ALGOL extension, namely: FORK , JOIN , TERMINATE , OBTAIN , and RELEASE . The special words FORK and JOIN are followed by labels denoting the independent sections. When the programmer wants to join independent sections, and not necessarily proceed on to the immediately succeeding statement, TERMINATE is used. This allows the FORK statement to be used recursively. OBTAIN allows the specification of variables for exclusive use in a particular path while RELEASE frees them. A simple example presented in Anderson's paper illustrating the use of FORK and JOIN is that of an inner product calculation broken up into two sections for vectors A and B. FORK FIRST, LAST; FIRST: BEGIN SI:=0; FOR I:=l STEP 1 UNTIL N + 2 DO SI:=SI + A[I] X B[I]; GO TO CONTINUE; END ; LAST: BEGIN S2:=0; FOR J: = (N + 2) + 1 STEP 1 UNTIL N DO S2:=S2 + A[J] x B[J]; GO TO CONTINUE; END ; CONTINUE: JO IN FIRST, LAST; S:=SI + S2 The advisability of using these terms and this means of expressing independent segments of a code has come under question. Wirth [5], in response to Anderson's article, distinguishes two cases of parallelism: 1) the use of processors in parallel and 2) The use of a processor configuration by a program requiring the use of various special components in parallel. He protests the use of FORK and JOIN in ALGOL as contradictory to the principles of machine independence on which ALGOL is based since the JOIN statement is not logically necessary but is present for machine implementation. He introduces the use of and to denote the possibility of parallel execution in a program for case l) with essentially the same effect as Anderson's FORK and JOIN . The problem in case 2) he states is the communication between different facilities requiring the access of common variables. This could be solved in one way by a special procedure including a number of programs, the first queueing requests to the others and permitting use of another program in the procedure only when all previous requests had been honored. The topic of a recent paper by Constantine [6] is the control of sequence and parallelism in modular programs. He first presents a number of technical and programming considerations for the operation and specification of parallel processes and references appropriate papers. The technical considerations include: (1) the prevention of simultaneous critical section usage in a shared code or resource, (2) the assurance that no program will be delayed indefinitely, and (3) the reproducibility of results under different conditions such as program mix and time. The programming considerations include: (1) simplicity of programmer specification, and (2) allowing errors that are discoverable and correctable in a reasonable time. His proposal for parallel activity in terms of modular (i.e. procedure level) units is a result of these considerations, its applicability to real problems, and the low overhead for implementation in comparison to that of the lower level FORK and JOIN . In particular, this proposal is that procedure input and output parameters should be isolated with the intent that the procedure call and its input specification be made as early as possible and the call for output parameters as late as possible. 1. 3 Implicit Parallelism The detection of parallelism implicitly from a code is desirable if possible in order that this parallelism might be utilized in multiprogramming and multiprocessing systems without having the user explicitly find and indicate it. This detection can be studied from several viewpoints. One approach is the development of a model for the description and analysis of parallel computations. This model has taken in several instances the form of a graph. In a 1964 paper by Karp and Miller [7] such a model is presented for the description and analysis of parallel computations. They include several theorems on determinacy, termination, and queueing, where computation steps correspond to nodes of a graph and dependency "between computation steps is represented by branches and associated queues of data. In another paper by Martin and Estrin [8] the nature of cycles in computed programs is discussed for parallel processors. Their model nodes again represent computational steps or processes and the areas connecting the nodes represent data flow associated with control conditions, branching probabilities, and data transfer time costs. The relation of sequential execution in these graphs is not separated from simultaneous execution. The basic unit is a node : INPUTS OUTPUTS which represents a subprocess operating on inputs and yielding outputs. The actuation of a node via a single input or all inputs directed to the node can be specified as well as the output on one or all of the output lines. Significant results from studying implicit parallelism through this or any type of graph as yet do not exist. A group at the Burrough's Corporation is studying the implicit detection problem from the standpoint of computer program 3 and multiprocessor relations [9, 10, 11]. They have presented algorithms to automatically detect the essential order between assignment statements involving variables, but it appears that the time involved for real problems is large even if hardware is used in implementation. They have also investigated the automatic recog- nition of possible parallel executions for a loop body and have described a system design to exploit both instruction and data parallelism with as yet no significant detailed practical results. A related problem is the translation of a serial language into a parallel language for use on a parallel machine. An initial approach to the transformation of FORTRAN into TRANQUIL, the language for use on ILLIAC IV, appears in Appendix C. Before reading it, however, one should read the remaining chapters in order to become familiar with TRANQUIL, as a basic understanding of it is assumed there. 2. TRANQUIL CONTROL STATEMENTS 2.1 An Introduction to TRANQUIL and ILLIAC IV TRANQUIL is the name of the algorithmic language which is being used to write programs for the array processing computer, ILLIAC IV. The specification of TRANQUIL is the first project to define a language for a real parallel machine and its development has proceeded side by side with hardware development. A general description of ILLIAC IV is given at the beginning of a paper by David J. Kuck [12] and is reproduced in the following paragraphs for later reference. ILLIAC IV is an array of 256 coupled computers driven by instructions from a common control unit. Each of the 256 processing elements (PEs) has 20kd words of 64-bit memory with a 2^0-ns cycle time. Each PE is capable of 64-bit floating-point multi- plication in 400 ns and addition in 2^0 ns. 32-bit floating-point operations and 8-bit fixed-point operations are also available. The PE instruction set is similar to that of conventional machines, with two exceptions. First, the PEs are capable of communicating data to four neighboring PEs by means of routing instructions. Second, the PEs are able to set their own mode registers to effectively disable or enable themselves. ILLIAC IV has four control units (CUs) each of which may drive 6U PEs independently. The machine may thus be operated as four independent 64-PE quad- rants or as two 128-PE halves. In the united configuration, all 256 PEs are effectively driven by one CU and routing proceeds across quadrant boundaries. This allows some flexibility in fitting problems to the array. The complete ILLIAC IV system includes a Burroughs B65OO computer which contains most of the software for the entire system. Also, there is a lO^-bit, head-per-track disk with a 4-0-ms rotation speed and 10 an effective transfer rate of ICk bits per second. This allows the loading of the 32 X 10^ -bit ILLIAC IV memory from the disk in a transmission time of 32 ms. The input/output controller (IOC) contains a queuer for disk requests and a 2 1 ?-bit buffer memory to smooth transmissions to and from the slower B650O memory and other input/output devices. In developing a language such as TRANQUIL for a parallel computer several considerations are necessary. The first is that it is desirable to be able to express algorithmic parallelism from the perspective of a problem and not the machine on which it is run. This does not mean that data structure mapping should not be a user concern but that once data is delegated to memory the user should only have to think in terms of his problem structures. The second is that the specification of parallelism should not be intricate, but straightforward and easy to learn and use so that all potential parallel activities can be specified. This is necessary if a parallel computer is to be utilized efficiently. These considerations were made in the development of TRANQUIL. In particular, TRANQUIL is designed for algebraic problems and con- sists of a collection of data declarations, arithmetic and boolean operations, set definitions and operations, and control statements. The control statements are used to express parallel operations on chosen subsets of arrays or other geometric configurations. This is accomplished by linking control variables simultaneously with all the elements of associated sets. When the elements of a set are used simultaneously the actual implementation may take the form of PE indices or mode words. These sets can also be used in the specification of sequential or iterative control in much the same 11 way as in ALGOL. In contrast many loops can be eliminated from ALGOL code by using in TRANQUIL simultaneous control statements as mentioned and also by specifying operations on whole arrays such as the vector inner product or matrix multiplication operation. Further, there are control statements that allow branching on condi- tional boolean tests involving whole or partial arrays. This then is a brief description of TRANQUIL control state- ments. The following section expands upon this description in manual form. 2.2 TRANQUIL Control Statement Manual 2.2.1 Introduction The following manual is designed to help the TRANQUIL user become familiar with writing control statements in the language. A basic understanding of ALGOL is assumed and the approach is informal. The formal specification of the syntax is located in Appendix B and should be referred to when necessary. Control statements are used in TRANQUIL to designate con- ditional and unconditional jumps, sequential loops, and simultaneous statement execution. Sets, which are an integral part of these control statements, are the subject of the next section. 2.2.2 Set Definitions, Declarations, and Operations 2.2.2.1 Defining Sets Sets in TRANQUIL are collections of elements and are dis- tinguished from vectors and arrays by their associated control func- tions. 12 A set is composed of ordered elements having integer values. These elements are n-tuples of arithmetic expressions (0 < n < 7) rounded via the entier function where n is constant for any given set and is known as the dimension of the set. For example, SET1 *- [ ] SET2 - [1, 2, 3, h, 5, 6, 7, 8] SET3 - [[10, 10], [9, 8], [8, 6], [7, 4], [6, 2]] SET4 - [25, -2, P, Q-R, 25] where SET1 is empty and thus has dimension zero, SET2 and SET4 are 1-dimensional sets, and SET3 is 2 -dimensional. Sets can only be defined when not in use by a control statement and their definitions fall into two basic categories, list sets and comparison sets. 2.2.2.1.1 List Sets The basic list set is specified by the explicit statement of its elements as in the examples just given. The specification of SET2 can be shortened to the increment form; i.e., SET2 <- [1, 2,..., 8] The increment form can be used for any 1-dimensional set that is composed of elements either in a strictly increasing or strictly decreasing arithmetic progression. For example, SET5 ♦- [6, k, 2, 0, -2, -h, -6] 13 can be shortened to SET5 «- [6, h,..., -6] This form can be extended to allow as many increment specifications as desired as long as the first two and the last elements of each group appear explicitly and the groups do not overlap, as in the following definitions : SET6 - [1, 2,..., 5, 7, 8, 10,..., Ik] SET7 - [11, 10,..., 7, 5, 3,.-., 0] which are equivalent to : SET6 - [1, 2, 3, k, 5, 7, 8, 10, 12, 14] SET7 - [11, 10, 9, 8, 7, 5, 3, 1] Note that the last element of a group indicates the largest or smallest acceptable value for that group whether or not it is a member of the resulting set. A further extension for 1-dimensional set definitions is the ability to specify the repetition of an element a fixed number of times. The format is similar to PL/l, for example, SET8 - [1(3), h, 5(2)] is equivalent to SET8 - [1, 1, 1, k, 5, 5] 11+ 2.2.2.1.2 Comparison Sets The comparison set is the result of comparing data values via some boolean expression. The general format is SET [J , ...,J : ] where each J. is an identifier. The comparison set is specified to allow parallel generation of an index set at execution time. Thus at least one of the identifiers must he a subscript in the boolean expression and should also be under simultaneous control. The result of this definition is an n-dimensional set consisting of elements for which the boolean expression is true. For example, suppose A and B are vectors with elements A: (-1, 3, 2, 10) B: (2, -3, 1, 12) and SET9 is defined as FOR (I) SIM ([k, 3, 2, 1]) DO SET9 - SET [I: A[I] < B [I]] The resulting set consists of the elements 1 and k. To illustrate further consider the following matrices and statement: 15 FOR (I, J) SIM ([1, 2, 3Ml, 2, 33) DO SETIO *- SET [J, I: A[l, J] < B[l, j] ] the resulting set is [[1, l], [2, l], [1, 2], [2, 3]]. These sets are designed for use under simultaneous control; however, in the case of the 1 -dimensional set, the ordering is monotonically increasing if one desires to use it for sequential control. Also it should be noted that the above examples are small for clarification, as much larger data sets will typically be involved on ILLIAC IV. 2.2.2.1.3 Set Ordering Definition One dimensional sets are ordered from left to right when their elements are explicitly stated in the basic or shortened list form or in monotonically increasing order as mentioned above for comparison sets. Sets of greater dimension cannot be used in loop control and thus their ordering is not a user concern. 2. 2. 2.1. ^ Set Operations Sets can be combined using operators such as concatenation and union. For example, the set of factorials {1, 2, 6, 2U,...,NJ} can be generated as follows: TEMP «- 1; SF <- [1]; FOR (I) SEQ ([2, 3,...,N]) DO SF «- SF UNION [TEMP <- I X TEMP] 16 where UNION joins the new element to SF and orders SF so that it is monotonically increasing. The use of concatenation ( CONCAT ) allows the user to add elements to either end of a set without a reordering hy the compiler and REVERSE specifies the reverse ordering of a 1-dimensional set. The cartesian product (x) and pair (,) operators are useful in set assignment statements and control statements. For example: 51 «-[[l, 2, 3, h] , [2, k, 6, 8]j 52 -[[1, 2] X [3, h]j 53 «-[[!, 2] x [3, U] , [5, 6]1 are equivalent to: 51 «- [[1, 2], [2, k], [3, 6], [h, 8]] 52 - [[1, 3], [1, hi, [2, 3], [2, h]\ 53 - [[l, 3, 5], [l, h, 6], [2, 3, 5], [2, h, 6]] where , has higher precedence than X. Further set operations are discussed in the section of the TRANQUIL manual on set expressions [13] 2.2.2.2 Set Declarations There are three types of set declarations, which are written in the following format: { INCSET I MONOSET | GENSET | PATSET ) SET , • . • ,SET ffi () [L,:U, f L«:U rt , .. .,L :U ,MS] \ 2_ 1' 2 2' ' n n 7 IT where {} means one of the alternatives separated by | is chosen, L. and U. (i = l,...,n) stand for the lower and upper bounds of component i, MS is the maximum number of elements or n-tuples possible, and SET. (i = l...,m) are set identifiers. INCSET , MONO SET , and GENSET signify 1-dimensional sets with the dimension number specification optional. The lower and upper bounds and size can be arithmetic expressions whose values are known at the beginning of the block of the associated set definition. The attribute INCSET (increment set) designates sets defined only in the form first second last element, element, . . . , element The attribute MONO SET (monotonic set) refers to sets that are strictly monotonic, the attribute GENSET (general set) refers to 1-dimensional sets, with no restrictions and PAT SET (pattern set) refers to multi- dimensional sets (n > l). The lower bound is 1 if not specified. Some examples are: MONOSET SI, S2 (l) [250,50] PATSET S3 (2) [0:100,0:200,30] GENSET S5 [50] 2.2.3 Sequential Control: The SE£ Statement Sequential control is another term for loop control and is specified in the general form: FOR (l 1 ,...,I n ) SEQ (II 1 {X I ,}...{X I , } II n ) {DO | WHILE < boolean expression > DO] S 18 where the scope is the statement S, n as an integer, I.(i = 1, ...,n) are control variables, and II. (i = l,...,n) are 1-dimensional set identifiers. The use of this statement is illustrated by the following examples. (a) FOR (I, J) SEQ ( [l, 2,. ..,10], [5, 10,. ..,50]) DO A [I] +- B[I + 1] + C[J] is evaluated as A[l] «- B[2] + C[5]; A[2] «- B[3] + C[10]; A[10] «- B[ll] + C[50] Note that the comma denotes pairwise ordering for the control variable values . (b) FOR (I) SEQ ([2, k, 6]) WHILE I < A [i] DO A[l] «- B[l] - A[I] will continue looping until the boolean expression is false or the index set has been exhausted. As in ALGOL no pass through the loop is made if the boolean expression is false after the index variable is assigned the initial value of 2. (c) FOR (I, J) SEQ ([1, 2, 3, h}, [5, 6]) DO B[I, J] *- A[l, J] * In the remaining examples set definitions are also used for simplicity. 19 In this case the difference in size of the two defined sets is resolved by considering only the pairs (l, 5) and (2, 6), that is, the exhaustion of the smallest index set signals the end of the loop. To indicate otherwise an asterisk is placed after the set the exhaustion of whose elements is to be used as the stopping condition. This means that any other sets which run out of elements before completion will be repeatedly used as many times as necessary. If the previous statement is rewritten as FOR (I, J) SEQ, ([1, 2, 3, *0*, C5, 6]) DO B[I, J] - A[I, J] the result is B[l, 5] *- A[l, 5li B[2, 6] *- A[2, 6]; B[3, 51 - A[3, 5]| B[k, 6] .A[l, 6]: (d) FOR (I, J) SEQ ([1, 2] X [6, 7, 8]) DO A[I, J] <- B[J, I]; yields A[l, 6] «- B[6, 1]: A[l, 71 - B[7, 1], A[l, 8] - B[8, 1]; A[2, 6] «- B[6, 2] A[2, 71 «~ B[7, 2]: A[2, 8] - B[8, 2], 20 where the lengths of the two sets do not create the problem that occurred with the pairwise operator. This example also illustrates that the frequency of element change is greatest for the rightmost set used. (e) FOR (I, J, K) ^Q ([1, 2], [3, h, 5] X [6, 7]) DO C[I, K] - D[J, K] yields C[l, 6] - d[3, 6], C[l, 7] - D[3, 71 C[2, 6] - d[4, 6], C[2, 7] - D[4, 7] where the comma has higher precedence. For exits from loops via any means the control variables retain the last value assigned. 2.2.4 Simultaneous Control: The SIM Function and the SIM Statement The parallel structure of TTiLIAC IV is utilized through TRANQUIL by the specification of a simultaneous control function or statement. The functional form (refer to Appendix A for notation) is SIM EEGIN list < assignment statement > separator ; EM) where the enclosed assignment statements are executed simultaneously; i.e., the data used by any one of them is the data available before the SIM function was encountered. In the following example, the 21 contents of vectors A and B are interchanged without specification of a temporary location : SIM BEGIN A «- B; B «- A END The general statement form for simultaneous control is: FOR (l 1 ,...,I n ) SIM (II 1 {x |, }...{X |, } IlJ DO S where m, n are integers, I. (i=l,...,n) are control variables, II. (i=l,...,m) are k-dimensional sets (0 < k < 7)> n equals the total number of dimensions of all II., and S is a statement. For this 1 statement each substatement S. of S is executed with the data avail - 1 able before it is reached, i.e., just as if a SIM function was placed around each S.« In this regard it is important to note that simul- 1 taneous control is not loop control, but designates that each S. is to be executed in parallel and thus the order of the associated sets is not important. Several examples will illustrate the use of simultaneous control. (a) FOR (I, J) SB4 ([1, 2, 3]*, [k, 5]) DO A[I, J] - B[J, I] is evaluated as SIM BEGIN A[l, k] *- B[4, 1]; A[2, 5] - B[5, 2]; A[3, h] - B[k, 3] END 22 (Id) FOR (I) SIM ([1, 2,. ..,256]) DO A[I] «-A[l-l] yields SIM BEGIN A[l] «- A[0]; A[2] - A[l]; A[256] «- A[255] END which shifts part of a vector one position. (c) FOR (I, J) SIM ( [1, 3], [2, U] ) DO BEGIN A[l] «- B[j]j A[J] <- 3 END yields SIM BEGIN A[l] «- B[2]; A[3] -B[U] END ; SIM BEGIN A[2] «- 3; A[l+] <- 3 END (d) FOR (I, J) SIM (II, JJ) DO BEGIN C[I, J] - 0; FOR (K) SEQ (KK) DO C[I, J] «- C[I, J] +■ A[I, K] X B[K, J]j END is a general routine for the multiplication of two matrices A and B. 23 It should be noted again that when a set is used in a sequential or simultaneous control statement, it cannot he altered in the scope of that statement. 2.2.5 Nested SEQ. and SIM Statements The sequential and simultaneous control statements described in the previous two sections can be nested. This nesting is straightforward except in the case where a SIM statement occurs within the scope of another SIM statement. When this occurs the area common to them is executed simultaneously with their sets related by the cross product operator as illustrated in the following example: FOR (I, J) SJM (II, JJ) DO BEGIN FOR (K) SJM (KK) DO BEGIN ... area a .... END; END where in area A the control statement in effect is FOR (I, J, K) SJM (II, JJ X KK) DO This example is readily extended to nesting in greater depth, 2k 2.2.6 If Clauses General forms: (a) IF {FOR (I ,...,1 ) SIM (II (X | , } . . . {X | , } II ) | } (AM | ALL | } | THEN Form (a) of the if clause can appear in designational, arithmetic, boolean, and set expressions. It results in a single logical value. The common form IF THEN is easily seen to be a subclass of (a). The ANY and ALL modifiers are used when the boolean expression involves at least one subscript under SIM control and results in a true value when any or all of the tests are successful, respectively. For example, if the vector A of length 2 has elements 5 and 10: IF FOR (I) SIM ([1, 2]) ANY A[l]< 7 THEN has the value true since A[l]< 7. When the SIM appears in the if clause its scope extends only over the boolean expression. Form (b) can be used in arithmetic and boolean expressions of assignment statements where the boolean expression of the if clause and the left hand part of such a statement both have subscripts under SIM control. The expression after the THEN is executed as if the set under SIM associated with the common subscript contains only those original elements for which the test is true and after the ELSE only those for which the test is false. Thus a single logical jump does not occur; rather, the original index set is reduced under 2 5 SIM control via the boolean test for use after the THEN and the ELSE when it occurs. Further, if this set is paired with any other set then only those pairs for which the test is true for the original set are used after the THEN and similarly after the ELSE for the false test. For example, if A[l, J] = 2 I + J, FOR (I, J) SIM ([1, 2, 3, h], [5, 6, 7, 8]) DO A[I, J] *- LFSET A[l, J]< 8 OR A[l, J> 10 THEN 20 ELSE 30 yields A[l, 5] - 20; A[2, 6] *- 20; A[3, 7] - 30; A[J+, 8] - 20 Form (b) also can be used in an IF statement where similar action is taken. An example of both the first and second cases is FOR (I) SIM ([1, 2,..., 100]) DO T[I] «- LFSET A [I] < B[I] THEN A[l] ELSE B[l] is equivalent to FOR (I) SIM ([1, 2, ...,100]) DO JFSET A[I] < B[I] THEN T[l] ♦- A[l] ELSE T[I] ♦- B[I] In either form T[l] <- A[l] for all values of I for which the boolean expression is true and T[l] *- B[l] otherwise. 26 When IF statements are nested the innermost THEN and the immediately following ELSE will be treated as one pair, and from this center the pairs proceed outwards. However, any desired arrangement is possible using BEGIN and END in forming compound statements. 2.2.7 Label and Switch Declarations Labels are identifiers which must be declared before their use in statements and switch declarations. The declaration for a label is: LABEL L n ,...,L 1' ' n where L. is a label identifier. Labels may be declared locally or globally with respect to the block in which they appear. A switch must be declared before it is used, either in statements or in other switch declarations. The switch identifier in a declaration is followed by a list of designational expressions. Examples: SWITCH SWT1 «- L ± , L 2 , L ; SWITCH SWT2 «- L^, SWT1 [I], IF V > 5 THEN L ELSE L^ where I and V are simple variables. The designational expressions are numbered from left to right starting at 1. They are evaluated each time they are selected. If another switch is involved its sub- script value must be a positive integer and not exceed the number of designational expressions in that list. 27 2.2.8 Designational Expressions and GO TO Statements Designations! expressions in TRANQUIL involve labels, switches, and further designational expressions as in ALGOL. They are used in switch declarations and in the following examples in GO TO statements: GO TO FINISH GOTO swr [2] GO TO LJ_ A < 3 THEN CONTINUE ELSE STOP where FINISH, SWT, CONTINUE, and STOP are labels, SWT is a switch, and A is a simple variable. Note that when designational expressions involve if clauses a single logical value must result. Also it should be noted that the destination for a go to statement must not be an interior block. 2.2.9 Statements and Block Structure The block structure of TRANQUIL is identical to that of ALGOL. Hence, the following form is used: BEGIN D; D;....D; END where D represents a declaration and S a statement. 28 2.3 Comparison with Other Languages 2.3.1 ALGOL TRANQUIL has the same general features of ALGOL; i.e., "blocks, compound statements, assignment statements, conditional statements, go to statements, and iterative statements [15]. The conditional statements have "been expanded as discussed in Section 2.2.6, The ALGOL FOR statement appears as the TRANQUIL SEQ statement which has been restructured to incorporate the use of index sets. The SIM statement is an addition following the same format as the SEQ . Together with the SIM statement for parallel specification there are the additional arithmetic, logical and relational operators which can "be used on arrays. Storage mapping functions necessary for proper array storage are a further addition. 2.3.2 MADCAP MADCAP is a language developed to aid a programmer in specifying combinatorial problems [l6]. This obviously involves the use of sets which are denoted either in "tabulated" form, for example, 51 = {0, 3, h, 5, 8, 13} 52 = (r, s, 10, 12} or in "standard description" form, for example, 53 = {x: for i = 5 to 31, x = i} Sk = {x: for n = 1, 2,...,nTn, if N=0(mod n), then x = n} 29 Included with the set when it is introduced is the maximum range of its elements. Further set description can be obtained using the operations of complementation, union, intersection, subtraction, and symmetric subtraction. This is similar to TRANQUIL. Further, these sets can then be used in conditional clauses: if j £ J, . . . if a = b, . . . if a 3 b,... and for iterative statements: for j 6 J In general the index sets are unordered and thus the iterative state- ments are not the same as the TRANQUIL SEQ statement for which sets are considered to be ordered. In this general sense a MADCAP iterative statement is similar to the TRANQUIL SIM statement. 2.3.3 APL A set in APL [17], a mathematically oriented language, is considered to be ordered and is denoted as a vector in which no two elements have the same value. These sets can also be altered using the standard set operators; however, they are not used in the high level control statement fashion of MADCAP or TRANQUIL. Loops must be specified using tests and jumps and set values choosen by indexing through the set. On these sets (or vectors in general for 30 APL only) the operations of cartesian product, concatenation, and end around shift can be used as in TRANQUIL. APL allows the selection of elements of a vector or an array via the use of a pattern of l's and 0«s, for example, if S «- 1, 2, 3, h, 5, 6 and U - 1, 0, 1, 1, 0, 1 then U/S is 1, 3, h, 6. The vector U can be thought of in TRANQUIL terms as a mode word and the result U/S as a set which can be used for index values of an array. This, however, is only one interpretation in APL for U/S can just as easily be considered a vector. It should be noted that U/S only has k values whereas S has 6. Thus, if this method of compression is used to select elements of a vector to be added to similarly placed elements in another and then the sum is to be stored back in S in the positions of the selected elements expansion or masking must be used. In this way one picks out certain elements for an operation and then has to worry about putting the results back in place. For example, let A *- 1, 2, 3, b, 5, 6 B - 2, k, 6, 8, 10, 12 U - 0, 1, 0, 1, 0, 1 C *- U/A + U/B A - /A, U, C/ where the final result in A is 1, 6, 3, 12, 5, l8 and where /A, U, C/ is a mask operation such that A. = A. or C. according as U. =0 or U. = 1„ ill & l l 31 This could also be written in terms of a loop as mentioned earlier. In TRANQUIL the same operation appears as FOR (I) SIM ([2, k, 6]) DO A[I] «- A[I] + B[I] In TRANQUIL implementation the set [2, k, 6] would generally he used in mode form; i.e., 010101, where this mode pattern is used to disable the PEs containing the first, third, and fifth elements of A and B, and not to compress or expand a vector. In comparing the case of using APL with TRANQUIL it should be noted that TRANQUIL is a higher level language than APL. This is of particular importance to users who do not desire to spend hours understanding the various ways that he can program sections of code and then deciding which way is best. Many of these decisions in TRANQUIL are left to the compiler; i.e., the sweep direction through an array being worked on under SIM control. In APL this decision is made by the programmer, in general. 3. COMPILER IMPLEMENTATION OF CONTROL STATEMENTS 3-1 Introduction The syntax of TRANQUIL has been specified in a form which is accepted "by the syntax preprocessor of the Translator Writing System (TWS) being built at the University of Illinois. The preprocessor automatically generates the parsing algorithm for the compiler. In pass 1 of the compiler the recognition of source code constructs invokes calls, via the action numbers embedded in the syntax definition, to semantic actions. These actions build descriptor tables containing, in part, information about declaration types, attributes, and block structure, and transform the source code into an intermediate language form which is composed of operators and operands, the latter being references to descriptor tables. One table of importance is the identifier table (IDTAB). This table contains information about declared variables, arrays, sets, and labels. These entries have associated fields which are shown in Figure 1. A location in IDTAB is reserved when a decla- ration is encountered and thus all declarations for a given block occur in one connected segment. The BFLAG field is used to denote whether the end of the scope of an identifier has been reached. The other fields will be described later or else are described in [13, lM . For identifiers that are declared more than once 32 33 WICIHVA CO "( n [h r K O o a<[AL aiiow m&La IdUD vanvno oraa co o o « CO wichss ad^ias aajiai o CD H ,Q cd -p u 0) •H CM v£> In -P ) use a free space in LDB-2, c) remove a word from LDB-3 in the lowest possible priority group and use the vacated location, d) remove a word from LDB-2 in the lowest possible priority group and use the vacated location. k) If the LINK parameter is zero an LDB location is gotten without pointer connections, the PRIORITY parameter used in choosing a location as in 3) and the MOVECHANGE parameter ignored. Care must be taken in using a zero LINK since unless the returned location is frozen its contents could disappear if another GETLDB or a GETCAR call is made. 5) An LDB location can be frozen, i.e., removed from possible allocation, by FREEZELDBNUM:= number ; FREEZELDB and it can be unfrozen by FREEZELDBNUM:= number j UNFREEZELDB 1+1 6) This procedure uses LOOSECAR. The implementation of LDB allocation utilizes a mock-up of the LDB called CULDB and several fields from the COMSTK mock-up. The fields are: CULDB location 1 2 1 3 k 10 k 12 a b c d e f h i,J I -^ 1 ' v ' # bits g COMSTK location 1 m # bits a: CUCHANGE g: BACKLK b: CUPR h: TABSTK c: FREEZEBIT i: TABSTKPT d: CARLK j : FLDBLK e: BACKLKAREA k: TABLK f: BACKLKPT 1: PRLKUP m: PRLKDN The CUCHANGE bit is used to indicate whether the contents of the word are considered new or old(l or 0, respectively). The CUPR field contains the priority and the FREEZEBIT indicates whether or not an LDB location is frozen. If there is an associated CAR the CARLK contains this number (- ). The BACKLKAREA points to k2 VARIABLE, COMSTK, or DOPETB1 memory with location BACKLKPT ( . . . — ) . TABSTK points to IDTAB, COMSTK, or D0PETB1 with location TABSTKPT (—1 — 1-»). The FLDBLK is used to keep 2 linked lists of free LDB locations, one for LDB-2 and the other for LDB-3. The array USEKPKPT [0:7] is a user priority pointer array, LDB-2 priorities with 0-3 indices and LDB-3 priorities with k—J indices. The allocation and freeing of LDB locations does not in general, take place on a stack basis and priority lists for LDB locations are thus necessary in choosing a word to leave the LDB. The PRLKUP and PRLKDN fields are used for the up and down pointers of this list. 3.2.3.2 INTEGER PROCEDURE GETCAR (PRIORITY, LINK, MOVECHANGE) This procedure selects a CAR register on a priority basis. Further, 1) CAR 0, known as the LOOSECAR, is selected only when USELOOSECAR is TRUE. This CAR is considered by all allocation routines as being free whether it is linked or not. 2) The PRIORITY and LINK parameters are as in GETLDB. 3) If the linked word is in a CAR that CAR number is * Arrows in parenthesis refer to Figure 3« ^3 returned and the CUCHANGE bit is set from the MOVECHANGE parameter. k) If the LINK parameter is zero a CAE is selected without pointer connections, the PRIORITY parameter used in choosing the CAR and the MOVECHANGE parameter ignored. Care must "be taken in using a zero LINK since unless the returned location is frozen its contents could disappear if another GETCAR is used. 5) CARs 1, 2, or 3 can be frozen if they have a priority of 3> i.e., removed from possible allocation, by FREEZECARNUM:= number ; FREEZECAR and they can be unfrozen by FREEZECARNUM:= number ; UNFREEZECAR Only two CARs can be frozen at any time. 6) This procedure uses LOOSECAR. The implementation of CAR allocations utilizes a mock-up of the CAR registers having the following fields: 12 1 CAR register k 10 k a b c d e g h,i -J<. 12 # bits kk a: CUCHANGE f: BACKLK b: CUPR g: TABSTK c: FKEEZEBIT h: TABSTKPT d: BACKLKAREA i: FCARLK e: BACKLKPT j: TABLK The CUCHANGE, CUPR, FREEZEBIT, and TABLK fields are as in the LDB mock-up. The BACKLK field ( ► ) has the added possibility of an LDB register. The FCARLK field is used to keep a list of free CARs. 3.2.3.3 IMEGER PROCEDURE CSPUSH (PRIORITY, PLACE, LOC) This procedure pushes a word onto the compile -time allocated stack (COMSTK). Further, 1) the integer result is the LDB location in LDB-4 that is allocated. 2) The PLACE parameter indicates whether a CAR or LDB location is to be associated with the top of the stack when CARMJM or LDBNUM are used. When this occurs the CAR or LDB location CUCHANGE bit is set on to indicate a new value and the priority is set. Otherwise CSJNUM should be used if just a location is desired. 3) The LOC parameter indicates the place in the CAR or LDB for 2) and if CSMJM is used is ignored. For example , U5 TEMP:= GETCAR(0,0,0); LOC: = CSPUSH(2,CARNUM,TEMP) results in the selection of a CAR that is associated with the top of the COMSTK and which has priority 2. h) No moving is done and thus LOOSECAR is not used. Implementation involves a mock-up COMSTK: COMSTK location k 10 a b . , ) # bits a: CUAREA c: CULOC b: CUPT where CULOC is as described earlier. When LDB-4 is full the lowest element in the stack is moved to the stack extension in memory. 3.2.3A PROCEDURE CSPOP This procedure pops a word from COMSTK with the following possible actions: 1) If the top of the stack is associated with a CAR and/or LDB register, these registers are freed. 2) If more than 1 location in LDB-4 is available stack words in PE memory are loaded into LDB-4 until 1 word in LDB-4 is free or until no words are left 1+6 in PE memory. 3) This procedure uses LOOSECAR. 3.2.3.5 PROCEDURE MOVETOCS (PLACE, LOC) This procedure moves a word in a CAR register or LDB register in area LDB-2 or LDB-3 to the appropriate area, LDB-4 or stack memory. Further, 1) all associated LDB or CAR registers are freed. 2) The move occurs only if the CUCHANGE hit of the CAR or LDB location given hy the parameters is on. 3) This procedure uses LOOSECAR. 3.2.3.6 PROCEDURE MOVETOMEM(LINK) This procedure moves a word in a CAR or LDB register in areaLDB-2 or LDB-3 to the appropriate memory, i.e., variable memory, stack memory, or dope table memory. Further, 1) the LINK points to IDTAB, COMSTK, or D0PETB1 as before. If the CULOC field in the designated table points to its corresponding memory location or the CAR or LDB location has a zero CUCHANGE bit no move occurs. 2) The associated LDB and/or CAR registers are freed. 3) This procedure uses LOOSECAR. hi 3.2.3.7 FREELDB ( NUMBER) This procedure frees the LDB register whose number is given by the parameter NUMBER. An associated CAR, if it exists, is also freed and the freed LDB number goes on the FLDBLK list. 3.2.3.8 FREECAR ( NUMBER) This procedure frees the CAR register whose number is given by the parameter NUMBER. If there is an associated LDB register, its CAR link (CARLK) is severed. 3.2.3.9 INTEGER PROCEDURE GETBIT This procedure allocates a bit in LDB [0]. 3.2.3.10 INTEGER PROCEDURE FREEBIT ( BITNO ) This procedure frees the bit given by the parameter BITNO. 3.3 The Storage and Use of Sets 3.3'1 Introduction Associated with the introduction of sets in TRANQUIL is the task of finding storage schemes which can be used efficiently. The storage schemes must take into account that sets can be used for loop control, for enabling or disabling PEs and for PE indexing. This requires the possibility of representing sets via the use of mode words or explicit numbers. Mode words are 64-bit words used kQ to store the elements of a set by position number, where a 1 in the n-th bit indicates that n corresponds to an element of the set. Further required is the ability to change from one of these forms to the other as the use of a set changes. The decision on a storage scheme must also account for the fact that the order of execution of a program, in general, depends on some run time calculations. This requires keeping track of the present set elements associated with a particular set identifier. Finally, it must allow the reservation of memory space for a set within the block in which the set is declared. This is apparent when one notes that the storage form(s) needed for a set expression associated with a SIM control statement cannot be determined, in general, until the arithmetic or boolean expressions or statements in the scope of the SIM statement have been analyzed in pass 2. 3.3.2 Set Storage Tables The key location for set information is found in the identifier table, in a word having the following fields: Set IDTAB location CO 11 e s Q W CO CO w CO CO CO EH CO s w a fei pq o EH ^9 1) The IDTYPE field contains the SET indicator. 2) The SETYPE field contains the declaration type. 3) The SETDIM field contains the dimension of the set. k) The DYTIAM field indicates whether the range and size specifications are given "by constants or general arithmetic expressions. 5) The SETNUM field contains a distinct number for every declared increment set starting at zero and a distinct number for every declared monotonic or general set also starting at zero. 6) The SETBIAS field is used to denote whether a set is known to have any negative numbers or not. 7) The MOD field indicates if the mode form of storage is desired. 8) The EXP field indicates if the explicit form of storage is desired. 9) The SETLK fields points to further set information in the table called SETTAB. The first 5 fields explained are filled in during the first pass and the remainder are set and used in pass 2 of the compiler. The table SETTAB is an extension of IDTAB for sets and appears as : 50 SETTAB information INCSETLOC 1 |a SAFEMJM— ' ^ SETDESLOC t MAXRANGE } BLKNUM MAXSIZE ) n I I One of the important details in a set storage scheme is the reser- vation of TTJi TAf! IV memory space. When the maximum range (s) and size are constants the compiler can fill in the MAXRANGE field for each of the n dimensions and the MAXSIZE field. This is the only case considered here. Such information allows compile time memory allocation and, further, set density calculations can he made to help determine which way to sweep through an array whose indices are under SIM control. The field labeled (b) in SETTAB is a presence hit for the MAXRANGE and MAXSIZE fields. 3.3.3 A Set Storage Scheme One solution to the memory allocation problem in TRANQUIL requires that at the beginning of a block memory space is allocated in the set storage area (SETSTO) according as to whether a set is declared monotonic or general, in the former case enough space for mode words and in the latter for explicit numbers. Thus, in the program of Appendix D space for the mode word representation of the sets II, KK, and LL are allocated at the beginning of the block in which they are declared. The arithmetic statement in line 19 51 requires LL in mode form and JJ in explicit form. This then requires the translation of mode words into explicit numbers and a place to put these numbers in SETSTO. Space is allocated when this is known, after mode Word space has been allocated for LL. In order to accomplish this an in-use linked list of spaces for each block is kept along with a free list of spaces available for allocation. Additions to the use list are made at block heads and interior points and additions to the free list are made at block ends. The bookkeeping concerning what set is presently valid is carried on in the run-time set descriptor table (SETDES) which for a particular set looks like : SETDES information 1 a b PSAFEPT EXPSTOLOC MODSTOLOC | c MGSAFELOC i 1 n The fields EXPSTOLOC and MODSTOLOC in the first word contain the first location in the SETSTO area for the explicit and mode word representations of a set and fields a and b are their presense bits, respectively. The set storage scheme is amplified so that set definitions involving lists of arithmetic expressions exemplified by 52 [lj 3, -2, 6] [1(2), 3(6)1 can be stored permanently. The area for their storage is called the monotonic-general set area (MGSAFE). Sets stored here are used directly. All other set expressions for non-dynamic sets are allocated space in SETSTO. In SETDES, then, n words contain the addresses of the n set definitions in MGSAFE in the field MGSAFELOC with the 1-st word field PSAFEPT indicating which one of these is valid at any point in program execution, if any. Field c is the MGSAFELOC presense bit for compile-time use. The address in SETDES of a set is found in the SETDESLOC of SETTAB where field a is a presense bit for this location. Also in SETTAB the SAFENUM field contains the number of set definitions to be stored in the MGSAFE area and the INCSETLOC field points to a 2 word block where an increment specification is stored as outlined in the next section. The BLKMJM field in SETTAB allows allocation of space in SETTAB to be associated with the block in which the set is declared. The following section deals with the specific storage representations for 1-dimensional sets in increment, mode, and explicit forms. 53 3«3«^ Increment, Mode, and Explicit Storage Forms and Their Use The increment set (by declaration) is stored using two words per set. One word contains the first element, the increment, and the limit packed for use "by CAR instructions : Increment Limit Base ^ sign hit for increment The other word is a bias value based on zero and is used in the case where negative elements are, or may be, in the set. The base location and table name for these sets is INCSET and for a given set the appropriate two-word block is obtained by multiplying the value in the SETNUM field of TDTAB by 2 and adding the location number INCSET. When an increment set is used for sequential control, CU test and increment instructions operate on the appropriate CAR register. When an increment set is used for simultaneous control, it can be expanded at run time into mode words or explicit numbers and stored in SETSTO. Mode words can be generated from an increment set by using a memory row that contains the PE numbers in ascending and descending order and regular mode patterns similar to the k PE system shown in Figure k. In the figure the mode pattern was formed by considering the b bits to be all ones, the b bits to be alternating zeroes and ones, the b_ bits to be two zeroes alternating with a one, and finally the b bits to be three zeros alternating with a one. In the general 6k PE case, the word in the i-th 5^ 1000 3 1100 1 2 1010 2 1 1101 3 Figure h. Mode patterns and explicit values for increment sets PE is Mode Pattern i 63-i where the 32-bit mode pattern results by considering the b bits to be all ones; i.e., all PEs on when in use, the b bits having the pattern 0101..., the b^ bits 001001..., and the b. bits 0.10.1 where * '2 ill 0. stands for i zeroes. Explicit numbers can be generated using appropriate multiples of the PE numbers plus an addition or sub- traction. Now consider the example of expanding the increment set JJ of Appendix D into mode words and explicit numbers. The set JJ is used simultaneously in forming the comparison set KK by a boolean test on the skewed arrays A and B. For a given I every other element of A, as signified by JJ, is moved to the A register in the PEs using the base address of A that has been brought to the CU data buffer as indicated in Figure 5. Every other element 55 A B X M E M R Y Local data buffer I] [ mode word Base addre ss of A Base addre ss of B • • • • 10000000100101000001001 A CAR register A[0, A[l, A[2, • • 0] 63] 62] • JJ in mode form A[2, 63] B[63, 2] 63 A[0, 1] A[l, 0] A[2, 63] A[0, 2] A[l, 1] A[2, 0] 1 A[2, 1] B[l, 2] 1 A[0, 3] A[l, 2] A[2, 1] • * * 1 A[2, 61] B[6l, 2] 61 A[0, 63] A[l, 62] A[2, 61] • • PE PE, PE, PE, PE 63 A refers to PE registers A. B refers to PE registers B. X refers to the PE index registers Figure 5* General PE and CU picture for line 10 of the problem in Appendix D where 1=2 56 corresponds to the b.. "bit mode pattern, this pattern appearing in the PE mode positions of Figure 5* The case for I = 2 is shown. Every other element of the I-th column of B is moved to the B register. In this case every other ascending PE number is used in the PE index registers (X) with appropriate routing to account for the skewed storage. For I = 2 in Figure 5 > an end around route of two is necessary. Every other element of a column is fetched to the B register again by the use of JJ in mode form. For the explicit representation of JJ to be used in line 19 the ascending PE numbers are multiplied by 2 and then 2 is added to each of these resulting numbers. The mono tonic set is stored originally as a list of mode words together with a header word in the following form: Bias a 1 Number of Words The bias is the first element of the set and the field a indicates whether the set is increasing or decreasing. Anytime mode storage is used this header is used. Similarly for general sets or explicit represention, a header word is used, but this time with the CU increment format where the base and increment are 1 and the limit is the number of elements at present. When either a MONOSET or GENSET is defined using the increment format, 2-word blocks of space are allocated in the INCSET table with the location appearing in the field INCSETLOC of SETTAB. 57 Size restrictions are imposed on the number of words used for mode or explicit storage for non-dynamic sets and if they are exceeded they are treated as dynamic sets. These restrictions are 6h and 512 words, respectively. 3.3.5 Index Set Usage in SEQs and SIMs The routines for outputting code for SEQ loops involves 3 particular cases, when the set is stored in the increment, mode, and general forms. The increment form was discussed in the last section. The selection of loop values from mode forms is accomplished via leading ones detection with adjustments for the "bias while for the explicit form the loop values are simply loaded into the CU from set storage. For example, the sets II and KK in Appendix D are examples of monotonic sets and are stored in mode form with no "bias value in these particular cases. For looping on II the CU does leading ones detection on the II mode pattern, illustrated in Figure 5> "to determine the explicit set elements used in the CAR as CU indices for array A, and KK is used in mode form in the PE mode registers under simultaneous control. The header words aid in this task in an obvious manner and the CU stack is used to store intermediate calculations. If a loop is not left via its natural completion adjustments are made to finsure the proper CU set-up. In order to keep track of the control variables associated with the sets in a SEQ or SIM statement a variable stack (VARSTACK) 58 is used. This stack has the fields: VARSTACK ■ ' *. -YARD IV SEQREL VARLINK The VARDIV field indicates the number of control variables in a SEQ. or SIM statement. The SEQREL field is used in determining for a SEQ, statement with more than one set whether there is SEQ, within a SEQ or just a single SEQ. This is determined via whether the associated sets appear with the cross product or the pair operator, respectively. The VARLINK field points to the corresponding TDTAB position for the control variable. For SIM control statements information is stored in a stack (VSSTACK) concerning the relationships between sets. The format is illustrated together with an example. FOR (I, J) SIM (II, JJ) DO FOR (K) SEQ (KK) DO FOR (L,M) SIM (LL,MM) DO FOR (N) SIM (M) DO where all the sets are 1-dimensional results in: 59 VSSTACK 1 / / / 1 II / 2 1 JJ 2 LL 1 2 MM f 1 m „ > K * — j VSBLOCK SETREL SETADR The VSBLOCK field indicates the number of VSSTACK entries per SIM via the non-zero integers where integers m greater than 1 indicate the occurence of ra-1 SEQ statements. The SETREL field indicates the relations between the sets via groups. If there is a zero in this field the single set is considered a group while if some integer appears here the associated set belongs to that numbered group. Thus the pairs II, JJ and LL,MM form a group. The SETADR field contains the associated set address in IDTAB. Returning to IDTAB, the control variables associated with SIM control have the VARSET field which contains a pointer to VSSTACK and the VARDIM field which contains the associated dimension. The VARLIWK field is VARSTACK is used to zero these fields at the end of a SJM statement. The use of VSSTACK and these IDTAB fields is discussed in [ 13] • 6o In closing this section is should be noted that little has been said about sets with dimension greater than 1, i.e., PATSET s. The reason for introducing these sets was to allow the user the ability to work on scattered elements of an array which is otherwise not possible. For example, the 2-dimensional mode pattern: 10 1 111 10 1 10 can be used to work on elements of the following array which are marked : X X X X X X X X PATSETs are stored always in mode patterns which is possible since repeated elements are not permitted in defining these sets. 3.3.6 Mode Pattern-Explicit Word Conversion The conversion of explicit numbers to mode patterns can be accomplished in parallel at run time by having each PE turn on the bit corresponding to the set number it has. For each 64-bit mode word the range of explicit elements is set at 6k and the mode bits are set only after the explicit numbers have been properly scaled. The parallel run-time conversion of mode words into explicit numbers is done, however, less efficiently. This is 6l because only those PEs with mode bits on will contain set elements after using appropriately the PE numbers, thus leaving intervening PEs with no set elements. It is then required to pack these explicit numbers and as the number of gaps increases so does the number of routes and time to do this. h. CONCLUSIONS AND SUGGESTIONS There are a number of additions that should be considered for TRANQUIL with regard to control statements. These include the introduction of procedures and Burrough's case statements. It would also be useful to be able to specify the sweep direction through an array whose indices are under SIM control such as in line 22 of Appendix D. For example, to sweep by rows one could write FOR (I*,K) SIM (HxKK) DO Further, in such control statements the use of parentheses would allow the user greater power in grouping the sets after the word SEQ, or SIM . Also with the addition of input-output statements should come the ability to read in sets as data. The work that has been done with regard to sets has centered around 1-dimensional non-dynamic sets. Further work in the area of developing a scheme to handle dynamic sets is necessary. This is designed to be, in general, an extension to the facilities and tables presently available. The CU allocation schemes need to be expanded to allow for run-time space allocation. this again is designed to be an extension of what already exists. 62 6 3 APPENDIX A METALANGUAGE FOR SPECIFYING SYOTAX The TRANQUIL syntax in Appendix B is specified in a form of BNF which is extended as follows: 1) Kleene star: < A >* =<> | | | ... where < > represents the empty symbol 2) Brooker and Morris' question mark (here &) : < A > & = < > | 3) List Facilities list =* list < A > separator = []* k) Brackets ::=[ | |] is equivalent to : := < R > < D > ::=|| 5) Metacharacters: A sharp (#) must procede each of the following characters when they belong to syntactic definitions: #, U, *, ;, <, >. 6k In the syntax < * I > is used to designate an identifier and < * N > is used to designate a number. Further, the special words in the language are capitalized and underlined. 65 APPENDIX B TRANQUIL SET AND CONTROL STATEMENT SYNTAX B.l Statements < PROGRAM > : : = < BLOCK > < BLOCK > : : = BEGIN list [< DECLARATION > # ; ] list < STATEMENT > separator # ; [# ; ] & END; < STATEMENT > : : = < NONEMPTY STATEMENT > | < > ; < NONEMPTY STATEMENT >::=[<* I > : NOT =] * [ < CONTROL STATEMENT > | GO TO < DESIGNATIONAL EXPRESSION > BEGiEN < STATEMENT > END | < BLOCK > | < IF CLAUSE > < STATEMENT > [ ELSE < STATEMENT > ] & | < ASSIGNMENT STATEMENT > ] ; B.2 Control Statements < CONTROL STATEMENT > : := FOR (< SET VARIABLE LIST >) [SEQ, | SIM] (< SET NAME LIST >) DO < STATEMENT > | FOR (< SET VARIABLE LIST >) SEQ (< SET NAME LIST >) WHILE < BOOLEAN EXPRESSION > DO < STATEMENT > | < SIM BLOCK > ; 66 < SET VARIABLE LIST > : := list < * I > separator, ; < SET NAME LIST > : : = list [< * I > | < SET DEFINITION TAIL, > ] E # * ] & separator [ , | X ] ; < SIM BLOCK > : : = SJM BEGIN list < ASSIGNMENT STATEMENT > separator # J [# ; ] & END ; B.3 Sets B.3-1 Declarations < DECLARATION > : : = { INCSET | MONOSET | GENSET | PATSET} list < SET SEGMENT > separator , ; < SET SEGMENT > : : = list < * I > separator , [ (< * N >) ] & |_ # [ list [< ARITHMETIC EXPRESSION > [: < ARITHMETIC EXPRESSION > ] &] separator, f\ | & B.3.2 Definitions < SET DEFINITION TAIL > : : = # [< LIST SET > #] | < COMPARISON SET > ; < LIST SET > ::= [, < ELEMENT >,..., < ELEMENT > | , < ELEMENT > ] * | < > J < ELEMENT > : : = #[ list < ARITHMETIC EXPRESSION > separator , # ] | < ARITHMETIC EXPRESSION > [ ( < ARITHMETIC EXPRESSION >)] & J < COMPARISON SET > : : = SET # [ list < * I > separator , < BOOLEAN EXPRESSION > #] ; 67 B.3.3 Set Assignment Statements < ASSIGNMENT STATEMENT > : : = < BOOLEAN ASSIGNMENT STATEMENT > | < ARITHMETIC ASSIGNMENT STATEMENT > | < SET ASSIGNMENT STATEMENT > ; < SET ASSIGNMENT STATEMENT > := list [< SET IDENTIFIER > [ *- | : = 3 1 < SET EXPRESSION > ; < SET EXPRESSION > : : = < SIMPLE SET > | < IF CLAUSE > < SIMPLE SET > ELSE < SIMPLE SET > ; < SIMPLE SET > : := < SET PAIR > [ < SET PAIR > ] * | REVERSE < SET PAIR > ; < SET PAIR > : : = < SET UNION > [ PAIR < SET UNION > ] * ; < SET UNION > : : = < SET INTERSECTION > [ [ UNION | DELETE | SMD | CONCAT J < SET INTERSECTION > * ; < SET INTERSECTION > : : = < SET FACTOR > [JNT < SET FACTOR > ] * ; < SET FACTOR > : : = < SET OFFSET > [COM < SET OFFSET > ] * ; < SET OFFSET > : : = < SET PRIMARY > | < SET PRIMARY > [+ | - ] < ARITHMETIC EXPRESSION > ; < SET PRIMARY > : = < SET IDENTIFIER > | (< SET EXPRESSION <) CSHIFT (< SET EXPRESSION >, ) < SET DEFINITION TAIL > ; 68 B . U Switch and Label Declarations < DECLARATION > : : = LABEL list < * I > separator , | SWITCH < * I > [*- | : = ] list < DESIGNATIONAL EXPRESSION > separator , ; B.5 Designational Expressions < DESIGNATIONAL EXPRESSION > : : = < SIMPLE DESIGNATIONAL EXPRESSION > | < IF CLAUSE > < SIMPLE DESIGNATIONAL EXPRESSION > ELSE < DESIGNATIONAL EXPRESSION > ; < SIMPLE DESIGNATIONAL EXPRESSION > : : = (< DESIGNATIONAL EXPRESSION >) | < SWITCH IDENTIFIER > # [ < ARITHMETIC EXPRESSION > # ] | < LABEL IDENTIFIER > ; B.6 IF Clauses < IF CLAUSE > : := IF < CONTROL HEAD > & [ANY | ALL] & < BOOLEAN EXPRESSION > THEN | IFSET < BOOLEAN EXPRESSION > THEN ; B. 7 Global Operators < ARITHMETIC EXPRESSION > : : = < GLOBAL PRIMARY > J < GLOBAL PRIMARY >::= [FOR (< SET VARIABLE LIST >) SIM (< SET NAME LIST >) ] & [SUM | PROD | GOR | GAND | MAX | MIN J < ARITHMETIC EXPRESSION > ] ; 69 APPENDIX C AN INTUITIVE LOOK --- THE TRANSLATION OF FORTRAN INTO TRANQUIL The translation of FORTRAN into TRANQUIL requires the detection of implicit parallelism in FORTRAN and its explicit representation in TRANQUIL. The explicit loops in FORTRAN such as DO 12 1=1, 100 and the implicit loops involving the IF statement are possible indicators of potential parallelism. C.l Essential Ordering The question immediately arises in the survey of loops in search for parallelism as to what the essential ordering of the statements enclosed is. If this can he determined unnecessary calculations can be removed from a loop and information is then available for optimizing code, for determining more efficient schemes for memory usage, and for parallel detection. A possible method for determining the essential ordering is illustrated for a set of assignment statements involving variables TO A = B + C B = D + E E = A A = B + D C = D + F Forming an assignment matrix T = [t. .] where ID t. . = ID 1 if the variable j is on the right hand side, where i is on the left hand side otherwise yields A B E A C D F 1 1 1 1 1 1 1 1 1 A B E A C and taking the transpose of the square section and ORing it with the original square section results in: A B E A C A B E A C 1 1 1 1 1 1 1 1 1 1 1 1 Now removing all ones except those most closely surrounding the diagonal one gets: A B E A C A B E A C 1 1 1 1 1 1 1 71 The result is that in each row the ones enclose the range of each statement. In this example the 5-th statement can be interchanged with either the 2-nd, 3-rd, or U-th statements. The further questions concerning consideration of the total effect of a number of order changes and the incorporation of indices are opened by Kuck [l8]. C.2 Translation Decisions In TRANQUIL Parallelism can be explicitly stated using the SIM control statement, where each statement Sj_ in its scope is executed using the data available before any part of is executed. In examining, in particular, a FORTRAN DO loop a decision must be made as to whether a SIM control statement can be used to replace the DO, this task requiring knowledge about essential ordering. Consider the example of matrix multiplication: DO 20 I = 1, 200 DO 20 J = 1, 20 C[I, J] = DO 20 K = 1, 300 20 C[I, J]: = C[I, J] + A[I, K] * B[K, J] The possibilities that exist without considering the arithmetic are 8 in number ( SIM or SEQ for each DO). How, then, does one rule out SIM execution? The first criterion is whether a statement in the scope of the loop can be done in parallel as deter- mined from statement and context analysis. This is the case for both statements of the routine if I and J are run simultaneously and K 72 sequentially. The next criterion is relating the storage structure of the arrays involved. Again in the example we are content if matrices A, B and C are stored straight or skewed. A last criterion for the present is the size of the index sets associated with the control variables. In the example, since I is associated with a set of 200 elements and J with a set of only 20 elements one chooses to run I simultaneously. Thus we have the following TRANQUIL program segment : II := [1, 2,..., 200]; JJ := [1, 2,..., 20]; KK := [1, 2,..., 300]; FOR (I) SIM (II) DO FOR ;. J) SEQ, (JJ) DO BEGIN C[I, J] - 0; FOR (K) SEQ (KK) DO C[I, J] «- C[I, J] + A[I, J] X B[K, J].; END It should be noted that mere replacement of sequential loops by parallel ones is not enough. In the following program I can be run simultaneously and J sequentially for the 1-st statement and J can be run simultaneously only for the 2-nd. 73 DO 15 I DO 15 J A[I, J] 15 C[J] = 1, 200 = 20, 60 := B[I, J] + A[I, J-l] := C[J-1] It should also be noted that the last statement can be done in parallel because of the routing capabilities of ILLIAC IV. Another more complicated program may further illustrate what to watch for in translation. The table look-up problem involves a table like the one below with value ordered temperatures and pressures as the co-ordinates. h p 5 P 6 P 7 1 5 21 2 6 22 3 23 h 2k The task is to find out what area an experimental points falls in. A procedure to solve this simply involves noting when a test value TT becomes less than a table value where the table values are checked in ascending order (see [19]). A FORTRAN IV program to do part of this for 256 points is Ik DO 30 J = 1, 256 DO 20 I = 2, 5 IF (TT[J] < T[I]) GO TO 25 20 CONTINUE 25 A[J] := (1-1) * h 30 CONTINUE Note the exit from the inner loop on test completion. The first questions are can TT[j] < T[l] be done simultaneously for I and J in the context of the loop it is in and can A[j] := (i-l) * k be done simultaneously. In the latter case I is not a subscript and thus I is out of the running for this statement. Now we note that the transfer out of the inner loop can be taken care of by mode setting via index sets on ILLIAC IV and that since I is so small we do not run it simultaneously for the 1st statement either. Thus J can run simultaneously over both statements if A and TT are stored across ILLIAC IV memory. We can develop the following TRANQUIL program segment : 75 II - [2, 3,..., 5] JJ <- [1, 2,..., 256] FOR (I) SE& (II) DO BEGIN FOR (J) SIM (JJ) DO BEGIN SS ^_SET[J: TT[J] < T[l]]; for (s) sm (SS) DO A[S] - I; IFF OR AM TT[J] > T[l] THEN SETEMP «- SET[J: TT[J] > T[l]] ELSE GO TO TTEND; END ; JJ <- SETEMP; END ; TTEND: A[JJ] «- (A[JJ] - l) X h It is clear that the problem of translating a serial language like FORTRAN into a parallel language like TRANQUIL involves close inspection of statement relationships, control, storage schemes, and machine capabilities as in the examples above. 76 APPENDIX D A SAMPLE TRANQUIL PROGRAM BEGIN REAL SKEWED ARRAY A, B[0 :100,0 :100] ; INCSET JJ; MONOSET Ilfl)f27:61, KK(l)[lOO:60] ;' INTEGER I,J,K,Lj II «- [2, 10, 13, 21, 2U]; JJ - [2, 1+,..., 98]; FOR (I) SEg (II) DO BEGIN FOR (J) Sffl ( Jj) DO KK *- SET ( J:A[I, J] < B[I, J] ) ; FOR (K) SIM (KK) DO A[I, K] - A[I+1, K] + B[I, K+l] END ; BEGIN ; MONOSET LL [50:50]; REAL STRAIGHT ARRAY C[0 :100,0 :100] ; LL - [1, 2,..., 1+9] FOR (L, J) SLM (LL,JJ) DO C[J, L] *- C[J, L+l] + C[J+1, L] END ; FOR (I, K) SIM (II X KK) DO A[I, K] «- A[I+1, K] + B[I, K] END END APPENDIX E GENERAL FDCW CHARTS FOR THE TRANQUIL COMPILER 77 o Program The TRANQUIL Compiler Scanner - Table Driven Recognizer Pass 1 Semantics Intermediate Language Code Pass 1 Optimization Intermediate Language Code Pass 2 Procedure EXEC2 Assembly Language Assembler Machine Language Loader ILLIAC IV From a Program to ILLIAC IV via the TRANQUIL Compiler 78 O perators Use Operators to Call Appropriate Semantic Actions Allocation of Set Storage Code Generation for SEQ and SIM Statements Code Generation for IF Statements Allocation of Array- Storage Operands i Branch on Context, Identifier Type, or Operand Type I Preparation for Operator Actions Code Generation for Arithmetic Expressions Code Generation for Set Expressions Code Generation for Boolean Expressions General Simplified Structure of EXEC2 79 LIST OF REFERENCES [l] Gosden, J. A., "Explicit Parallel Processing Description and. Control in Programs for Multi- and Uni- Processor Computers/' 1966 Fall Joint Comp. Conf., AFIPS Proc , vol. 29. Washington, D.C. : Spartan, 1966 , pp. 651-660. [2] Bernstein, A. J., "Analysis of Programs for Parallel Processing," IEEE Trans. Electronic Computers , vol. EC -15, PP- 757-763, October 1966. [3] Opler, A., "Procedure-Oriented Language Statements to Facilitate Parallel Processing," Comm. ACM , vol. 8, pp. 306-307, May 1965- [h] Anderson, J. P., "Program Structures for Parallel Processing," Comm. ACM , vol. 8, pp. 786-788, December 1965. [5] Wirth, N., A Note on "Program Structures for Parallel Processing" by Anderson, Comm. ACM, vol. 9, pp. 320-321, May 1966. [6] Constantine, L. L., "Control of Sequence and Parallelism in Modular Programs," 1968 Spring Joint Comp. Conf ., AFIPS Proc, vol. 32. Washington, D. C,: Thompson Book Company, 1968, pp. U09-U1U. [7] Karp, R. M. and Miller, R. C, "Properties of a Model for Parallel Computations: Determinacy, Termination, Queuing," IBM Watson Research Center, Yorktown Heights, N. Y., RC-1285, September 196k. [8] Martin, D. C and Estrin, G. , "Models of Computational Systems - Cyclic to Acyclic Graph Transformations," IEEE Trans . Electronic Computers , vol. EC-16, pp. 70-79, February 1967. [9] Bingham, H. W., Fisher, D. A., and Simon, W. L., "Detection of Implicit Computational Parallelism from Input-Output Sets," Technical Report EC0M-02U63-1, Burroughs TR-66-4, AD6U5^38, Paoli, Pennsylvania, December 1966. [10] Bingham, H. W. and Reigel, E. W., "Parallelism in Computer Programs and in Machines," Technical Report ECOM-02463-6, Burroughs TR-68-1, Paoli, Pennsylvania, April 1968. [11] Bingham, H. W., Reigel, E- W. , and Fisher, D. A., "Parallelism in Computer Programs and Multiprocessing Machine Organizations," Technical Report ECOM-02^63-5, Burroughs TR-67-6, Paoli, Pennsylvania, January 1968. 8o [12] Kuck, D. J., "ILLIAC IV Software and Application Programming," IEEE Trans, on Computers , vol. C-17, pp. 758-770, August 1968. [13] Budnik, P., "TRANQUIL Arithmetic," M.S. Thesis, Dept. of Computer Science, University of Illinois, January 1969* [lU] Muraoka, Y., "Storage Allocation Algorithms in the TRANQUIL Compiler," M.S. Thesis, Department of Computer Science, University of Illinois, January 1969* [15] Naur, P. (Ed.), "Revised Report on the Algorithmic Language ALGOL 60," Comm. ACM , vol. 6, pp. 1-17, January 1963. [l6] Wells, M. B., "Aspects of Language Design for Combinatorial Computing," IEEE Trans. Electronic Computers , vol. EC-13, pp. I+31-I+38, August 196I+. [17] Iverson, K. E., A Programming Language . New York: Wiley, 1962. [18] Kuck, D. J., "Trip Report," Department of Computer Science, University of Illinois, August 1, 1968, ILLIAC IV (unpublished) . [19] Wilhelmson, R., "Table Lookup Problem and Solutions," Department of Computer Science, University of Illinois, March 19&7* ILLIAC IV Doc. 113 (unpublished). UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA -R&D (Security claatltlcatlon ol till; body ot abatrmet and In towing annotatio n muat ba anlarad mrhan tha overall report la cla*»Hlad. ORIGINATING ACTIVITY (Corporal* author) Department of Computer Science University of Illinois Urbana, Illinois 6l801 2*. REPORT SECURITY CLASSIFICATION UNCLASSIFIED 2b. a roup REPORT TITLE CONTROL STATEMENT SYNTAX AND SEMANTICS OF A LANGUAGE FOR PARALLEL PROCESSORS DESCRIPTIVE NOTES (Typa of raport and Inclualra dataa) Research Report AUTHOR(S) (Flrat naata, mlddta initial, laat nama) Robert B. Wilhelmson REPORT DATE January 13, 1969 7a. TOTAL NO. OF PACES 86 7b. NO. OF REFS 19 •. CONTRACT OR CRANT NO. •a. origin; 46-26-15-305 PROJECT NO. USAF 30(602)1+11+1* DCS Report No. 298 ftb. OTHER REPORT NO