Method and apparatus for scheduling requests within a data...

Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C710S058000, C709S241000, C711S157000

Reexamination Certificate

active

06334159

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates generally to the field of data processing systems, and more particularly, to data processing systems that schedule the execution of selected requests to increase the performance of the system.
Most modem data processing systems include at least a processor and a memory. The processor is typically connected to the memory by a system bus or the like. Other system components may also be connected to the system bus including, for example, I/O modules, other processors, and/or other memory devices. During normal functional operation of the system, the processor typically executes a series of commands to accomplish a desired result. Some of these commands can result in read requests and write requests to the memory and are typically issued in the order of processor execution.
A read request typically provides a read address to the memory over the system bus. The memory reads the requested data from the location identified by the read address and returns the data to the processor for subsequent processing. Typically, the processor cannot process further commands until the processor receives the return data. In contrast, a write request typically provides a write address and write data packet to the memory over the system bus. The memory writes the write data to the write address. For a write request, no return data is typically expected, and thus, the processor can continue processing further commands immediately after the write request is provided to the system bus and/or memory. In many systems, the system bus operates at a lower speed than the processor. In addition, more than one system component may use the system bus and/or memory. For these and other reasons, the read and write requests issued by the processor may not be immediately serviced by the memory, thereby reducing the performance of the system.
To help alleviate this bottleneck, a write queue can be provided between the processor and the system bus to increase the speed at which the processor can issue write requests. As indicated above, no return data is typically expected from a write request, and thus the processor can continue processing further commands immediately after the write request is provided to the system bus and/or memory. The write queue is used to temporarily store write requests that are provided by the processor until the memory and/or system bus can service the write requests. This frees up the processor more quickly because the write queue, rather than the processor, waits for the system bus and/or memory to service the write request.
U.S. Pat. No. 5,790,813 to Wittaker discloses a pre-arbitration system and look-around circuit for increasing the throughput of a data processing system by allowing read requests to be executed prior to previously issued write requests so long as the data coherency of the system is not compromised. As noted above, read requests can slow processor throughput by not allowing the processor to process further commands until the read data is returned from the memory. Write requests, on the other hand, typically do not prevent the processor from processing further commands after the write request is issued. Thus, by assigning a higher priority to read requests relative to write requests, Wittaker suggests that the overall throughput of the data processing system may be increased.
Some data processing systems are configured such that the execution of two or more request types is faster when the requests are executed in a particular sequence. For example, the execution of two read requests followed by two write requests may be faster than the execution of a read, a write, a read, and finally a write request. In some systems, it is the transition from one request type to another that introduces a delay in the system. Therefore, it has been found that it may be more efficient to execute a string of a first request type followed by a string of another request type. Simply assigning a priority to one of the request types relative to the other request type, as suggested by Wittaker, typically will not provide the desired sequence of two or more different request types. Thus, it would be desirable to provide a data processing system that can schedule the execution of selected requests such that two or more request types are executed in a particular predetermined sequence to achieve increased system performance.
SUMMARY OF THE INVENTION
The present invention overcomes many of the disadvantages of the prior art by providing a method and apparatus for scheduling the execution of selected requests received in a first-in-time sequence, such that two or more request types are executed in a particular sequence for increased performance. Briefly, the present invention identifies two or more requests that have two or more predetermined request types, and schedules the identified requests in an order that corresponds to the particular sequence.
In one illustrative embodiment, a data processing system is provided where the execution of two read requests followed by two write requests is faster than the execution of a read, a write, a read, and finally a write request. This may be caused by any number of reasons. In the illustrative embodiment, however, it is the transition from one request type to another that introduces a delay into the system. Often, requests of the same request type can be interleaved more efficiently than requests of different request types. Thus, for some systems, including an illustrative embodiment, it may be more efficient to execute a number of requests of a first request type followed by a number of requests of another request type.
Preferably, each of the requests issued by the data processing system are stored in a queue. A selected number of first requests of the first request type are then identified by examining the requests stored in the queue. The identified first requests are then scheduled for execution and subsequently executed. Preferably, the identified first requests are scheduled and executed regardless of whether additional requests are provided to the queue after scheduling and/or execution is initiated. After the first requests are scheduled and/or executed, a selected number of second requests of the second request type are identified by examining the requests stored in the queue. The identified second requests are then scheduled for execution and executed.
It is contemplated that the execution of the first requests may be initiated before or after the selected number of second requests are completely scheduled and/or executed. Likewise, the execution of the selected number of second requests may be initiated before or after the selected number of first requests are completely scheduled and/or executed. In one illustrative embodiment, the number of first requests of the first request type may be continually scheduled and executed until all but “n” of the first requests that are stored in the queue are executed (where “n” is greater than or equal to zero). Likewise, the number of second requests of the second request type may be continuously scheduled and executed until all but “m” of the second requests stored in the queue are executed (where “m” is greater than or equal to zero). This may maximize the number of requests of each type that are executed in succession, and thus, minimize the number of transitions that occur between request types. It is recognized, that to maintain data coherency in some systems, it may also be desirable to ensure that all requests of a particular request type are executed in first-in-time sequence relative to all other requests of the same request type.
It is contemplated that the illustrative data processing system may include a memory with a number of memory locations, a first processor for issuing the number of requests to the memory, and a second processor coupled to the memory. In this configuration, the requests may include read-type requests and write-type requests. The read-type requests preferably submit an address to the memory, and in return, receive a re

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for scheduling requests within a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for scheduling requests within a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for scheduling requests within a data... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2598160

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.