Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
1999-11-12
2001-04-10
Lee, Thomas C. (Department: 2782)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S005000, C710S029000, C710S036000, C710S040000, C710S041000, C710S058000, C710S116000, C710S123000, C710S244000, C709S241000, C709S241000, C709S241000, C711S158000, C711S167000, C712S216000
Reexamination Certificate
active
06216178
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains generally to computing systems. More specifically, the present invention relates to a providing access to shared resources in a computing system such as multi-processor computer systems and the like. More particularly, techniques for detecting the collision of data on a data bus in case of out-of-order memory accesses or different times of memory access execution are described.
BACKGROUND OF THE INVENTION
In the basic computer system, a central processing unit, or CPU, operates in accordance with a pre-determined program or set of instructions stored within an associated memory. In addition to the stored instruction set or program under which the processor operates, memory space either within the processor memory or in an associated additional memory, is provided to facilitate the central processor's manipulation of information during processing. The additional memory provides for the storage of information created by the processor as well as the storage of information on a temporary, or “scratchpad”, basis which the processor uses in order to carry out the program. In addition, the associated memory provides locations in which the output information of the processor operating set of instructions are placed in order to be available for the system's output device(s).
In systems in which many components (processors, hard drive, etc) must share a common bus in order to access memory presents there is a high probability of memory access conflicts. Especially in the case of multiprocessor computer systems, and the like, in which systems utilizing different processors are simultaneously in operation, access to memory or other shared resources, becomes complex. Since it is likely that each of the processors or processor systems may require access to the same memory simultaneously, a conflict between processors will generally be unavoidable. Essentially, the operation of two or more processors or processor systems periodically results in overlap of the memory commands with respect to a common memory, or other shared resource, in the multi-processor computer system.
Conventional approaches to solving the problem of conflicting memory access requests to a shared memory include, in one case, complete redundancy of the memories used for each of the processors, and isolation of the processor systems. However, this approach to solving the problem of conflicting memory access requests often defeats the intended advantage of the multiple processor system. Such multiple processor systems are most efficient if operated in such a manner as to provide parallel computing operations upon the same data in which one processor supports the operation of the other. Conventionally, such processor systems may be either time shared in which the processors compete for access to a shared resource, such as memory, or the processor systems may be dual ported in which each processor has its own memory bus, for example, where one is queued while the other is given access.
Various approaches have been used to avoid the above described conflict problems. In one approach, the avoidance of conflicts is accomplished by sequentially operating the processors or by time sharing the processors. In this way, the processors simply “take turns” accessing the shared resource in order to avoid conflict. Such systems commonly used include “passing the ring” or “token systems” in which the potentially conflicting processors are simply polled by the system in accordance with a pre-determined sequences similar to passing a ring about a group of users.
Unfortunately, use of sequential processor access methodologies imposes a significant limitation upon the operation of the overall computer system. This limitation arises from the fact that a substantial time is used by the system in polling the competing processors. In addition, in the case where a single processor is operating and requires access to the shared memory, for example, a delay between the processor accesses to the shared resource is created following each memory cycle as the system steps through the sequence.
Another conventional approach to conflict avoidance relies upon establishing priorities amongst the processors in the computer system. One such arrangement provides for every processor having assigned to it a priority with the hierarchy of system importance. The memory controller simply provides access to the highest priority processor every time a conflict occur. For example, in a two processor system, a first and a second processor access a shared memory which is typically a dynamic RAM (DRAM) type memory device which requires periodic refreshing of the memory maintain stored data. Generally, the DRAM type memory is refreshed by a separate independent refresh system. In such a multi-processor system, both the processors and the refresh system compete for access to the common memory. A system memory controller will process memory access request conflicts, or commands, as determined by the various priorities assigned to the processors and the refresh system. While such systems resolve conflicts and are somewhat more efficient than pure sequential conflict avoidance systems, it still suffers from lack of flexibility.
Another approach to conflict resolution involves decision-making capabilities incorporated into the memory controller. Unfortunately, because the decision making portions of the memory controller are operated under the control and timing of a clock system, a problem arises in the substantial time is utilized in performing the actual decision making before the memory controller can grant access to the common memory.
Unfortunately, this problem of performing the actual decision making substantially erodes the capability of conventional memory controllers granting access to multi-bank type memory systems. In multi-bank type memory systems, the actual memory core is departmentalized into specific regions, or banks, in which data to be retrieved is stored. Although providing faster and more efficient memory access, the complexity required of conventional memory controllers in coping with a multi-bank memory device substantially slows the overall access time of the system as a whole.
In view of the foregoing, it should be apparent that techniques for detecting the collision of data on a data bus in case of out-of-order memory accesses or different times of memory access execution are desired.
SUMMARY OF THE INVENTION
According to the present invention, techniques for detecting the collision of data on a data bus in case of out-of-order memory accesses or different times of memory access execution are described. A system for reordering commands to achieve an optimal command sequence based on a target response restriction that determines an optimal slot for a data transfer between an initiator controller and a target subsystem by prohibiting an issuance of a command that would cause a data conflict includes a command queue arranged to stores commands to be issued, a time indicating when the data transfer appears on a data bus between the controller and the target device after the command was issued to the target, a burst-bit indicating data burst transfer and a read write-bit (r/w). A data queue coupled to the command queue arranged to store a time indicating when the data transfer will appears on the data bus between the controller for an already issued request to the target device as well as arranged to store the burst bit and the w bit. The system also includes a collision detector coupled to the data queue and the command queue arranged to detect the possible collisions on the data bus between to be the issued command that is stored in the command queue and already issued commands that are stored in the data queue. The system also includes a queues and link controller coupled to the collision detector and the data queue and the command queue arranged to store and reorder commands to be issued wherein the controller calculates the new issue time of commands as well as a time when the data appe
Stracovsky Henry
Szabelski Piotr
Beyer Weaver & Thomas LLP
Infineon - Technologies AG
Lee Thomas C.
Nguyen Tanh
LandOfFree
Methods and apparatus for detecting the collision of data on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for detecting the collision of data on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for detecting the collision of data on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2461264