Memory request reordering in a data processing system

• US 6,272,600 B1
• Filed: 02/28/1997
• Issued: 08/07/2001
• Est. Priority Date: 11/15/1996
• Status: Expired due to Term

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Hyundai Electronics America Incorporated (SK Hynix Inc.)
• Inventors: Talbot, Gerry R., Hypher, Austen J.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US08/808,849
• Time in Patent Office: 1,621 Days
• Field of Search: 395/729, 395/732, 711/169, 711/3, 711/140, 711/158, 711/152, 711/117, 711/157, 711/105, 711/151, 711/133, 711/159, 371/41
• US Class Current: 711/140
• CPC Class Codes: G06F 13/1631 through address comparison

Abstract

Memory transactions are carried out in an order that maximizes concurrency in a memory system such as a multi-bank interleaved memory system. Read data is collected in a buffer memory to be presented back to the bus in the same order as read transactions were requested. An adaptive algorithm groups writes to minimize overhead associated with transitioning from reading to writing into memory.

Claims

1. In a data processing system, a method for reordering a plurality of memory access requests, the method comprising:

accepting the plurality of requests;

reordering the plurality of requests such that at least one memory access request for an available memory location precedes at least one memory access request for a non-available memory location;

selecting a request to access an available memory location, from the plurality of requests, wherein the selecting a request comprises;

determining whether a read request to access an available memory location exists, among the plurality of requests;

selecting a read request to access an available memory location, if the determining determines that such a read request exists; and

selecting a non-read request to access an available memory location, if the determining determines that a read request to access an available location does not exist;

scheduling the selected request;

determining whether the selected request is a write request; and

after scheduling the selected request, successively scheduling at least one write request from the plurality of requests, if the selected request is determined to be a write request;

wherein successively scheduling at least one write request comprises;

counting write requests that have been successively scheduled; and

successively scheduling write requests until a predefined maximum number of write requests has been counted.

2. The method of claim 1, wherein successively scheduling at least one write request comprises:

determining whether a write request upon an available memory location exists among the plurality of requests; and

stopping the scheduling of write requests if a write request upon an available memory location is determined not to exist.

3. In a data processing system, a method for scheduling a plurality of requested memory operations, wherein the requested operations have default priorities, the method comprising:

accepting the plurality of operations;

determining whether a particular operation of the plurality of operations operates upon a non-available memory location;

if the particular operation operates upon a non-available memory location, selecting a requested operation, herein referred to as the selected operation, that operates upon an available memory location and has lower default priority than the particular operation, from the plurality of operations; and

scheduling the selected operation, prior to scheduling the particular operation that operates on the non-available memory location;

wherein each requested operation is of a type from a set of types including a more-critical type, and wherein the step of selecting an operation comprises;

(a) determining whether a more-critical operation exists, among the plurality of operations, that operates upon an available memory location;

(b) selecting, as the selected operation, a more-critical operation that operates upon an available memory location, if the determining determines that a more-critical operation exists; and

(c) selecting, as the selected operation, an operation not of the more-critical type that operates upon an available memory location, if the determining determines that a more-critical operation does not exist; and

wherein the set of types includes a burstable type, the method further comprising of;

determining whether the selected operation is a burstable operation;

if the selected operation is determined to be a burstable operation, successively scheduling at least one burstable operation from the plurality of operations; and

wherein the burstable type includes a write type.

4. In a data processing system, a method for scheduling a plurality of requested memory operation, wherein the requested operations have default priorities, the method comprising:

accepting the plurality of operations;

determining whether a particular operation of the plurality of operations operates upon a non-available memory location;

if the particular operation operates upon a non-available memory location, selecting a requested operation, herein referred to as the selected operation, that operates upon an available memory location and has lower default priority than the particular operation, from the plurality of operations;

scheduling the selected operation, prior to scheduling the particular operation that operates on the non-available memory location; and

wherein at least one operation from the plurality of operation produces a return value, and wherein the plurality of operations have an original ordering, the method further comprising;

collecting return values of operations from the plurality of operations; and

ordering the collected return values according to the original ordering.

5. In a data processing system, a method for ordering a plurality of requested memory operations, the method comprising:

accepting the plurality of operations;

determining whether a particular operation of the plurality of operations operates upon a non-available memory location, and if so, selecting a requested operation new than the particular operation that operates upon an available memory location from the plurality of operations, the selecting a requested operation comprising

determining whether a read operation exists, in the plurality of operations, that operates upon an available memory location;

if the read operation exits, selecting an oldest operation of read operations that operate upon available memory locations; and

if a read operation does not exist that operates upon an available memory location, selecting an oldest write operation, of the plurality of operations, that operates upon an available memory location;

scheduling the selected operation; and

after scheduling the selected operation, determining whether the selected operation is a write operation, and if it is successively scheduling a burst of at least one write operation from the plurality of operations.

6. In a data processing system, a method for ordering a plurality of requested memory operations, the method comprising:

accepting the plurality of operations;

determining the availability of memory locations for two memory operations from the plurality of operations, prior to scheduling or reordering of either of the two operations;

