[1]0 32439,340 Ullited States Patent Office ,tented Apr. 15, 1969 3,439,340 SEQUENTIAL ACCESS MEMORY SYSTEM Lee E. Gallaher, Middletown, N.J., assignor to Bell Telephone Laboratories, Incorporated, New York, N.Y., a corporation of New York 5 Filed July 30, 1965, Ser. No. 476,039 lnt. Cl. Gllb 13100 U.S. Cl. 340-172.5 10 Claims 10 ABSTRACT OF THE DISCLOSURE The information transfer rate of a sequential access memory system is in-creased by queueing random address, information transfer requests in the serial manner in which 1,5 addresses in the sequential memory system occur, such that a group of requests may be processed during a single memory period. While one group of queued requests is being processed, another group is ql-teued for - subsequent processing, thereby providing an endless queue of data 20 transfer requests. This invention relates to sequential access memory systems and more particularly to a method and arrangement for increasing the information transfer rate of se- 25 quential access memory systems. Memory systems are divided generally into two classes according to the type of access that ma), be had thereto foi transferring information into or out of the memory. The time required for transferring an item of information 30 itito a selected memory location or for transferring an item of information out of a selected memory location is generally referred to as the access time, or inforfnation transfer rate, of the memory system. Random access memory systems, such as those employing magnetic core or '35 storage tube memories, afford access selectively to any location in the store for information readout or for information storage, and thiis the information transfer rate tberef is independent of memory location. Sequential access memory systems, on the other hand, such as magnetic 41) drum or megnetic disc systems, have an information transfer rate dependent upon the memory location, affording access to the memory locations on a oneafter-the-other basis in a fixed memory location pattern. Memory units for sequential access memory systems 4 @-, tend to provide considerably greater storage capacity at less cost than their random access memory system counterparts, and they have thus found particularly advantageous application in inventory data processing systems ' such as those for maint-,iining a running accotint of items in stock 50 oi- of customer accomniodations available. Similarly, seql,ential access memory systems find advantageous application in other types of storage and retrieval systems wherein large ntimbers of independent items of information are received and stored for subsequent retrieval. How- 55 ever, in these and other applications the information transfer requests made on the memory system generally occur for random memory locations or addresses, thus brin-ing into consideration the speed or rate at which the - individual transfer requests can be processed by the system. Nor- 60 nially, a sequential access memory system is limited to processing an average of two or fewer random address information transfer requests during a memory period, where a memory period is the time between two consecutive accesses of the same memory location. For example, 65 the memory period of a magnetic drum or disc memory ha@,ing an individual transducer head for each information stora-.e track is the time required for one complete revolution of the drum or disc. 1 In many applications an information transfer rate of an average of only two or fewer items of information per 2 memory period has been found to be inadequate and a considerable disadvantage. Accordingly, various approaches have been devised in the art for increasing the information transfer rate of sequential access memory systems. It is known, for example, to employ a plurality of access circuits, such as a plurality of transducer heads positioned along cach information storage track of the meniory, or to employ a plurality of shorter period memories operating in parallel rather than a single long period memory. These arrangements, however, sliffer from a concomitant increase in cost, bulk and circuit complexity, detracting from the advantages in using a sequential access memory. Other known memory arrangements have sought to increase the effective information transfer rate of the system by increasing the operating speed of the memory. This tends, however, to decrease the reliability of the system and to increase the cost, circuit complexity and power re-quirements of the memory system, particularly in the case of a magnetic drum or disc. It is accordingly a general object of this invention to provide a new and improved method and arrangement for increasing the information transfer rate of sequential access memory systems. More particularly, it is an object of this invention to increase the information transfer rate of sequential access memory systems by a method which is simple and economical and which overcome-s the disadvantages and shortcomings of known arrangements. A further object of this invention is to provide a simple and economical method and arrangement for incrcasing the rate at which random address information is transforable into and otit of a sequential access memory system, without increasing the system operating speed and without requiring multiple memories or multiple access circuitry for a memory channel. In accordance with a feature of my invention, the above and other objects are attained in a simple and economical manner by queueing, or ordering, groups of random address information transfer requests in the serial manner in which the addresses occur in the sequential access memory system, such that entire groups of transfer reqtiests can be processed during, for example, a single memory period. Normally heretofore, the information transfer reqiiests have been accumulated for processing in a work list in the consecutive order received. Each new information transfer request was added to one end of the list and processed in its turn, processing proceeding on a sequential basis from the other end of the transfer request work list. I have found, however, that the information transfer rate is increased substantially byconsidering the transfer reqiiests in the work list a group at a time rather than singly, ordering the individual transfer requests in the grotip for processing in the same serial manner as the addresses or memory locations in the sequential access memory system. While the system is processing a first group of information transfer requests so ordered, a second group of transfer requests may be ordered for subsequent processing, the first transfer request of the second group following immediately behind the last transfer request of the first group. Repeating this ordering of the transfer requests by groups thus transforms the randomly oriented work list, in effect, into an endless queue of requests. This provides an information transfer rate for the sequential access memory system which may approach the nun-iber of items of information contained in a memory period, the information transfer rate depending principally upon the number of accumulated transfer requests considered in each group from the work list. For certain applications of sequential access memory
[2]3,439,340 3 systems it is not feasible to obtain access to adjacentsequential address in the memory. This may occur, for example, due to the time required to read an information transfer request and to initiate processing thereof, or due to the time required for switching between individual access circuits in a multiple channel memory system and for any switching transients to subside before information transfer can be effected. In accordance with another feature of my invention, therefore, the information transfer requests are individually ordered into predetermined memory address groups, such as memory sector address groups or even and odd address groups. Thus, in the latter instance, the information transfer requests may be ordered alternately into even numbered address groups and into odd numbered address groups, an even address group of I transfer requests to be processed during one memory period and an odd address group of transfer requests to be processed during the next memory period. This method of quelteing the information transfer requests is particularly advantageous in memory systems wherein the individual word locations of adjacent memory addresses are interleaved within each memory channel. Another aspect of the present metbod for increasing theinformation transfer rate of sequential access memory systems, in accordance with analternative illustrative embodiment thereof, relates to the provision of circuitry for ordering the individual information transfer requests as they are received. A memory period may be divided advantageously into a plurality of memory storage sectors cach including one or more memory addresses; and a like plurality of information transfer request lists may be employed, each of which is respectively associated with a corresponding one of the memory storage sectors. When an information transfer request is received, therefore, it is placed in the particular list associated with the storage sector to wbich the information transfer request is directed. Each of the lists thus comprises a series of information transfer requests with respect to a particular memory storage sector associatcd therewith, new transfer requests being added to one end of the appropriate work list as received. Accordingly, the first information transfer requests in each of the plurality of work lists form a first quelie ordered forprocessing in the manner described above, the second information transfer requests form a second queue ordered for processing, and so on. This arrangement is particularly advantageous in memory systems wherein information to be stored in the memory is assigned to aparticular storage location by the memory system rather than it being preassigned. In such systems, reference to the plurality of information transfer request lists readily shows which memory storage locations have the least backlo- of transfer requests. This permits better distribution of the work load by assigning the new transfer requests to those locations whenever possible. These and othcr objects and features of the invention may be fully apprehended from the following detailed description when considered with reference to the accompanying drawing in which: FIGS. I and 2 comprise a block diagram of an illustrative embodiment of an arrangement in a sequential access memory system for performing the method of the present invention; FIG. 3 illustrates a typical memory information storage pattern; FIG. 4 depicts an alternative illustrative queue register ,trrangement; and FIG. 5 is a block diagram of another alternative illustrative embodiment of a transfer request queueing arrangenient for a seqttential access memory system in accordance with the principles of the present invention. For purposes of description, the illustrative embodiment of the present invention shown in FIGS. 1 and 2 of the drawing is depicted in a sequential ,iccess niemory systeni 4 access memory 130 compi-ises magnetic drum 131 and its associated circuiti-y including read-write heads 132, head selection circuit 135, clock circuit 136, read circuit 137 and write circuit 138. It will be apparent from the desci.iption below, however, that the present invention niay be employed readily in connection with other known sequential access memories, such as magnetic disc or delay line memories, to increase the information transfer rate of the sequential access memory system. Of course, it will be appreciated that the arrangement of the memory, in the case of multiple memory channels such as multiple drum or disc tracks or multiple del-,iy lines, must be such that a fixcd relationship exists between the information storage locations in the several channels. Magnetic drum 131 in sequential access memoi-y 130 coiiiprises a plurality of parallel information storage tracks TK1 throtigb TKp and one or more timing tracks TC. Information storage tracks TK1 through TKp may be divided typically into a number of memory sectors ST1 @)o through STt?i, each sector comprising a plurility of serially ai-ranged memory locations or storage blocks for the storage of information. For example, as shown in FIG. 3, each memory sector of a storage track may comprise four storage blocks, such as blocks Bll through B41 of 25 memory sector STI, each storage block comprising one or more words of information serially arranged along the storage track. Each memory sector typically furthcr comprises a control block, such as block BC1 in memory sector ST1, to provide for various control functions. in@-o dex IX is an arbitrarily chosen reference point defining the beginning of each new memory cycle or period for each of the memory storage tracks. Read-write heads 132 comprises a plurality of heads Hi through Hp individually associated with respective ones of :@5 infoi-mation storage tracks TKI through TKp. A particular one of heads Hi thi-ough Hp is selected in known manner for transferring information to or from its associated storage track by head selection circuit 135 under conti-ol of control circuit 110. A particular head HI 40 thi-ough Hp is selected by head selection circuit 135, for example, via a selection potential placed on the individu-,il one of selection leads HSI through HSp connected to the particular head. Control circuit 110 may comprise wired logic for performing the various control functions de45 scribed herein or, advantageously, it may comprise a program control of the type employed, for example, in general pui-pose data processing eql[ipment. Read-write heads Hl thi-ough Hp are connected in common over information lead 133 to read circuit 137 50 for transfer of information from the memory and to write circuit 138 for transfer of information into memory storage. Read circuit 137 and wi-ite circuit 138 are selectively enabled to perform their respective functions by control circuit 110 over leads 114 and 116, respectively. Timing 55 information, obtained for cxample in the usual n-tanner from timing tracks TC by clock transducer HC, is extended over lead 134 to clock circuit 136. Responsive thereto, clock circuit 136 provides timing signals on clock lead 144 associated with the bit and word storage loca60 tions of tracks TK1 through TKp, on clock lead 145 associated with the memory sectors, and once each revolution on index lead 147 associated with index IX. Information to be transferred into sequential access memory 130 is provided to write circuit 138 over lead 122 C,5 fl-Om information buffer store 120. Information buffer store 120 comprises a small, random access memory of any stiitable known construction. Infoi -mation to be transfeired out of sequential access memory 130 appears on lead 139 from read circuit 137 which may be connected, 70 as shown in FIG. 1, to information buffer store 120. The output of information buffer store 120 is connected over lead 143 to output circuit 190. Eich transfer of information into or otit of sequential iccess memory 130 is initiited by an infoi-iii-,ition ti-.tnsfeireqtlest fi@om inplit cirCLlit eniploying a n-iagiletic (ii-@ini meiiioi,y. Thtis sequenti@il 7,r, 140. The infoi-niation transfei- i-equest compiises the pai--
[3]5 licular address location on niignetic driiiii 131 at Arhich the transfei- of information into or out of storage is to b@, execlited, a i-ead-write instruction, and the address in information buffer store 120 at which the information is stored awaiting execution of the transfer reqtiest, or to which the information is to be transferred in the case of a transfer of information OL)t of seqi-iential ,iccess memory 130. In many applications for which sequential access memory systems are particularly well suited, SLIccessive information transfer requests occur with respoct to randoni address storage locations in memory 130. The transfer reqiiests are normally aCCIIMLI]ated for processing in a "push-down" work list in the consecutive order received. E,-icli new information transfer reqltest is added to one end of the work list and processed in its turn, processin.proceeding from the other end of the work list on i sequential basis. Assuming the use of a single read-wi-ite head for each memory storage track as shown in FIG. 1, the in@formation transfer rate of the sequential access memory system is thus limited to an average of two or fewer random address information transfer requests during each revolution of drum 131. 1 have found, bowever, that the information transfer rate is increased substantially by considering the transfer requests in the work list a groiip @lt a time rather than singly, ordering the individual transfer requests in the group for processing in the same serial manner as the addresses of the stot-age locations in the sequential access rnemory. In accordance with the method of the present invention, therefore, the randomly oriented information transfer requests are transformed, in effect, into an endless queue of requests providing an information transfer rate approaching the number of storage locations contained in a memory period, that is, approaching the number of storage locations in a storage track of driim 131. In the illustrative arrangement for performing the method of the present invention shoa,n in FIGS. I ancl 2, an information transfer request register 150 is provided, comprising a plurality of register stages RS1 throligh RSn for receiving successive information transfer requests over request lead 141 from input circuit 140. Each register stage in information transfer request register 150 is of sufficient capacity to re.-ister an individual information transfer request which, as mentioned above, comprises a sequential access memory address, an information buffer store address, -,ind a read-write instruction. The assignment of an address in information buffer store 120, at A,hich the informalion is stored a",aiting execution of the corresponding transfer reqtiest or to which the information is to be transferred in the case of a transfer of information out of memory 130 is macle by control circuit 110 over lead 111, Thus in the case of a request for transfer of information into rnemory 130, for example, conti-ol circuit 110 via lead III assigns to the transfer reqliest an empty storage location in information buffer store 120 for storage of the information associated with the i-equest tintil the request can be execlited. The information is then directed over information lead 142 to the assigned storage location in information btiffer store 120 under control of control circuit 110; and the corresponding transfer request, inclusive of the assigned information buffer store location, is directed over request lead 141 to information transfer request register 150. The information transfer requests are accumulated ;n information transfer request register 150 in the conseCLIlive order received, the first request being registered in register stage RSI, the secord reqtiest being regislered in register stage RS2, and so forth, each successive transfer request being registered in the bottom-most vacant register stage of request register 150. A number of the request register stages, namely register stages RSI thrOLIgh RSIC, are individitally connected to respective read eirCLlits RDI 3,439,340 6 throiigh RDk @issoci-,ited tlici-e%@,itil. Reid Cil-CLlits RDt ttiroul-!h RDk ni@i@, be selecti@,ely enzibled by re@id sclcctor 210 over respective leads 211 thrOLigh 21k foi- reading out the contents of the associated one of rcqtiest i-eister stages RSI through RSk. The OLitpUtS of re-,id cii-cuit, @D I ilirough RDk are connected over respectin,c leids 161 through 16k and thrOLIgh g:ite 155 to le@id 157. Read selector 210 is conlrolled by control cii-cuit 110 over leall 113 in a manner described below. 10 The individual infotmatioii tr@insfer rcqliests read out on lead 157 are ordcred in qtielic re_-,islers 220 and 240 for processing. Initiall@', for exainple, a first gi-oup of information transfer reqtjesls from infoi-iiiitioii transfer request register 150 mliy be orderect for processing in queue register 220. Wliiie the systeiii is piocessing the first I-rotip of reqLICStS SO ordered i:l qLlClle i-egister 220, a second grolip of transfer I-CqLICStS fr(iiii request register 150 is orclered in qlietie iei@ister 24) fL)I' SLI[iseqLlent procesiing. The first transfer i-eqliest in the sect)n@l ordered oo group in queue register 240 f(-illoA@s iniiiiediatel@, bellind the last transfer request of the first grolip in qLICLiC rCgiSter 220. Repeating this ordei-ing of the inl'oi-niation trzin@;fer request by grOLIPS thus transforiiis the i-andoiiily oriented transfer reqtjests in i-eqliest i,e_Qister 150, in effect, 25 into an endless qUeL]C of ti-anstei, requests for piocessin,@ As will be described in detail beloa,, the requests ark: shifted OLit of qL[CL[c registers 220 and 240 through gate 290 and over lead 291 to control Cil'CL]it 110 for processin.-. @o It has been assumed in the iliLIS,,rative embodiment iri FIGS. I and ? thit access niiy be had to onl@, a single memory address per sector during eacii memory perioci, that is, during each revolution of drLIM 131. Advant-,i,,eotisly, therefore, e,,icti of re,,ister stages QRI thrOL1,111 p,,5 QRY@Z in queue repister 220 and eacli of register sta,-es QSI thrOLIgh QSiii in qLieLie re.-is,er 240 ni,,i@, Lie associated with a respective one of meniory storage sectoi-s STI throtigh STitt of drum 131. Thus qlicue registers stages QRI and QS1 are associated with memory se-etor 40 STI, stages QR2 and QS2 ni-e associ-,itelf NN@ith sector ST2, and so forth, stages QRiii -,ind QStii bein@_,, associated wi,h memory sector STitt. Accor(.Iin,-[Nr, eacli information transfer request may be directed to the appropriate re-.ister stage in either queue register 220 or qLieLle register 240, 4 la cori-esporidin- to the memory sector of drum 131 to which the tr@insfer ieqLleSt is directed. This permits a reduction in the capacit@, requirements of the individual register stages in queue re_pisiers 220 ind 240 siiice it :s not necessary to store therein the inenior@, sector iden+,ity 50 portion of the meniory a(ldi-ess of the inforniition transfer request, The operation of the arr@ingem,.-nt shown in FIGS. and 2 will now be described. Assuine that a ntiniber )f information transfer i-equests have aCCLinlulated in trans55 fer request register 150 and th,,it they @@ire continlling to be received over reqliest lead 141 and i-e---istered in register 150. The first i-equest recein,ed is re,-istered in request register stage RS1, the second in stage RS2, and so forlh. Qi-leue registers 220 and 240 ii-e assujiied to be initially (30 empty. QUeLie register 220 is ,issuiiied to be ttie quetic register into which the first grc)Lip of ti-ansfor rCqLICStS al,c ordered. Operaticn is initiated by control circuit 110 A,hicli directs read selector 210 via leid 113 to enable read cir65 cuit RDI. It iS aSSLinied that operatioii is initiated at a point when index TX is idjacent heads 132, as indicated to conti-ol circuit 110 by a sliitable tiining si@-n@il froiii clock circuit 136 over index leall 147. Reid selector 210, responsive to the direction of conlrol cirCLlit 110. enibles 70 read circliit RDI to read olit the inforniation transfcr request i-egistered in register sla@,e RSI of reqliest register 150. The transfer reqL[eSt is out nondestrtictively i).@, i-ead circuit RDI on,er leid 161 throu.-Ii -ate 155 over leid 157 to steerin, cit-cuit 230. Steet-inl- circuit 230 75 dii-ects the contents of the ii-@trisfei- i-cqtiest, cxcept for t[ic
[4]3,439,340 7 memory sector identity portion thereof, over lead 231 to gates 262 and 264. Gates 262 and 264 are disabled at this point and neither passes ttie request therethrough. The memory sector identity portion of the information transfer reqttest is directed by steering circuit 230 over lead 232 to coiltrot circliit 110 zind to steering cii-cuit 225 in queue register 220. Control circuit 110, responsive thereto, enables gate 262 to direct the transfer request on lead 231 therethrotigh over lead 265 to steerijig circuit 225 in qLieLic register 220. Steering circuit 225 is controlled by the memory sector identity of the information transfer reqljest, appearin- on lead 232, to direct ttie ti-ansfer request on lead 265 over the appropriate one of leads 251 thi-olioli 25/ii to the individual queue register stage QR1 thi-ough QRtiz associated with the iiiemory sector to A,hich the request is directed. For example, assume that the first information transfer i-equest registered in request register stage RS1 and read out of lead 157, in the nianner desciibed above, pertains to storage bloct,, B22 in iiie.niory sector ST2 on track TKI of drum 131. The meniory sector i,,Ientity ST2 of the transfer request, appearin.- on lead 232, controls steering circuit 225 to direct the remainder of the transfer request over lead 252 for storige in qtieue register stage QR2 whicli, it will be recalled, is issociated with memory sector ST2. Upon storage of the first information transfer request in queue register st@ige QR2, that is, upon the enabling of gate 262, control cirCL]it 110 energizes shift circuit 153 over lead 112. The output of shift circliit 153 on lead 154 shifts or pushes down the transfer requests in register 150. The first request, re,-istered in request register stage RSI and transferred to qLieLie register stage QR2 in the manner just described, is thus destro@red. The request previously registered in request register stage RS2 is shifted down into reqtiest register stage RSI, the request registerell in stage RS3 is shifted doNN,n into stage RS2, and so forth, each request being thits shifted doa,n one stage. Thereupon, contrDI circuit 1.1.0 directs read selector 210, via lead 113, to enable relid circuit RD1 again to read out the contents of request register stage RSI. This tinie, of course, request register stage RS1 contains the second information transfer reqitest, which was initially registered in stage RS2 of reqticst register 150. The memory sector identit@, of the transfer request, it will be recilled, is directed over lead 232 to control circtjit 110. Control circuit 110 keeps track, via such mcillory sector identities, of tht storage condition of the variotis quetic register st,,iges to insure thit a transfer request is not directed tlirough gates 262 and 264 to a queue register stage that is already occupied by a previously stored transfer request directed toward the same memory sector. Thus, if the next inforniation transfer request in the ilIListrative, ex,iniple being described also pert-,iins to memory sector ST2, such ,is to storage block B12 therein by way of example, control circuit 110 would not enable g@ite 262 to direct the transfer rcqttest to quelie register 220, and control circuit 110 would not energize shift circuit 153. Rather, that trinsfer request would be retained in register stage RS1 of request register 150 for ordering in queue register 240 with the next group of reqliests and ordering of the present grolip would continue to the third information transfer request, which is presently registered in stage RS2 of request registei- 150. This is accomplished by control circliit 110 directing read selector 210 to enable re@id circuit RD2 to read out the contents of request re@.ister stage RS2. Assume, bowever, that the second information transfer request pertains to a different memory storage sector, such as memor)r sector STI for example. Responsive tO the appearance of the memory sector identity STI on lead 232, control circiiit 110 enables g@ite 262 to pass the transfer request therethrotigh to steering circuit 225 in qlietie register 220. SteCTing cirCLlit 225, iindei- conti-ol of the menior@r sector identit@, on leid 232, directs the 8 transfer request over lead 251 to queue register stage QRI for storage, stage QRI being associated with memory sector STI. Control circuit 110 also energizes shift circuit 153 upon such transfer to shift the contents of transfer Yequest register 150 down one stage again, destroying the request registered in stage RSI (which transfer request is now registefed in queue register stage QR1) and placing the third transfer reqiiest in stage RS1 of transfer request register 150. The operation proceeds in this manner to place the random address transfer requests from request register 150 into ordered sequence in queue register 220. When a transfer request is encountered in request register 150 pertaining to a memory sector with regard to which a transfer request has already been placed in queue register 220, cotitrot circuit 110 directs read selector 210 to the next higher read circuit and thus to the next higber register stage of request register 150, retaining the subseqtiently received transfer request in the bottom-most reg)o ister stages for ordering in the next gi-oup. For example, if during the ordering of the first group of transfer requests in quetie register 220, two such transfer requests are encountered pertaining to memory sectors with regard to which a transfer request has already been placed 2,3 in queue register 220, these reqtiests will be retained in request register stages RSI and RS2, respectively. Control circuit 110 will at this point in ordering requests in queue register 220 be directing read selector 210 to read out the transfer requests from the next higher request 30 register stage, stage RS3 via read circuit RD3. Similarly, shifting opcration in request register 150, via shift circuit 153 under control of control circuit 110, takes place only down to request register stage RS3 after read out of each new request therefrom, the transfer re35 quests in stages RSI and RS2 remaining undisturbed. When ordering of a second group of transfer requests, in queue register 240, is initiated, therefore, control circuit 110 directs read selector 210 to read out the transfer request retained in reqtiest register stage RSI. Upon reg40 istration of the request in queue register 240, control circuit 110 shifts the requests down one stage in request register 150, the request from the first group which was originally retained in stage RS2 being shifted to stage RSI for readout and transfer to queue register 240. 45 The ordering of information tran@fer requests in a queue register, such as qucue register 220, is effected during one revolution of drum 131. Thus, upon receipt of the next index timing signal over lead 147, control circuit 110 proceeds to order the next group of information trans50 fcr requcsts in queue register 240 while the first group of transfer requests ordered in queue register 220 are processed. The information transfer requests in qtieue register 220 are read out for processing, one at a time, through gate 290 over lead 291 to control eirciiit 110. 55 Read out of queue register 220 is effected in synchronism with the rotation of drum 131, each sector timing signal on lead 145 energizing shift circuit 275 to shift the next information transfer request out of queue register 220. The output of shift circuit 275 is directed to the proper queue (;o register, in this case queue register 220, via one of shift gates 261 and 263 enabled by control circuit 110. Whenever a group of requests is being ordered in one of queue registers 220 and 240, the shift gate 261 or 263 associated with the other queue regitser is enabled by control circuit 65 110. Tbus, in the present instance, shift gate 261 is enabled by control circuit 110 over lead 127 to extend the shift signals from sbift circuit 275 therethrough to queue register 220. 7o Accordingly, at the beginning of memory sector ST1, advantageously during passage of control block BC1 thereof adjacent heads 132, shift circiiit 275 shifts the first information transfer request out of stage QRI of quelie register 220 over lead 291 to control circuit 110. Responsive to the memory addi-ess portion thereof, con75 trol circliit 110 directs head selection circuit 135 over
[5]2)4391340 9 lead 1 15 to select the -,ippropriate one of heads 132,- illtistratively head HI in the example herein. Read circliit 137 or write circuit 138 is enabled by control circuit 110 in accordance with the read-write instruction in the information transfer request. Similarly, control circuit 110 selects the proper storage location in information buffer store 120 via lead 121, as indicated by that portion of the inforniation transfer request. As mentioned above, timing signals for the read or write operation by control circuit 110 are derived in known manner froni clock circuit 136 over lead 144. As the beginning of memory sector ST2 passes adjacent heads 132, a memory sector timing signal on lead 145 causes shift circuit 275 to advance the next information transfer request out of quelic register 220 over lead 291 to control cirCL[it 110 for processing. The remaining transfer reqliests ordered in queue register 220 are read out sequentially for processing in this manner. Shortly after processing the last information transfer request in queue register 220, the transfer request pertaining to memory sector STt?i on drum 131, index IX will again be @idjacent heads 132, the resulting index timing si_gnal on lead 147 causing control circuit 110 to disable shift gate 261 and to enable shift gate 263 via lead 128. During the ensuing memory cycle, therefore, the transfer re- 25 quests ordered in queue register 240 are processed in the manner just described, while another grotip of transfer requests from request register 150 are ordered in qlieue register 220. In the illustrative arrangement of the invention shown 3( in FIGS. I and 2, it was assumed that memory 130 was divided into memory storage sectors and that access could be had to only one storage block address in each sector dui-ing a memory cycle. Therefore, the register stages in queue registers 220 and 240 were each associated id- .9,-) vantageolisly with a respective memory storage sector and steering circuitry in the two re-.isters steered each information transfer request from request register 150 into the appropriate queue register stage. However, in some seqliential access memory systems, access may be 40 had to each consecutive storage address in the memory. It may be appreciated readily that if such were the case it would not be practical, generally, to provide an individual register stage in each quetie register associated with each memory acidress. Rather, each queue register would be provided with a plurality of register stages depending upon the number of accesses to the memory desired during a memory cycle, that is, depending iipon the desired information transfer rate. An illustrative embodiment of an arrangement for effecting the ordering 50 of random address information transfer requests in such a sys'em is shown in FIG. 4. For the purposes of clarity and to facilitate description, the sequential access memory, the information buffer store, and the input and outptit circuitry are not shown in FIG. 4, it being assumed that 55 these portions of the sequential access memory system are substantially similar to that shown in the embodiment of FIGS, I and 2, with the above-mentioned exception that access may be had to each consecutive address in the sequential access -niemory employed with the arrange- 60 ment in FIG. 4. In the arrangement in FIG. 4, information transfer requests are received on lead 441 from an input circuit similar to input circuit 140 in FIG. I and registered in sta.-cs RSI thrOLIgh RSii of informifion transfer reql]est 65 register 450 in a manner substantially similar to that described above for request register 150, However, inasmuch as qtleue register stages QR1 through QRk and QSI thrOLigh QSk have no relationship with particular portions of the sequential access memory, the ordering of the trans- 70 fer requests in queiie registers 460 and 480 is handled in a considerably different manner than in the arrangemcnt of FIGS. I and 2. Each of request register stages RSI through RSii have associated therewith individit-,i] read-er,,ise cirCLlits REI through REir. Read-erase sclec- 7,) 10 tor 420 enables each of i-ead-crase cii-cuits REI through REii in sequence to scan the contents of the associate-d request register stages RS1 through RSti. The contents of stages RSI through RSii are thus read out nondestrtictively in sequence over respective leads 461 throtigh 46ii, through gate 455 and over leid 457 to comparator 419. Comparator 419 compares the seqtiential access memory address portion of each information transfer request appearing on lead 457 with a memory address provided by address selector 415 on lead 416. Control circuit 410 via lead 412 controls address selector 415 to provide consecutive memory addresses on lead 416 in the same serial manner as the addresses appearing in a memory cycle. This arrangement, therefore, permits the scanning of the information transfer requests in reqtiest register 150 in search of a request directed to the first address in the memory cycle, then for the second address, etc., through all of the memory addresses. For example, let it be assumed that the sequential memory addresses in the memory cycle, that is within a track of the memory, are numbered consecutively from 1 to 1,000 and that a track address and a memory address identify a particular memory storage location. Control circuit 410 initially directs address selector 415 to provide memory address I on lead 416 to comparator 419; and read-erase selector 420 is enabled via lead 411 to initiate a scanning cycle through the contents of transfer request register 450 for a transfer request directed toward memory address 1. Read-erase selector 420, responsive to the enabling signal on lead 411, selectively enables read-erase circuits REI through REir in sequence to read oiit nondestructively the contents of request rcgister stages RSI through RSti, one at a time, over lead 457 to comparator 419. If a transfer request appears on lead 457 which is directed toward memory address 1, comparator 419 provides a suitable comparison signal on lead 413. The comparison signal on lead 413 is directed to control circuit 410, to gate 431 and to read-erase selector 420. It will be noted that each transfer request appearing on lead 457 is also direetcd over lead 458 to gate 431. Gate 431 is enabled by a comparison si,@nal on lead 413 to extend the transfer request on lead 458 therethroligli to queue register gates 433 and 435. Thus in the example described, the appearance of a transfer request on lead 458 which is directed to memory address I is detected by comparator 419, which generates a comparison signal on lead 413, enabling gate 431 to extend the transfer request therethrough to queue register gates 433 and 435. One of gates 433 and 435 is enabled by control circuit 410, such as gate 433 over lead 417. The transfer request is thus directed through enabled gate 433 to queue register 460 for storage in the bottom-most vacant stage thereof, stage QRI in this instance. Control circuit 410 is responsive to the comparison signal on lead 413 to direct address selector 415 to provide the next consectitive memory address on lead 416, that is, memory address 2. Read-erase selector 420 is responsive to the comparison signal on lead 413 to erase the contents of the request register stage whose contents were just transferred to quelic register 460 in the manner dcscribed above and to initiate a new scanning cycle. For example, if during the first scanning cycle an information transfer request directed toward memory address I is found in request register stage RS2, read-erase selector 420 is responsive to the comparison signal on lead 413 to halt the advance of the scanning cycle at register stage RS2, to erase the contents of stage RS2 via read-erase circiut RE2, and then to initiate a new scanning cycle starting again with register stage RSI looking now for a tranfer request directed toward memory address 2. Upon the contents of one of the request register stages being erased, such as the contents of stage RS2 in the illustrative example, the contents of the register stages above that stage are pushed down one stage prior to initiation of the next scanning enrcle.
[6]If during a scanning cycle no transfer request is found in request register 450 which is directed toward the memory address provided by address selector 415 on lead 416, address selector 415 is advanced to the next memory address and a new scanning cycle is initiated. Control circuit 410 is advised that a scanning cycle is complete by the enablement of the last read-erase circuit REn, this indication being provided by the enabling signal from readerase 'selector 420 on lead 42n to control circuit 410. Responsive thereto, in the abscnce of a comparison signal of lead 413 resulting from readout of stage RSn, control circuit 410 advances address selector 415 to the next memory address via lead 412 and directs read-erase selector 420 via lead 411 to initiate a new scanning cycle. Accordingly, it will be appreciated that the contents of queue register stages QR1 through QRk will, via the successive scanning and read out of the contents of transfer request register 450 in the above manner, comprise information transfer requests ordered in the serial manner in whir-h memory addresses occur in the sequential access memory. The ordering of transfer requests in anindividual one of queue registers 460 and 480 is effected during a single memory cycle, whereupon during the next memory cycle the requests so ordered are processed while another group of transfer requests are being ordered in the. other queue register. Processing of the transfer reqtiests in one of queue registers 460 and 480 is effected in the same manner as that described above in connection with the embodiment of FIGS. 1 and 2, the requests being read out through gate 490 over lead 491 to control circuit 410. Read out is synchronized to the sequential access inemory via shift pulses generated by a shift circuit (not shown) in synchronism with memory address timing signals from the sequential access memory. The shift pulses are directed to the appropriate one of queue registers 460 and 480 through one of shift gates 471 and 473 enabled by control circuit 410 over a respective one of leads 427 and 428. If a quetie register is filfed A,ith tr@insfer reqtiests befoi-e the end of a memory cycle, as will generally be the case, control circuit 410 terminates further scanning of request register 450 until the beginning of the next memory cycle, during which time requests will be ordered in the other queue register. Control circuit 410 keeps track of the loading of the queue registers via the comparison signals on lead 413 from comparator 419. Initiation of the next scanning cycle by control circuit 410 to load the other qtieue register begins at the memory address following that for which the last comparison signal was received on lead 413. Of course, if desired for a particular application, address selector may be reset by control circuit 110 to initiate the new scanning cycle with memory address 1. It will be appreciated that queue registers 460 and 480 may be associated with predetermined memory address groups and that control circuit 410 may direct address selector 415 to provide the appropriate memory addresse@s on lead 416 dliring a scanning cycle in accordance with the particular queue register being loaded. Thus, for example, in memory systems employing interleaved words for adjacent memory addresses, one qtieue register may be associated advantageously with the evennumbered memory addresses and the other register with the oddnumbered memory addresses. The transfer requests in request register 450 may be scanned alternately for ordering even-numbered memory address requests irL one queue register and for ordering odd-numbered memory address requests in the other queue register. The even-numbered address requests may be processed during one memory period and the odd-numbered address requests during the next memory period. In the alternative ilILIstrative embodiment shown in FIG. 5, circuitry is provided for ordering the individiill r,tndoni address information transfer reqliests ,is they ai-c rceeived by the sequential access memory systeii-t. Let it 3)439)340 12 again be assumed, as was the case with the embodiment in FIGS. I and 2, that a memory period of sequential ,iccess memory 530 is divided into a plurality of consecutively numbered memory sectors, such as sectors I through x, and that each sector can be accessed only at a single address during each meniory cycle. A plurality of information transfer request registers 551 through 55x are thus provided in FIG. 5, each register being respectively associated with a corresponding one of the memory 10 sectors. For example, transfer request register 551 may be Lissociated with memory sector 1, register 552 with memory sector 2, and so forth, register 55x being associated witti memory sector x. Each of transfer request registers 551 through 55x is provided with a plurality y of stages 1,5 indin,idually capable of registering a single information transfer request directed toward the particular memory sector with which the request register is associated. The bottom stages WHIL through WHxl of request i-egistei-s 551 throui_@h 55x are each connected through 20 gating circuit 562 to a corresponding register stage in queue register 560 and to a corresponding register stage in queue register 580, which queue register stages are therefore individually associated with respective ones of the memory sectors of sequential access memory 530. 25 Thus, for example, request register stage WHll is connected through gating circuit 562 over lead 571 to queue register stage QRI of queue register 560 and over lead 581 to queuc register stage QS1 of queue register 580, queue register stages QRI and QS1 bcing associated there30 fore with memory sector 1. Similarly, request register stage WH21 is connected through gating circuit 562 over leads 572 and 582 to queuc register stages QR2 and QS2, respectively, which stages are thus associated with memory sector 2; and request register stage WXI is connected 35 over leads 57x and 58x, respectively, to queue register stages QRx and QSx associated with memory sector x. Accordin@,,Iy, each information transfer request received on request lead 541 is steered by steering circuit 550 into the bottommost vacant stage of the appropriate one of 40 information transfer request registers 551 through 55x in accordance with the memory sector identity portion of the request. If, by way of example, the first transfer request received on lead 541 is directed toward memory sector 2 of sequential access memory 530, steering circuit 43 550 steers the request into transfer request register 552, the request being registered in stage WH21 thereof. If the next transfer request on lead 541 is also directed toward memory sector 2, it is steered into request register stage WH22 of request register 552. If, on the other hand, 50 the next transfer request is directed toward a different memory sector, such as memory sector x, it is steered by stcering circuit 550 into the bottommost vacant stage of the, request register associated with that sector, stage WHxl of transfer request register 55x. 55 Once during each memory period of sequential access memory 530, such as rcsponsive to the appearance of an index timing signal on lead 547 from memory 530, control circuit 510 enables gating circuit 562 via lead 569 to transfer the contents of transfer reqltest register stages 60 WHIL through WHxl into one of queue registers 560 and 580 for processing. Assuming that the transfer requests are to be placed into queue register 560 for example, control circuit 510 enables gating circuit 562 to transfer the contents of request register stages WHll through WHxl 65 over leads 571 through 57x into respective queue register stages QR1 throtigh QRx of queue register 560. Read out of the transfer requests from queue register 560 for processing is effected in a manner substantially similar to that described above in connection with the em70 bodiment of FIGS. I and 2. Shift circuit 565 provides shift pulses on lead 566 through shift gate 561, enabled by control circuit 510 via lead 517, over lead 567 to queue register 560. The shift pulses are properly synchi,oiiized to the oper',tting speed of sequential access meniory 7 @-) 530 by appropriate timing signals provided to shift circuit
[7]3,439,340 13 565 over lead 545 from memory 530. The individlial transfer requests read out of queue register 560 are directed through gate 590 over lead 591 to control circuit 510 for processing in the manner described above. Incident to the transfer of the contents of transfer request register stages WHll through WHxl to queue register 560, the remaining contents of each of transfer request registers 551 through 55x are pushed down one stage by control circuit 510 via lead 568. Thus, the transfer requests registered in stages WH12 through WHx2 are advanced into respective stages WHIL through WHxl. Therefore, during the read out and processing of the transfer requests from queue register 560, the next group of transfer requests, those now registered in transfer request stages WHll through WHxl, are transferred through gating circuit 562 over leads 581 through 58x into respective queue register stages QSI through QSx of queue register 580. Accordingly, well prior to the completion of the processing of the transfer request from queue register 560, the next group of transfer requests to be processed are registered in queue register 580 for subsequent processing. Read out of queue register 580 is controlled, of course, by control circuit 510 enabling shift gate 563 via lead 518 and disabling shift gate 561. The arrangement depicted in FIG. 5 is particularly advantageous in sequential access memory systems wherein the information to be stored in memory 530 is assigned to a particular memory storage location by the memory system, rather than it being preassigned. In such memory systems, reference by control circuit 510 to the plurality of information transfer request registers 551 through 55x readily shows which memory storage sectors have the least backlog of transfer requests. This permits control circuit 510 to make a better distribution of the workload by assigning the new transfer requests to locations in those sectors whenever possible, In each of the illustrative embodiments described above, it has been assumed the individual transfer request queues correspond to, and are processed during, a single memory period of the sequential access memory. In general, however, it will be appreciated that the queues need not correspond to a memory period, although such correspondence is usually desirable. The queues may correspond, for example, to a multiple or si-ibmultiple of the memory period, the size of the queues varying accordingly to provide a given information transfer rate. It is to be understood that the above-described arrangements are merely filustrative of the present invention. Numerous other arrangements miy be devised by those skilled in the art without departing from the spirit and scope of the invention. What is
