1*H ; ; ;' & 1 X I B R.AR.Y OF THE U N IVLRSITY Of ILLINOIS 510.84 iJfcr cop 2. The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN MAY 111979 MAY 3* ■jun v iq MAY 041938 L161 — O-1096 Digitized by the Internet Archive in 2013 http://archive.org/details/websystempartiif232bond Report No . 232 f 6/J ■ i t coo-1018-1118 THE WEB SYSTEM PART II* A Formal Description of the WEB Input Language by W. D. Bond E. S. Davidson B. H. McCormick June 19, 1967 w * imm of r//£ WG 30 i%7 Report No. 232 THE WEB SYSTEM Part II* A Formal Description of the WEB Input Language by W. D. Bond E. S. Davidson B. H. McCormick June 19, 1967 Department of Computer Science University of Illinois Urbana, Illinois 6l801 ^Supported in part by Contract AT(ll-l)-10l8 with the U.S. Atomic Energy Commission and the Advanced Research Projects Agency 1. INTRODUCTION It is the intent of this report to describe the input language for the WEB design automation system. An attempt has been made to keep the definition of the input language flexible. Accordingly, the input language should be applicable to design automation in widely differing technologies. Yet the language is sufficiently specific as to be presently useful for printed circuit construction. The description of seemingly different types of input data needed for design automation has been kept syntactically similar wherever the problems of accurate specification were sufficiently analogous, even though the elements so described bear little or nothing in common. Thus, features may be found in the language for which the reader may have little immediate applicationo These features have been included either because they were required for some known application of the language, or because it was felt that future trends in computer technology might make these features desirable, or to preserve a certain symmetry in the definition of the language. In such cases precautions have been taken so that these features can be easily ignored by the user who has no current interest in using them. It is not anticipated that the description of the WEB input language, as given here, will be used as an initial introduction to the language. Rather, a concise description is attempted for reference purposes. For an initial introduction, the reader is referred to Part I of the WEB System: A Language to Describe the Interconnection and Packaging of Logical Units in a Digital Processor . The WEB input consists of: (1) A Logic Description , in which the logic of the system is described. Starting with the irreducible packag- able logic units, block structure is used to define more complex system components in terms of previously defined ones. (2) A Housing Description , in which connector geometries are described. Also using block structure format, more complex housings are defined in terms of arrays of pins. (3) A Module Description , which might more generally be called a pluggable unit description, describes pluggable units (e.g., boards) in terms of their constituent logic units and the terminals to which they are connected. (U) An Assignment Description , in which the packageable logic units are assigned to constituent logic units 1. J. H. Hazelhurst, B. H. McCormick and W. D. Bond, Department of Computer Science Report, University of Illinois, in progress. This report supercedes DCS File No. 625, Revised February 10, 1965 of modules, and the modules (boards) are assigned actual locations in the housing. As the main text of this paper is essentially a semantic description of the WEB language, the syntax found in section 6 should be read in conjunction with the text. Accordingly, throughout the text, underlined phrases correspond to major syntactic variables found in the syntactic description of WEB. 2. LOGIC DESCRIPTION The logic description consists of a sequence of block defi- nitions, each of which may be preceded by a title or drawing statement. The title statement provides descriptive comment on the data being processed. Each title statement causes a new page to be started in the listing of the input description, and all subsequent pages will bear this title. The purpose of the drawing statement is to reference, by name, files kept elsewhere which contain drawings or other information pertinent to the data being processed. A block definition defines a new block in terms of previously defined sub-blocks. If for some reason it is desirable to give a previously defined block a different name, a simple equivalence statement may be used rather than duplicate the entire definition. Initially there are no predefined blocks. Hence one must first define all lowest level blocks by the use of unit descriptions . Accordingly, the unit description is given for each irreducible package- able unit. After the units have been defined, higher level blocks are given block descriptions . Block descriptions differ from unit descriptions in that they contain listing and interconnection of component sub-blocks (units are lowest level blocks) and the reserved word BLOCK is used rather than UNIT. A block description need not have a block identifier, in which case it is an "unnamed block" and cannot be used in the construction of higher order blocks. New blocks can only be constructed by using previously defined named blocks: hence, all unit descriptions must have a unit identifier. The terminal list is an ordered list of signal names. The choice of actual names used is immaterial except as these names have meaning to the user. A judicious choice of names, however, will enable the user to make opportune use of the iterative properties afforded by the FOR clause. The signal names occurring in a terminal list have different connotations, depending on whether the terminal list occurs in the heading of a block description or as part of a component sub-block. The distinction is entirely anologous to that of formal (dummy) parameters versus actual (calling) parameters as used in sub-routines and macros. That is, let (actual) signal name oc occur in the ith position of the terminal list of a component sub-block with block name p and let (formal) signal name y occur in the ith position of the terminal list of the block description with block identifier (3 . Then each occurrence of the signal name y in any sub-blocks of the block description of (3 is to be replaced by signal name a. when the logic description is eventually expanded. Terminals renamed with the same signal name are electrically common. Each signal name occurring in a block component of a named block, which does not occur in the terminal list of the block, is treated as a local actual signal name. Such a signal name is treated as a global actual signal name in the case of an unnamed block. Embedded in the definition of signal element may be found simple identifiers and identifiers subscripted with one or more sub- scripts, as well as provision for coordination (identifiers with periods between them) for identifying parts of a tree containing either a single final node or an ordered set of final nodes, each of which ultimately becomes a signal element of the terminal list. It is for this latter purpose that a subscript may be a pair of integer expressions sepa- rated by a colon, e.g., "a:b", which means "from subscript a to sub- script b 'inclusive'". Signal group declarations are required if efficient use is to be made of the coordination facility, as well as to specify a sequence of signals by one signal name expression. The declaration is local to the block or unit in which it occurs. An identifier is used to give an overall name to the signals (or subscript ranges) contained in the set of parentheses immediately following it, or, if there is no set of parentheses, the identifier is simply a signal name. Integers (or pairs of integers separated by colons) separated by commas indicate allowed ranges on subscripts. The allowed range is 1 to a for the single integer "a", and a to b for the pair a:b. An integer, n, enclosed in parentheses which occurs in a sequence of signal groups merely reserves n as yet unnamed places. This is a distinction not to be overlooked, as Abercrombie (8,5,2) declares 8*5*2 = 80 signals, whereas Fitch ( (8), (5), -(2) ) declares only 8 + 5 + 2 = 15 signals. Finally, the occurrence of "*" followed by an integer, n, is an iterative operator, and iterates n times the signal group enclosed in parentheses immediately preceding it. The block components form a listing of the constitutent (previously defined) block names with their terminal lists. The block components, of course, are the elements used to determine the structure of the block being defined. For clauses may be used to iterate over block components as well as within terminal lists. Iteration takes place on the elements between the DO and matching END. Nesting is permitted. The block identifer may be repeated, if desired, after the END of a block definition, to improve readability. 3. HOUSING DESCRIPTION The housing description consists of a sequence of array definitions, each of which may be preceded by a title or drawing statement. There are two types of packaging modules: the connector and the more complex cell . Accordingly, an array definition is either a connector description, or a cell description, or possibly an equivalence statement if it is desirable to give a previously defined array a different name. In the simplest case, a connector description may be used to describe a two-dimensional array of pins. The generalization of this is to allow a connector to be described in terms of previously defined connectors. As in the case of logic blocks, a connector de- scription must include a connector identifier if the connector is to be used in the definition of higher order arrays. The main body of the connector description is a sequence of array components, which determines the basic make-up of the connector being described. The purpose of the sequence of array components is twofold: to describe the array in terms of distances between its elements both horizontally and vertically; and to define a nomenclature wherewith the elements can in fact be named. The array vector lists the array elements for a horizontal row of the array. Each array element, however, may actually represent more than one physical element of the eventual array row- The fixed point constant which may occur between array vector definitions correspond to the vertical spacing between successive rows of the array. The fixed point constant which may occur between array nomenclature expressions corresponds to the horizontal distance between successive elements in the array vector. These distances re- main in force until a new spacing definition occurs. If a connector array is made up of connectors other than pins., the connector to be used as a particular element is specified by an array identifier labelling that element. Like distances, array identifiers remain in force until a new identifier is encountered. A FOR clause may be used to modify the integer expression part of an array nomenclature expression. FOR clauses may iterate sequences of array elements as well as sequences of array components. As with block components, possibilities for nesting FOR clauses are quite broad. As array nomenclature expressions consist of any alphanumeric character string with optional additive integer expressions, a rule of addition (subtraction) must be defined by any particular implementation of WEB to give definite meaning to an expression such as A5B + 17 which might arise in the iteration of a FOR clause. One rule of addition which would seem to have widespread application would involve defining an alphabetic sequence (eliminating undesirable characters, e.g., 1,0) and a numeric sequence. A character position in the nomenclature would be either alphabetic or numeric as defined by the augend. When the end of a sequence is reached, a carry is propagated and the beginning of the sequence is returned to for that position; in other words, radix addition with a radix scheme based on alphabetic and numeric characters. Further rules would be specified for overflow* underflow, etc. The cell description may be more complex than the connector description in that cells may possess two types of connectors: external connectors and internal connectors. As usual, a cell must be named to be used in the construction of higher order cells or connectors. The connector identifier specifies the optional external connector of a cell. It is this connector which is used by higher order structures using the cell in their construction. In addition to the external connector, the internal connector of a cell is specified by means of a sequence of array components. A part of this internal connector must be identified with the external connector by having the same nomenclature. The remainder of the internal connector is made up of other connectors corresponding to external connectors of yet more cells, or connectors corresponding to those of the modules (i.e., pluggable units). The distinction between external and internal connectors of a cell is thus quite similar to that of global and local signal names of the logic description. It should be observed that connector and cell descriptions may be used in any order to build a complex structure. That is, although the cell is more complex than the connector, it is not of higher order. When a pin of a complex structure is to be named, probably the simplest name is the concatenation of the nomenclatures of the connectors, of progressively lower orders, until the pin nomenclature has been uniquely identified. 10 By way of example, a mother board containing integrated circuit connectors (not wired to those on another board except through the use of an intermediate connector) is a cell. The Illiac III backpanel is a second order connector made up of first order connectors into which boards are inserted. Cabling between backpanels can be treated by making a backpanel an internal connector and a cable connector {or set of cable connectors) an external connector of a cello At a higher order of description, the I3M System 36O models 50 and 75 in the ASP configuration could be described by making the model 50 and model 75 internal connectors of different cells, while describing the data paths between them in terms of external connectors of these cells. 11 k. MODULE DESCRIPTION The module description essentially consists of a sequence of available modules, each of which may be preceded by a title or drawing statement. The module description is used to describe each module type to be used. Logic units described in the logic descrip- tion are to be assigned to the units of the module. Each such module unit has a pin list, the elements of which correspond in order to the elements of the terminal list of the logic unit which are to be assigned to it. The pin list consists of the nomenclature of the pins as given by the first order connector to which the module may be assigned. FOR clauses may be used for iteration within pin lists as well as to provide iteration over a sequence of modules, modifying the pin nomenclature at each iteration. 12 5- ASSIGNMENT DESCRIPTION The assignment description consists of a module assignment and a unit assignment. The module assignment is used to assign previously defined modules to first order connectors in the housing. Each assign component consists of the name of a module followed by the list of first order connectors to which the module is to be assigned. The first order connectors are named by the concatenated nomenclature from the highest order connector, in decreasing order, to the position which the first order connector occupies in the second order connector. (Concatenating the pin name of the module description to this connector name yields a complete pin name as indicated in section 3«) FOR clauses may be used to modify connector nomenclature expressions to assign a module or set of modules in any regular pattern. The unit assignment is used to assign the units of the logic description to the housing, where they are matched with the units of the modules assigned to the housing. As the logic description is expanded, each logic unit description is assigned an index number by which it is referred for the unit assignment. The array nomenclature expression in the fill component refers to the nomenclature of a first order connector to which the unit is to be assigned. 13 Since the module assigned to a connector will in general have more than one unit, the unit's module position expression is necessary to determine which unit of the module is to correspond to the logic unit being assigned. The module position of a unit refers to the sequential numbers given in the order of occurrence to each of the modules, and hence, module units. Ik 6. SYNTAX OF THE WEB LANGUAGE Certain syntactical symbols not normally present in BNF are used in the syntax given here. The symbols essentially abbreviate common groupings of BNF statements, and the transformation between these symbols and regular BNF is obvious. The symbols and their in- terpretation are as follows: [ ] entry enclosed is optional entry enclosed is optional or may be repeated as desired. In terms of Kleene's star, J_ A J_ = A* entry enclosed may be repeated as desired. In terms of Kleene's star, [_Aj = AA* {A|B} exactly one of the symbols A and B may occur 15 A A d d o o •H •H -P -P Q- Qa •H •H rH 5h CJ CJ 00 oo tJ Td bO -P a Sd •H CD 00 & d d O bO w •H V co 03 • »N < V o s • *\ M CO EH p fe o W W § A C3 sd H o CO ■H CO -P < a •H A In sd CJ o oo •H (LI -P -d a ■H u SH •H CJ bO 00 o Td • »\ H 3 o Td H o O 9 h! • o\ , — , A CO -p EH G H i g 1 o W o iJ V m < *\ a pq Cs O & h) J Ph 4 A -P 3 Cb c •H =1 A sd o •H -P ■H sd •H •rH -d Pi H a 1 V W V 4 4 A A e cd cd o sd •H -P bD •H sd sd •H •H s •H 53 cr W V A -p oo ■H rH H cd id •rH s rH EH V 1 1 A ■\ a o Eh ■H H -P H cd 5 rH cd H o A rH 13 •H COj

CO t_— I h S3 S3 cd HI bO A bO V •H Sh cd CO CD -p * V ^"* s bO (D S3 ^-^ ^ — 1 P S3 V A i — | A H e , Ch Ch v d A 2 | , ,^— s o Sh O . t Sh CD M A A bO •H bO A u M ch h CD CD H ■H H CD bO bO CO P 1 cO •H CD CD S3 S3 S3 ch -P -p bO CD bO ■H S3 S3 •H TJ •H +3 H n CO H CO S3 V V V V V CD T3 H V — 1 4 A Da 3 o Sh bO H cO S3 bO •H CO V p s W =1 A -p S3 • «\ CD S3 A O -p CU w 6 ■H o H o H ^j cO CJ S3 o •H H s pq Ph V CD &H _J V =j •N A CD A w (V 3 B cO cO H S3 o M P4 o O o H C P3 V 4 A -p S3 CD S3 O Pj s o o ^ o o H pq V A Sh CD •H Ch •H -P S3 CD •H o o H PQ V A M CD •H Ch •H -P S3 CD T3 •H -P •H 9 A CD cO S3 o o H pq v A S3 o ■H -P •H a •H > CO Sh < A V o l_ ' •rH -p A Q -p •rH S3 M CD O £ CO CD CD P 1 73 cO P H co o -p bO O S3 CD •H S3 S S3 CO o in CJ> o V V . 1 - J A 1—1 -p S3 A CD A -P £ S3 S3 CD o CD -P •H £ CO -P CD -P Dj -P co ■H cO H -p CD o w O CO S3 CD CD CD Td H H -P CO H •rH > rH EH •H CD v 3 O a 1 V •— ' V =1 4 I A S3 A o S3 •rH O -P •H ■H -P S3 CO, •H •H Ch H CD O t3 m CD >> t3 cO bO h S3 < •H. V CO ^ o 9 18 4 CO H Ph O •H -P a, •H Ph o w d o P CJ G o o V A •H

> CO d Ph a Ph o <5 o V V A •H ■H -P CI T3 H V A Ph •H £h •H P d •H Ph O P> a cl d o o V A -p cl <$ p w d o CJ p> a •H o a, -d x •H A p d QJ a o a. a o a >> co Ph =1 A -p a Cl o a o o >> cO Ph Ph 9 -. =J A A ?H QJ O CO P d o CO H > CJ >> « CO O Ph Pr h V A p d a H !>S cO Ph iH 9 1 A p> cl S H >> CO Ph Ph 9 A Ph O P> CJ > !>> CO Ph V o •H W w ^H Dj X Ph d p CO H CJ Cl a 1 1 o d *\ >> -^ A CO p Ph A d Ph p *§ d £ V cO -p rH g w w 1 — 1 d o >> • * CJ cO A -p Ph Ph A p Ph d <; d •H v •H O a > T3 •H H cO ■H pH o Ph V Ph >J S3 ■3 CO "~~\ O v Ph P"h Ph *s V *\ < V 1 1 - — . 1 A p d a H i>s CO Ph A Ph •H Ch •H P d 'd •H H o V A s~< •H

s cO Ph Ph 9 A A d bfl d •H •H co Ph CO P CO Ph a Ph X -P Ph CO Ph taO CO xj -P o d H o V •rH Ph 1 — , a 1 d d — CO XI + a r-j v-w < V i 1 i A d •H CO CO Ph CU X Ph d -P CO H d a d :>> cO ^ Ph < V 19 H O O S A !h (D •H Cu ■H ■P d CD H V A !h 0) •H <+H •H -P d CD T) •H H rH 0) o V h CD •H Cl > cd rH rH H ^H CD < O V V o •H -P •H rH O W CD 13 O V =1 A CD 8 cd d o =1 A -p 1 — 1 d CD A 8 CD CD 8 -P cd CO d -P CQ CD H bD d d T3 •rH o s JgJ cd V rH Q V 4 o •H -P Cu •H rH O CO CD -3 CD 3 o =1 A -p A d -p CD cl 8 CD CD Cl -P o cd Cb -p 8 w o CJ CD rH CD -P H ■H 3 EH T3 V o =1 =1 A rH CD •H MH •H -p d CD Hi V A CD CI CD o 9 A -p w •H H cl •H PM V A rH CD ■H HH •H -P Cl CD Td •H -P •H Cl A -P d CD d o cu 8 o o CD o =1 A -p d CD d o s o CJ CD H o =1 A CD W d cd Pd O 9 - A U CD •H Ch •H -P d CD Hi V A rH > s cd o rH fe rH V <; V A -p d CD d •H PM V 20 g A d w o •H =t -p •rH w A o -p a. d cu cu d rH o 3 A Dj -d -p S o d A o £ H a i — i •H •rH W bfl P-4 d CO •H W W A -p d V ? 0) CO CD —1 •\ H d A d -p CD A -p A TJ •H -P -p d d O a CO • *\ CI cu o 9 5 -P CD 6 ■H V W s £ QJ ra pf CD •P w • *\ i — i 1 — 1 bO w H CO OJ A A d •H =1 CD -P w rH cu g -P -p 3 rH X W d d cO o bD CD (U fl • »\ A -p -p o d •H CU =1 CD cu V d cu 3 rH -P -p A CD d CO d A CO CO 1 | -p d d rH -P -p A -P -p w o o « CO d d to ra 1 1 •H a, o V rH CU O H £ V CJ d •H bD bo A o 1 1 d o co d d -p ^H o *\ CD Qj w •H •H d o 1 — 1 £ a CD 3 3 CU -p d — 1 o o rH CO cO g • *\ o bfl A d u Cu rH !h CD •H A •p X P o -P Q d ra •p d >> rH A CD V V CO § d w d CD cO H d -P W o <: (V a rH •H o rH W o v & CD rH Ph •H CU A -p A -p 0) rH -P =1 A V =i H cu -P CO -P CO V =4 w CO CD rH bD QJ -p d d d •H p A A rH CU H 0) EH d cu cu o CD A A X V s £ V QJ £ W -p H rH CU CD CD OJ d cO d o -p CD w I -P ■P I t o d cO cu •H £2 d rH CO CO a H d EH £ CO QJ A -P w =4 £ o cu rH o d o V d d rH o bO CD d o o d « o ■ . -P •H 0) cu • «\ T3i O V X W d -P rH rH d o c =1 CD o H •H +5 •H ■P s bO •rH s I T3 d & V W O EH EH Hi ra A • »\ H 4 Q< V V CO w 1 -p V CO < w HH A CU t — ' 1 — '