determining whether a particular operation of the plurality of operations operates upon a non-available memory location, and if so, selecting a requested operation newer than the particular operation that operates upon an available memory location from the plurality of operations, wherein selecting a requested operation comprises;

determining whether a read operation exists, in the plurality of operations, that operates upon an available memory location;

if the read operation exists, selecting an oldest operation of read operations that operate upon available memory location; and

if a read operation does not exist that operates upon an available memory location, selecting an oldest write operation, of the plurality of operations, that operates upon an available memory location; and

scheduling the selected operation;

wherein each memory location corresponds to one of a plurality of semiconductor non-associative memory banks, and wherein selecting a requested operation comprises;

identifying a memory location upon which an operation from the plurality of operations operates;

identifying a non-associative memory bank, of the plurality of non-associative memory banks, to which the identified memory location corresponds; and

determining whether the identified non-associative memory bank is available.

17. The system according to claim 6, wherein:

each memory location is associated with one of a plurality of memory banks; and

the availability determiner is coupled to a memory controller that indicates whether a memory bank is available.

7. In a data processing system, a method for scheduling a plurality of requested memory operations including read operations and write operations, wherein at any time, there exists a current preference from among possible preferences including a read preference, the method comprising:

determining the current preference;

determining whether there exists a write operation upon an available memory location among the plurality of operations;

determining whether there exists a read operation upon an available memory location among the plurality of operations;

scheduling a read operation upon an available memory location upon one of the following conditions;

it is determined in the determining that a read operation upon an available location exists, and that the current preference is read preference; and

if is determined in the determining that a read operation upon an available location exists and that no write operation upon an available location exists;

wherein the possible references further include a write preference, the method further comprising scheduling a write operation upon an available memory location upon one of the following conditions;

it is determined in the determining that a write operation upon an available location exists, and that the current preference is write preference; and

it is determined in the determining that a write operation upon an available location exists, and that no read operation upon an available location exists;

setting a new current preference after one of scheduling a read operation and scheduling a write operation; and

wherein the step of determining whether there exists a write operation upon an available memory location comprises determining whether a write path is clear.

8. A data processing system that reorders memory access requests, the system comprising:

a request buffer for holding a plurality of memory access requests;

an availability determiner for determining availability of memory locations to which access is sought by at least some of the plurality of memory access requests; and

a request reordering unit responsive to the availability determiner for selecting a memory access request to access an available memory location from among the plurality of memory access requests;

wherein the request reordering unit comprises;

a read identifier responsive to the availability determiner for identifying a read request to access an available memory location, if such a read request exists;

a non-read identifier responsive to the availability determiner for identifying a non-read request to access an available memory location, if such a non-read request exists; and

a controller for selecting the identified read request, if it exists, and selecting the identified non-read request, otherwise;

wherein;

the read selector is adapted to identify the read request according to an original ordering of the plurality of operations; and

the non-read selector is adapted to identify the non-read request according to an original ordering of the plurality of operations.

9. A data processing system that reorders memory access requests, the system comprising:

a request buffer for holding a plurality of memory access requests;

an availability determiner for determining availability of memory locations to which access is sought by at least some of the plurality of memory access requests; and

a request reordering unit responsive to the availability determiner for selecting a memory access request to access an available memory location from among the plurality of memory access requests;

wherein the request reordering unit comprises;

a read identifier responsive to the availability determiner for identifying a read request to access an available memory location, if such a read request exists;

a non-read identifier responsive to the availability determiner for identifying a non-read request to access an available memory location, if such a non-read request exists; and

a controller for selecting the identified read request, if it exists, and selecting the identified non-read request, otherwise;

wherein;

the controller is adapted, if the selected request is a write request, to successively select a least one additional non-read request to access an available memory location from the plurality of requests, the additional at least one non-read request thereby defining a burst; and

wherein the controller is adapted to select up to a predefined maximum number of non-read requests to define the burst.

10. The method of claim 9, wherein the non-read selector is adapted to stop selecting non-read requests to define the burst upon detecting that no write request upon an available memory location exists.

11. The method of claim 9, wherein at least one request from the plurality of requests produces a return value, the system further comprising:

a data reordering unit for collecting return values of the plurality of requests and ordering the collected return values according to an original ordering of the plurality of requests.

12. A data processing system that reorders memory access requests, the system comprising:

a request buffer for holding a plurality of memory access requests;

an availability determiner for determining availability of memory locations to which access is sought by at least some of the plurality of memory access requests; and

a request reordering unit responsive to the availability determiner for selecting a memory access request to access an available memory location from among the plurality of memory access requests;

wherein the request reordering unit comprises;

a read identifier responsive to the availability determiner for identifying a read request to access an available memory location, if such a read request exists;

a non-read identifier responsive to the availability determiner for identifying a non-read request to access an available memory location, if such a non-read request exists; and

a controller for selecting the identified read request, if it exists, and selecting the identified non-read request, otherwise;

wherein at least one request from the plurality of requests produces a return value, the system further comprising;

