LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.S4 i\o. 5>^7- 342 cop. 2 Digitized by the Internet Archive in 2013 http://archive.org/details/partitechnicalpr342univ U&r Report No. 3^2 KV cue*-- PART I: TECHNICAL PROGRESS REPORT Atomic Energy Commission Contract AT(ll-l)-10l8 COO-1018-1187 by Illiac III Staff submitted July 23, 1969 THE LIBRARY OK THE NOV 9 1972 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAiGN DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMP, llNif-^F-IB I3MM COO-1018-1187 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS URBANA, ILLINOIS 6l801 Report No. 3^2 PART I: TECHNICAL PROGRESS REPORT Atomic Energy Commission Contract AT(ll-l)-10l8 for the period October 1, 1968 - September 31, 1969 submitted to The Atomic Energy Commission by The Department of Computer Science University of Illinois submitted July 23, 1969 i) TABLE OF CONTENTS AEC - Supported Research Page SUMMARY OF ACHIEVEMENTS DURING CONTRACT YEAR 1 1. HARDWARE DEVELOPMENTS 2 1.1 Taxicrinic Processors 4 1.1.1 Function 4 1.1.2 Design Features 1+ 1.1.3 Documentation 5 1.1. 4 Hardware Status Report 6 1.2 Fast Core Storage Units 7 1.2.1 Function 7 1.2.2 Status • . 7 1.3 Arithmetic Units 8 1.3-1 Function 8 1.3.2 Design Features 9 1.3-3 Documentation 9 1.3.1+ Hardware Status Report 10 1.4 Pattern Articulation Unit 11 1.4.1 Function 11 1.4.2 Design Features 11 1.4.3 Documentation 12 1.4.4 Hardware Status Report 13 1.5 Interrupt Unit 14 1.5*1 Function 14 1.5-2 Documentation 14 1.5-3 Hardware Status Report 15 11 i) Page 1 . 6 Exchange Net 16 1.6.1 Function 16 1.6.2 Documentation 16 1.6.3 Hardware Status Report 17 1.7 I/O Processors 18 1.7-1 Function 18 1.7.2 Design Features 18 1.7-3 Hardware Status Report 19 1.8 Channel Interface Unit 20 1.8.1 Function 20 1.8.2 Hardware Status Report 21 1.9 Device Controller 22 1.9.1 Function 22 1.9.2 Hardware Status Report 23 1.10 S-M-V Controller 2k 1.10.1 Function 2k 1.10.2 Design Features 2k 1.10.3 Prototype Scanner 26 1.10.U Interim Scan/Display System 26 1.10.5 Documentation 28 1.10.6 Hardware Status Report 29 1.11 Scan-Display Devices 30 1.11.1 Scanners 30 1.11.2 Monitors 31 1.11.3 Video Switching Matrix 32 l.ll.U Character Generator 32 1.11.5 Videograph Printer 32 1.11.6 1536 F/S Cameras 32 1.11.7 Remote Video Consoles 33 Ill Page 1.11.8 525 Line T.V. Cameras and Monitors 33 1.11.9 Hardware Status Report (Scanners) 3k 1.11.10 Hardware Status Report (Monitors) 35 1.12 Intermachine Link 36 1.12.1 Function 36 1.12.2 Hardware Status Report 37 1.13 Low Speed Terminal Network 38 1.13.1 Function 38 1.13-2 Design Features 38 1.13-3 Hardware Status 39 l.ll+ Power Distribution 1+0 l.lU.l Function 1+0 l.lU.2 Design Features 1+0 l.lU.3 Documentation 1+0 1.1U.1+ Hardware Status Report 1+1 SOFTWARE DEVELOPMENTS 1+2 2.1 Operating System 1+2 2.1.1 Supervisor - Processor Interface Definition 1+2 2.1.2 Directory Structure 1+3 2 2.1.3 Telecommunication Processing Package (TP ) 1+1+ 2 2.1.1+ Image Processing Package (IP ) 1+1+ 2.2 Translators 1+6 2.2.1 IBAL Assembler 1+6 2.2.2 PL/1 1+7 2.2.3 PAX II 1+7 2.2.1+ LEFT: Language for Editing and Formating Text 1+8 IV Page PATTERN RECOGNITION THEORY 1+9 3.1 Graph Transformation Grammars 50 3.2 Game Model of Image Processing , 51 3.3 Analysis of Simple Line Drawings 52 BIBLIOGRAPHY 5 1 * k.l Publications 5I+ U.2 Papers Presented (Conferences) 5U U.3 Outside Talks $k k.h Reports and Pile Numbers Issued 55 ILLIAC III STAFF 58 SUMMARY OF ACHIEVEMENTS DURING CONTRACT YEAR 1 . Illiac III Computer System Illiac III is an experimental computer being designed and con- structed by the Department of Computer Science as a first instrument to explore the potentialities of high speed image processing. Major accomplish- ments this contract year include: 1.1 Construction of Scan/Display Center allowing bypass com- munication with the service IBM 360/75 computer. 1.2 Specification of the Taxicrinic Processor and the inter- face of this processor with the Operating System. 1.3 Design of the high speed Arithmetic Units . l.k Design of tne I/O Channels of the Illiac III System. 2. Pattern Recognition Theory 2.1 The discovery of the concept of name-independent picture parses . 2.2 First prototype investigation of the game theory of image processing. 2.3 First lattice-theoretic definition and algebraic classifica- tion of graph transformational grammars. -1- .JWARE DEVELOPMENTS The Illiac III Computer System can be described in terms of Ik constituent subsystems of processors, units and peripheral device groups as follows (see Figure l): i) Central Jystem (6 subsystems) ii) I/O System (3 subsystems) iii) Peripheral System (h subsystems) iv) Power Distribution System (global to all subsystems). Only one, the Fast Core Storage Modules, is of commercial design. The other constituent subsystems have been designed almost entirely as part of the graduate research program of the Department of Computer Science. This massive design/development program was ret undertaken lightly. Rather, central to the contract program has been the study of the computer architecture appropriate for high speed image processing . These peripheral devices, units and processors must be able to talk to one another — and with minimum data format conversion: the Scanners feed the Pattern Articula- tion Unit, whose output in turn is interpreted by a Taxicrinic Unit. This global integration of the design has been costly but integral to the integrity of the system design presented here. Each following section summarizes briefly on constituent subsystem: Taxicrinic Processor, Arithmetic Unit, etc. In general a function description is followed by a discussion of special design features (if any), available documentation, and finally by a design/hardware status report (in a standard- ized bar graph form). Documentation listed is that printed during the current contract period with the exception of an occasional listing of an earlier report as required for conceptual continuity. -2- 77?'/7777\ ( ( ( ( ( CX I/O PROCESSORS/^ CHANNEL INTERFACE >% r.'crol Point Flowcharts '5/» 1 1 _v_C JCJ1 Q .. ■■■ i • ^ w* w ! 1 1 1 1 i i cClCOUt 1 1 ~L".3."Uc;G. . . urn o c r oi uor.^ro_ I'oin^s i 600-800 1 1 1 I Percentages refer to the TP Logic Simulator. A previous instruction-level simulation, consisting of 5000 assembly language instructions, was completed to correspond to the machine of Summer 1967- Processing Logic Simulation currently comprises -1000 statements. Control Logic simulation employes an interpretive subroutine to simulate the action of the control points. This code is expected to run ~500 statements. The control sequences, as read directly off control point level flowcharts might run as high as 2500-3000 statements. -6- 1.2 Fast Core Storage Units 1.2.1 Function Two Fast Core Storage Units are presently used in the Illiac III system. Each module has a capacity of l6,38U memory words and a cycle time of TOO ysec. The standard memory word is 80 bits, consisting of 6k data bits, 8 flag bits and 8 parity bits . This corresponds to an Illiac III double-word cell, augmented by parity bits. Each memory word is divided into eight byte zones which may be read and/or written independently of one another. 1.2.2 Status Each unit is a self-contained assembly consisting of all registers, timing circuits, power supplies and interface circuitry necessary for opera- tion of the system and compatible with the Illiac III environment. The two units described above were built under subcontract by Fabri-Tek, Inc. and are now operational. -7- 1.3 Arithmetic Units 1.3-1 Function Two identical Arithmetic Units (AU) perform most arithmetic operations in the Illiac III system. Integer addition and subtraction, as well as several unary operations form exceptions and are actually executed in the Taxicrinic Processors. The prime responsibility of the Arithmetic Units is the high-speed execution of floating point arithmetic operations. The units also provide facilities for integer multiplication and division and conversions from one number-type to another, e.g. , floating to long fixed. As in the case with all other units of the system, com- munication with the processors is via the Exchange Net. The Exchange Net assigns an AU to a requesting processor and also returns the results of an arithmetic operation to the processor which initiated the operation. Figure 1 illustrates the location of the AU's in the overall system. The execution of an arithmetic instruction begins in a Taxicrinic Processor. The operands are assumed to be in the top of the operand stack of the TP. Upon completion of the arithmetic opera- tion the result is returned to the operand stack of the initiating TP. 1.3.2 Design Features In keeping with the experimental nature of the Illiac III, the arithmetic units are intended to be a practical testing ground for recent theoretical work in computer arithmetic. Their design uses redundant number systems and a structure in which multiplication and division are executed radix 256. The heart of the unit is the stored- sign subtracter, a recently discovered member of the family of borrow- save subtracters and carry-save adders. A cascade of these subtracters controlled by a multiplier recoder, provides multiplication. The same structure, controlled by a "model division" (a quotient recoder), performs division. -8- 1.3-3 Documentation Publication Atkins, Daniel E. , "Higher-Radix Division Using Estimates of the Divisor and Partial Remainder", IEEE Transactions on Electronic Computers, Vol. C-1T , No. 10, October 1968. Report Report No. 330 Report No. 290 Atkins, Daniel E. , "Design of the Arithmetic Units of Illiac III: Use of Redundancy and Higher Radix Methods", May 1969. Koo, Ping L., Atkins, D.E., "Arithmetic Unit of Illiac III: Simulation and Logical Design- Part II", October 28, 1968. File Number File No. 713 Atkins, Daniel E. , "Arithmetic Unit of Illiac III: Simulation and Logical Design - Part I, September 27, 1966. Volume I of the Arithmetic Unit Manual has been largely completed and is in the final editing stages. This volume (approximately 200 pages) covers the details of the processing structure (the total logic exclusive of control ) . A report describing the more theoretical aspects of the arithmetic unit was prepared for presentation at the Workshop on the Theory of Computer Arithmetic, Third Annual IEEE Computer Conference (Minneapolis). This paper, DCS Report No. 333, describes the use of redundant number systems and the design of a structure with which multiplication and division are executed radix 256. A manuscript has been submitted to the IEEE Transactions on Computers for publication in a special issue devoted to the arithmetic workshop. -9- 1.3.4 HA] Arithmetic Unit ■ocessmg .:aravare ntrol Secuences 100$ 10 100$ Intimated Number of Statements 1800 ,u... iJci>J.feI* 100# juosign 100$ 100$ (1 AU only) 100$ .._ :aCU* ed Number of Cards : 475 .-iigh ^evel Flowcharts 100# 1st passlU0# Control Point Fl ova-harts 2nd pass:60$ Logical Design 40$ Layout --" — ' ^ Checkout ^szimated Number of Control Points: 130 20 i j M W o.j ^/69 -10- l.k Pattern Articulation Unit l.U.l Function Image processing can be reduced to the study of those sequences of basic, or root, instructions which permit recognition and description of the input image. These basic instructions can then be implemented in a processor designed specifically for that purpose. Here the duty of the Pattern Articulation Unit (PAU) is to perform local preprocessing on the input from the scanners, such as track thinning, gap filling, line element recognition, and so forth. The logical design of this all-digital processor has been optimized for the idealization of the input image to a line drawing. Nodes representing end points, points of inflection, points of intersection, and so forth, are labeled in parallel by appropriate programming under overall supervision of a control, or taxicrinic, processor . The abstract graph describing the interconnection of labeled nodes is then extracted as a list structure, which comprises the normal output of the processing unit. 1.U.2 Design Features The PAU employs a two-dimensional Iterative Array (IA) of 102*+ (32 x 32) identical processing modules locally connected to execute Boolean functions, threshold logic, and signal path building. It is augmented by its own control unit and by an unconventional core memory, called the Transfer Memory (TM), which in conjunction with the Iterative Array, can operate as an associative memory. -11- 1.U.3 Documentation Report Report No. 338 Borovec, Richard T. , "The Pattern Articula- tion Unit of Illiac III: Hardware Imple- mentation of the Homogeneous Instruction "BOOLE", June 20, 1969. Report No. 285 Koo , Ping L. , Borovec, Richard T. , "The Pattern Articulation Unit of Illiac III Simulation: Part I, Iterative Array Transfer Memory, BOOLE Control", September 20, 1968. Report No. 253 McCormick, B.H., Watson, W. J. , Borovec, Richard T. , "The Pattern Articulation Unit of Illiac III: Homogeneous Boolean Functions in the Iterative Array", January 8, 1968. -12- l.U.U HARDWARE STATUS REPOI - Perc entare Conroiote ;r Unit : Pattern Articulation Unit r -recessing r.aravare 100* 10 .rcl sequences 20* L_^ imaged Number of Statements TOO Hardware System Design Lcjieai Design - ay o ux 95* 95* 95* 95* onecAOUu 10* Estimated Number of Cards: 1800 High Level Flowcharts 10* Control Point Flowcharts logical Design 'out Wiring LnecKout timated Number of Control Points: not applicable 20 30 ko >u 7 -j \j. ^Microprogrammed control is planned except for the BOOLE instruction realization. . -5/69 -13- 1. 5 Interrupt Unit 1.5.1 Function The Interrupt Unit (IU) of Illiac III is a message store-and- forward processing unit through which all processor-processor communica- tion takes place. In addition certain system-wide facilities, e.g. system accounting clock, etc., are maintained by the unit. 1.5«2 Documentation Two DCS file notes are in draft form: "Design Considera- tions for the Interrupt Unit of Illiac III" "by R. M. Lansford and L. N. Goyal and "A Hardware Realization of the Interrupt Unit of Illiac III" by R. M. Lansford and L. N. Goyal. -Ill- 1.5.3 PATUS R] Pore e n t a r c C o :.'. r . 1 '-• t e Interrupt Unit are ^.utinatec. i-Junoer c; Statenenos 90$ )esi~r- "out 20$ 10$ ! .-". O J.". .istmatea. ijumoer oi oarc.3 : 25 I.C. Cards Level Flowcharts 80$ Control Point Flow.&harts _c/:ica^ Design 6o# ijayoui 20$ O..CCAU -* v tiiaated Number of Control Points U0 20 ;C \k0 ■yj I 6o 7C I i *Simulated as indirectly as called by the TP and I0P simulations. /o9 -15- 1.6 Exchange Net 1.6.1 Function The Exchange Net is depicted in Figure 1 as having six Processor ports and eighteen Unit ports. The purpose of the Exchange Net is to provide a 50-bit Processor-to-Unit information path and a 50-bit Unit-to-Processor information path for every possible Processor- Unit pair. 1.6.2 Documentation File Number File No. 790 Krabbe, S. Paul, "A Discussion of Illiac III Processor-Unit Communiction Via the Exchange Net", March 8, 1969. -16- 1.6.3 .. : _ : Exchange Net 10 20 20 1 1 1 i 1 1 y ■*• 1 ■> . _-^_ _:.. • .;..r^'.;-re . _ -" C _ L _ "U^I.JCS ! . ...... \J ~ ^~ - . ^^-^ ^ _. *_* ^ ^ ' ^J i. ^ w . 1 1 ! 1 ■ .- ■ , Of . .... :_:::: 100$ 1 1 100$ 100$ 90$ , ~^ -■ .jicir oi Lc.rc<6 912 1 Flowcharts *_ . :cl Dej 100$ 100$ ; mil c e ic o* ^ ontrol Points *Not applicable. Control point strategy was not used in the Exchange Net -IT- 1.7 I/O Processors 1.7.1 Function An Input /Output Processor (I0P) directly controls all input/ output operations on the 8 channels under its jurisdiction. Each of the 8 channels operates similarly to a selector channel while the I0P directs their operation in a multiplexing fashion. The I0P control is divided into two parts: the Task Sub- processor (TSP) and the Channel Subprocessor (CSP). The Task Subproces- sor controls the sequencing of tasks within the I/O Processor, the handling of the various interrupts, and the execution of device inde- pendent commands (DIC's). The Channel Subprocessor handles the execution of device dependent commands (DDC's); thus it controls the information exchange with the Channel Interface Units (CIU's) and initiates memory access requests when data transfer is required. 1.7-2 Design Features The I0P design accommodates very high data rates (up to 10 megabits per second is required for scanner data). Prior to the initiation of any data transmission command, the I0P determines whether or not suf- ficient channel capacity remains to insure that the maximum I0P data rate is not exceeded by adding this device's data to that already being handled. In addition to conventional block data transfers the I0P per- mits I/O data to be in a linked list format in core memory. Another feature of the I0P design is the capability of controlling from a single I/O program the operations on up to 3 different channels. -18- 1.7-3 ::. . CATUS -■- I ... • . Gen, ". tc , . - . I/O Processors iJ 20 30 M >>G L>0 r r ' ' j j J J i ! z io:: * 1 ! ! .--•^cc5si::^ Hardware I ^cr.wrol Sequences I ;."_^ea Kujiber of Statements: j I . ... ^ ..- .,._. •oies D«oi«a» 8o ?< ^^^^^^^ i . . :icol Deeicn 50?, ! 1 ■ _ '_ .' Oli L , 1 i *. . ' " in ff , i .> *.C ClCO .a w 1+50 1 ■ - . ~ - ili~h Level flowcharts 80% atrol Point Flowcharts 60% _c^;ica_ Design Layout Wiring Checkout Estimated Numoer of Control Points: 350 - *The general I/O structure was simulated by G. Cederquist in 19&7 and - the control flowcharts for the proposed register structure was simulated by L. Katoh during the first quarter of 1968; however, no simulation has been done on the present form of design. .'/ o/c9 -19- 1.8 Channel Interface Unit 1.8.1 Function A Channel Interface Unit (CIU) provides 3 words of buffering between the very fast 1/0 Processor and the relatively slow peripheral devices. In conjunction with this buffering function the CIU provides the necessary interface control signals to the device controller for all data transfers, and it properly formats this data as it flows in and out of its buffers . The CIU also insures that the control signals to the device controller occur in the proper time sequences, as defined in the IBM System/360 Interface Manual. -20- 1.8.2 te -CC.-GU"0 ^_~a^ec. iVumoer ■ ; Channel Interface Units 10 20 iO »0 y. SO YG I - * ! ! ! ! ..vjcjj:::j ..^:v.._re 1 ; Zov.ztqI £ . aces 1 \ i Ziwinaued Iranber of Statements : ; s : .. • H irdvare i ! I i ^Extensive simulation has been done by J. Hayes during 1967 on the form of the CIU that existed at that time. -21- 1.9 Device Controller 1.9-1 Function A Device Controller (DC) provides the proper interface control signals between the peripheral devices and the 1/0 channel. With respect to the channel the Device Controller affords the standard IBM System/360 Interface. With respect to the peripheral device the Device Controller assumes the task of decoding the various control signal sequences, but enough flexibility is allowed to enable the peripheral device to control such DC features as mode of operation (multiplex or burst) and the sup- pressibility of device data. -22- 1.9.2 HARDWARE STATUS REPORT Percentage Complete Lt: Device Control i Pr 10 20 30 uo 50 60 70 bo 90 Si: :.' -ion ■ocessinc Hardware 0% r»zrol Sequences 0f> Estimated Number of Statements : s.re System Design 80$ :ical Design 30% i»ayout V.' ir in ~~ Checkout timated Number of Cards: 10 i.e. Cards . - v. level Flowcharts 90% Control Point Flowcharts 60% . Logical Design Luyout Wiring Checkout Estimated Number of Control Points: 6o ■ 10! 728/69 -23- 1.10 S-M-V Controller 1.10.1 Function A new direction in image acquisition and display is to append a Video Communications Net to the central computer so as to provide the remote users with video communication to a centralized image processing facility. In addition to facilities for the acquisition of pictorial information, there is also a need for interactive display systems to present both intermediate and final processed data. The subject of graphic display terminals has been extensively discussed in the litera- ture. Scan-display systems oriented towards image processing, however, with particular attention to bypassing the central processing unit for as many tasks as possible, have not had comparable development. The system described below, called the 'Scanner-Monitor -Video' (SMV) system of Illiac III, is focused on this latter area. Central to this system is the S-M-V Controller. 1.10.2 Design Features Figure 2 shows the system as it has evolved. High resolution scanners allow the scanning of the film for accurate measurement purposes and also allow the construction of images on film. High resolution monitors are slaved to the scanner system in a manner which allows the monitors to borrow inexpensively the scanner control. The video switching matrix pro- vides the closed circuit television facilities for remote users. High resolution CCTV cameras are provided for image encoding and acquisition. Remote video consoles, consisting of two high resolution monitors and a teletype set, provide information display at the remote user's end. The Videograph printer outputs a fascimile copy at the rate of one sheet every 0.8 seconds, where the copy can have any admixture of text, graph or half- tone pictures. Video images can be treated as if they were on film and thus the same encoding techniques and the same programs could be exploited for both without program change. The character generator provides facili- ties for message handling and display in general, particularly for CAI, which along with the scanner provides the flexibility of displaying line drawings and half tone pictures intermixed with the text. More details about the devices shown in Figure 2 are given in Section 1.11. -2k- DIGITAL DATA INPUT CHARACTER GENERATOR 525 TV CAMERAS 1536 F/S CAMERAS MICROIMAGE STORAGE DIGITAL DATA INPUT/OUTPUT , 1 i VIDEO SCAN CONVERTER i I . i VIDEO SWITCHING MATRIX VIDEOGRAPH PRINTER 525 LINE TV MONITORS REMOTE VIDEO CONSOLES VIDEO STORAGE Figure 2 - Block Diagram of the Scan/Display System. Note that the Video Scan Converter can be bypassed under program control -25- 1.10.3 Prototype Scanner A simplified scanner has been "built as a means of testing various logic and analog portions of the final SMV system. The simpli- fied scanner scans a 512 x 512 raster in one of 6k selected areas of the object film, packs the gray level information into 32 bit words and stores this information in one of the Fabri-Tek memories. The same logic permits the stored information to be extracted, decoded and dis- played on a monitor. The system is operational, but is now being dismantled for replacement by the final S-M-V system. 1.10.1+ Interim Scan/Display System Under the current contract a link between a scanner /monitor of Illiac III and the IBM 360/75 is being established. This link utilizes the full Scanner-Monitor-Video Controller as described in the presentation at the Spring Joint Computer Conference 1969- Scanned data is transmitted through the Exchange Net to the fast core modules of Illiac III. Data can then be transmitted first to the PDP-8, then 2 exploiting a previously established graphics connection between the PDP-8 and the IBM 360/75 » data can in turn be transmitted to the service computer, the IBM 360/75' This "interim" scan/display system is illus- trated in Figure 3. 1. Dunn, L.A. , et.al., "Parametric Description of a Scan-Display System", Department of Computer Science Report No. 308, February 5> 1969- 2. Supported under Contract AT(ll-l)-lU69 with the AEC. -26- UJ CO \- I- A o / \ £T c D O C £ c D ! V A Q o o: £ o £ V o G0>Q_> en S3* H ft w •H O CO is 0) •p I 0) •H or UJ < o CO GDX-UJ o O -27- 1.10.5 Documentat ion Publication Dunn, L.A. , et.al., "Parametric Description of a Scan-Display System", AFIPS Conference Proceedings, Vol. 3 1 *, p. 187-206. Report Report No. 320 Divilbiss, J.L. , "illiac III Scanner Analog Circuits", April 10, 1969- -28- 1.10.6 HARDWARE : STA rus ] REPORT Per c en tage Complete i _. S-M-V Controller 10 20 30 1+0 50 60 TO oO &o ZoTiZrol Sequences iinated Number of Statements: j ': :.r Hardware Cy --" Design 90% - :al Design 90% _ lYout 90% Checkout 60% . timated Number of Cards: 220 . -.rcl Lii h eve" Flowcharts 80% - — Control Point Flowcherts 60% 1 Logical Design 50% 1 30% ■ 1. Checkout 10% Estimated Number of Control Points: 250 - fjfj _ 3/69 -29- 1.11 Scan-Display Devices 1.11.1 Scanners The scanners are flying spot scanning systems with an added diquadrupole coil for astigmatic defocusing of the spot into a line element to achieve a slit mode. All scanners are capable of either scanning from developed film or photographing onto unexposed film. The optical path of the beam is split, with one path transversing the film and the other path through a reference grid to establish stability against engraved fiducial marks. Several types of media transports are provided to handle the projected range of problems. A 70 mm. scanner is provided primarily for 70 mm. negative bubble chamber film. Here the format of the raster is 2.362 inches x 3-522 inches, and the minimum spot size is approximately 0.001 inch at the film. Due to the length of the frame to be scanned, scanning is done in two steps. The two horizontal halves of the frame are scanned successively with a h mm. overlap to establish half-frame continuity. Large motors are used for slew and gross positioning of the film and a small digital stepper motor is used for fine positioning of the frame. Frame position sensing is accomplished by using the digital stepper motor as a tachometer and by counting sprocket holes. Total film capacity is 1000 feet. A scanner for handling hj mm. film is similar to the 70 mm. transport design except for the following: The film format is different. A friction drive is used on the digital stepper motor, since the film is unsprocketed. The frame position is determined by sensing small index blocks at the lower edge of the film using a fibre-optics light guide and a photodiode. -30- The microform scanner contains three units. The first is a 35 mm. full frame digitally controlled camera/ scanner which can read light through the film, or alternatively record computer-generated images. The second unit contains a 16 mm. Bolex camera for making computer-generated black and white movies and a modified 16 mm. film editor for scanning 16 mm. film of all types. The third unit is a microfiche transport mechanism for scanning and producing a single microfiche in the 72 image COSATI format. For the three different units the C.R.T. raster is adjusted optically to fit the particular frame size. A fourth type of scanner is built around a microscope with a digitally controlled automatic stage. Positional accuracies are on the order of _+ 2 microns, and the maximum slide area coverage is 1.2 inches x 1.2 inches. Variable reduction is available from a four objective rotating turret. Full visual observation is available to an operator. 1.11.2 Monitors The monitors consist of 21 inch cathode ray tubes controlled in a manner similar to the scanner C.R.T.'s; viz., digital position counters control the spot location through accurate, high-speed digital-to-analog converters. The monitor counters are digitally controlled directly from the S-M-V Controller via an incremental communications scheme; essentially the only commands issued by the S-M-V Controller for the monitors are increment the counters, decrement the counters, reset the counters, and reset the parameters. Therefore, any spot movement possible on a scanner C.R.T. can be accomplished on the monitor C.R.T. The video input for the C.R.T. grid is also synchronized by the S-M-V controller. Included with the monitors for communications to a central processing system are a selectric typewriter, microtape input /output tape drives, and a light pen for cursor control. -31- 1.11.3 Video Switching Matrix The video switching matrix is a mechanical cross bar matrix. Therefore, the switching speed will be in the order of 100 milliseconds or less. In this routing switch any source can be switched to from one to three different destinations simultaneously. In addition, switching provisions are also included to mix any two video sources to provide a composite signal to the selected destinations. 1.11. k Character Generator The Character Generator is designed to accept up to 512 ASCII characters into its h096 bit memory. A 99 dot matrix, 9 dots wide by 11 dots high, is used to develop each character into the appropriate video levels. The maximum TV screen display is l6 horizontal rows of 32 characters or spaces each. Alternatively 132 characters/line printout can be generated on the Videograph printer. A special cursor is also available along with eight commands for controlling it. 1.11.5 Videograph Printer The Videograph Printer can print on demand at a rate of 0.8 seconds i er 8-1/2 x 11 inch sheet. Horizontal resolution is 128 lines per inch and vertical resolution matches the high resolution of the 1536 line slow CCTV cameras. Gray scale resolution is limited to four shades. Tne paper used is inexpensive zinc-oxide coated stock. 1.11.6 1536 F/S Cameras The 1536 F/S cameras are vidicon camera units which can be remotely selected to operate either in fast scan mode (15 frames per second) or slow scan mode (1.25 frames per second). The format of either mode is 1536 lines per frame done in a sequential (non-interlace ) scan. The aspect ratio is variable, but it is set for a nominal 8-1/2 x 11 aspect ratio. The camera bandwidth is limited to 9-5 Mhz for fast scan and l.U Mhz for slow scan. -32- 1.11.7 Remote Video Consoles Each remote console is a self-contained unit with two video monitors and the necessary equipment for communicating with a digital computer. The video monitors consist of a 17 inch 1536 lines per frame slow (1.25 frames per second) monitor with a P-26 phosphor and a 17 inch 1536 lines per frame fast (15 frames per second) monitor with a VC-U pnosphor. Each monitor matches characteristics of the associated camera. Of the six remote consoles, three can be provided with high resolution television camera input. 1 . 11 . 8 525 Line T.V. Cameras and Monitors The 525 T.V. Cameras and Monitors are conventional television units; namely, 525 lines per frame, 30 frames per second interlaced (60 fields per second). These units provide for relatively low cost reduced resolution, which is sufficient for many message routing and simple acquisition and display purposes. -33- 1.11.9 Percent . . ...... Scanner 10 20 30 ko 50 70 j > i ... JS i r - hardware C^.:-ro2 Seq jes i _Ijuirr.atea dumber of Statements : i i i ~. Desi»n 100 $ 1 I Desi-n 90?* i . -out 90$ .-. - 90$ i lockout ^ Lczimated Number of Cards : 1 55 , c 2 Hi~h Level Flowcharts Tirol Point, Flowcharts Logical Design i^ayout s_- . - '•- C -\ y-/ «*, - .-i::._;;e:L Number of Control Points: 1. Digital-to-analog converters and other special function cards 2. Subsumed to S-M-V Controller. _ 3 U_ 1.11.10 ■ • , : Monitor 10 2:0 30 : i i : ! : I i - 'S' . 1 T 1 ! i i — • oi Statements : 1 i l j - i 1 .. _ zL.;:. 100% *" • « V^ \-/ /I/ 90 ■ i I : _ Point jjlowchacrts i i i i ; i ■*- -' --- — ;-> -* | ! 1 ; j i i ! u - 1 i tea ITumber of Control Points: ! \ ! 1. Indicator panels associated with the display of TP registers is not included in this estimate. 2. Control is sufficiently simple so that it has been subsumed to the processing hardware . -35- 1.12 Intermachine Link 1.12.1 Function An Intermachine Link provides direct coupling between the PDP-8/338 Computer Graphics System in the Department of Computer Science and a processor port of the Illiac III Exchange Net. The link provides two 50-bit data registers at the Illiac III end (one for receiving data, one for transmitting), full parity checking and timing signals to effect the information exchange. Four PDP-8 words are assembled to form one 146-bit word (augmented by four parity bits) in approximately 15 microseconds. Included in the link is a teletype which may be used as a remote console typewriter to the PDP-8/338. An independent link exists between the Department's PDP-8 and the Computation Center IBM 360/75 wherein these two machines can communicate via a graphics partition in the service computer. By extension then the Illiac III - PDP8/338 Intermachine Link allows exchange of data with the IBM 360/75 system. -36- 1 .12.2 Intermachine Link . C- w - , 10 2 G ■"" o ■• vj i 5'-» j i ! i f 95% 85% ~cs : 1^0 -iOVci £ — over, a.; owe not used not used 95% 85% 85% 85% i jc .'.tur.0Si" oi Jontrol Points not used • ! j : 1 ;' Statements : | ! ! I ! i | 95% i i ; | . ; 1 l 1 ' I I ! -37- 1.13 Low Speed Terminal Network 1.13*1 Function This net is used to communicate with Illiac III via numerous remote consoles . Each remote console can have the following low data rate equipment from the available equipment pool: a teletypewriter, a Line-type magnetic tape module, a machine control patch panel, and an analog instrument interface and a cursor control. Thus as many as five or more signal lines must be provided for each console to accommodate low speed equipment . The communication channels can be Bell Telephone lines (both analog and digital data-phone connections), direct wire links to local teletype consoles, or over multiple twisted-pair cables laid in conjunction with the Video Communications Net. 1.13.2 Design Features The low speed terminal devices communicate with Illiac III through two Low Speed Buffers, each capable of handling ik terminal devices. These buffers form in effect memory units directly accessible by a Taxicrinic Processor using standard operand addressing procedures. -38- 1.13.3 : r'-RBWARE Perccr.ta '•; Lov Speed Terminal Network 10 :;&rc.vare liurr.&er of Statements 20 jol Uog .ec .,w"cer oi Caras ,evel flowcharts 70$ 3or.wrol Point .r'lowchsrts 1+0$ — ^ e t> i j 20$ —you-; 10$ ^;.^C;:GU' — w - J — - - . ICuxaber of Control Joints 30 ^0 >u OJ ' to o: _ i -• l.lU Power Distribution l.lU.l Function The purpose of this system is to provide an effective means of controlling the power supplied to various subsystems of the Illiac III. The system allows individual sections of the machine to be de-energized for trouble-shooting and for initial calibration during checkout. I.II4.2 Design Features The DC Power Distribution System comprises 1) the Primary Power Supplies 2) the Power Distribution Center, and finally 3) the Turn-on/Regulation Control. This latter control can be subdivided into four stages: turn-on of the control voltage supplies , turn-on of the primary voltage supplies to 50% nominal ratings, regulation of the primary supplies at full load and finally regulation and remote sensing of the DC power as distributed to the individual sections of the machine. The AC Power Distribution System provides two 200 amp secondary panels and a tertiary 20 amp service with distribution to the requisite sections of the machine. l.lU.3 Documentation A 150 page manual detailing the design and operation of the DC Power Turn-on/Regulation System is currently in draft form. -1*0- l.iU.U .: ...... . Power Distribution 100$ 100$ ;ement s 100$ 100$ 100$ 30$ 20$ _ .- -_..._ l,Cl .,„'.:er or Caras : 400 Level Flowcharts 100$ .Oi.trOi. i'Oj.IVC Flowcharts not used 90$ 20$ 20$ irol Points : not used • r0 , I fU , J , I J., I *Simulation here is interpreted to mean analog circuit studies of the turn-on and regulation functions. -Ul- SOFTWARE DEVELOPMENTS 2.1 Operating System 2.1.1 Supervisor - Processor Interface Definition One of the concerted goals of the Illiac III Computer System has been to formulate a simple but powerful Operating System. A key constituent of this strategy has been to study closely the Supervisor - Processor interface, with the hope that the software-hardware boundary might be bridged as harmoniously as possible. The report discussed below describes this work. At the present the published description of the Taxicrinic Processors of Illiac III is deficient in three distinct areas. It is the purpose of a note by R. M. Lansford (now in draft form T to supply most of this needed description. a) The Taxicrinic Processors include sophisticated hardware to implment a two-level addressing scheme. The resultant software orientation and the operation of the paging hardware is explained. b) A multi-level priority interrupt scheme is defined. In the note is described the interrupt classes and the appropriate interrupt action and attempt is made to isolate data which must be manipulated. c) Specialized instructions must be provided to assist in the required manipulations. These instructions are defined and discussed. 1. Lansford, R. M. , "Operating System of the Illiac III Computer: Super- visor-Processor Interface", Department of Computer Science Report (in progress) . -U2- 2.1.2 Directory Structure Two classical directory schemes are the binary-chop and sequential-link pointer* methods. The method to be described, which is essentially that of Hibbard , embodies many of the desirable features of these two schemes, while avoiding many of the disadvantages. This method or storage directory system will be referred to as the Binary-Chop Pointer method. The BCP method reduces to either the binary- chop or sequential pointer linked directory methods at either end of its functional spectrum. The storage/directory method developed in the following paper, "Suggestions for Use of a Particular Directory Scheme" by D. Austin Henderson, Jr. and David E. Gold, Department of Computer Science Report No, 321, April 10, 19&9, allows for flexibility in modification of a rapidly growing directory while maintaining a reasonable number of searches neces- sary to locate items whose keys are stored in the directory. A mathe- matical analysis shows the average number of searches to be of the same order of magnitude as for a binary-chop method of table look-up while the directory itself need not be reordered to accommodate new entries. The analysis is followed by a series of procedures and suggestions for procedures which should prove useful when employing this method. *i.e. a directory in which a pointer in each entry indicates the next entry . 1. Hibbard, T.N. , "Some Combinatorial Properties of Certain Trees with Application to Searching and Sorting", JACM6 (January 1962), 13-28. -1+3- 2 2.1.3 Telecommunication Processing Package (TP ) A job control language has been defined consisting of approxi- mately twenty directives covering the following areas: 1) Initialization and Access Privileges 2) File Manipulation 3) Program Assembly and Execution h ) Debugging A task is the smallest unit operation which the computer may be requested to execute subject to a given deadline for completion. The command or instruction which causes the task to be executed is called a task directive . Accordingly task directives are commands or messages sent from the user's console to the computer to specify the next gross action the computer is to take. The set of permissible directives defines a programming language — one that is directly interpreted by the supervisor program. All other languages available to the computer system are considered sub- servient to this Task Directive Language. For this reason the latter language has been kept as simple and transparent as possible so as not to needlessly burden the user. A description of the language can be found in File No. 782, "Task Directive Language for the Illiac III Computer" by Linda M. Katoh, December 9, 1968. 2 2.1. h Image Processing Package (IP ) A number of graphical or pictorial description languages have been studied to determine desirable features of an image processing language, and to evaluate for each language its satisfaction of stated a priori criteria. After a brief survey of some of the most repre- sentative of these languages, a new image processing language IC0N was defined. 1. Schwebel, John C, "Toward the Specification of a New Image Processing Language", Department of Computer Science File No. 788, February 6, 1969 • -kk- It is our contention that the evolving formal theory of cog- nitive systems provides a basis for defining an image processing language. Also implied here is that this language has a structure intrinsic to visual data processing and may transcend the Chomsky language framework. A paper is in preparation. -U5- 2.2 Translators All work on translators has been stopped momentarily as all Research Assistants previously working in this area have heen drafted for the war in Viet Nam. 2.2.1 IBAL Assembler "The Illiac III Basic Assembler Language (IBAL)", Department of Computer Science Manual, March 1968 describes IBAL, the lowest level language used for Illiac III programs. With suitable constraints upon the naming of operands, each primitive operation in IBAL directly cor- responds to one Illiac III machine instruction. In comparison to other programming languages usually classified as "assembler languages", IBAL allows very general data declarations. In particular, declarations allow specifications of generalized tree-structured data items whose irreducible constituents are the smallest addressable basic elements of the machine. It is believed that this capability is essential to any programming language adequate for the translation of languages as complex as PL/l. Work was resumed on Pass 1 of the IBAL translator, written in PL/I for the IBM 36O. A state-transition matrix is used to process dec- larations. A structure table is set up for storage of declared structures (including single identifiers and arrays), with attributes and adjustment of node levels in the table according to declared levels and number of subscripts at higher levels. Reserved words are recognized and those which are storage attributes are indicated in the appropriate places in the structure table. Cell sizes (B, W, H, D) are distinguished from node names by context. Terminal node attributes are evaluated (except for values and lengths of constants) in the structure table in terms of number of bytes or a pointer to a list to handle the LIKE attribute. -1+6- It is anticipated that the only further major additions that will have to "be made to Pass 1 are suitable indication of alternate access structures and conditional format items. 2.2.2 PL/1 During the first quarter a set of nearly ^50 productions for PL/1 was completed. In addition, the set of actions necessary to build tables during the Declaration pass was finished. 2.2.3 PAX II In the course of design studies for the Pattern Articulation Unit (PAU) , it proved useful to introduce a programming language PAX, initially considered as a simulator for the PAU. This language intro- duced, we believe, the first systematic use of connectivity information in image analysis. The PAX concepts were systematized and extended in a series of basic papers by Narasimhan (then at this laboratory). The PAX language, as PAX II, has recently been implemented for the IBM 360/75 by J. W. Snively, Jr. and E. B. Butt, formlery of the University of Maryland, and is used, for example, by Kirsch and Lipkin in their experimental studies of bio-medical image processing at the National Institute of Health. In addition PAX was taught this year as the language for picture preprocessing and feature extraction in a recent commercial course on Image Processing by Cybex Associates, Inc. PAX shows every promise of becoming the FORTRAN of image processing. In an effort to provide a bridge between the present IBM 360 simulation and the PAU hardware execution of local feature extraction algorithms, the Snively-Butt version of PAX II was adapted to the Illinois installation. Report No. 3lU, "The PAX II Picture Processing System at the University of Illinois, March 19&9, edited by R. T. Borovec describes the translator. -1+7- 2.2.U LEFT: Language for Editing and Formating Text The problem of recognition and transcription of text, for example, the automated extraction of citation listings from technical serials, has elicited considerable interest. Central to all tasks of this character is the intermediate step of extracting a typographical description of the input text. Our observation has been that much research on information retrieval has collapsed from sheer clerical burden — the transcribing and editing of data for augmented catalog listings, etc. Accordingly it would appear more appropriate to master the textual transcription task first. This view has been consistently in mind in the design of the Illiac III computer system, and has dictated the choice of high resolution television equipment, the Videograph printer and our microfiche production and scanning equipment. If an entering document is to be scanned and stripped of its typographical description, it must then be mapped into the analysis language (LEFT: Language for Editing and Formating of Text) . That is, sufficient information is extracted from the input image that a type- setting machine could regenerate the document . The LEFT language embodies a complete distinction between the medium- independent structure of text and the purely typographical (or packaging) description of text. Because of budgetary limitations, work on the LEFT translator was terminated early in the contract period and the definition of the LEFT language was summarized in Report No. 291. 1. Flowerdew, Stanley J., "LEFT: A Language for Editing and Formating Text", Department of Computer Science Report No. 291, October 31, 1968. -U8- 3. PATTERN RECOGNITION THEORY 3.1 Graph Transformation Grammars Work in this area is intended to provide a theoretical founda- tion for the study of graphical transformations applied to a set of objects interrelated by binary relations. Given a large set of objects with complex interrelations, it may be possible to apply a transformation to a subset of objects — and relations — in order to simplify structure. The inherent hierarchial structure existing on the set may suffice to determine the simplification criteria. For example, consider a Boolean algebra, X, of subsets of a set. The inherent structure is given by the binary operations "union" and "inter- section". An example of a possibly desirable transformation is: X R X and X R X transforms to (XCX )R X . A criterion for performing this transformation may be its reversibility, i.e., if: (X X UX 2 )R 2 X 3 and \\^ 2 — * X 2 R 2 X 3 The transformation given above allows us to form an expression by grouping two elements of the set into a composite element. Other transformations may correspond to general ways of forming expressions of operations, relations and elements of X. We would like to be able to answer questions such as the following : 1) For which individual relations is a transformation possible for all x independent of other relations involved in the subgraph being transformed. 2) For which groups (e.g. pairs or triplets) of rela- tions is the transformation always possible. -1*9- A report to be issued in August entitled, "Consistent Properties of Composite Formation Under a Binary Relation" by J.C.Schwebel and B.H.McCormick attempts to define properties of binary relations that will be useful in implying graph transformations. Properties of a general relational system between lattices are defined. Then a reduction of the set of possible consistent combinations of properties is carried out, followed by a construction procedure to obtain examples of all consistent combina- tions. This paper supersedes File No. 769 • A paper in progress enumerates and considers some specific graph transformations. An attempt is made to answer the first question above by showing which transformations can be implied by properties defined in the above report. Question 2 is approached by considering the partitions induced on a class of relations according to their behavior in a transformation. It is our intention to apply the theoretical work in this area to image processing. The results so far are quite general and may have application to other areas requiring a classif icatory or general composite analysis approach. -50- 3.2 Game Model of Image Processing In what sense can it be said that a given machine can recognize and describe pictures as well as a man? In what way is the machine demon- strated to be as clever as a given human observer? One can envision matching machine and human image recognition abilities at interim stages in the recognition process. To do so implies that the human perceptual processes must be slowed down — by selective information starvation — so that the recognition algorithms can be better monitored. We can withhold from the observer spatial information — allowing him to see only small "chips" of the total image, constrain his exposure time (image flashing), delete from the image given spatial frequencies (holographic filtering), compress gray and color scales, etc. However, consider the following game (Figure l): the player is presented an image projected onto a light-absorbing surface. He is then given a set of chips, of various sizes and weights (costs). The "game" is to place these chips upon critical nodal areas of the image in a manner to first achieve an adequate description of the image (the "aha" point) at the least aggregate cost in chips. Given a homogeneous class of images (aerial photographs, blood cells, machinery, etc.) it should be possible to train players: by recording the moves and strategy decisions of the experienced player, the novice can acquire the requisite techniques. And this training process in turn can be used to better codify the recognition strategies employed — extending in greater detail the familiar scanning instructions , as previously developed for scanning fingerprints and bubble chamber film. A feasibility study was undertaken this past contract year to probe the reality of this game model of image processing. Simple line drawings, cartoons and cytological smears were used as test scenes. For line drawings and cartoons the experience with the game soon lead to the concept of a name- independent parse of the scene (see Section 3-3 below). However, the original definition of the game for images rich in texture proved inadequate, and has forced us to formulate alternate definitions of texture. In general the game model approach to image processing would now appear to warrant serious and systematic investigation. -51- 3.3 Analysis of Simple Line Drawings Is it possible to decompose a visual scene into the consti- tuent objects forming it, without requiring prior detailed knowledge of these objects? For the restricted but important case of scenes of juxtaposed 3-dimensional blocks, Guzman has given a heuristic strategy: "[The program] does not need to know the "definitions" or descriptions of a pyramid, or pentagonal prism, in order to isolate these objects in 2 a scene containing them, even in case they are partially occluded. For more general scenes there are as yet no comparable image articulation strategies. To view the question differently, consider simple line drawings — such as the illustrations of a child's coloring book. Here we instinctively group together the heavily-outlined regions of these scenes to build compo- site structures, and continue this process to decompose the scene into its constituents. Hence, prior to the naming of the objects of the scene we can extract the lattice (i.e. the extension for scene description grammars of the description tree , or P-marker, of context-free languages) representing the decomposition of the scene into composite items. Of course these items may represent partially occluded objects, which can probably be filled in (revealed) only with the use of supplementary name-dependent information. (The classical case of implying the occluded table leg comes to mind. ) But the critical observation is that a name-independent structural decomposition of the visual scene is normally possible — even though we do not yet know how to mechanize the process. If we were to descend the evolutionary scale we might hypothesize that successive animals must survive with an ever smaller vocabulary of object names, and hence these animals need to rely increasingly upon a name-independent type of scene decomposition. 1. Guzman, A., "Decompositon of a Visual Scene into Three Dimensional Bodies, AFIPS-Vol. 33, 1968. 2. ibid, p. 303. -52- An early attempt to mechanize this latter type of image 3 articulation has been reported by John Schwebel . In the strategy employed there, the irreducible regions of the image are presented as the nodes of a digraph, linked by inter-regional relationships of "near", "inside", "abuts", etc. A consistent procedure for clustering nodes (regions) together to form new composite nodes, and extending the relational links to these composites, is described. This contract year the above name- independent "parsing" k strategy has been further studied , with an eye to using similar digraph representations of the input scene, and like visual clues which are intrinsically name -independent. Strategies of this type will in the future require computer simulation, as the eye/brain is too easily beguiled in making faulty hand simulations which ignore consistent, but visually-abhorrent, scene decompositions. 3. Schwebel, John C. , "Use of Graph Transformations to Characterize an Image: An Illustrative Example", Department of Computer Science File No.. 770, July 1968. k. Schwebel, John C. , McCormick, B.H., "Analysis of Simple Line Drawings", Department of Computer Science File No. 796, April 11, 1969 • -53- BIBLIOGRAPHY k.l Publications McCormick, B. H., "Advances in the Development of Image Processing Hardware", Image Processing in Biological Science, Ramsey, D.M. (Editor), University of California Press 1968. Atkins, Daniel E. , "Higher-Radix Division Using Estimates of the Divisor and Partial Remainders", IEEE Transactions on Electronic Computers, Vol. C-17, Number 10, October 1968. Dunn, L.A. , et.al., "Parametric Description of a Scan-Display System", AFIPS Conference Proceedings, Vol. 3 1 *, p. 187-206. k.2 Papers Presented (Conferences) Atkins, Daniel E. , "Design of the Arithmetic Units of Illiac III: Use of Redundancy and Higher Radix Methods", Workshop on the Theory of Computer Arithmetic, Third Annual IEEE Computer Con- ference (Minneapolis), June 19&9* Borovec , Richard T. , "A Report on the Use of Microprogramming for the Illiac III Image Processor", ACM Workshop on Micro- programming, Bedford, Massachusetts, October 6-9, 1968. U.3 Outside Talks McCormick, Bruce H. , "Graph Grammars for Image Processing", Joint Meeting with the Society of Photo-Optical Instrumentation Engineers and the Pattern Recognition Society, Washington, D.C., August 25, 1968. McCormick, Bruce H., "Seeing and Believing by Machines", Sixth Annual Allerton Conference on Circuit and System Theory, Allerton House, Monticello, Illinois, October 2, 1968. _ 5 U- k. k Reports and File Numbers Issued Report Report No. 275 Report No. 285 Report No. 290 Report No. 291 Report No. 308 Report No. 31 1 * Report No. 320 Report No. 321 Report No. 333 Report No. 338 Report No. 3^1 Borovec, R.T. , "The Logical Design of a Class of Limited Carry-Borrow Propaga- tion Adders", August 1, 1968. Koo, Ping L. , Borovec, R.T. , "The Pattern Articulation Unit of Illiac III Simulation: Part I- Iterative Array Transfer Memory- B00LE Control", September 20, 1968. Koo, Ping L. , Atkins, Daniel E. , "Arith- metic Unit of Illiac III: Simulation and Logical Design-Part II", October 28, 1968. Flowerdew, S.J. , "LEFT: A Language for Editing and Formating Text", October 30, 1968. Dunn, L.A. , et.al., "Parametric Description of a Scan-Display System", February 5 5 1969- Borovec, R.T. , "The PAX II Picture Processing System at the University of Illinois Pro- gramming Manual", March 18, 1969- Divilbiss, J.L., "Illiac III Scanner Analog Circuits", April 10, 1969 Gold, D.E. , Henderson, J. A. , "Suggestions for Use of a Particular Directory Scheme" , April 10, 1969. Atkins, D.E., "Design of the Arithmetic Units of Illiac III: Use of Redundancy and Higher Radix Methods", May 1969. Borovec, R.T. , Watson, W. J. , "The Pattern Articulation Unit of Illiac III: Hardware Implementation of the Homogeneous Instruc- tion "BOOLE", June 20, 1969. Nordmann, B. J. , "illiac III Computer System Manual - Taxicrinic Processor (TP)", Volume 1, July 1969. -55- File Number File No. 769 Schwebel, J.C., McCormick, B.H. , "Properties of a Discrete Space Preserved by Image Processing Relations", July 18, 1968. File No. 770 Schwebel, J.C. , "Use of Graph Transformations to Characterize an Image: An Illustrative Example", July 18, 1968. File No. 771 Engle, J.T. , "PL/l Declaration Pass I - Structure", June 28, 1968. File No. 773 Krabbe, S.P. , "Specifications for a 9" False Floor for DCL 223 That Overlaps Existing False Floor in DCL 280" , August 7, 1968. File No. 776 Borovec, R.T., "The Pattern Articulation Unit of Illiac III: Display System: Design and Implementation", September 30, 1968. File No. 780 Flowerdew, S.J. , "Automatic Karyotyping: A Statement of the Problem and Summary of Image Processing Procedures", November 6, 1968. File No. 782 Katoh, L.M. , "Task Directive Language for the Illiac III Computer", December 9, 1968. File No. 788 Schwebel, J.C, "Toward the Specification of a New Image Processing Language", February 6, 1969. File No. 790 Krabbe, S.P., "A Discussion of Illiac III Processor-Unit Communication via the Exchange Net", March U, 1969. File No. 79^ Dunn, L.A. , et.al., "Programmed Aids for the Scan-Display System of Illiac III" (to be used with Report No. 308), March lU , 1969. File No. 796 Schwebel, J.C, McCormick, B.H. , "Analysis of Simple Line Drawings", April 11, 19&9* File No. 797 McCormick, B.H. , "illiac III Bibliography, Condensed Listing", April 30, 1969. -56- File Number (550 Series) File No. 550-116 Krabbe, S.P., "Supplemental Specifications for Wire Wrap Wiring of Sections 1 and 3 (PAU) of the Illiac III Computer System, August 13, 1968. File No. 550-117 Serio, F.P. , Pelg, E. , "Procurement and Design Specifications for Printed Wiring Boards", September 23, 1968. File No. 550-118 Krabbe, S.P., "Specifications for Termi- Point Wiring of Section 6 (Taxicrinic Processing) of the Illiac III", November 29, 1968. File No. 550-119 Krabbe, S.P., "Specifications for Wire Wrap of Section 13 (Exchange Net)", November 6, 1968. File No. 550-120 Krabbe, S.P., "Specif iations for a 9" False Floor for DCL 223 That Overlaps the Existing False Floor in DCL 280", November 5, 1968. File No. 550-121 Krabbe, S.P., "Specifications for Wire Wrap of Section iV 1 , November 5, 1968. File No. 550-123 Krabbe, S.P. , "Specifications for the Mechanical Termination of Twisted Pair Transmission Line Z =95 ohms + 5 ohms With Burndy Contacts in o — the Illiac III Exchange Net", January 28, 1969. File No. 550-124 Krabbe, S.P., "Specifiations for Power Wiring of Section 7 (Arithmetic Unit) of Illiac III Computer System", February 5, 1969- File No. 550-125 Krabbe, S.P., "Specifications for Termi-Point Wiring of Section 7 (Arithmetic Unit) of Illiac III Computer System", February 18, 1969. File No. 550-126 Borovec, R.T., "Specifications for Wire-Wrap Wiring of Integrated Circuit Board 1018-299-00", March 13, 1969- File No. 550-127 Krabbe, S.P., "Specifications for Mechanical Termination of Coaxial Cables (RG-195/U Used in the Illiac III System", March 11, 1969. File No. 550-128 Lewis, G.T., "Specifiations for Termi-Point Wiring of Section 32B (Descrete Beam Motion Logic) of the Illiac III Computer System", April 16, 1969. -57- 5. ILLIAC III STAFF Senior Staff Dr. James L. Divilbiss - Principal Research Engineer Dr. Robert M. Lansford - Research Associate Professor Bruce H. McCormick - Principal Investigator Professor Sylvian R. Ray- Prof essor K. C. Smith - Consultant Professional Staff Engineers Robert C. Amendola Richard T. Borovec Lawrence A. Dunn Mrs. Linda M. Katoh Ronald G. Martin Electronic Engineering Assistants David L. Foster S. Paul Krabbe Edmund Pelg Frank P. Serio Joseph V. Wenta *Daniel E. Atkins *Sergio Franco *Lakshmi Goyal *Richard P. Harms *Ber.nard J. Nordmann *Val G. Tareski Programmers Miss Mary Ann Hag en *John C. Schwebel Drafting Electronic Technician II John L. Fileccia Robert G. Thomson Ronald C. Morrison Stanislavs Zundo Secretarial Electronic Technician I Mrs. Donna J. Stutz Eugene E. Althaus George T. Lewis William A. Miller Bennie D. Williamson *Research Assistants -58- FormAEC-427 U.S. ATOMIC ENERGY COMMISSION (6/68) UNIVERSITY-TYPE CONTRACTOR'S RECOMMENDATION FOR aecm3201 DISPOSITION OF SCIENTIF C AND TECHNICAL DOCUMENT ( See Instructions on Reverse Side ) 1. AEC REPORT NO COO-1018-1187 Report No. 3^2 2. TITLE TECHNICAL PROGRESS REPORT - Oct. 1968 - September 31, 1969 3. TYPE OF DOCUMENT (Check one): H a. Scientific and technical report 1} b. Conference paper not to be published in a journal: Title of conference Date of conference Exact location of conference Sponsoring organization □ c. Other (Specify) 4. RECOMMENDED ANNOUNCEMENT AND DISTRIBUTION (Check one): □ a AEC's normal announcement and distribution procedures may be followed. 1 b. Make available only within AEC and to AEC contractors and other U.S. Government agencies and their contractors. Q c. Make no announcement or distrubution. 5. REASON FOR RECOMMENDED RESTRICTIONS: 6. SUBMITTED BY: NAME AND POSITION (Please print or type) Bruce H. McCormick (Professor) Organization Dept. of Computer Science, University of Illinois, Urbana, Illinois 6l801 Signature S$n~~^4V- U^&v-LX Date July 30, 1969 FOR AEC USE ONLY 7. AEC CONTRACT ADMINISTRATOR'S COMMENTS. IF ANY. ON ABOVE ANNOUNCEMENT AND DISTRIBUTION RECOMMENDATION: 8. PATENT CLEARANCE: □ a. AEC patent clearance has been granted by responsible AEC patent group. □ b. Report has been sent to responsible AEC patent group for clearance. I I c. Patent clearance not required. *«' ^ tit