LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510,8+ tio .3(b|-366 copZ The person charging this material is re- s])onsihle for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of bookf aro reasons for disciplinary action and may result in dismissal from the University. To renew call Telephone Center, 333-8400 UNIVERSITY OF IlLINOIS LIBRARY AT URBANACHAMPAIGN ^&^ ^b^ ys\ffJJh Report No. 365 WEATHER ANALYSIS ON A PARALLEL COMHJTER David Martin Goddard December 1, I969 IHc LISRARV 0.- THE OCT ^ 1^/:^ .UNIVERSITY OF ILLINOIS j Report No. 3^5 WEATHER ANALYSIS ON A PARALLEL COMPUTER* by David Martin Goddard December 1, 19^9 Department of Computer Science University of Illinois at Urbana- Champaign Urbana, Illinois 618OI It This work was supported in part by the Advanced Research Projects Agency as administered by the Rome Air Development Center under Contract No. AF ^0{602)-klkk and submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science, September, 1969* The views expressed herein are those of the author and do not necessarily reflect those of the United States Air Force. Digitized by the Internet Archive in 2013 http://archive.org/details/weatheranalysiso365godd 11 ABSTRACT The niimerical weather analysis procedures of the National Meteorological Center are reviewed, and problems in adapting them to a parallel computer are considered. Algorithms for storage allocation, processing teletype data, dynamically arranging data, and producing the analyzed field are presented. Ill ACKNOWLEDCa^NT The author appreciates the interest and encouragement of his thesis advisor, Professor David J. Kuck. The information provided by Mr. James McDonell of the National Meteorological Center was most helpful. Major Harold D. Woods of the Forecaster Training Branch, Chanute Technical Training Center, and the iDersonnel of the base weather station at Chanute Air Force Base were helpful in providing reference material. Also, the author extends his appreciation to the B5500 operating staff and key punch operators. The assistance of Mr. James Madden of the ILLIAC IV professional staff is very much appreciated. And, of course, without the typing abilities of Mrs. Patricia Douglas this final form would not be. The Air Force Institute of Technology, Wright -Patter son Air Force Base^ wnio, sponsored the author's studies at the University of Illinois. IV TABLE OF CONTENTS Page 1. INTRODUCTION 1 2. NUMERICAL WEATHER ANALYSIS 2 2.1 Relation to Numerical Forecasting 2 2.2 Dynamics and Thermodynamics for Upper Air Analysis 2 2.3 The National Meteorological Center (NMC) Procedures 5 2.4 The NMC Grid 10 3. THE ILLIAC IV COMPUTER 12 3.1 Organization 12 3.2 Control Unit 12 3.3 Processing Elements l4 3.4 Memory Addressing ik 3.5 Mode Control I7 3.6 Routing 17 3.7 Input/Output and Array Control I8 k. STORAGE ALLOCATION I9 k.l Data Organization and Arithmetic Efficiency I9 U.2 Arrangement of Grid Points 20 4.3 Neighboring Points and Responsibility Areas 21 5. PROCESSING TELETYPE REPORTS 25 5.1 Structure of Teletype Messages 25 5.2 Scanning and Recognition 25 J V Page 5.3 Decoding 29 5.U hydrostatic Checking 30 5.5 Error Recovery 30 6. RELOCATION AND ANALYSIS OF DATA 31 6.1 Initial Assignment of Stations to EEs 3I 6.2 Interpolated Values and Consistency Check 31 6.3 Interchange of Field Values 32 6.k Analysis Calculations 33 6.5 Analyst Interaction 35 7. CONCLUSIONS 36 LIST OF REFERENCES 37 APPENDIX 38 VI LIST OF FIGURES Figure Page 1. Ihe NMC Analysis Grid 11 2. Control Unit 13 3. Processing Element 15 h. Data Word Formats l6 5. Assignment of Grid Points to PEs 22 6. Arrangement of Points within PE 23 7. Sample Teletype Data 26 8. Data Organization Daring Analysis 3^ Vll LIST OF TABLES TABLE Page 1. EXAMPLE OF RADIUS OF INFLUENCE AS A FUNCTION OF DATA DENSITY ... 7 2. ORGANIZATION OF DATA FOR ANALYSIS 20 1. INTRODUCTION Niomerical weather analysis was developed to provide improved input to numerical forecasting programs. Meteorological data is obtained by observa- tion from stations that are located neither in a regular pattern nor uniform distribution. This data, which is transmitted via teletype in standard code formats, must be collected, decoded, and reduced to the grid used by the fore- casting routine. The National Meteorological Center has developed effective procedures that produce operational analysis charts, as well as input to fore- casting programs. The ILLIAC IV computer will be an array of arithmetic units operating together \ander central control. In a one quadrant array, sixty-four processing elements can each be doing two 32-bit arithmetic operations simultaneously. Implementation of a numericaJ. weather analysis program on ILLIAC IV requires consideration of operation on teletype reports in some parallel manner, storage of data so that it is readily accessible to appropriate processing ele- ments, and maximization of simultaneous operations across the grid. ^ 2. NUMERICAL WEATHER ANALYSIS i ij 2 . 1 Relation to Numerical Forecasting |i From the time von Neuman and Charney investigated automated forecast i procedures, meteorologists realized that input data was a major problem. Indeed, j part of Richardson's difficulties in his early attempt at manuaJ. numerical inte gration to produce prognostic information was the lack of upper air data [IJ. It is the atmospheric layers above the surface to which dynamic and thermody- namic equations have been most successfully applied; upper air observing sta- tions are considerably fewer in number than surface ones. j Manual analysis is highly subjective and time consuming. The same objections apply to manual extraction of data from charts for input to machine analysis. In sharp contrast, the operation of a numerical forecast program is quite fast and as objective as the atmospheric model it simulates. 2.2 Dynamics and Thermodynamics for Upper Air Analysis The equations of motion applicable to a parcel of air on the rotating earth can be simplified by assuming that the only forces present are those due to pressure gradient, gravity, and the earth's rotation, and that motion reaches an equilibriiun state [2]. The simplified equations are ^ 1 ^P ^ 1 ^p 1 ^p . ^ ^ fv=-r^ fu=--«N^ g=-— =r^+2n cos cp p ox p oy *= p dz ' v/h-^re X is positive in the eastward direction, y northward, and z upward; u and Additionally, Richardson's work failed because the compensation of horizontal forces was not considered and because of computational instability in his model. V are the x and y components of velocity, respectively; p is pressure, p is density, g is acceleration of gravity, and f = 2 fi sin op is the Coriolis para- meter at latitude q? for the earth's angular velocity fi. The third equation is ■X- the equation for hydrostatic equilibrium after the small vertical Coriolis term is neglected. The horizontal equations are termed the geostrophic wind equa - tions and express the horizontal balance of Coriolis amd pressure gradient forces. When the vertical coordinate is transformed to pressure, the horizon- tal equations sire V = f If 1 and u = - I In analysis work these equations have the advantage that density is not explicitly involved. The constant pressure surfaces are sufficiently quasi -horizontal that they are easily usable in place of constant height surfaces. Ihe hydrostatic equation, ignoring horizontal forces, is dp = -0 g dz. Substituting the ideal gas equation of state and integrating from z, to z^ yields [3] the hypsometric equation z^ - z, = — (In p^ - In p_), 2 1 mg 1 j'2'-' where m is the average molecular weight of dry air, R is the gas constant, and Ifydrostatic equilibrium is one of the most basic assumptions made in theoretical meteorology. It quantifies the fact that the vertical scale of mo- tion is orders of magnitude smaller than the horizontal one. T is the mean virtual temperature of the layer. Virtual temperature, T , is the temperature of dry air of the same density and pressure as the given moist sample. It rarely exceeds the actual temperature by more than three degrees Celcius. Thus the thickness of a layer of air between two constant pressure sur- faces is directly proportional to the mean virtual temperature of the layer. From a plot of temperature and moisture content versus logarithm of pressure, the virtual temperature plot can be easily developed. Equal area averaging of the virtual temperature between two pressures then yields the thickness of the layer. Because of the averaging nature of the hypsometric equation, relatively simple upper air sounding equipment will yield good measurements of the heights of constant pressure surfaces. The hydrostatic, geostrophic, and hypsometric equations contain the factor g, the earth's acceleration of gravity. Meteorologists usually combine the acceleration due to gravitational forces with the centrifugal force of the earth's rotation into g. Thus g varies slightly with latitude and surfaces of equal geopotential (specific potential energy due to gravity) do not correspond to those of geometric altitude. The above equations are usually formulated in terms of geopotential rather than geometric height. The geopotential meter is defined from ' /o ^^' 9:^ and gives geopotential height measurements numerically similar to geometric heicht in meterr, fP]. Actually, geopotential meters are a measure of specific energy. In much of the development of theoretical meteorology, specific vol- tune, specific force, etc., are used and explicit measure of the mass of air and air parcels is not required. In sunmiary, the hydrostatic and geostrophic equations express the equilibrium that is the general nature of the atmosphere. The geostropic equations yield a simple relationship between vrind velocity and the gradient of pressure, or equivalently, of geopotential height. The hypsometric equation provides a simple means of determining geopotential height of constant pressure surfaces. 2.3 The National Meteorological Center (NMC) Procedures Cressman [h], later at the Joint N-umerical Weather Prediction Unit (the or- ganizational predecessor of NMC), considered an analysis procedure for geopoten- tial height based on quadratic least squares interpolation of observed data at grid points. The asymmetry of data distribution, particularly over ocean areas, caused poor results in such areas of sparse data. Furthermore, extensive compu- tation was required to invert the matrices of coefficients during the computa- tion at each grid point. Bergthorsson and Doos [5] developed a procedure at the University of Stockholm based on modification of a first -guess field. Their reasoning was that interpolation of any nature will fail in an area lacking observational data and that in such areas a forecast based on old data is better than an inter- polated analysis. In tropical areas, climatological normals are relatively good first guesses. Their procedure begins with determination of a first-guess field as a weighted average of the climatological normals and the numerical forecast based on the data from the preceding observation time. Next, three types of corrections to the first-guess field are determined for each reporting station. The first correction assumes that the difference at the station of observed height (z ) and first-guess height (z , as determined by interpolation) is equal to the difference at s\irrounding grid points of the actual height (z^) and first-guess height (Z„) ^1 = ^f ^ ("O - "fs^- By assimiing the observed wind is geostrophic and representative of the interval between the station and the pointy a second corrected value (z ) is obtained \-\* tejg "^ ' l57Jo ^ where d = \/(Ak)2 + {^f is the distance in grid units from station to grid point and (^j and [■t~] are the x and y components of height gradient as computed from the observed wind. The third corrected value is similar to the second but uses the gra- dient at the grid point. The relative weighting (w^ \t , w ) of the three corrected values was determined by statistical regression. For stations report- ing only height, the correction z, is computed but a different weighting func- tion is used. Because of the correlation of data from stations in areas of high station density, the composite corrected value is further weighted by the in- verse of station density. The computed value at each grid point is then the weighted average of all composite corrections for stations and of the first- guess value. One scan of the grid was used by Bergthorsson and Doos in most of their experimental work. Cressman [6] modified the Bergthorsson emd Doos procedure by adopting a simplified weighting function and making multiple scans of the grid (see Figure 1 for NMC grid). This modification also drops the third type of cor- rection. The weighting function, the same for both types of corrections, is 2 2 - R - d w - R + d where R, the radius of influence, is the maximum d for which a station is used to correct a grid point. This type of weighting function effects a smoothing of all data within distance R. The value of R is decreased on each of four consecutive scans in order that the phenomenon of decreasing scale can be in- cluded in the resulting final anal.ysis while errors in the first-guess field are quickly smoothed out. In order that height data may be given greater weight, wind data (correction 2) is not included on the first scan of a height analysis. Sta- tions reporting wind only are utilized by forming a type 2 correction (z') with z^ replaced by z _ . IS Since 196^, the value R (the radius of influence) at a grid point is determined by data density [7]. This variation of R is a discrete function of the number of height reports (see Table l). TABLE 1 EXAMPLE OF RADIUS OF INFLUENCE AS A FUNCTION OF DATA DENSITY R in grid units Number of height reports 2.2 5 or more 3.5 7 or more 6.9 1 or more 8 The calculated value at the grid point is i m n AZw.c. +B Z-W.C.+ Sw, c, i=l " " ,1=1 J J k^l ^ ^ ^ ^f ^ Ai + Bm + n "i = ^\ - "f^i ^ "O - "fs ^d = ^^2 - ^P, ^ ^fs ^ f4"^rlr),^r ^f The subscripts i, j, and k indicate values for one of the i + m + n stations that can influence the report. The coefficient A can be regarded as the weight given to gradients of the first-guess field in relation to the observed winds, weighted as 1 [6]. A equals t^. B similarly is the weight given to the inter- polated first-guess value as a basis for extrapolating the gradient [7]. B = 0, 7T, -r, and — on scans 1, 2, 3^ and h, respectively. o z o z The value of the components of height gradient v- and ^^ are computed relative to the grid coordinates. If the geostrophic gradients are determined by \^/ g ^ \5y/ g ^ then an approximation of non-geostrophic affects can be included by computing if = ¥1 ^ fi (-(I) °i. ^ (ll>) g I o g g Again f and g are the Coriolis parameter and acceleration of gravity, respec- tively; m and 6 relate to the map on which the grid is based. K is a constant less than one which is assigned to a constant pressure surface for a season. D' , D' , and D' are the second derivatives of the height field. On the square xx' yy' xy oh grid used by NMC, the neaj*est eight points to a given grid point are required to compute these derivatives. Before each scan of the grid, each station report is checked for its consistency with its neighbors. The mean difference of each station within two grid Tinits from the first-guess field is compared with the difference for the station under consideration. The station's report is marked for acceptance or rejection on the basis of this comparison and data density. The source first-guess fields used by NMC vary. The 1000 mb, 500 mb, and 200 mb first-guess fields for height are obtained by adjusting in the tropic- aJ. regions the preceding forecast by climatological height gradients. For some levels, vertical extrapolation or interpolation from levels previously analyzed provides the first-guess field. Except for the 500 mb level, temperature is analyzed at the same time as height. The temperature analysis is like that above but omits gradients. The u and v components of wind are analyzed by taking the geostrophic winds from the corresponding height analysis as the first-guess. Two scans are used to adjust the field to reported data. Other modifications to the basic procedure are used to accomplish objective tropopause analysis and wind fields in the tropics [8]. The latter uses a grid on a Mercator map projection. 10 2.k The MC Grid The grid used "by NMC (Figure l) for both analysis and forecast pro- cedures is obtained by drawing one-half inch squares on a 1:30^000^000 scale polar stereographic projection of the northern hemisphere. This projection is true at 60° N latitude. The resulting grid unit 6 is 38I kilometers or 206 nautical miles. The map factor, the ratio of projection image distance to distance on the earth, is 1 + sin 60' m = 1 + sin -"p The grid is oriented so that the meridians 10° E, 80° W, 170° ¥, 100° E are along grid lines. The grid is numbered so that the i (x coordinate) and j (y coordinate) zero lines intersect in the Indian Ocean and the North Pole is i = 33^ j = 26. The following formulas may be used to convert the latitude and longitude of any location to grid coordinates R cos I'D e r = 1 + sin i-p i = ip + r sin(^ + lOO) j = jp + r sin(^ + 100) R = 21.20U grid units e ^ where ip and jp are the grid coordinates of the pole and ^ is west longitude. The MC analysis procedures use the 1977 points enclosed by the octo- gon depicted in Figure 1. R is the radius of the earth on the map projection image plane-- R = 6371.2 km (1 + cos 30°)/38l km per grid unit. 11 / ^ * \\-^_.-^--^^~^ ^ \^'^ r*/ / / . \ \ / ^ > ^. ly' "V' I , \ \ / \ 1 ^_ ~t \^ \^ ■ \ > / •. M ^^ -,' > ?J \, -^ N / • ^' f-- i;-. ::— ^ 4 1 n "\, ^. \ ' \ * / »♦ \ - t V *i^ r^ ^ f ^ V ■'•, \ \ / * '. V ^ '\^ ■t» 1 / ) 0,1 \ / jj - ', \ ^ 1 / ■• \ »■ '' X / >,, ^ ' ) ^ «U V -V ^ \ \ \ 'V, \ » / .^ Z"'' III i ^^ Vi ( \ / >j '. /I ^' ^ \ , I \ \ », / *. - '^ \ . / ' - I / \ >, \ / ■, t \ «'^ i )'J .' I f ■ )• \ / ^ \ ,f \ "■ > ^^ r'^ • \ 1/ V, F •> ^ , .<■- § \ '■V i 1, \ -•| , ii >< T -- 1 ] !> ■ '-. ^ 1^ J, .-' * -- J _i _ 1 V H 1 ) ■>- \A / '■ ■' ': • ' ^:- ' 0- s. \ H •i- , C '^ . 1 i' <4 .'■ • t- 'V .-'1 < v? '/, ■> f ' \, y. '- > \ \ ^^ •1 i >J ^' i^ I }, f^ ^ "^ '' \ ^ > k ^^ ^' ^w -f? $ V .._. ^ , } \ !>■ "^ '-/ '^ fe 1, h '?' r" ^ ■' * ■ r n. r t \y '«:i ""!' .^,> M ■>,> 7' ■'f'l \ .- ' i 1 I ■ -V >-' ,'• ■«> ■ ^ H-1 "^ \. (f if t' ^■< J^ V '. :^ % <^ 5 'j ^ ? • - , *f \ ^.^ ■f~ .'/, J. '^ f ■\' \ '^ -"» \ ■" 1 ■» ? a ^r\ ^^ \j \ ^. . ' ' ? yr- ■^•- ^1 'C' *? ■^ t t- 1 -"i 1 ' ^' * c ^T/ "X ;? s % '''I 'W ■'.^i t ')\ -^ li .- » * j ^ ,.| ', !•, , 1 •i Ik \- ;.y ^ ^ P \^ • t i - ' » 1 V % '"^'j wi . t tr' '- ■^i •0- 1 Ik ^ ^'. ^ 1"^ . - . I ■•^ i' ^ A lid ti '/ n^ ^ If { '^ V' V- ~^ T v. ~^ r' ■ V ^^ j .. ' 'i »■ I ~ a . - ' +1 .^i' .• ■ • >■ -_..; « * .-- / h. s d \i ■r 4 f k V ■j- "^ 1 . ^ ^ P f ^ ^■^ ?. ' p ^« » I» * \ y J / • i ^ « ' ' / \ s / \ ■4 \ 7 >^ \^ ', ^ ' / \ L * U" ' «^ V V 'v ,j> / ^ \ r C .■ / ^ -v_- ^. *"*. " ■ r-^ •' / V -^ ^ \ ^ ■' ) r <* y / \ ►■ ; n f /^ \ > . . ■' ~\ ^■a / / \ • ,/- i y _^ ,1' / N« ■ / V •> ^^ -^" j ? ■) a 1 /^ t >^j / ■ ■ ^-A \ . I " " »• • L; :S? ^^ / < * ' ■ / \ / 1 -^' I \ 1 J M ^, t- >K 7 ' -, /^, / %^ ^ : ^ ' ., / •■ -, /_ / 1 •.-/..■' !l/ \ y\. - ^ \ ^ v^ J L . ^ * Figure 1. The NMC Analysis Grid. 12 3. THE ILLIAC IV COMPUTER 3.1 Organization The basic concept of ILLIAC IV is that the rate of calculation on a digital computer can be increased by executing more than one arithmetic operation simultaneously. Furthermore^ the parallel execution of arithmetic operations does not require duplication of control functions. To this end, ILLIAC IV has 6U arithmetic units, or processing elements (PEs), under the control of one control unit (CU). The combination of one CU and 6h PEs is termed a quadrant and one, two, or four quadrants can be united to operate as an array [9]. 3.2 Control Unit The control unit (Figure 2) fetches and decodes all instructions. Only address arithmetic (2U-bit, fixed point) can be done in the CU. Instruc- tions that only involve the CU include branching instructions that allow the entire quadrant to execute from another part of the instruction stream. The advanced station (ADVAST) in the CU does the initial decoding of instructions. It contains four accumulator registers (ACARs) and 6k words of data buffer (ADB). Transfer instructions are entirely executed by ADVAST. The final station (FINST) completes the decoding of all instructions requiring PE action. This includes data fetches to ADVAST. A queue of up to eight instructions is maintained between ADVAST and FINST. The instruction look-ahead unit (ILA) maintains a buffer of up to 128 instructions and fetches all instructions from memory. The test and maintenance unit (IMU) is the only path to or from out- side control. Loading IMU registers can affect initialization of the control unit. 13 IOC TEST MAINT. UNIT (TMU) IOC r i_i MEMORY SERVICE UNIT (MSU) T t FROM ALL PEMS INSTRUCTION LOOK- AHEAD (ILA) w INSTRUCTION STACK 1 [ ADVANCED STATION (ADVAST) FINAL INSTR. QUEUE (FINQ) FINAL STATION (FINST) I 1 OPERAND STACK CONTROL BUS DATA AND CONTROL MODE STATUS ADDRESS BUS BUS FOR 64 PEs TO 64 PEs DATA FLOW INSTRUCTION FLOW ADDRESS FLOW Figiire 2. Control Unit. Ik 3.3 Processing Elements I Processing elements (PEs^ Figure 3) execute arithmetic, boolean, I shift, and data transfer instructions in lock-step \inder sequencing from FINST. Arithmetic instructions can be either 6U- or 32-bit floating point or k8- or I 24-bit fixed point (see Figure h) . There are also a limited number of instruc- tions for operation on eight-bit bytes. Each processing element is assigned 20U8 words of storage (PEM). The term processing unit (PU) denotes the PE plus its storage. J The addressable PE registers are the A (accumulator) register, the R (routing) register, the D (mode) register, the X (index) register, the B regis- ter, and the S register. Register C (the carry register in the arithmetic logic) ' is addressable in connection with byte operations by only one instruction. | Register X is I6 bits in length; register D is eight bits (see 3«5)« All others are 6U bits long. The S register can be used to store operands. Its I6 low order bits can function the same as register X for index operations. The 6U-bit wide common data bus (CDB) allows the CU to broadcast oper- ands to all PEs. H Register X and register S indexing may be done on shift operations as | well as on memory fetches and stores. 3.4 Memory Addressing The control ■unit addresses memory such that the low order six bits indicate a particular PE. The preceding I6 bits address a row of 64 words in PE memory (five of these allow for expansion from the present 2 = 20h8 words per PE). Indexing by an AGAR is by word; by register X or S, by row (low order bits discarded). 15 To % from Neighboring P.E.s Data from P.E. Memo 1 I Common Data Bus rom C.U. To & from C.U.I OPERAND SELECT GATES 6 n R REGISTER (Routing register) n B REGISTER (Extension register) -6- 1 ARITHMETIC UNIT A REGISTER (Accumulator) ZLU LOGIC UNIT (Boolean operations) BARREL SWITCH (Shift unit) 1 MODE REGISTER T I S REGISTER (Temp, storage register) ADDRESS ADDER I X REGISTER (Index register) Addresses to P.E. Memory Data to P.E. Memory Figure 3« Processing Element. 16 Bit No.: 64-Bit, Floating Point Bit No.: SIGN OF OUTER MANTISSA - 7 8 9 32 -Bit, Fl oating Point 15 16 OUTER EXPONENT SIGN OF INNER MANTISSA INNER INNER EXPONENT MANTISSA Working Bits: °outer ^outer 7 0. 1 7 8. inner inner inner 39 40 OUTER MANTISSA 31 8 outer 63 31 Bit No.: 64-Bit. Fixed Point (no sign) or Logical OPERAND (NO SIGN BIT) 63 Bit No. 48 -Bit, Fixed Point (no exponent) Bit No. Working Bits: 24-Bit. F iYP^ Point (no exponents ) ■15 16 outer inner Inner outer Bit No. 8-Bit. Fixed Point (no signs) 7 8- 15 16- - 23 25 -31 32 39 40 47 48 55 56' BYTE #1 BYTE 12 BYTE #3 BYTE *4 BYTE #5 BYTE #6 BYTE #7 -63 BYTE #8 Figure ^4. Data Word Formats. 3.5 Mode Control input to storage and to three of the programmer addressable PE registers (A, S, and X) can be inhibited by mode setting operations. Thus during instruction execution, PEs can be "turned off", and different PEs can in effect execute different instruction streams at different times. Note, how- ever, that even if all PEs are disabled, FINST sequences through the instruc- tions. The first two bits of register D, the E and El bits, are the enable bits. A test on register A or an index test on register X (or the low l6 bits of register S) results in setting the I or J mode bits (in 32-bit opera- tions, the G or H bits are also set by the results of the tests on the inner word of register A). The F and Fl bits reflect faults (exponent overflow, for example). The setting of an F bit results in an interrupt in the CU. The SET instruction is available to set any mode bit from the results of a logicalAND or of an inclusive OR of any mode bit and either the E or the El bit. For example, SET I J AND -El will set bit I to the result of J and not El. Mode bits may also be set by broadcast from the CU. In this situation, each bit of an ACAR goes to the designated bit in the PE of corresponding number (i.e., bit to PE 0, bit 1 to PE 1, etc.). 3.6 Routing Because a given memory location is directly accessible to only one PE, routing operations are implemented to allow transmissions of data from the designated register to register R of another PE. A route of length one or eight takes one clock cycle [10]. Routes of other distances are accomplished by a sequence of routes of distance eight and one. 18 3.7 Input/Output and Array Control The only means of input/output for ILLIAC IV is through a disk sys- tem with a transfer rate of 0.5 billion bits per second and maximum access time of Uo milliseconds [9]. A Burroughs 65OO computer channels data to and from the disk system. The B650O also has executive control of the array. Through the IMU it can initiate a program, accept l/O requests from the operating program, re- turn results of l/O operations, and halt the array. 19 h. STORAGE ALLOCATION U.l Data Organization and Arittimetic Efficiency In order that the analysis of a field on the NMC grid may be executed most efficiently, it is necessary that the number of operations executed in each PE be as nearly equal as possible. The analysis routine is based on ad- justing the first-guess field at each grid point. Therefore, allocation of grid points equally is a first step. Unfortiinately, reported data has a dens- ity far from uniform. Furthermore, there are reports, such as aircraft ob- servations, that will not occur in the same location with each analysis. Thus, some execution time procedure must be devised to associate the reported data and the grid points. Use of 32-bit fixed point (2U-bit mantissa only) arithmetic will maximize arithmetic efficiency while maintaining accuracy consistent with ob- servational accuracy. Furthermore, l6 bits of accuracy in the observed quan- tities is sufficient if they are translated against some fixed value. For in- stance, 500 milibar heights expressed in whole meters with a base of 3500 geo- potential meters allows computation with 11 bit quantities ; 3500 to 7595 is sufficient range for this analysis. Positive translation against some lower bound is preferable to positive or negative differences about a mean or stan- dard value in that the latter would require programmatic setting of the sign bit after unpacking the data. The organization of I6 bit quantities in a block of four 32 -bit words is shown in Table 2. ^'lultiplication of two 11 -bit fixed point quantities results in 22 bits of product and is within the 24 bits allowed. 20 TABLE 2 ORGANIZATION OF DATA FOR ANALYSIS Word number Contents of Upper Half i coordinate 1 average temperature 2 observed temperatiore 3 1 wind component Contents of Lower Half j coordinate average height observed height j wind component ^.2 Arrangement of Grid Points The assignment of grid points to PEs is governed by two somewhat con- n * flicting requirements. With 1977 points to be assigned to 12o PEs , with four quantities (height, temperature, and two components of height gradients as com- puted from observed winds) at ten standard constant pressure levels required by the analysis system, one report may present forty quantities to be used in various analyses. If only 200 of the better than 1000 reports per analysis contain all Uo data items, there would be far more data items than can be con- tained in one PE. The total report must then be kept in one location only. Since a complete analysis at one level of both temperature and height can be accomplished with only eight pieces of data , this data can be extracted from each report and associated with all appropriate grid points. Blocks of 15 to l6 points must be arranged so that on one hand the total number of stations to be used by the points is evenly distributed, and on the other hand the total Actually "half" PEs, the inner/outer portions of the arithmetic lonits will be termed "PEs" as their functions during the analysis procedure are essentiaJ-ly independent. The inner words will be referred to with even numbers; the outer, with odd. In addition to the four observed quantities, station location and the first-guess height and temperature values (as interpolated from surround- ing grid points) are required. i 21 number of stations assigned to each PE is kept to a reasonable number. A totally random distribution of the points for a PE across the hemisphere would be disastrous. With each point possibly being influenced daring analysis by stations up to 6.9 grid units away [7] such a distribution wo\jld force each PE to store practically every station. An arrangement of four by four blocks, however, would result in blocks over western and central E\arope with every point being influenced by many stations. Figure 5 indicates an empiracally determined arrangement that not only baJLances the above two objectives but also results in a simple algorithm to interchange grid point values for neighboring points. The blocks are eight points long in the increasing i direction, two wide in the increasing j direc- tion. The points indicated by o in Figure 5 are those of smallest i and j values for each group of I6. Coverage of the octagon used by NMC is not complete; ^0 points at boundaries are omitted. I9 of these points are the j = 51 row and only one (i = 49, J = 10) is as distant from the octagon boundary as the diagonal of a grid square. Only two rows of three blocks each do not start in columns i = 9, 17, 25, 33^ ^1^ or k<^, and these six are exactly four points "out of phase ". U.3 Neighboring Points and Responsibility Areas With the assignment of points for which analysis computations will be done, the problems of determining average (interpolated) field values and non- geostrophic height gradients for each station can be solved. In Figure 6, the encircled points are those to be assigned to a PE for the analysis calculation. The inner rectangle, three by nine grid squares in size, covers the 22 « V'' ' ^ ^ ^--1 \ ^ ...y^'^r::) ~v:r--/^ - . ./ / ■•••. / -^ y \ ' ■\' ' / ^ >^- \ . ^ V ■«.• / ■ ■' N ^/ /. /^\_ A ^•"' "^ c^"" / \ . (Z {. _ ~-fH /2 7 I N K- / ■••' ' ^ /\'"' ■ Y 1 Vr ^ - > ■' (■^ \^ -- \ • / / ■ ' / '• \ n/2f / vi L - /•' ^-^ r _ ~"^ -t : 4 I, ;.i ^i'^ v- ^ ' . • ' / !.■• \ - / y. 1 ' \ \ '0/ / \ i f- ni V ^ I'c^ ' ■if 1 . / IZt Jt "'/ N • ■ \ X" ^ ■- t \ \ ■'1 1 1 /■ , / '' i / ' N K ■• -'^ 1 \ 1 • /tt ,"3i. , l"'l\ ■ ' (1^^ >' ' •u.? ^- -v 1 '/< \. -V, \ » [^ ' , 1 ■ / ■ A . i ■■ \ \1 / . . \ > ^ ■■■ 1 H /' ■ '- • ^\ ' ■ , ' • xC . >. \^ 1/0/ Xl. I ) •_ ■• J ■ - i ■ 1 ')i . -.rl / (1 . f ^ I 7 — 1 ' , •f, \ \-''' i /I i : ^ 1 ^ ■''. \. y2 \ '■ y ^4" "*'' r , 1 f .-■ , . "V 1 1^/ ! :. ; : . 1 t . 1 ' ■ 1 ^ ti"/ .ft'" \^ ^' ^' , >y 1 ^■ ^--^ '-' : , ; : ^ M ■ 1 I ^ 'v;: '" i" 1- \ \' ,^ r^ / - (^ •' 1 :^r , 1 f-1 i j >. i i f V ! r' ( ' 1 ; .' r * v ■'■ 1-' ''■ 1 ' ■ ■ : I i ; < !■■■ 1 • ^ • Vi ■% . 1 1 » . • "• "r?' ' r ■ C ^1 ,. ■ ' 1 ; 1 i?3 -: 1 i ••^ i' j * 1 ^ ■ -1^ '<-' •-" 'f / ' I. 'V ■•- ? : I i , 1 \ y \ X •■ - *" "1 --l ■ 1 1 ! ' ! 1 1 1 : 1 • -^ , ■ ( ) \ f-' '-P' \, "■■-( ^^ 5ii 1.; " ■>> "* •' \\ ■ . ■ V ■ ••i L \ >,^- . I.I ■ 1. , [; f -^ .^ -\ '-* „ (fi -1. 1. ^"z ' r \-< , \ .^' > '. ■ -v \-\ . ^ - , 1 : U '• i:-. y^^V- ;^y.: -'. T i — i p' if t H. •1/'' 'S- •'. ^ '\ ^ 1 .. — - ' I it! i'' ■ i ' ^ i' ) i ,■'1^ •1 _ -- V >-^ ■', "^ f ;.i I'i- ^r ; . . i n : • 1 ' ? -^ ■; 1 A .9 ■.1 9 ? \ J 4 > ^v ^ r N , 1 : ;: era . ' 1 1 ! ■ .' 1 ■ ' >-. 1 h^' {■ ' 1 ' !'^'j 'i^ s j 1* -^1^ / ; , 1 "! ! 1 1 ■.r i 1 L^-'P^ 7 ' ■'■- /• ,< ".^ t? r% ,' J * j ^ i . ^3 1 1 'j i 1 :l- i- ■\k • t ', 4x ■fv \^ \4' -,4! . v^ V 1. . . t r : 1 , • ' i ■ 1 T.-i..*^ ■ 1 . rv • 1.1 J , *. if '"» •O- 1 !'' ^. V^ ■.'■ . . . V ■ ■ !.'! :' 1 , ! ! 1 . -b'-l-. -S^ — 1 r j^ .';^. ■J , / (;T K^ < \ '- / ■ 1 ' 1 1 ; : ' ! " 1- i \ V^- V -T- - _' , v t^ i — r' — ^ t i_ 1 1 1 <*• II /-A ' ■■ J 'i;ri J ■J '■1 1 I 1 A t • 1 i i 1)— . "-^ r~ ' F**- ' .^'• ? 1 > ■ ! "- All .. .' , / '•J '^,'; ; 1 1 U- 1-1^ 9 . 1 -1 1 1 1 1 1 1 -•! , -.1^ ' : / ' — c * /I. — rt " ■•\ 1 ^1 ' .^- ; : i ■ ■ I 1 ! • 1 \ ' ' \ C ^ ''■' • 1 . 1 ^: :■■ : ' ^ i-r. i ^ >' ■^ V, 1" — K. 4 \ ' 1/ -23 \j • , ; J, 1:' 1 1 i " " ■ ^ \ /• >j -1 1 ^ 1 f ^ '^ % ■| ' V. ? / ,'7 -\| .: >.;f, i-( v'-^ \y z«| ^• S- ..w j •ri J / ..-, N .. T i i i 4 1 i 1 ) , 1 ■ \ •^ s / \ ,'3'-l , 1 !• 1 1 . IH- 1 15 r- r /6 / \ . ~~. _ . — ^ '• \ -1 ! 1 I't ■■ 1 ' , < -'' /- X ? ! I. , : ■ ■ , i'o II ) 1 ■u -■ / N M 1 Y ■' i .■^ / /of / \. .1.1 6^ 7 .,]^' '' ■IS vl' / >< ' \ : r ^ "^""i; ""s. ~~*^ '■1^ ! 'T ■ ) ./ / ■■/■■ '^^■'- ;s:7-i , j I ;^ ^ h '■: . \ / ' * > \r T } -'' •■.,?. 7 '■■) /^ 5\ "• I' • ' / ■' \>4r .PI j 1 \J » ^, /A / :p^ ^ ■ 9 / • ■ / ■ ■ ■ . ,' • -17 V . / ; . '. i^ \ I. \_* ) •. ^ 1 _ Figure 5. Assignment of Grid Points to PEs. 23 78 65 52 39 26 13 J / • Ul6 O O O O . 28 h o — o o Figiire 6. ArrsLngement of Points within PE. 24 responsibility area for that PE . The stations falling within this area will be the responsibility of the FE for calculation of average values and height gra- dients and for consistency check. An array of length 9I in each FE provides analysis field data for these requirements. The consistency check of observed data against first-guess field values requires inclusion of the outer rectangle -points to 13, 25, 26, 38, 39, 51, 52, 6k, 65, and 78 "to 90. The inclusion of these points allows inter- polated field values to be found for any station within two grid units of the responsibility area. A station falling on a boundary would be assigned to the higher number PE. 25 5. PROCESSING TELEIYPE REPORTS 5.1 Structure of Teletype Messages Figure 7 shows a portion of a teletype message that contains two upper air reports — those from Topeka (TOP) and Dodge City, Kansas, for 1200 Greenwich Mean Time ((3^), May 8, 1969* Appendix A gives a grammar for this type of report, the type transmitted by North American stations [11] , inBNFmeta- language. Ihe syntactic structure is relatively simple. Thus it is possible to apply the methods of He imerdinger [12] to scan and parse this language of teletype reports. Unfortunately, however, this is not the only form for messages trans- mitted over the national and international meteorological circuits. Because of the slow rate of teletype transmission, it would also be undesirable to tie up ILLIAC IV with the task of scanning incoming teletype messages. It is therefore appropriate to use the B650O computer to receive the messages. While sorting out types of messages, the B6500 can remove the communications system portions of the incoming stream. The first three lines in Figure 7, as well as the transmitting station identifiers (TOP and DDC) , are such communications informa- tion and not part of the standard meteorological code. They do, however, identify the type and area covered by the message (UJ is a standard upper air report and US is self-explanatory). The B65OO would block all reports of the same type together . 5.2 Scanning and Recognition Heimerdinger ' s procedure checks for tokens of the language by loca- ting delimeters (in some cases the delimeters are tokens themselves). In the language of teletype reports, delimeters have no other meaning; the tokens are the five character data groups plus the identifying TT, W, and QQ groups. The 26 NNNN ZCZCWNfcLC449C IAA6/L UJUS KSTL 081410Z TOP TT 5B121 72456 99983 12222 36015 0fcl24 ///// ///// 85473 05203 00531 70040 02738 30018 50565 16930 26531 4072b 29345 25529 20927 457// 20041 ^0190 471// 24562 15378 533// 25555 10636 583// 25529 88231 571// 23072 ' 77223 24076(5 VV 5812/ 72456 209^3 122-22 1^553 10415 22820 03600 33733 00100 44711 01505 55696 03149 66645 04245 77572 10313 88499 16930 99400 29349 11333 40147 22255 543// 33231 571// 4421,8 ^93// 55l98 471// 66170 513// 77132 551// 68120 545// 99100 583// 31313 25046 549// 20558

) PEs that pass the tests are disabled and failures recorded for use by error recovery routines. The successful PEs are then enabled and data portions of the group are converted to binary. At this stage, data are placed into 32 -bit words with height and temperature in one word and the two wind components in another. 30 The determination of station location is based on directory compari- son. After building in each PE an index table based on the last digit of the ( I I station numbers^ the CU broadcasts the directory entries for each of the last t digits. With 128 PEs, a typical set of 500 to 600 surface stations can be i i checked with only one or two comparisons per directory entry. It would be indeed imusual if ten stations of the same last digit were stored together in one PE. Once station location is determined in i and j coordinates, the wind data for each reported level can be converted to the i and j components of geo- strophic gradient. The sine of latitude, calculated to find the geostrophic components, is saved to be used in the calculations of non-geostrophic gradients during the analysis routines. As the array of decoded data is built, the data actually present in a report is recorded for later use. The basic recognition algorithm should be better than ^0% efficient. Perhaps 2'^% of the total time would be spent waiting during memory fetches for which no successful match will occ\ir. However, the directory lookup can be no more efficient than 1/128 because a station will only be found in one PE. 5.^ Hydrostatic Checking The check of the report with the hydrostatic formula can be done in parallel on 128 stations at one time. However, as with all errors, at best invalid data can be flagged for later processing. 5.5 Error Recovery The types of errors possible are many and the assumptions made con- cerning them will determine to what degree parallel operation can be effected. At best, only a few PEs would be involved for one particular type of error. 31 6. RELOCATION AND ANALYSIS OF DATA 6.1 Initial Assignment of Stations to PEs As the controlling routine of the analysis procedure sequences to a new level, the data stored in the total report of each station must be ex- tracted and passed to all PEs with points within 6.9 grid units of the station. Hie location of the station reports is totally a function of the original tele- type message stream. However, broadcast of station location from the CU allows 128 simultaneous tests for the location. The data can then be broadcast with only PEs passing the location test enabled to store the data. The most efficient way to transmit data to the CU is by the indexed block fetch (BINX) instruction. Preliminarily, each PE checks for the first station with data for the indicated level. Stations with both height and wind information are transferred first, then height only and wind only. The source of data for the BINX instruction is a skewed array formed by placing the loca- tion half word in array location of the PE of origin, the sine of latitude in location 1 after a route of +1, the height and temperature in the location 2 after a route of +2, and the wind (height gradient) components in location 3 after a route of +3. The indices of the PEs are set so that one block fetch •.'ill transmit four complete sets of data (two 32-bit words in each location fetched). As each station is received by a PE it is further checked for loca- *:ion within its area of responsibility or in the neighborhood area required for the consistency check; appropriate index lists are built. ■•2 Interpolated Values and Consistency Check Before actual analysis can begin, the average field values for each .station Tirust be computed. The responsibility index list facilitates this 32 calculation. The sine of latitude is removed from its location and is re- placed by the interpolated height and temperature values. The geostrophic ; wind components are also extracted and the two are saved in arrays ordered 1 indentically to the responsibility list. The consistency check can then use j the calculated averages as it compares for consistency of the observed data. ! The interpolated field data is then transmitted to all other PEs using the station. This transfer requires routing first the location word (to identify the station) and then the interpolated data. The routing must be | < done for the rows of l6-point blocks up to +k and -3 away and to the adjacent PEs of the * f' same row. Routing between the inner half and outer half of the same PE is actually the execution of a SWAPA instruction^ which interchanges the inner and outer words of the A register. A sequence of routes and interchanges will cause the sta- tion report in question to pass through many PEs (the differences in lengths of rows cause this situation). Broadcast of a mode pattern controls the store of the resiolts of the distance test so that the proper mode test resiilts can be restored when the interpolated data is routed and ready to be stored. i 6.3 Interchange of Field Values ' " The first-guess field is initially loaded only into the PEs in which the calculation is to be done. Before each scan, field values must be trans- ferred into all PEs requiring the points for consistency check and height gra- dient calculation. The method is essentially that of 6.2; however, it is programmatic ally known from and to which array locations the data transfer involves. Thus no tests are required; broadcast of appropriate mode patterns will enable only the desired stores after each route and interchange operation. This interchange is also simpler than that of 6.2 because routes to adjacent rows are the greatest required. 33 6.U Analysis Calculations Once the transfer of data to appropriate PEs is complete, the cal- c\ilation of the analysis is straight -forward. Appendix B contains listings of two routines necessary to the actual analysis. The routine STATIONSORT builds the array of pointers to stations to be used for analysis at each point. Note that the order of points is not that of their occurrence in the array, but rather, an order designed to improve com- putationetl efficiency. That is, the point within each PE's block of l6 for which the greatest number of stations are used in the correction computation is first and the one with the least number of stations is last. At the label ALL in the procedure, one of the foirr bit pointers is extracted from the two word array POINTORDER (see Figure 8). The first step accomplished with the data for a grid point is to calcvilate the distance from grid point to station (label AL2). Thereafter a sequence of tests compares this distance with each of the three radii of in- fluence. For the lowest of the radii of influence, RLOW, and data with both height and wind reports, stations are stored directly into the pointer array STAPERPNT. For the other combinations of radii and reported data, temporary arrays are built. After all stations with height reports are checked, wind only reports are processed. The array STAPERPNT packs four 8-bit pointers to each word. Since the pointers are to four word blocks in a PE's memory, they must be left shifted before use. Also, in order to use an all zero pointer as a delimeter between types of data, the pointers are initially set one block (four rows of PE memory) high. The constant checking of the same stations against points, obviously leads to some con^jutational inefficiency. However, the routine that assigns 3h -P « C n •H C Is o •H OJ ^ ft fl — — 1— 1 o 0) P !>5 n5 m p VO rO w ^ F-i H ^ 00 0) O 5-1 M O P cd Ch Tif S O O ?H ^. — —— —i _ — w o •H EH w id ^ s FH •P o w P Ph ro — -1 _ Si! •H ^ « • Q) P (U >5 ^ p -P O O o O H .Q CO c C o ft i w •H W H 03 CQ / H 1 S 1 M 1 o / ^ Ph / ^ / p^ p:: / K O W fin \ ^ P? \ ^ n \c. S V D 4 CJ o CO •H I 35 stations to grid points has a beneficial effect here — all points do not have to be checked against all stations. An estimate of 30-50^ efficiency is rea- sonable. With the possibility some PEs have 200 stations, the time for this procedure approaches one fourth of a second. The routine SCAKFIELD, however, is highly parallel. The procedure UNPACK takes pointers to STAPERPNT and locates the station data into temporary storage. The computation that follows is a straight -forward application of the analysis formulas. The building of STAPERPNT was such that the computations of the three types of corrections are done sequentially. The final computed value replaces the previous first -guess value. The efficiency of computation begins at lOO/o as every block will contain some data. However, it will quickly drop off. The distribution of data will probably force efficiency under '^0%. The time of one scan over the field is estimated to be 75 milliseconds. 6.5 Analyst Interaction During the execution of the system presently employed at NMC, an arialyst monitors the machine analysis. In particular, he has the option of forcing into the analysis bogus or doubtful data. Such procedures would be wasteful of ILLIAC IV processing power. Considering the speed with which one scan can be made, it is suggested that more than one complete set of analyses cam be computed, with the analyst inserting bogus data between runs in order to control the results as desired. 36 7. CONCLUSIONS The weather analysis problem is primarily one of much data, assym- metrically distributed, and a few calculations. Algorithms for storage of unevenly distributed data can be developed for ILLIAC IV. The handling of input data and calculation of the analysis can be done with a great deal of parallelism. The most difficult, and time-consuming, steps are those requiring broadcast of data from the CU. More detailed knowledge of the input data may lead to more efficient means of directory look-up and of assignment of station reports to grid points. Considering that several time- con s\;iming routines have not been coded, an estimate for total analysis time for one level is five to ten seconds. 37 LIST OF REFERENCES Thompson, P. D. Numerical Weather Analysis and Prediction , McMillan Co., New York, 19^1! Hess, S. L. Introduction to Theoretical Meteorology , Holt, Rinehart, and Winston, New York, 1959- Beyers, R. B. General Meteorology , third edition, McGraw-Hill, New York, 1959- Gilchrist, B. , and Cressman, G. P. "An Experiment in Objective Analysis", Tellus , vol. 6, no. h, Nov. 195^, pp. 309-318. Bergthorsson, P., and Doos, B. "Numerical Weather Map Analysis", Tellus , vol. 7, no. 3, Aug. 1955, PP. 329-3^0. Cressman, G. P. "An Operational Objective Analysis System", Monthly Weather Review , vol. 87, no. 10, Oct. 1959, PP- 367-37^4-. McDonell, J. E. "Notes on NMC Objective Analysis Programs", Data Auto- mation Division, National Meteorological Center, Oct. I968, 9 pages plus attachments (unpublished paper) . Bedient, H. , Collins, W. G. , and Dent, G. "An Operational Tropical Analysis System", Monthly Weather Review , vol. 95, no. 12, Dec. 19^7, pp. 9^2-9^+9. Burroughs Corporation, ILLIAC TV Systems Characteristics and Programming Manual, with Change 2, Jan. 20, I969. Westlund, G. "A Timing Simulator for ILLIAC IV", ILLIAC IV Document No. 202, Department of Computer Science, University of Illinois, Sept. 6, 1969. Air Weather Service, Meteorological Codes , Manual 105-2U, July 15, I968. Heimerdinger, W. L. "String Processing on a Parallel Computer", M.S. Thesis, University of Illinois, Feb. I969 (also. Department of Com- puter Science Report No. 299, Jan. I969). Alsberg, P. A. , et al. "A Description of ILLIAC IV Operating System", ILLIAC IV Document No. 212, Department of Computer Science, Univer- sity of Illinois, Nov. 1, I969. Grothe, D. , and Luskin, C. Reference Manual for ILLIAC IV Assembler (ASK) , Burroughs Corporation, Mar. I7, I969. 38 APPENDIX A SYNTAX FOR UPPER AIR REPORTS FOR LAND STATIONS 1. Report Structure ::= ; ::= . 2. Standard Level Report Structure ::= ; ::= TT' ::= 99 ; ::- ; ::= } : : = 00 1 ^5 | 70 | 50 | Uo | 30 | 20 | 15 | 10 ; ; 39 ::= | | 88999 j : : = ; ::= 88; ::= | | 77999 i : : = <-wind group>; ::= 66; : : = | ; ::= ; : : = 77. 3. Significant Level Report Structure ::- <250 milibar report> (D ; ::= W / ; ::= ; ::= ::= | ho ; ::= ; : := 11 | 22 | 33 | ^^ | 55 | 66 | 77 | 88 | 99 ; <250 mlllbar report> ::= 31313 25 ; ::= 51515 ; : := <101 group> | ; <101 group> : : = lOKlOl code>; <101 code> ::= ; : : = SUPER ; ::= - | - . h. Upper Wind Report Structure ::= ® ; ::= ; ::= QQ ; : : = ; ::= | j i+1 ::= | | ; ::= 9^tens digit> // ; ::= 9*^tens digit> / ; ::= 9"^tens digit> ; : : = ; ::= . 5. General Terminal Symbols : : = | j ::= {combination of the carriage retiirn and line feed teletype control symbols that cause typing to begin on a new line} ; ::= (teletype impulse that spaces the typing equipment without printing a character] . 6. General Non-Terminal Symbols ::=