Browse Prior Art Database

Method for a partially queued scheduling algorithm for out-of-order processors

IP.com Disclosure Number: IPCOM000008307D
Publication Date: 2002-Jun-04
Document File: 5 page(s) / 61K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a partially queued scheduling algorithm for out-of-order processors. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 38% of the total text.

Method for a partially queued scheduling algorithm for out-of-order processors

Disclosed is a method for a partially queued scheduling algorithm for out-of-order processors. Benefits include improved functionality and improved performance.

Background

              Some computer microprocessors reorder instructions prior to sending them to the execution units. This approach is taken to improve the utilization of hardware resources. Issue logic determines the next instruction to be processed. It can be any of the waiting instructions as long as all the required data is available. This procedure makes use of fully associative buffers. These  buffers and schedulers consume a high amount of power and usually contain several timing speed paths, which constitute one of the most important architectural speed limits.

              Several academic works prove that the issue buffer, especially the wake up logic, constitutes one of the bigger obstacles for building a fast, low complexity, and low power microprocessor. Based on the idea of putting chains of dependent instructions in first in, first

out (FIFO) queues, a schedule mechanism handles only the instructions at the top of the queue. Other instructions are not available to the selection logic. This approach is acceptable because, by construction, at least one of the instruction sources is not ready.

              This design works well when the dependency graph of instructions is comprised of large chains of instructions that depend on one source. If an instruction depends on more than one source and the extra source must still be generated when the instruction gets to the top of the queue, the algorithm can stall or cause a non-optimal result. Therefore, many queues must be built, complicating the design and having a big effect on die size and power consumption.

General description

              The disclosed method is an improvement to the queue scheduling design. It uses associative reservation stations similar to those implemented in conventional microprocessors in combination with in-order queues. The top queue entries are also reservation station entries. The design schedules exclusively from the extended reservation stations. At dispatch time, the allocator decides if the instruction is inserted directly in the associative reservation stations or queued into one of the processor FIFO queues, based on dependency information provided by the renamer.

              The design combines a small associative buffer with issue queues that contain data dependent instructions that are scheduled serially. The power consumed and the timing limitations are relieved, supporting the design of higher performance machines in a predetermined power envelope.


Advantages

              The disclosed method provides advantages, including:

·        Improved functionality of a microprocessor’s out-of-order issue queue and the combination of a fully associative design with a queue-based scheduler

·        Reduced power consumption, cycle time, or die size of the target processor

Detailed description

              The disclosed...