Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-12-21
2003-12-02
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06658524
ABSTRACT:
BACKGROUND OF THE INVENTION
In a computer system, a processing unit (CPU) is commonly connected to a memory device. One of the routine operations to be performed by the CPU operated program is that of scanning a predetermined part of the memory locations, in order to find the memory cell in which a specific data is stored. Because the position of the searched data is not known in advance the scanning operation is a lengthy process allowing for the CPU to scan a whole section of memory, addressing each cell, reading the data in that cell and comparing it to the searched data.
The prior art may be demonstrated by the example of a computer system with a memory that stores an extensive list of names, first names, age and other personal data all arranged in an alphabetic order by name. When a list of all persons having the age of 20 is required, the computer system will scan the whole memory, read the age of each of the persons on the list, and in case that the age is 20, register the name of the respective person in a new list. For a list of 100000 persons, the program will be required to perform 100000 operations.
It is therefore necessary to design a new, time saving process for locating data in a memory system without scanning each of the data in the memory. Such a process would have an almost universal application improving efficiency in many fields including personal computers, internet servers, computerized production methods, data processing and any other art that employs computer systems.
In the prior art it is known to use a Content Addressable Memory (CAM). However existing CAM devices are different from the conventional memory devices and they require the use of a specially adapted interface circuitry (U.S. Pat. No. 4,805,093). It is a further drawback of the prior art that separate devices are required in order to enable a system to perform both conventional read/write operations and CAM data searches. It is therefore desirable to have a CAM device that may be connected to the processing unit via an Data Bus and an address bus and therefore may be used in most conventional computer systems. It is also desirable to have a device that may be operated in both normal and call out modes alternatively.
In some prior art CAM systems the response time usually increases with the size of the memory being searched, the reason being that cells are linked by a signal that passes each cell in turn (U.S. Pat. No. 4,805,093) or that the search function is performed by a scanning mechanism (U.S. Pat. No. 5,502,832). In other prior art systems, a match signal is propagated through the cells, passing each of the cells in turn, so that if a matching cell is far from origin, the response time will be longer, due to some propagation delay occurring at every cell.
In some CAMs of the prior art the address of the data to be stored is not specified. The device stores the data at an address determined by the device logic and retrieval of the data may only be achieved by Content Addressing. It is therefore desirable to have a memory in which data storage is performed by specifying the address of a cell on an Address Bus and subsequently presenting the data to be stored on a Data Bus whereby data may be stored and retrieved in the same way as in a conventional memory and the call out search mode is provided as an additional function.
In another prior art device, described in U.S. Pat. No. 5,568,416, a content addressable memory contains a plurality of memory cells, in each cell a match output line is provided and all match output lines from all cells are connected to a priority encoder that generates the address of the highest priority matching cell. In this type of prior art it is necessary that the priority encoder comprise a large number of inputs, one for each of the cells. Consequently a large number of gates and an extensive surface are required to allow for the routing of the matching lines from each of the cells respectively to the priority encoder, whereby the practical capacity of these CAMs is most limited.
It is therefore desirable to have a Call Out memory that is not operated through a global circuitry, in which the “Call Out” function is added separately in each of the cells. In such a memory with a parallel organization where each cell is independent and connected to an Adress Bus, a Data Bus and an Origin Bus, response time is not dependent on the size of the memory, nor on the position of the searched data and the number of logic gates necessary to implement the “Call Out” function. A device of this type has the advantage that a large memory device may be implemented at low cost and due to the parallel structure several “Call Out” devices may be used to implement a large memory.
SUMMARY OF THE INVENTION
The present invention concerns a method for increasing the velocity of operation of an electronic searching system such as a computer searching system and an increased velocity memory and circuit to be used in the implementation of an advantageous memory device for computers, electronic systems, internet servers etc.
The inventive device and method greatly improve the searching sequence of the system, providing means to search the position of a given data, previously stored in the memory, while eliminating the need to scan all the data in the memory. Due to an innovative logic device comprised in the circuit of the invention, in spite of the fact that many cells of the memory device may respond to the request, only one address is seen. The required time to find one memory cell containing the searched data is thus reduced to a single memory cycle.
A set of lines or an additional memory cell is used to define an “Origin” for the search, so that the address of the cell with matching data that is seen is the one closest to the “Origin” address in a predefined direction and the search can be repeated in that direction until all matching data are located.
The memory comprises an array of innovative memory cells, each cell comprising a masking circuit that selectively inhibits the output of the search data depending on the position of the cell relative to the Origin and to other matching cells.
The memory has a parallel organization wherein each cell is independently connected to a Bus system comprising an Adress Bus, a Data Bus and an Origin. Data storage is performed by specifying the address of a cell on the address bus and subsequently presenting the data to be stored on the Data Bus whereby data may be stored and retrieved in the same way as in a conventional memory and the call out search mode is provided as an additional function.
For a comparison with the above example of the prior art, we may take the example of a memory that stores data for 100,000 persons of whom only 5000 have the age of 20. The memory of the invention will be programmed to first set the Origin address to the address of the uppermost item of the list in a predefined direction. Next the system will be operated in the Call Out mode and the data 20 will be set on the Address Bus. The Call Out memory will then set on the Data Bus the address of the person with the age of 20 that is highest on the list in the predefined direction. A processor will then read in normal mode the data at that address and write it down in a new list. Next the processor will set the Origin to the address of the first found name and repeat the search in the Call Out mode. After repeating the procedure 5000 times, a complete list of persons with the searched data (age: 20) will be obtained. The prior art process would require 100,000 operations to arrive at the same result, which makes the inventive search method 20 times faster.
It is an important advantage of the invention that the device is capable of operating in two alternative modes: In the first mode (Normal) the function is similar to that of a common memory device. In the second mode (Call Out) the device implements the Call Out function.
It is another advantage of the present invention that the device architecture is compatible with commonly used computer devices, and it may b
Prokopets Shmuel
Villaret Emanuel Yves
Ellis Kevin L.
Lowe Hauptman & Gilman & Berner LLP
MEMCALL LLC Corporation Service Co.
LandOfFree
Memory with call out function 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 with call out function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory with call out function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124467