Boots – shoes – and leggings
Patent
1991-05-21
1995-06-06
Gossage, Glenn
Boots, shoes, and leggings
395600, 364DIG1, G06F 1300
Patent
active
054230152
DESCRIPTION:
BRIEF SUMMARY
The present invention relates to a memory structure and, in particular, to a memory structure which is adapted to permit relatively fast shuffling of data stored in the structure through the structure thereby commercially facilitating operations such as sorting.
DISCUSSION OF PRIOR ART
A particular, although by no means exhaustive, use for the memory structure outlined in this specification is in the field of content addressable memories (CAMs).
In the late 1970's it was realized that the majority of the work that computers were being called upon to perform in the majority of applications was associative in nature, including sorting information, accessing information by key and the like. It was also realized that the storing of information according to a memory address in a memory (e.g. random access memory (RAM) and the like) was not the most efficient way of storing that information where associative type operations were to be performed on that information. Ideally it was preferred that the information be stored according to specific search keys, and clustered in accordance with an algorithm which related the search keys, in some way (for example alphabetical order, numerical order or the like).
Storing information in memory according to the content of the information being stored (ie. according to a key which is itself part of the stored information) rather than storing according to an address became known as content addressable memory (CAM). Software tree structures were and still are a software implementation of a content addressable memory. In essentially all cases to date, the memory in which the elements of that tree structure reside is still conventional random access memory with elements of the tree stored by address. Ideally a hardware content addressable memory structure should be much faster than a hardware RAM combined with a software tree structure. Various attempts have been made to date to make normally addressable RAM behave as content addressable memory thereby combining the inexpensiveness and large memory capacity of commercially available RAM, with the desired CAM structure. U.S. Pat. No. 4,758,982 to PRICE discloses one such attempt and also provides a good summary of CAM issues. U.S. Pat. No. 4,758,983 to BERNDT discloses another attempt at making commercially available RAM behave as a CAM.
SUMMARY OF THE INVENTION
In at least one particular embodiment of the present invention, commercially available RAM is combined with surrounding hardware logic so as to provide a (relatively) very fast CAM structure.
In other embodiments of the invention a memory stack structure which can be shuffled very rapidly, in an arbitrarily and user selectable small number of CPU cycles is disclosed. This structure seeks to go at least some way in overcoming a commonly held belief in the industry that maintaining data in sorted list order is computationally highly inefficient (even though desirable).
In one broad form there is provided a memory structure for storing records. The structure comprises a plurality of contiguous memory locations each for storing one of the records, the plurality of memory locations being functionally separated into memory sub-structures, each of the memory sub-structures comprising a separate but contiguous sub-portion of the memory structure, each of the sub-structures including a buffer memory location attached thereto, each of the buffer memory locations being arranged to receive a record stored in a memory location within the associated sub-structure and to transfer a record stored in the buffer memory location to a memory location within another of the sub-structures, each of the buffer memory locations being further arranged to receive a record stored in a memory location in a sub-structure which is immediately adjacent to the sub-structure corresponding with the buffer memory and to transfer a record stored in the buffer memory location to a memory location in a sub-structure which is immediately adjacent the sub-structure located with the buffer memory location.
REFERENCES:
patent: 3713107 (1973-01-01), Barsamian
patent: 4030077 (1977-06-01), Florence et al.
patent: 4031520 (1977-06-01), Rohner
patent: 4110837 (1978-08-01), Chen
patent: 4663742 (1987-05-01), Anderson et al.
patent: 4740917 (1988-04-01), Denis et al.
patent: 4758982 (1988-07-01), Price
patent: 4758983 (1988-07-01), Berndt
patent: 4811305 (1989-03-01), Watanabe et al.
patent: 4833655 (1989-05-01), Wolf et al.
patent: 4839866 (1989-06-01), Ward et al.
patent: 4847812 (1989-07-01), Lodhi
patent: 4864544 (1989-09-01), Spak et al.
Weller et al, "Optimal Searching Algorithms for Parallel Pipelined Computers", Proceedings of the Sagamore Computer Conference, Aug. 20-23, 1974 (Springer Verlag, New York, 1975), pp. 291-305.
Segal, "Hardware Sorting Chip Steps Up Software Pace", Electronic Design, vol. 34, No. 15, Jun. 26, 1986, pp. 85-91.
Baudet et al., "Supercomputing With VLSI: Sorting", 1987 IEEE International Conference on Computer Design: VLSI In Computers & Processing, Oct. 8, 1987, pp. 8-11.
LandOfFree
Memory structure and method for shuffling a stack of data utiliz does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory structure and method for shuffling a stack of data utiliz, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory structure and method for shuffling a stack of data utiliz will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-994175