International Business Machines Corporation

Tien C Chen

Chin Tung

Hsu Chang

Daniel Jonathan Auerbach

Share-Young Lee

Wolfgang J Paul

Vincent Yu-Sun Lum

Kapali P Eswaran

In a centrally controlled resource arbitration system, each of the units concurrently requesting access sends its identity code and the binary complement thereof to a central arbitration processor. The identity codes are logically combined into a first word, and the binary complements are logically combined into a second word. A subset identifier of the requesting units is then formed by combining corresponding bits of the first and second words. Unresolved values in the subset identifier are iteratively removed to eliminate a subset of the requesting units. When all but one of the requesting units have been eliminated, access to the resource is given to the remaining unit.

Method and apparatus for communicating data between a host and a

Disclosed is a multiple port memory apparatus responsive to r+w addresses within an instruction cycle for supplying data read from the r read addresses and for writing data received to the w write addresses. The memory apparatus comprises r groups of w+1 memory banks, responsive to the r read addresses and the w write addresses, for supplying for each of the r read addresses data read from one of the w+1 banks in one of the r groups and for writing data received to each of the w write addresses in the other of the w+1 banks in the r groups. A pointer for controlling the r groups of w+1 memory banks directs the read and write accesses to the memory banks so that one of the w+1 banks obtaining valid data is read in response to a read address and so that data is written to the other banks in each cycle. The pointer directs memory accessing to prevent conflicts. Conflicts are always avoided because one bank in each of the r groups is directed to supply data in response to a read address and the w remaining banks are available for writing data in response to the w write addresses redundantly so that each of the groups of memory banks will have valid data in at least one of its w+1 memory banks for a given address.

High-performance multiple port memory

This invention describes an automatic sorter which consists of a linear array of n modules called permuters. Each permuter contains an upper-lower pair of registers, a comparison mechanism and gating arrangement to the permuters immediately above and immediately below. A sequence of N records, N being no larger than 2n, can be loaded, one at a time, into the sorter from the top during the 'down mode': at the same time each of the permuters function to save the lower-ordered record in the lower register, to expel the higher ordered record to the permuter below, and to receive a record from above into the upper register. As soon as all records are loaded, the sorter enters the 'up mode' of operation, in which each permuter keeps the higher ordered record in the upper register, expels the lower-ordered record through the top, and receives a record into the lower register. The uppermost permuter thus ejects one record at a time, in sorted order. There is no discernible sorting time, the sorting being completely overlapped by the loading and unloading of information records.

Apparatus for the sorting of records overlapped with loading and

This invention describes a pipeline sorter, in which record-pairs are compared and conditionally swapped while being advanced along the pipeline synchronously. The pipeline sorter has the topology of a U-shaped tube, with regularly spaced crosspaths linking the two arms. Records are loaded one at a time, into the input arm synchronously, and emerge out of the output arm, also one at a time and synchronously. Within the sorter, at periodic time intervals a number of record-pairs at correlated positions of the U-tube are compared. Dependent on the comparison outcome, either the original records themselves, moving along vertical paths, or their permutation, moving along crosspaths, will arrive at the next down-stream positions. In this manner, as soon as the last record has been loaded, the correctly sorted output will begin to emerge, with the overall sorting time completely overlapped by the loading and unloading of records.

Apparatus for sorting records in overlap relation with record loading

