Compaq Computer Corporation, Inc.

Digital Equipment Corporation

George Z Chrysos

Jeffrey Adgate Dean

Carl Alan Waldspurger

William Edward Weihl

James E Hicks, Jr

Joel S Emer

Edward J McLellan

Daniel Lawrence Leibholz

Robert H Halstead, Jr

Henry M Levy

Susan Jane Eggers

Wilson P Snyder, Ii

Dean Tullsen

Trggve Fossum

Rebecca Stamm

John H Edmondson

Robert A Eustace

Bruce E Edwards

A method is provided for scheduling execution of a plurality of threads executed in a multithreaded processor. Resource utilizations of each of the plurality of threads are measured while the plurality of threads are concurrently executing in the multithreaded processor. Each of the plurality of threads is scheduled according to the measured resource utilizations using a thread scheduler.

Method for scheduling threads in a multithreaded processor

A multi-threaded processor comprising a pipeline including a number of stages processing instructions belonging to a plurality of threads. A buffer stores instructions from different ones of the threads. Count logic stores count information relating to each of the threads to indicate the number of instructions in each of the corresponding threads that have a particular attribute. A selection logic circuit has an output coupled to the buffer to determine which instruction is to be read from the buffer based on the count information stored by the count logic. The count information may, for example, provide information relating to a likelihood that one or more instructions belonging to each of the threads will be cancelled; relating to a count of unresolved branch instructions; or relating to a count of outstanding data cache misses. In operation, a thread may be selected for execution based on a selected attribute to enhance processing performance.

Pipelined multi-thread processor selecting thread instruction in inter-stage buffer based on count information

A method for sampling the performance of a computer system is provided. The computer system includes a plurality of functional units. The method selects transactions to be processed by a particular functional unit of the computer system. State information is stored while the selected transactions are processed by the functional unit. The state information is analyzed to guide optimization.

Apparatus and method for monitoring a computer system to guide optimization

A method of limiting, in a digital processor, low-priority utilization of a resource in favor of high-priority utilization of the resource comprises determining a value predictive of high-priority utilization of the resource. Low-priority utilization of the resource is inhibited if the determined predictive value is greater than a threshold. On the other hand, if the predictive value is less than or equal to the threshold, then low-priority utilization of the resource is allowed. In a preferred embodiment, the predictive value is derived by counting the number of actual high-priority utilizations of the resource out of the last N opportunities in which the resource could have been utilized for a high-priority need. Preferably, recent utilizations are given more weight than others. In a preferred embodiment, the resource comprises one of main memory, instruction cache memory, or data cache memory. High-priority utilization comprises high-priority access to memory and low-priority utilization comprises memory prefetching. Low priority utilizations are throttled when the threshold is exceeded. Counting and comparing are done with a shift register, counting logic, and a comparator; or with a counter and a comparator; or with two shift registers in which case no comparator is needed.

Dynamically inhibiting competing resource requesters in favor of above threshold usage requester to reduce response delay

Dynamically disabling speculative prefetch when high priority demand fetch opportunity use is high

An apparatus is provided for sampling instructions in a processor pipeline of a computer system. The pipeline has a plurality of processing stages. Instructions are fetched into a first stage of the pipeline. A subset of the fetched instructions are identified as selected instructions. Event, latency, and state information of the system is sampled while any of the selected instructions are in any stage of the pipeline. Software is informed whenever any of the selected instructions leaves the pipeline to read the event and latency information.

Apparatus for sampling instruction execution information in a processor pipeline

An apparatus is provided for determining an average number of instructions entering a stage of a processor pipeline of a computer system during a clock cycle of a processor clock. The number of instructions entering a particular stage of the pipeline are stored in a queue during each of a predetermined number (N) of clock cycles. The total number of instructions processed over the last P clock cycles is computed, where P is less than or equal to N. The total number of instructions processed is divided by the last P processor cycles to yield the instantaneous average number of instructions processed for each processor cycle. This average number of instructions processed is communicated to software.

