Reference / Paper · 1983
Design and Use of an Electronic Sieve (thesis, University of Manitoba)
Thesis on the UMSU electronic sieve built at the University of Manitoba.
Reference / Paper · 1983
Thesis on the UMSU electronic sieve built at the University of Manitoba.
Design and Use of an Electronic Sieve by Cameron Douglas Patterson A thesis presented to the University of Manitoba in part ial fulf i1 lment of the requirements for the degree of I{aster of Science 1n The Department of Computer Science Lrlinnipeg, Manitoba, 1983 (c) Cameron Douglas Patterson, I983 DESIGN AND LTSE OT' AN I]LECTRONIC SIEVE BY CAMERON DOUGI,AS PATTERSON A thesis submitted to the Faculty of Graduate Studies of the Uriiversity of Manitoba in partial fulfillnrent of the requirenrents of thc' degree of MASTER OF SCIENCE d r 983 Pernrission has been granted ro the LIIIRARy OF THE UNIVER- SITY OF MANITOBA ro lend or sell co¡ries of this thesis. to the NATIONAL LIBRARY OF CANADA ro microfilnr this thesis and to lend or sell copies of the film, and UNIVERSII-y lvf ICROFILMS to publish an abstract of this thesis. The author reserves other publicatiou rights, a'cl neither the thesis llc¡r extensive extracts frorn it nray be printed or otherwisc' reproduced without the author's writte¡r pernrìssion. .j,r: iill['*i i,! i i){1,\ ,.j ,ô1'\\'"' A CKN OI,]L E D GEI.{E NT S The sieve project was ínitiated after H. Lehmer ancl Robert Cof f in. Doug Kimelman, Gilbert participatecl Detillieux implementation solved with of the software. a discussion in the Electronics with D. Gi11es ancl design and problems were the readv assistance of Jim Reimer. Brad Day helped to assemble the hard\^rare. Glen Ditchf ield's wirelist progran aíded consËruction especially thanked, f or immensely. he r\7as an Ínexhaustible advice and support throughout Hugh tr{illiams arranged funding Forbes Burkowslci is the project. is the patient for its acknowledges the financial Scholarship from the source of user of the sieve, construction. assistance Natural Research Council. 1V sciences of The and he author a postgracluate and Engineering CONTENTS ACKNOI^ILEDGEMENT S fv Chapter pag e I. I NTRODU CTI ON .l II. THE SIEVE PROBLEM .2 III. THE SIEVE DEVICE MODEL .5 IV. DESCRIPTION AND JUSTIFICATION OF THE DESIGN .g v. HARDI.JARE . 13 Des lgn 0ve rvl ew Physfcal Construction . . Sleve Hardvrare Subsys tens ControlUnlt.... HosÈ Interface . . . Counter . . Solutlon Detectors . Rlngs . . . . . . . Clock Systern . . . . . Remote Control . . . . o VI. FIRMI.TARE Sieve Control Unlt . . Mlcrof ns tructlon Format Sfeve Instructlon Set SOFTI^IARE T7 l8 1B l9 20 23 24 29 33 The Sleve Comrnand . . . . . . The Sleve Background Monitor Sivmon Slvdlag aaaaaaaaaa Flles . . aaaaaaaa VIII. t6 t6 I7 20 Microprogramming Model VII. l3 15 16 USER'S GUIDE TO THE SIEVE Unlversal Command At trfbutes Command Descrlption Key . . Command DescrlptLons . . Problem Ftle Creatlon . . v 33 34 36 36 42 44 4B 5t 93 Fllter IX. Program Creatlon 95 CONCLUS I ON S 96 REFERENCES 98 LIST OF TABLES Table paSe I. Lehme r's 2 Hos t Computer Sfeves Labour. .6 / Sieve Peripheral Divlslon of T2 vl LTST OF FIGURES Ffgure page 1. Baslc Mlcroenglne Conflguration 2. Protocol for lIrite 3, Protocol for I^/rite from Sieve to Host 4. Sieve Command HÍerarchy o ê ê ê e . from Host to Sieve vll è .21 . 30 . 31 .47 Chapter I INTRODUCTION This document describes construction use, of an electronic device is linear congruences. a tool operations the the device in number used evolution, The callecl theory sieve of whether congruences. This Neumann style computer currently There v/ere inplementaiion speed no is not performs 133 f irmwa re , and software \^/ere created in fu1fi11ed the design goa1s. describe the from the author number theory, the not applications it is have extensive of the in depth. It is the intent provide ínformation to the users 1 be al L of har<lrvare, that necessary to the reader system. explored síeve system. medium configuration a perspectives, several does to on any von result, Although should regard the sieve as a unifÍed Since of mi1,[1on satisf Íes the upon Asa sieve sets is defined attaÍnab1e sieve. the The known to the autho r. constraints for sieve. solve integer an anci to per second, where one operation determination a design, and sieve of this training in will be not document to maintainers of the Chapter II THE SIEVE PROBLEM Let rl, 1n m I m *k be integers 2 pairs. I^/e specify permissible ) l, and relatively residues for prime each modulus as f ol1ows: X = r.rJ (mod m i) i = l, ) k L) j = l, The problem ís congruences certain to find n.(m. I1 2 a value simultaneously; for further, X that all X must be within a range, say A < X < B. There are three classes of sieve problems. all satisfies i ( i.e. r^/e specif y only one residue If ni = I for f or each modulus) , then X can be determined using the Chinese Remainder Theorem ( cRT) . An example of this type of problem is: X=4 X=8 (mod 5) (mod 13) X = 2I (mod 31) There is only one solution in the range given by A 0 B 5*13*31 = 2015. If rhe first k prime numbers are used as modul i , and \{e specify all permissÍb1e residues except for zero (i.e. m,-1 and r.,rJ = j), 1 the resulting 2 n.1 problem is the famous Sieve 3 Each X found cannot divÍde of Eratosthenes. Thus, if m then all solutions is k any of the m.. prime not greater the largest in the range A to B will than A =6, be prime. An example.of a prime-f inding sieve is: X= I (mod 2) X = Ir2 (mod 3 ) X = I,21314 (mod 5 ) Y=1)'1,1!5 the primes betvreen l0 an<1 t 00. This sieve produces all roughly If modulus (i.e. of the residues half ri is approximately ca11ed a quadratic-type since this situation Diophantine equations X will 6 (mod 7) t 'r", n. /2), when investigating arises each then the problem is The name is sieve. for are specified well-chosen, second degree and quadratic residues. An arbitrary have a I in 2 chance of satisfying a particular Ilence, congruence. satisfyÍng all k will have congruences. expected is therefore quadratic-type X (B-A) /Zk. a 1 in 2k The number of The following chance of solutions exemplifies a sieve: X X = I,4 (mod 5) X = I12r4 (rnod 7) Even a large computer becomes overwhelmed wlren attempting to enumerate all quadratic-type sieve. approximately rlor2o combinations of congruences in a Such a sieve with k moduli represents *m. /2k ñ s ieve problems that can be 4 solved using the CRT. Typical first quadratic-type 35 prime numbers as moduli; 4*I046 CRT problems! Ít solutioas, is Since this Ís the equivalent a range necessary to solve sieves use fhe is all imposed on the CRT problems, check each result for inclusíon in the range. An alternative approach is Ëo search numbers in the technique is acceptable quickly. Unfortunately¡ serially apply specified the range for of and sequentially the solutions. This as long as the search can proceed general-pl.rrpose congruences computers must Ëo each number, and each congruence may require several machine ins tructions. Tn the next chapter, be shown how specÍa1-purpose hardware a11ows all it will congruences to be tested simultaneously. Chaprer III THE SIEVE DEVICE MODEL D. H. Lehmer \4Tas the first solving the sieve concept of a discrete Af ter choos ing 0, Fina11y, The connect ion and ring the to permissible to A ring \¡re will will of between the physical world was is divided can represent section proceed vre only one section The the which corresponding problem. employ custom hardware for rf a closed loop or ring sections, res idue problem. modulus straightforward. to the ring distinguish into Tn the rnodulus m. will represent those sections residues in a given be constructed for each rnodulus. maÍntain a window on each ring sieve that shows at a time. algorithm for running the sieve problern is setup each ring so that the residue 0 section is in as follows: 1. Èhe window. 2. Check if all sections distinguished. If 3. Shift by one section. 4. Repeat from step 2. all LIhen a solution rings is found, in the windows are so, v¡e have a solution. its value is the number of times that step 3 has been performed. 5 6 For the sake of windows inspected speed, it is símultaneously, simultaneously. Table I lists been co4structed by Lehmer. desirable to have all and all rings shifted the sieve devices that have TABLE I Lehmer's Sieves DATE TRIALS/SEC DESCRIPTION 19 26 bi cyc 1e chains r932 gears with pho to-elect solution detector 1936 I 6-mm film r9 46 sieves on general-purpose computers 60 ric 5000 REFERENCI]S r ,7 z r') ) I 7 ENIAC 7 S I^lA C 4 IBM 7094 100,000 ILLÏAC IV 3, ooo, ooo 1960's delay line r97 5 electronic r9 82 memory-driven microcomputer-based (under development) 1,000,000 shift register 16,000,000 ? 7 7 617 7 7 might It limi ted s trict appear that the speed of 1y by the rate at shifted. However, using possible' to test a sieve which the shift more than one number per ring time by loading s, 2*s, contained [5], In order for all 0, l, 2, be it is In a in one in the order 0, residues in the sequence, m and s must be relatively A window is placed over resÍdues is can shift. of s shifts the ring with residues (mod m). 3*s, rings an idea suggested in ring of length m, one can get the effect device to be prime. , s-1 (mod m). iìence, we initially have the value of the f irst s resiclues for After the each modulus. residues s, s*I, s*2, one , left 2s-l windohTs. Thus, we are checking for shift time. shift of (mod m) appear solutions ring, in the s numbers per Chapter IV DESCRIPTION AND JUSTIFICATION OF THE DESIGN 0rigina11y, it r,ras planned to simply reconstruct Berkeley electronic the r975 sÍeve, using a pDp rl/03 microcompurer system as the user interface. Later, it was considered desirable to have a communications path between the ll/03 and a PDPLr/ 45 access to minicomputer system. a variety of I/ 0 peripherals, storage, and remote login. the rr/03 entirely; This would províde The final more secondary configuration the sieve is a direct omits peripheral of the rr / 45. The sÍeve has its ov/n microprogrammed control unit, and may be thought of as an array processor. The above evolution of the sieve. is The consequence of the requirements Some of the more irnportant the \^/ays of achieving 1. a sieve objectÍves and are as follows: them must be capable of running unattended a Èime. poTirer failures months at should noË require automatically In particular, for human intervention. The PDPII/45 reboots when pov/er resumes. The UNIBUS initializatíon causes the sieve microcode to signal enter a povrer-up sequence. 2 A user-friendly environment is required. The user ].s not be a programmer, or to be familiar assumed to I 9 hrlth the hos t operaÈlng sys tem. The user s lmply deals with a lrorkspace of actf ve problems. Cornpleted problems are automatfcally archived ln order to keep the workspace uncluttered. 3. The PDPt I/ 45 UNIX system facllitaÈes provfdlng the deslred envlronment. Addf tlonal tests nay have Èo be performed by the host computer on solutlons detected by the sieve. For example, a user roight wlsh to use moduli that are not turplemented ln origlnal the sieve hardware. motLvatfon for lncludfng the PDPI I/03 ln rhe sieve system archftecture. PDPI I/ 45 This vras the system could It was feared that the not provlde the requlred to keep the s Leve from walt ing . the prlorl ty of the s f.eve response Increas lng proces s would be unacceptable to the other users of the IL/ 45. As it turns out, most sleve problerns do not require a great deal of software tes tf.ng. In addttlon, the superlor speed of the II/ 45 over the I 1/03 more than offsers the fact that the lI/ 45 fs nor dedfcated to servlclng sfeve lnterrupts. 4. The sf.eve system must be rellable. The floppy dtsk-based PDPI I / 03 has a greater ltkelthood errors, and does not memory reads. perform parlty of f/ O checking on The PDPI I/ 45 sys tem has an order of magnltude greater Mean Tlrne BeËween Fallure than the t l/03 systern, even though the lI / 45 system ls more IO complex. As wel1, excellent record for robustness. Versatllity síeve. the UNIX operating ls deerned the most lmportant ' Even speed is subordinate durfng the design. 1. rt goaI, of the although noduli hardwa re . advance that other than As a resul t , a per second r^7as enforced Examples of some of the tradeoffs vias known in requlre âttribute to this minimum speed of 100 mí11ion trials systern has an are: sone problerns would those implemented a convenient in and minimun number of hardware modulf was used. 2. Solution counting hardvrare speeds, for cannot since each solution. proceed at fu11 the pDpII/45 is interrupted Atthough possible to ínclude hardware, the problerns that could not exploit solution counters solutÍon detector. solution the Ít would counters required solution in sieve have been the sÍeve software modul i counters. would be necessary Eíght one for The added hardvrare each complexity could not be justified. 3. The hardware clock 0verflows 4. counter has a 100 day period. are remembered ln software. The sieve can operate aE a cycle time of 50 os, but a ring bit A will 60 ns cycle ring bit flips f1íp on the average of once per day. time r,ras chosen, with the result roughly once per month. that a lL The checkpointing performed by the sieve background process not only records the sieve hardware state, as we11. Knowing the initial far the.counter of contents state rings. of the rings, This gives checking Ít and horv is easy to predict has advanced, it the but verifies the the new user confidence that the sieve hardware is perforrning properly. In adclition, all sÍeve unit \^Jrites are immediately verif iecl by a read of the unit. not verified rightfully Solutions by the sieve generated by the sieve are software, because this be done by independent software. overhead would slow down the solution slrotrlci A1so, the extra counting mocle even more. Table 2 indicates sieve device is and the to keep the minimum. first wrítes of transfers. require provides m-bit of functions host computer. communication Solutions and the the division rings the initial are An overriding between only l¡ bet\^reen the the t\^/o uni ts 16-bit data interrupt. perfornìed concern i" to a trarisf ers, Reads and [(m/I6) data T2 TABLE 2 llost Computer / Sieve Peripheral HOST RESPONSIBILITIES S Division of Labour IEVE RESPOI']S I]]ILITI I]S user interface generate interrupts solutÍons, counter overf low integrity checks execute commands from hos t initiate por¡¡er up sequence oPerate as a complete slave to the host (irnpose no real-time constraints upon it ) implement less commorl modu1i non-vo1ati1e data storage for implement mosL common moduli Chapter V HARDI^IARE rt \,ras decided not to thoroughly in this document, because of description. layouts describe the size The board layouts, remain in and nature wiring the possession the sieve hardware lists, of of the and baclcplane the author, and are cìecodable only by him. However, provided. some high-1eve1 The integrated chosen will sieve circuit be summarized. output is design circuit diagrams diagram are folded documentation included is and packaging technology Each major in'i11 be characteri-zed. progran 5.I hardware subsystern of A sample of the Appendix D. Fina1ly, in and the interrupt in a pocket inside the rvirelist the system tirning the back cover. DESIGN OVERVIEI,l The rings defined recirculating shift corresponding in length to their The f irst 4 rings Po\,7erS. in Chapter registers. 3 are There the first implemented are 32 of a ring must be at least lrave length 1 this 8 bits accomodates common moduli, 13 these, 32 pri.me numbers or 64, Bl, 49 for t\^ro reas ons : 1. as long such as B 25, ari<l I4 Each one bit in 4B-bit counter keeps track rings have been shifted. There are B solution detectors (i.e. B'numbers are tested per shift). detector a ring denotes is 1ogica11y a 32-input permissible resiclue. A of the number of tímes that the â AND gate. A solution The sieve hardware has a cycle time of 60 DS, and Ís completely speed is million therefore trÍals one trial every synchronous. Ilaximum 6O/8 = 7.5 ns, or 133 per second. A design requi rement for the machine was that there be no overrun of undesirable the rings when a solr_rtion is f ound. "back up" the rings, in to have to It is order to continue the search for solutions. Hence, the sieve has to ttstop on a dimett, rather than ttcoast to a stoptr. The rough equivalent of momentum in electronics for signals to propagate through gates and wires. hold times must be respected. clock and interrupt multi-1eve1 lines introduce skewing of the signals machine. rn detection logic shifted every solution to halt cyc1e, Globa1 signals tree. to has a the time required such l-1eve1 ancl require trees in different prevent setup antl such as the have a large fanout, distribution order is overrun, inevitably parts the pipeline. a of the solution The rings are although it the machine. The ,,earch f or solut ions continues by restartÍng the rings and the solution detection pipeline in unison. takes 2 cycles for a 15 5 .2 P}IYS TCAL CONSTRUCTION The sieve consists on three of over 400 integrated circuits, high density \^rire\,irap boards. and lowjpo\rer Schottky TTL are used exclusively. para11e1-out serial-in for shift registers enhanced reliability. serial-out shift Advanced Schottky The 8-bit are mÍlitary Unfortunately, registers packaged grade, longer length could not be used, because of the distribution of the 8 wíndows in a ring. power supply and cooling Including a 35 anp fans, the tightly packaged, some taps frorn sÍeve device occupies about 2 cubic feet. Although the rings should the sieve to be, the is solution and sígna1 detectors relections experience severe termination at Èhe receiving reflections are longer occur. have end. than they Those taps para11e1 that resistor This does noÈ e1Íminate the problem, because of impedance mismatches along the taps is ( impedance hard to control on wirewrap boards and backplanes ). Ripple problem, in the pot,rer and ground distribution because of the large clocked simultaneously. number of systems is devices In order to reduce this safe 1eve1, boards !rere chosen that have nearly po\"/er and ground planes. There is at least decoupling Íntegrated circuit, decoupling capacitors capacítor per dozen tantalum electrolytic The por4Ter supply capaci tance . has approximately 0 .2 that ripple a are to a continuous one reramic disc and several per board. farad s of load l6 The wirewrap wire colour 5.3 is as follows: convention black : clock distribution red : interrupt bljue : taps from rings white : all lines to solution detectors else STEVE HARDI{ARE SUBSYSTEMS 5 .3 . I Control Uni t The functions Note that other of this the control subsystems. are described circuitry unit in Chapter is clocked independently The control unit 6 from the is on the top board of the rack. 5.3.2 The Host Interface job of parallel-to-serial conversions is accomplished by 74I99's. to control the number of shífts. damp ing resistors are used for Paralle1 resistor termination f ide 1i ty of signals received a1low for cable a flat serial-to-para11e1 and A 74LSI61A Ís used Line drivers signals and line sent to the host. receivers improve the from the host. length of and series 25 feet These measures from the host computer to the sieve (this is the maximum length allowed by the interface). DEC DRI l-C circuitry para11el All is on the top board of the rack. host interface L7 5 .3 .3 Count er The 48-bit counter bÍnary counters. while the is implemented by r2 4-bit The least remainder significant 74LSl6lA's. counter overflow is most significant counter asserts its and read when the Terminal count capability of these chÍps Ís exploited. circuitry 5.3.4 A output. and writing, individually counter is a 74sl6l, are detected readÍng synchronous The the addressable broadsÍde load For the purposes of counter is I6-bít units. split up The into 3 counr-er is on the top board of the rack. Solution Detectors solution 13-input detector NAND gates, is followed implements the AND function de1ay. implemented detectors All Èo form a single interrupt distributed via a 1-1eve1 distribution that the clock other inputs para11e1 The resrrl,t wÍth roughly a r2 ns propagation D-type flip-f1ops. interrupË inputs three by an AOr gate. The output of the solution drive by is pipelined souïces are oRed together 1ine. This sÍgna1 of the rings select 1ine. portÍon of the middle board Ín the rack. detectors is then tree to the AND gates and counter. to these AND gates are the clock 1ine, The solution by occupy the The and unit center IB 5.3.5 All RÍngs rings are implemented using AllD 25LSl64Dlf's. All registers in a ring share the same clock driver. A 2-input 0R gate'is spliced into the rirrg. The firs t ring special reading or writing, ít shift register. recirculating 8-bit is recirculating searching for accomplished a ring in that for appears as registers a single This by the use of a 2-input adjacent shÍft registers. the left side of the middle located on the right remaining r2 rings The first of the 64-bit up into B sieve is transformation multiplexer of is bet\,reen 8 rings are located on The next rz rings are the middle board. The bottom board in the board. hand side splits while solution. purposes the However, it shift a in order to write shift occupy the enLire rack. 5.3 .6 Clock System The clock signal detection pipeline, Lrhile for counter, solution and ríngs Ís generated by an A¡{D 2925. is searching for used. During the sieve frequency is frequency is divided the 2925 is the hos t interface, exploited. board of the rack. by I0, a solution, I/ O operations , and the single the crystal the crystal step facility This 2925 is located of on rhe mi<idre t9 5.3.7 Rernote Control A handheld remote control the rack. unit ir controls Basically, 2925 oseillator may that be clocks reset microinstruction to signals by the affecËed box connects to the backplane of the operation the control unit. single stepped or the next. disconnected. The sieve will remote control box is disconnected. AMD The control from one defines the box when it is A multiplexer remote control of the be in a "runt' state when the Chapter VI F I R}IWARE 6. I MICROPROGRAMMING MODEL Mfcroprogrammfng is control a conflguratlon the use of a programmed "englnet' to larger machlne. fs shown ln Figure l. ls the m word by n bit control signals. slnply A slrnple microengine The most lnportant uniE memory, whlch fs the source of the The memory ls drlven by a sequencer that determlnes the next address to be lssued to the memory. The next-address selecÈ lon defaults to the current addres s + I (urodulo n) . Alternatlvely, the next address 1s a functlon of addresslng lnformatlon ln the current €xternal data slgnals, word r memory and addresses "remernbered" by the sequencer. All of the conÈro1 varf.ations perrnltted on von ln Neumann computers microprogrammlng: seguential, jumps, subroutine calls are usually avallable uncondftlonal and conditlonal and returns, bounded and unbounded loops, and even multf-way branches (case statements ). (Advanced Mlcro Devices' The ttplpellne reglstertt termlnology) exLsts to al1ow the nlcroenglne Èo operate fas ter. llithout tfne the mlcroprogram memory. The plpellne holds of the fÈ , currenÈ the cycle tlme would fnclude fhe access mlcrol-nstruction, 20 whlle reglster the next 2I OPCODE MAPP]NG PROM OE Iflrx SEL MAP t,t, I SEQUENCER PL MICROPROGRAM MEI'10RY PIPELTNE OE REGISTER CONTROL SIGNALS Figure l: Basic ìlicroengine Configuration 22 mlcrolnstructlon ls beÍng addressed in the memory. Thus, Èhe memory access tfrne has been removed from the critfcal path. The 'use of microprogramrnlng to generate control in a dÍgltal slgnals machLne ls analagous to Èhe use of structured prograrnmíng to manage control flow in software. In both cases, a slmple solutlon helps to solve a complex problern. A sËructured approach to control has the followlng advantages, in elther a hardware or softhrare envlronnent: 1. The chances of corning up with a close-to-error-free des lgn are frnproved when fundamental cons trafnts lmposed upon control. are Independently-designed modules are more easlly lntegrated. 2. Debuggíng is easLer, because errors can be isolated. Knowirrg that certaln modules cannot fnteract hetps to narrow down the posstbllitles. 3. Flxes or enhancements can be made with conf Ídence thaÈ we wfll more not corrupt something already wo rking . Thus¡ wê see that all phases of project benef 1È from controls a hardware or on control. software 23 6.2 SIEVE CONTROL UNIT A schematfc of the sfeve control unlt ls glven fn the back cover pocket. rt fs very sfmllar to the basic ¡nlcroengine ¡node1 prevf.ously descrtbed. The Arn2910 is a blpolar mfcroprogram controller that can access up to 4K words of microprogram. rt executes L6 dtfferent microprogran address modiflcation Lnstructfons. The address provlded on the yi outputs may come from the Di lnput pfns, the lnternal reglster/counter, nicroprograu counter, or stack. Ffve Ãn27s29 512x8 bipolar pROM's are arranged horizontally to give an overall words. nfcroprogran An2920 octal pfpeline reglster. memory slze registers Ftnally, of 5r2 40-bft are used to lnplement the an An2922 octal multiplexer and an Ar¡.2920 a11ows the Am2910 to fnterrogâte one of eight values to determLne the outcome of condltlonal lnsÈructÍons. All clocked chfps share the same I Mhz crock slgnal, which 1s produced by an An2925 system clock generator. ït should be noted that the sf.eve control unlt runs asynchronously wlth the res t of the machfne. The conErol unit does not lnfluence the 6peed of the rlngs. rn fact, the control unlt has a eycle tlme of 1000 DS r whereas the ríngs have a cycle tlrne of 60 ns. I.lhile the sieve is searchfng for a solution, the cont ro1 unit porls for assertlon of fnstructlon from the host computer. rf a solutfon occurs, and counter stop r.¡fthout assistance from the the rings the solutlon found slgnal, or for an 24 only functlons are control unlL. Indeed, the control unit's t o decode and execute Lnstructfons from the host computer, 6 .3 is detected. the host when a solutlon and to fnterrupt MICROINSTRUCTION FORMAT Each mLcroinstructlon field ln wt11 be descrlbed the following manner: fteld rnnemonfc (btt posltlons ) : fteld descriptlon A field nnemonf-c having an rrGrt sufflx ls active indicaÈes the signal 1ow. opcode (0-3) : 4m2910 Lns t ruc t lons . 0n1y 4 of the are used. They are: condlElonal possible lnstructlons junp-to-subroutfne, r e t u r n- f r om - s u b r o u t I n e , 16 jump-pipeline, conditlonal and continue. address (4-12) :4m2910 direcË lnpuE to the reglster/counter and nult lplexer ( l. e. pins DO Dg ) . the 2910 are tfed 1ow. Thls field Plns D9 Dt t of is used to directly access the 512-word rnlcroprogram memory. me22@ ( t3) : ArnZ922 condltfon code nultiplexer enable pfn. Thls pln ls held low throughout the mLcroprogram. re22G ( l4) : 4m2922 conditlon enable pin. code nultiplexer regf.ster This allows the 2922 selectlon Lnputs ( tfrat are determl-ned by the abc22 f.Le1d) Èo be changed. 25 pol22 ( l5) : 4n2922 condltion control pLn. code multiplexer polarlEy A low value on the 4m2910 condition lnput implies truth. code A lor+ value on poL22 lnverts the sign'â1 that passes through the 2922. abc22 (I6-18) selection : Arr.2922 condftlon pins. This fleld code multiplexer input encodes the slgnal number that the 4m2910 wlshes Èo fnterrogate. reqa (19) : DRlt-C parallel interface "REqA" signal. It ls used Èo acknowledge the reeelpt of data, or the executlon of a command, by the sieve. reqb (20): DRIl-C paralle1 lnterface used to interrupt "REqB" slgnal. Ir is the hos t computer when the s Leve has data for it. Le373 (21) : 745373 latch enable pin. Thls chip latches the rLng or counter unlt number that is contalned ln fnstructf.on frorn the host conputer to the sieve. ftller an I (22) : Reserved for future use. ccenG (23) sf-gnal : 4m2910 condirlon forces unconditlonally all eode condítlonal enable pf n. A high f.nstructlons to be executed. peoutbufG (Ztr¡ z 7 4I99 broads ide load enable plns f or the DRl t-C parallel edge of the clock, l6 data blts from the host compuÈer to lnterface output buffer. On the rislng the rfngs or counter are loaded lnto a palr of 7 4199' s. 26 pelnbufG (25) ¿ 74199 broadsfde Ioad enable plns for the DRi 1-C parallel lnterface lnput buffer. 0n the rlsing edge-of the clock, from the counter to the 16 data bits hos t computer are loaded fnto choose (26) : When asserted, palr of 7 4199' s. a on 1y the unlt (ring or counter) that ls selected in the unit number demultfplexer wf11 receive the clock signal. I.Ihen deasserted, all units receLve the clock sLgnal. f eed (Zl¡ : I^Ihen asserted, data can be serlally introduced Lnto a ring, or broads lde-loaded lnto next rfsing edge of the clock. hlhen deasserted, recl-rculate the data and counters rlslng dis clkG a counÈer, on the rings count upr oD the next edge of the c1ock. (ZA¡ : Prevents the sieve from haltlng due Èo counter ove rf I ow. haltG (29) : Thís slgna1 1s rhe lnpur ro a D-rype fltp-f1op that is clocked synchronously wlth the rlngs and counter. The output of thls synchronous halt sLeve clock at the proper place fn the clock s fgnal perf.od. flip-ftop jams the Assertlon and deassertlon of haltG is the means by whlch the control unlt stops and sÈarts the sl,eve looklng for a solutlon. 27 dts_l@ (30) : Prevents the sleve from halting due to a solutlon detected on cof.ncldence gate number 1. dis_28G, (31) : Prevents the sLeve from ha1 t lng due t o solutlons detected on cofncldence gates 2 through 8. In the current vers lon is of manipulaÈed lclenttcally the to dls_1@. one colncfdence detector one number at a tfme). at one-etghth prlmary solutlon clk hal t G (3 2) system clock rlngs, signal However, by asserting the Èlme, the sLeve reverts to havlng just dis 28G all operate thls mlcrocode, detector (i.e. fr checks for solut ions This would a11ow the sleve to should any but the speed malfuncÈLon. Drlves the run/ha1t pln of the generator. AnZ925 This master clock supplies the counter, and host interface unlt. I^Ihen c1k_haltG ls deasserted, the clock ls f ree-runnf-ng (although it nay be jarnmed by solutlon detectors, counter overflow, or the haltG sf gnal). I^Ihen clk_halt@ ls asserted, the clock nay be slngle-stepped. clk_ss@ (33) : Causes the Am2925 master clock to produce a s lng 1e s qua re r¡rave . The perlod of thls the perlod of the free-runnlng clock qrave ls ten tlrnes sfgnal ( i. e. Èhe single-step perlod is 600 ns). set_haltG (34) : Connected to the direct synchronous halt fltp-f1op. The must be low before the clk halt@ clear lnput of the output of rhls fllp-fIop s lgnal f s deasserted. 2B clr_ha1t@ (35) : connected to the direct synchronous halt flip-f1op. set lnpur of rhe The output of Èhts flip-f1op must.be htgh before the c1k_ssG slgnal is asserted. signal also crears the presence of solutions This from the sol-ution detection pipeline. cel99 (36) : PermLts the sfeve master clock signal to reach the 7 4I99's that are ln the hos t interface unf t. pe161G (3t¡ that ls Permfts load lnto the used to llrni t the number of times cycled during ls a broadslde a âccomplished a read or write rlng operatlon. 7 4L51 6 1A ring ls The load on Èhe next rls lng edge of the master c1ock. ce161G (38) : Permits the sleve masÈer clock slgnal to reach the 7 4LS 1614 that 1s used to limtt the number of times a rinB ls cycled durlng a read or write rlng operatfon. flller_2 (39) : Reserved for future use. Note tha! ffller is also avaLlable, and 1t 1s physically closer a documented listlng of to I the ba ckpl ane . Appendfx c contalns mfcroprogran. the sieve 29 6,4 SIEVE INSTRUCTION SET A DEC-supplled DRi t-C parallel lnterface connectB the sÍeve device to the UNIBUS of the host computer. Instructlons and data are sent to the sieve, and daÈa are recelved from the sf.eve, 1n 16-bit parcels. hos È The transmlssíon of data from the computer to the sleve ls acknowledged with done 1n lockstep, a handshake. The transmlsslon of data from the sleve to the host cornputer ls lnterrupt ls a1s o and fs driven, and acknowledged wlth a handshake. Figures 2 and 3 describe the communlcatlons proÈocol 1n detafl. The f ormat of a sf.eve Ínstruction opcode (o) unl-t number (n) (¡ bits) (6 bits) least slgnifÍcant The bit ordering computer. Data blts the most slgnlflcant is: shift (4 btts > mos t counÈ (c) unused blts) (3 birs) slgnlffcant frorn the perspective ls of blts the host are used by the sieve beglnnlng wlth bits. Data blts are generated by the sieve begfnnlng wlth the leas t slgntftcanÈ bits. The opcode fteld spectftes one of B possfble Lnstructions for the sieve devlce to execute. enumerated after the other fields The unlt number field l6-bit The insEructlons will be are descrlbed. selects one of the rings (0-31), a portlon of the eounter (32-34), or the output value of the colncídence gates (35). 30 S IEVE HOST (l) assembles command/data {polling for CSR0 set} (2) 1f T.EQA set, give tt"yttc (3) errortt wrlre ro DR0UTBUF (4) assert CSR0 {polling for (5) executes command/data when CSR0 set REQA set} (6) asserts REQA (7 ) ff REQA not set afEer 100 mi.cros econds , glve ttno responsett error (8) deassert {po1ling for CSR0 clear} CSR0 (9) deassert REQA Flgure 2z Protocol for Wrlte frorn Host to Sieve The shtft count determines the nu¡nber of data bits Eo be used fn a read or wrlte rlng command. An encodecl value of n (where n ls betl.reen 0 and 15) results 1n n*l shlf ts. The lnstructLons executed by tl're sfeve are: daÈa bit 31 SIEVE HO ST (I) asserts REQB (2) inferrupt by REQB generated {polling for CSRI set} (3) read DRINBUF (4) assert CSRI to acknowledge data read {po1ltng for (5) deassert REQB REQB clear} (6) 1f REQB set after t 0 mlcroseconds, gfve ttREQB s tucktt e rror , and disable lnterrupt capabtllty of REQB (7) deassert CSRI Figure 3: Protocol for llrlte from Sieve to Host read rlng (o = 0) : The host computer needs the value of the next c blts of ring number n. the data requested. The sLeve responds wfth Note that [ 1m/fO) instructions are requlred to read an m-bft rlng. read counter ( o counter unlt 1) : The host coruputer needs the value of rr¡ The entfre counter f-s 48 bfts, but it 1s broken up fnto 16-btt unlts for the purposes of readlng and wrltlng. 32 rrrrfte rfng (o = 2): The host computer needs to wrLÈe c bfts of daÈa to rlng number n¡ sLeve after lt The data value is sent to the has acknowledged the instructlon. that.I Cr /tA¡ fnsrructlon-data Note pafrs are requlred Èo write an m-blt rlng. write counter (o = 3) : The host computer needs to wrÍte to counter unft n. A I 6-btt data value fs sent after the lns truct ion ls acknowledged. go (o = 4) : The sleve ls solutlon uslng all units. host when a solution lnstructed to search for The sfeve wf11 fnterrupt ls found. a the Thls LnsÈructl,on sho'1d be fssued with n=35 so Èhat the coLncidence gate values are presented durlng the fnterrupt. onlL (o = 5) : The sfeve ls Lnstructed solutlon uslng only unft permfts isolated to search for number n. tesÈlng of unfts, a This lnsEruction ls therfore and usecl ln dlagnostLcs. stop (o = 6) : This lnstruction causes ackowledgement. As a slde effect go conmand. outs tandlng slnpliclty, or only it ls also used to test if ft a s lrnp 1e terminates an Because of lts the sieve conlrol unl,t fs a1fve. pulse (o = 7) : All s Leve rings and the counter are slngle-s tepped. Thts ls a dtagnostlc fnstructLon. Chapter VII S OFTI{ARE The essential sieve software consists of three programs: the ttsievett command, the sieve background process ttsivmontt, and the diagnostic these program "sivdiag". programs wÍ11 structures used The characteristics be discussed. by the above The files programs of and data will also be described. 7.1 THE SIEVE COMMAIII) This interactive program is the sole user interface sieve system - no other shell to the commands are required. use of the sieve command is documented ín Chapter 8. Error detection is The return code of memory is checked. a significant complete is performed on all found, is first "cleaning reported allocations are freed, terminated). The allocation syntax to the user, files (".g. are closed, program the multiprecision request fails. 33 never thÍs prograrn. and request and semantic user Ínput. up" is done as possible unfortunately, of every r/ o system call checking it part rf for error an error is and then as much outstandi.ng memory and the command is aborts package aborts if itself. a memory 34 As a precaution, copies are made of the queue and done before they are modifÍed. files These backups have the name where ".../files/temp/backup.xxxxxx", xxxxxx is obtained from the "n1çtemp" UNIX utility. The backup of the queue index in and string manage mode. files remains must not be allowed command. The hangup signal will abort throughout A backup of the done Índex and strì.ng files made cl r-rring execLrtion of the retrieve Signals existence the sieve is command. to terminate ignored. s ignal the sÍeve The quit command, and should debug the command. The interrupt is signal be used only sets a flag to that is interrogated by some commands. These signals are set their va1ue, though, before invocation of the ediÈor default ro or a she11 escape. 7.2 THE SIEVE BACKGROUND MONITOR STVTION The environnent of sivmon is very different from the sieve command. sivmon is a non-interactive program that messâges to the user only through the 1og fj 1e. The standard f iles indirectly can send input, standard output, are not usecl . Iluch ef fort \{as expended to make sivmon conpact and efficient, running