An apparatus for sorting of equal length records with the sorting time maximally overlapped by the time taken for loading and unloading of records. The minimal structure consists of a decision mechanism linked to and associated with a network of ladder structures. The activity within the network is so synchronized that the sorting activity in most ladders occurs while some ladder within the network is still undergoing the loading of input data; and during the unloading phase, the individually sorted data from each ladder are merged concurrently to produce a sequence of sorted records. The overlap between sorting and loading varies from 0 for records requiring no loading/unloading, to 100% for multi-ladder networks with loading/unloading. A single ladder structure supporting a type of transposition sort is first described both in a full exchange scheme and a fast version. Then, the mechanism for loading/unloading equal length records to the single ladder is set forth. Next, the use of two ladders of dissimilar lengths for facilitating the overlap between loading/unloading and sorting is revealed. Lastly, the general multi-ladder case with which complete overlap is achieved terminates the specification. The ladders themselves are formed from a plurality of equal length loops connected by dual mode switches such that when a switch between a pair of adjacent loops is set electrically into the first mode ('on') the adjacent loops are cross-connected facilitating an exchange of any records circulating therein. When the two switches bounding a loop are electrically set in the second mode ('off'), the loop is maintained as a circulating path. An end loop of each ladder operates as an input/output port. In one embodiment, control signals for operating the dual-mode switches are developed by an external decision mechanism through the expedient of storing and comparing the keys of each record to be sorted, said signals control the switches in loading, sorting, merging and extracting. An alternate embodiment can employ a plurality of detectors to transmit the detected keys to a decision mechanism dynamically without previously copying the keys.

Apparatus for transposition sorting of equal length records in overlap

Information processing is conveniently achieved by a structure which uses a novel binary switch. The switch can steer two data streams so that they will either cross one another or bypass one another, depending upon external control. A linear array of shift register loops are linked together by these flow-steering binary switches to form a storage structure which is termed a ladder. The ladder provides a variety of data structures. For example, it can alternate between LIFO (last in-first out) and FIFO (first in-first out). It can also dynamically rearrange data items according to recency of usage, in order to improve average access time to any data item. The binary switch and the ladder structure are conveniently provided using magnetic bubble domain technology, although other technologies can also be used.

Ladder for information processing

A bubble logic array with n data inputs for performing any Boolean (or switching) logic function. Each of the data inputs comprises binary information in the form of the presence or absence of discrete bubbles. The logic function is performed by the propagation, channeling, and interaction of the bubbles themselves. The particular logic function performed by the array may be fixed by permanent connections of selective control inputs to bubble generators. Alternatively, a universal logic array may be provided by using a further 2.sup.n bubble inputs as controls to separately personalize the array. In this manner, the logic function performed by the array may be varied with each set of controls to achieve dynamically alterable logic. When the data inputs each comprise an input bubble pattern the logic array in either the fixed form or the alterable form is capable of pipelining operations, producing one meaningful output at every bit cycle.

Pipelined universal bubble logic array

An apparatus for performing efficient transposition exchange sorts among equal length records is described. The apparatus takes advantage of the flow steering property of linkable circulating storage loops to minimize the average access time by positioning information closer to the output port in a storage structure. The apparatus is formed from a linear array of equal size shift register loops each holding one record. The loops are switchably interconnected such that when two boundary switches are set in a first mode, the contents of each loop normally circulate wholly therewithin. Upon a common boundary switch being set in a second mode, the contents within a first loop flow into a second loop and vis-a-vis. By setting a common boundary switch to the second mode, the contents of a pair of adjacent loops are exchanged in the duration of one loop cycle time. Further exchanges can be started before a previous one is complete; this overlapping of operations can lead to an effective exchange rate of two exchanges per loop cycle. By repeating the exchange for consecutive pairs of loops, then the contents of any reference loop can be migrated to an output port D loops away in (D + 1)/2 loop cycle times.

Apparatus and machine implementable method for the dynamic rearrangement

A text editing system is described which is comprised of single technology elements. That is, the system is comprised of dynamic shift registers which are entirely implemented with either magnetic bubble domain devices or charge coupled devices. These shift registers can be randomly accessed using write and read decoders to provide great flexibility in entry, retrieval, and restoring of data. An editing shift register is used for text editing functions, such as insertion of data, deletion of data, etc. This editing shift register performs the data manipulation functions by using techniques such as freezing of data bits and bypassing of data bits in order to change the order of the data and to close gaps which may occur in the data. The shift registers used for storage and the editing shift register are characterized in that all data manipulation functions and all accessing functions do not require a change in the sequence of the drive field used to move the data bits.

Growing community of inventors

San Jose, CA, United States of America

Tien C Chen