Browse Prior Art Database

Self Balancing Double Ordered Magnetic Bubble Memory

IP.com Disclosure Number: IPCOM000087847D
Original Publication Date: 1977-Mar-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 62K

Publishing Venue

IBM

Related People

Wong, CK: AUTHOR [+2]

Abstract

Dynamic reordering of data in the order of its last use is described in U. S. Patent 3,670,313. The ordering is dynamically maintained by a technique in which every access to position K requires K shifts of the register to bring the accessed data to the read/write location (position 0) and then another K shift to update the order, thus totaling 2K shifts. A technique for double ordering is shown in U. S. Patent 3,797,002, wherein the data in each shift register is divided into two disjoint groups each maintaining its own ordering of last use. The worst case storage reference service time is improved by the double ordering scheme but the average access time depends on how the data elements are grouped.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Self Balancing Double Ordered Magnetic Bubble Memory

Dynamic reordering of data in the order of its last use is described in U. S. Patent 3,670,313. The ordering is dynamically maintained by a technique in which every access to position K requires K shifts of the register to bring the accessed data to the read/write location (position 0) and then another K shift to update the order, thus totaling 2K shifts. A technique for double ordering is shown in U. S. Patent 3,797,002, wherein the data in each shift register is divided into two disjoint groups each maintaining its own ordering of last use. The worst case storage reference service time is improved by the double ordering scheme but the average access time depends on how the data elements are grouped. Particularly, if all the most frequently used data happened to be placed in one group, then the reduction in service time due to double ordering is very small.

In order to provide improved ordering, transposition ordering and double ordering are combined in a technique which is self-balanced so that greater reduction in average access time is insured. Notation

Suppose addresses are assigned to data locations in the shift register loop as follows. The read/write location has address zero. Ascending addresses are then assigned in a clockwise direction. Fig. 1 shows a shift register with N=16 locations. A clockwise cyclic permutation of the data elements is referred to as a positive shift and a counterclockwise shift is then a negative shift. Thus in this terminology, a shift equal to +1 will move a data element with address A to address (A+1)(mod N'), where x(mod y) = x-y.[x/y]. Description

If a memory reference is made to address 0, then access is immediate and no change is made in the data ordering. If a memory reference is made to the Kth address of either the address list 1,2,...N/2 -1 or the list N-1, N-2,...N/2, then, respectively -K or +K shifts are applied to bring the required data element to the read/write location. The next opera...