a data reordering unit for collecting return values of the plurality of requests and ordering the collected return values according to an original ordering of the plurality of requests.

13. A data processing system that reorders memory access requests, the system comprising:

a request buffer for holding a plurality of memory access requests;

an availability determiner for determining availability of memory locations to which access is sought by at least some of the plurality of memory access requests; and

a request reordering unit responsive to the availability determiner for selecting a memory access request to access an available memory location from among the plurality of memory access requests;

wherein at least one request from the plurality of requests produces a return value, the system further comprising;

a data reordering unit for collecting return values of the plurality of requests and ordering the collected return values according to an original ordering of the plurality of requests.

14. A data processing system that reorders memory access requests, the system comprising:

a request buffer for holding a plurality of memory access requests;

an availability determiner for determining availability of memory locations to which access is sought by at least some of the plurality of memory access requests; and

a request reordering unit responsive to the availability determiner for selecting a memory access request to access an available memory location from among the plurality of memory access requests;

wherein;

each memory location is associated with one of a plurality of non-associative memory banks; and

the availability determiner is coupled to a memory controller that indicates whether a non-associative memory bank is available.

15. A data processing system that schedules a plurality of requested memory operations having default priorities, the system comprising:

an availability determiner for determining availability of a memory location operated upon by a particular requested operation and a memory location operated upon by another requested operation having lower default priority than the particular operation, the particular and the other requested operations being from among the plurality of operations;

an operation reordering unit responsive to the availability determiner for scheduling the other requested operation, herein referred to as the scheduled operation, if the particular operation operates upon a non-available memory location;

each requested operation is of an operation type, operation types being classifiable as either more-critical or not more-critical;

the operation reordering unit comprises a controller that schedules, as the scheduled operation, a more-critical operation that operates upon an available memory location, if such a more-critical operation exists, and an operation not of a more-critical type that operates upon an available memory location, otherwise;

wherein a read type is a more-critical type; and

wherein;

operation types are classifiable as either burstable or not burstable; and

the controller is further adapted to detect when the scheduled operation is a burstable operation and to control selection of a subsequent burst of at least one burstable operation that operates upon an available memory location; and

wherein a write type is a burstable type.

16. A data processing system that order a plurality of requested operations upon semiconductor memory, possible memory operations including read operations and non-read operations, the system comprising:

a memory operation buffer for holding the requested memory operations;

an availability determiner for determining availability of memory locations, wherein the availability determiner is adapted to determine availability of memory locations operated upon by at least two of the requested memory operations before either of said at least two requested operations are scheduled; and

an operation reordering unit responsive to the availability determiner for scheduling from the plurality of requested memory operations an oldest read operation that operates upon an available memory location, if such a read operation exists, and an oldest non-read operation that operates upon an available memory location, otherwise;

wherein the memory operation buffer is adapted to dynamically accept new requested memory operations;

wherein at least one operation from the plurality of operation produces a return value, the system further comprising;

a data reordering unit for collecting return values of the plurality of operations and ordering the collected return values according to the age of their corresponding requested operations; and

wherein the operation reordering unit comprises a controller that responds to the condition that the scheduled operation is a write operation by initiating a scheduling of a burst of at least one requested write operation upon an available memory location.

18. A data processing system that schedules a plurality of memory access requests including read requests, the system comprising:

a request buffer for buffering the plurality of memory access requests;

a read selector for identifying a request to read an available memory location from among the plurality of requests, if such a request exists;

a preference generator for establishing a current preference from possible preferences including a read preference;

a scheduler for scheduling the identified read request upon the condition that the current preference is read preference; and

wherein;

the plurality of memory access requests further includes write requests;

the system further comprises a write selector for identifying a request to write to a available memory location from among the plurality of requests, if such a request exists; and

the scheduler is further adapted to schedule the identified read request upon the condition that the write selector identifies no request to write to an available memory location.

19. A data processing system that schedules a plurality of memory access requests including read requests, the system comprising;

a request buffer for buffering the plurality of memory access requests;

a read selector for identifying a request to read an available memory location from among the plurality of requests, if such a request exists;

a preference generator for establishing a current preference from possible preferences including a read preference; and

a scheduler for scheduling the identified read request upon the condition that the current preference is read preference; and

wherein;

the plurality of memory access requests further includes write requests;

the system further comprises a write selector for identifying a request to write to a available memory location, from among the plurality of requests, if such a request exists;

the possible preferences further include a write preference; and

the scheduler is further adapted to schedule the identified write request upon the condition that the current preference is write preference; and

wherein the scheduler is further adapted to schedule the identified write request upon the condition that the read selector identifies no request to read an available memory location and a write path is clear.

20. A data processing system that schedules a plurality of memory access requests including read requests, the system comprising:

a request buffer for buffering the plurality of memory access requests;

a read selector for identifying a request to read an available memory location from among the plurality of requests, if such a request exists;

a preference generator for establishing a current preference from possible preferences including a read preference; and

a scheduler for scheduling the identified read request upon the condition that the current preference is read preference;

wherein the preference generator is adapted to re-establish a current preference after the scheduler schedules a request.