Scheduler for avoiding bank conflicts in issuing concurrent...

Details Scheduler for avoiding bank conflicts in issuing concurrent... Scheduler for avoiding bank conflicts in issuing concurrent...

1999-09-27

2002-05-21

Kim, Matthew M. (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S005000

Reexamination Certificate

active

06393534

ABSTRACT:

BACKGROUND OF THE INVENTION
Main memory
10
(
FIG. 1A
) for a conventional computer is normally implemented by one or more dynamic random access memories (abbreviated as “DRAMs”) that are coupled by a memory bus
11
to an interface circuit
12
(implemented by a “north bridge chip”) that in turn is coupled to a central processing unit (CPU)
13
. Interface circuit
12
is typically coupled to a system bus
14
(such as a PCI bus) that may be coupled to other devices (not shown).
Certain CPUs that require main memory to support a bandwidth of at least 500 Mbytes/s can use a specific type of DRAM called “Direct RDRAM.” A main memory
10
, when implemented with a Direct RDRAM, requires interface circuit
12
to include a specific circuit called “Rambus Access Cell” (abbreviated as RAC)
15
(
FIG. 1A
) that supplies commands as well as row and column addresses to the Direct RDRAM. One example of a conventional Direct RDRAM includes sixteen memory banks
0
-
15
and seventeen sense amplifiers (abbreviated as “sense amps”) S
00
-S
15
(FIG.
1
B). Sense amplifiers S
00
-S
15
temporarily hold the data to be transferred to/from banks
0
-
15
. For example, a sense amp S
01
that is shared between adjacent banks
0
and
1
holds data to/from either of banks
0
and
1
. Due to such sharing of sense amps, two adjacent banks (e.g. bank
0
and bank
1
) cannot be accessed simultaneously in the Direct RDRAM.
This limitation on the simultaneous access of adjacent banks is described in a data sheet entitled “Direct RDRAM™ 64/72-Mbit (256K×16/18×16d),” available from RAMBUS Inc., 2465 Latham Street, Mountain View, Calif., USA 94040 that is incorporated by reference herein in its entirety. In an example wherein the two transactions have the same device and bank addresses, but different row addresses, the data sheet states that “[t]ransaction b may not be started until transaction a has finished. However, transactions to other banks or other devices may be issued during transaction a.” The data sheet further states that the second transaction “must occur a time t
rc
or more after” the first transaction. See the last paragraph in the second column of each of pages 20 and 21.
Conventional use of Direct RDRAMs in computers is described in an article entitled “DIRECT RAMBUS TECHNOLOGY: The New Main Memory Standard,” by Richard Crisp, IEEE Micro, November/December, 1997, pages 18-28 that is also incorporated by reference herein in its entirety. According to the just-described article, such “[d]irect RDRAMs avoid the empty time slots, or ‘bubbles,’ that frequently occur in single clocked SDRAM systems. Bubbles result from inadequate control bandwidth necessary to support page manipulation and scheduling while transferring data to and from random locations. Doubled data rate schemes only aggravate the bubble problem.” Id at page 22.
The article further states that “[u]sers can schedule the data resulting from the row operation to appear immediately after the column operation completes. This highly interleaved condition greatly improves the efficiency of the channel. This interleaving can only happen when the requests target different banks in either the same Direct RDRAM or a different RDRAM on the channel. The more banks in a system, the better the chances are that any two requests are mapped to different banks. The more interleaving that is possible, the more the memory system performance improves. The Direct RDRAM's memory array is divided into banks. . . . all 64-Mbit Direct RDRAMs in development have 16 banks with a page size of 1 Kbyte.” Id at page 23.
The article also states that “[b]ecause a Direct RDRAM spans the entire channel, the CPU accesses each RDRAM independently. So each RDRAM directly adds to the number of memory banks accessible to the memory controller. . . . Since an RDRAM system has more banks per megabyte than an SDRAM or a DDR system, RDRAM systems boast lower bank conflict rates . . . ” Id.
SUMMARY
A scheduler (hereinafter “main memory scheduler”) in accordance with the invention issues requests to main memory in an order different from the order in which the requests are received, in order to minimize bank conflicts. Specifically, the main memory scheduler has a scheduler input port for receiving in a first order (also called “received order”) requests (also called “memory requests”) for accessing the main memory (such as a read request, a write request, or a refresh request), and a scheduler output port that is couplable (i.e. capable of being coupled) to the main memory. A main memory scheduler of one embodiment temporarily stores each received memory request (also called “pending memory request”) in a store (called “memory request store”), and issues the pending memory requests at the scheduler output port in an order (also called “second order”) that is different from the received order.
The main memory scheduler includes, in addition to the just-described memory request store, a multiplexer and a memory request selector that uses the multiplexer to select, for issue to main memory, a pending memory request that avoids a bank conflict. The pending memory requests in the memory request store are checked by the scheduler for bank conflicts with one or more requests that were previously issued and are currently being executed (also called “currently issued requests”). Specifically, the main memory scheduler implements a scheme (also called “bank conflict optimization” scheme) by issuing a second request to a second memory bank that is not coincident with (and preferably not adjacent to) a first memory bank (that is being currently accessed). Therefore, a main memory scheduler as described herein can be used to interleave later-received requests among previously-received requests to the same bank or to adjacent banks, wherein adjacent banks share sense amplifiers (such as banks in Direct RDRAMs of the type described above).
Interleaving of accesses to adjacent banks (as described herein) reduces the time period from the time the request is received to the time the request is fulfilled (also called “access latency”). Also, such interleaving of accesses reduces the number of unused cycles (also called “bubble cycles”) otherwise required to be inserted when accessing adjacent banks successively, thereby improving utilization of the memory bandwidth. Furthermore, interleaving of accesses as described herein allows the interleaved accesses to be issued in accordance with one or more schemes (such as the “read bypass of writes”) as described herein, thereby further reducing or eliminating the need for bubble cycles.
The memory request selector includes a bank conflict detector that compares at least a portion (e.g. n bank address bits, when there are a total of 2
n
banks in the main memory) of a current address signal (i.e. an address signal generated by a currently issued request) with a corresponding portion of one or more (in one implementation all) to-be-issued memory address signals held in the memory request store, to select one or more next address signals that are ready to be issued to main memory. The bank conflict detector selects (via the multiplexer) a next address signal that identifies a memory bank that is not adjacent to and that is not coincident with the memory bank being identified by any current address signal, thereby to minimize bank conflicts. If a bank conflict cannot be avoided by issuing the pending requests in an order different from the received order, the main memory scheduler issues the pending requests in the order of receipt, and inserts bubble cycles in the normal manner.
In one embodiment, in addition to (or instead of, in another embodiment) the just-described bank conflict detector, the memory request selector includes an optimizer that issues read requests prior to issuance of write requests (thereby to give higher priority to read requests in a scheme called “read bypass of write”), unless a read request and a write request (also called “earlier-received” write request) that was

Affiliated with

Also associated with

Rating

Scheduler for avoiding bank conflicts in issuing concurrent... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scheduler for avoiding bank conflicts in issuing concurrent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduler for avoiding bank conflicts in issuing concurrent... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2834243