Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-12-21
2002-10-29
Thai, Xuan M. (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S309000, C711S147000
Reexamination Certificate
active
06473821
ABSTRACT:
TECHNICAL FIELD
The present invention relates to data processing computer systems and, more particularly, to an arbitration method and system for allowing multiple processors to access a shared memory in which each processor is allotted a fixed amount of time on a rotating basis to access the shared memory.
BACKGROUND ART
When processing is divided among multiple processors, a mechanism must be in place to allow communication between the processors to transfer data back and forth to memory. There is an inherent tradeoff when developing the architecture between a maximally flexible interface (fully connected network) and an area efficient interface (shared memory bus) or an intermediate solution.
Processors with a common address space (shared memory) offer a single memory address space which multiple processors can share. Communication is performed by writing and reading shared variables through this memory where any processor can access any variable or memory location.
The access of the shared memory must also be synchronized so that one processor cannot start working on data before another processor is finished working on the data, and so that multiple processors do not attempt to access the memory at the same time. A bus arbitrator performs the synchronization. A bus arbitrator is a controller which defines what processor may have access to the bus at any given time. When multiple processors attempt to access the bus concurrently, one processor is granted access to the bus while the other processors must wait for the bus to be released. Attempting to assign priority to different processors while ensuring that a low priority processor is not locked out or subject to unreasonable delays in accessing the bus can lead to very complex bus arbitration schemes.
Processors may also use message sending for communication where dedicated links exist between processing nodes. In the extreme case, a fully connected network offers a dedicated communication link between each processing node with a much higher performance and enormous cost in juxtaposition to the low performance and low cost of the bus approach. Because of the dedicated links there is no need for an arbitrator to select if one processor should wait while another processor is granted access.
Other network topologies exist that connect together subsets of nodes with mid range performance and cost. In cases where a less than fully connected network is used there is the possibility that a message sent between processors will have to go through one or more intermediate nodes to arrive at its intended destination. This results in a variable amount of delay to complete the communication, and the need for arbitration because a decision is required to determine whether data at an intermediate node should be passed along or whether the data of the processor should be sent.
A complication exists for real time processing in that a fixed amount of processing or a processing task must be accomplished within a specified amount of time or number of clock cycles. The program must insure that the longest path through the code will always be completed within the required time period. A typical shared memory/bus approach or a network which is not fully connected makes ensuring this difficult because of the arbitration which occurs and causes processors to wait for some unknown amount of time to access a bus. While waiting, processors are typically forced to suspend processing and execute wait states leading to uncertainty in how long it takes in the worst case to complete the processing tasks.
What is needed is a low cost shared memory and bus approach for multiple processors to access a shared memory which avoids the need for a complex arbitrator or the injection of wait states.
DISCLOSURE OF INVENTION
It is an object of the present invention to provide an arbitration method and system for allowing multiple processors to access a shared memory in which each processor is allotted a fixed amount of time on a rotating basis to access the shared memory.
Accordingly, the present invention provides a data processing system having a memory, multiple processors, and an arbitrator. Each of the processors is operable with the memory for accessing the memory. The arbitrator is operable with the processors for enabling each of the processors exclusive access to the memory for a predetermined time period on a rotating basis.
Further according to the present invention, there is provided a method for enabling a plurality of processors access to shared memory. The method includes associating a time period of a time frame with each of the processors. The time periods of the time frame are then counted. A processor is then enabled to have exclusive access to the shared memory for the time period associated with the processor when the counted time period is the time period associated with the processor.
REFERENCES:
patent: 4495567 (1985-01-01), Treen
patent: 4536839 (1985-08-01), Shah et al.
patent: 4682282 (1987-07-01), Beasley
patent: 4780812 (1988-10-01), Freestone et al.
patent: 4809217 (1989-02-01), Floro et al.
patent: 4894769 (1990-01-01), Conforti
patent: 5047921 (1991-09-01), Kinter et al.
patent: 5193193 (1993-03-01), Iyer
patent: 5255373 (1993-10-01), Brockmann et al.
patent: 5261109 (1993-11-01), Cadambi et al.
patent: 5333297 (1994-07-01), Lemaire et al.
patent: 5408629 (1995-04-01), Tsuchiva et al.
patent: 5463486 (1995-10-01), Stevens
patent: 5586331 (1996-12-01), Levenstein
patent: 5761731 (1998-06-01), Van Doren et al.
patent: 6163831 (2000-12-01), Kermani
patent: 6266751 (2001-07-01), Niescier
patent: 6401176 (2002-06-01), Fadavi-Ardekani et al.
Altmayer Terry Robert
Hagan Christopher John
Wargnier James Alfred
Brooks & Kushman P.C.
Thai Xuan M.
Visteon Global Technologies Inc.
LandOfFree
Multiple processor interface, synchronization, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple processor interface, synchronization, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple processor interface, synchronization, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941431