Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1998-09-08
2001-10-09
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S150000, C711S152000, C711S158000, C711S163000, C710S107000, C710S108000, C710S109000, C710S110000, C710S111000, C710S112000, C710S113000
Reexamination Certificate
active
06301642
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a bus arbitration system and method of controlling memory accesses from multiple memory users.
BACKGROUND OF THE INVENTION
The purpose of a memory bus arbiter is to decide which of several memory users (referred to herein as ports) is to be allowed access to a bus and hence to memory connected to the bus. A generalized scenario is illustrated by FIG.
1
. In
FIG. 1
, reference numeral
2
denotes a bus arbiter (labeled “bus arbitrator”) for controlling accesses by a plurality of ports PORT
0
. . . PORT
15
to a memory bus
4
. The memory bus
4
is connected to memory resource via an external memory interface not shown in FIG.
1
. Alternatively, it could be connected directly to on-chip memory. Each port has a memory access path MA
0
. . . MA
15
connecting it to the memory bus by which memory addresses can be sent to the memory resource and items returned from the memory resource. Each port has a request line r
0
. . . r
15
connected to the bus arbiter and a grant line from the bus arbiter to each port g
0
. . . g
15
. Each port also has a bus_busy line bb
0
. . . bb
15
connected through an OR gate
6
to the bus arbiter
2
. Each port signals its request by asserting the request line r
r
. . . r
15
. Some time later the arbiter asserts one of the grant lines indicating which port can use the bus. This process is known as “awarding tenure” of the bus. On receipt of a grant signal a port asserts its bus_busy signal then uses the memory bus to satisfy one or more of its memory requests via its memory access path MA. When the port is finished it de-asserts the bus_busy signal allowing the arbiter to award tenure again.
A wide variety of arbitration schemes have been used in existing bus schemes. When a port has its request signal asserted it is referred to herein as a requester. The three most common are:
1) static priority—the arbiter defines a static rank ordering of each of the ports. It awards tenure to the requester with the highest rank.
2) dynamic priority—similar to the static priority scheme insofar as the arbiter awards tenure to the requester with the highest rank, except that here following each granting the ranking is revised. The grantee is assigned lowest priority and the priority of all other ports which were below the grantee are increased by one.
3) round robin—the arbiter defines a static ordering of the ports and maintains an indication of the last requester which was awarded tenure. In determining tenure, the arbiter starts at the port which follows the last port to have tenure, then awards tenure to the next requester it finds in its traversal order of the ports. The arbiter traversal order for round robin is to start at the lowest numbered port and visit successively numbered ports in turn until the last port is reached and then to wrap around and start traversing from the lowest number port again.
Some schemes are combinations of the above. It is often the case, in real-time applications, that access to memory needs to be shared in a manner such that there is a limit on the amount of time that a requester can be passed over for tenure regardless of the request behavior of other ports. This constraint severely limits the usefulness of many obvious arbitration schemes.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, there is provided a bus arbitration system that comprises:
a memory bus having an interface for accessing memory wherein items are held at locations in memory organized in address sets such that when one location in an address set has been accessed, remaining locations in the same address set can be accessed more quickly by a subsequent memory access than other locations in the memory;
a plurality of memory users each having access to said memory bus and each operable to generate a request for access to the memory;
an arbiter for controlling access to said memory bus by said memory users in response to said requests,
wherein each memory user is operable to read the address of a current access to memory and to generate a same-address-set signal when the address of the last access by that memory user lies in the same set as the address of the current access,
and wherein the arbiter holds for each memory user a predetermined number of accesses which are permitted by that memory user during an access span and, responsive to a request, grants up to that predetermined number of accesses provided that the same-address-set signal is asserted.
In the described embodiment, an access span is a sequence of requests from a single port to which the arbiter grants tenure consecutively.
In one embodiment said locations are addressable by memory addresses comprising a number of addressing bits such that locations within an address set are addressable by a reduced number of addressing bits.
The invention can be used to advantage in any situation where clustering accesses on the basis of locality may ultimately lead to relative addressing (possibly as a side effect using fewer addressing bits). This may be the case in magnetic and optical disks, magnetic tape etc. because the clustering implies less disk head/tape transport movement per access.
The invention is particularly useful in the context of DRAMs having a so-called fast page accessing mode. In this mode, all the cells (locations) on a page are energized when the first word on a page is accessed, therefore expediting subsequent accesses.
DRAMs are normally addressed by applying a row address and a column address to identify a particular location in memory. Memory addresses that have the same row address are said to be on the same page. If successive accesses are on the same page, the row address does not have to be reapplied so the second and subsequent accesses cost less time. Thus, in the described embodiment each address set constitutes a page in memory and the reduced number of addressing bits address the line in each page.
In the described embodiment, the arbiter has sequence determining circuitry for determining the sequence in which memory users are examined by the arbiter to see whether or not they are generating a request. This sequence can be programmable to take into account the number and type of memory users having access to the memory bus. This allows any particular architecture to be optimized in terms of its memory access bandwidth and latency requirements.
Another embodiment of the arbiter includes timing circuitry for determining a maximum time allowed between consecutive requests in an access span. If this time is exceeded that span will be terminated and a next request from a different memory user will be considered.
In addition to being able to program the sequence, the predetermined number of accesses within each access span for each memory user may also be programmable to take into account the pattern of memory accesses effected by each memory user.
The invention also provides a method of controlling accesses by multiple memory users to a common memory wherein items are held at locations in memory organized in address sets such that when one location in an address set has been accessed, remaining locations in the same address set can be accessed more quickly by a subsequent memory access than other locations in the memory. Each memory user reads the address of a current access to memory and generates with a request for access to the memory a same-address-set signal when the address of the last access by that memory user lies in the same set as the address of the current access. A predetermined number of memory accesses are granted to that memory user during an access span provided that the same-address-set signal is asserted.
For a better understanding of the present invention and to show how the same may be carried into effect reference will now be made by way of example to the accompanying drawings.
REFERENCES:
patent: 4623986 (1986-11-01), Chauvel
patent: 5193194 (1993-03-01), Gruender, Jr. et al.
patent: 5655102 (1997-08-01), Galles
patent: 5983325 (1999-11-01), Lewchuk
patent: 5987574 (1999-1
Barnes Peter Malcolm
Jones Andrew Michael
Galanthay Theodore E.
Nguyen Than
Seed IP Law Group PLLC
STMicroelectronics Ltd.
Tarleton E. Russell
LandOfFree
Shared memory bus arbitration system to improve access speed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared memory bus arbitration system to improve access speed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared memory bus arbitration system to improve access speed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2560568