Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-12-28
2002-12-24
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S151000, C710S309000, C710S310000
Reexamination Certificate
active
06499090
ABSTRACT:
BACKGROUND
The present invention relates to a scheduler for use in processor devices and other agents.
As is known, many modern computing systems employ a multi-agent architecture. A typical system is shown in FIG.
1
. There, a plurality of agents
110
-
160
communicates over an external bus
170
according to a predetermined bus protocol. “Agents” may include general-purpose processors
110
-
140
, memory controllers
150
, interface chipsets
160
, input output devices and/or other integrated circuits (not shown) that process data requests. The bus
170
may permit several external bus transactions to be in progress at once.
In multi-agent systems, the bandwidth of the external bus
170
can define a limit to system performance. Clock speeds within an agent typically are much faster than clock speeds of the external bus. A processor core (not shown) for example can issue many data requests (read requests and write requests) in the time that the external bus
170
can execute a single request. Further, an agent must share the external bus
170
with other agents. These factors can introduce unwanted latency to the processing of data requests within an agent.
Not all data requests are created equal. Currently, Intel Corporation, the assignee of the present invention, is designing an agent that will process core read requests, prefetch requests and write requests. Core read requests are requests for addressed data to be read to the agent's processing core (“core”). Typically, core read requests identify data for which the agent has an immediate need. Prefetch requests, by contrast, refer to data that is likely to be used by the core in the not-so-distant future. By prefetching the data into the agent prior to the time the core actually issues a read request for it, the data should be available to the core in an internal cache. The internal cache may operate at a faster clock rate than the external bus and, therefore, may satisfy the expected core request with reduced latency. Write requests typically identify data that is being returned by the agent to system storage. The data may be evicted because the agent is no longer using it and new data is being read to a memory location that the evicted data occupied. Other data requests may be associated with other priorities.
Given the bandwidth limitations of an external bus and the relative priorities observed with respect to the different data requests handled within an agent, the inventors determined that there is a need in the art for a bus control algorithm that schedules requests to be posted on the external bus according to a predetermined priority scheme.
SUMMARY
Embodiments of the present invention provide a scheduler that stores data to be scheduled. The scheduler may include an array identifying relative priorities among the queue entries according to a first priority scheme, and a priority register array identifying relative priorities among the queue entries according to a second priority scheme. A plurality of detectors may be coupled to the array and to the priority register array to determine which data is to be scheduled.
REFERENCES:
patent: 4956820 (1990-09-01), Hashimoto
patent: 5524220 (1996-06-01), Verma et al.
patent: 5537573 (1996-07-01), Ware et al.
patent: 5586294 (1996-12-01), Goodwin et al.
patent: 5701426 (1997-12-01), Ryan
patent: 5706482 (1998-01-01), Matsushima et al.
patent: 5740399 (1998-04-01), Mayfield et al.
patent: 5761452 (1998-06-01), Hooks et al.
patent: 5761706 (1998-06-01), Kessler et al.
patent: 5790813 (1998-08-01), Whittaker
patent: 6286083 (2001-09-01), Chin et al.
patent: 0 391 517 (1990-10-01), None
patent: WO94/08301 (1994-04-01), None
patent: WO96/41271 (1996-12-01), None
Palacharla et al, “Evaluating Stream Buffers as a Secondary Cache Replacement”, 1994, IEEE, pp. 24-33.
Jouppi et al, “Tradeoffs in Twi-Level On-Chip Caching”, 1994, IEEE, pp. 34-45.
Wakerly, John F., Digital Design Principles and Practices, Third Edition, Updated, 2001, Chapter 10, pp. 866-872, Prentice Hall, Upper Saddle River, New Jersey.
Bachand Derek T.
Hill David L
LandOfFree
Prioritized bus request scheduling mechanism for processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prioritized bus request scheduling mechanism for processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prioritized bus request scheduling mechanism for processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927092