Apparatus for determining the instantaneous average number of instructions processed

An apparatus is provided for sampling multiple concurretly executing instructions in a processor pipeline of a system. The pipeline has a plurality of processing stages. The apparatus identifies multiple selected when the instructions are fetched into a first stage of the pipeline. A subset of the the multiple selected instructions to execute concurrently in the pipeline. State information of the system is sampled while any of the multiple selected instructions are in any stage of the pipeline. Software is informed whenever all of the selected instructions leave the pipeline so that the software can read any of the state information.

Method and apparatus for sampling multiple potentially concurrent

An apparatus is provided for collecting state information associated with an execution path of recently processed instructions in a processor pipeline of a computer system. The apparatus identifies a class of instructions to be sampled. Path-identifying state information of a currently processed instruction is sampled when the currently processed instruction belongs to the identified class of instructions. A shift register stores a predetermined number of entries storing selected state information, the shift register is simultaneously sampled along with additional state information about the instruction being executed at the time of sampling.

Apparatus for sampling path history in a processor pipeline

A method of scheduling program instructions for execution in a computer processor comprises fetching and holding instructions from an instruction memory and executing the fetched instructions out of program order. When load/store order violations are detected, the effects of the load operation and its dependent instructions are erased and they are re-executed. The load is associated with all stores on whose data the load depends. This collection of stores is called a store set. On a subsequent issuance of the load, its execution is delayed until any store in the load's store set has issued. Two loads may share a store set, and separate store sets are merged when a load from one store set is found to depend on a store from another store set. A preferred embodiment employs two tables. The first is a store set ID table (SSIT) which is indexed by part of, or a hash of, an instruction PC. Entries in the SSIT provide a store set ID which is used to index into the second table, which for each store set, contains a pointer to the last fetched, unexecuted store instruction.

Method and apparatus for predicting memory dependence using store sets

A technique is provided for selecting a preferred thread from a plurality of threads executing within a simultaneous multithreaded, out-of-order execution computer system, the preferred thread possessing those instructions which, while in flight within the pipeline of the computer system provide, in contrast to those instructions belonging to other threads, a more beneficial performance of the central processing unit of the computer system. To determine the preferred thread, a technique is provided to evaluate attributes of each thread which indicate whether the thread includes a number of instructions which are likely to be cancelled while in flight or whether a thread includes instructions which will remain in the instruction queue for a number of cycles, unable to execute, thus stalling the execution of the thread to which the instruction belongs.

Thread properties attribute vector based thread selection in

An apparatus is provided for sampling instructions in a processor pipeline of a system. The pipeline has a plurality of processing stages. The apparatus includes a fetch unit for fetching instructions into a first stage of the pipeline. Certain randomly selected instructions are identified, and state information of the system is sampled while a particular selected instruction is in any stage of the pipeline. Software is informed when the particular selected instruction leaves the pipeline so that the software can read any of the sampled state information.

Apparatus for randomly sampling instructions in a processor pipeline

An apparatus is provided for sampling values of operands of instructions in a processor pipeline of a system, the pipeline having a plurality of processing stages. Instructions are fetched into a first stage of the pipeline. Any one of the fetched instructions are identified as a particular selected instruction. Values of results computed during the processing of the particular selected instruction are recorded in a sampling record along with state information identifying the particular selected instruction. Software is informed whenever the particular selected instruction leaves the pipeline to read the recorded values and state information.

Apparatus for sampling instruction operand or result values in a

A method is provided for estimating statistics of properties of instructions processed in a pipeline of a computer system, the pipeline having a plurality of processing stages. Instructions are fetched into a first stage of the pipeline. Some of the fetched instructions are randomly selected. State information of the system is recorded in a profile record as samples while the selected instruction are processed by the pipeline. The recorded state information is communiucated to software. The software statistically analyzes the recorded state information from a subset of the selected instructions to estimate the statistics of the instructions.

Growing community of inventors

Marlborough, MA, United States of America

George Z Chrysos