Multi-thread processor and its hardware thread scheduling method

• US 8,365,179 B2
• Filed: 09/28/2009
• Issued: 01/29/2013
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Renesas Electronics Corporation
• Inventors: Adachi, Koji, Oomoto, Teppei
• Primary Examiner(s): Truong, Camquy
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US12/585,879
• Publication Number:
  US 20100083267A1
• Time in Patent Office: 1,219 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/507 Low-level
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A multi-thread processor in accordance with an exemplary aspect of the present invention includes a plurality of hardware threads each of which generates an independent instruction flow, a first thread scheduler that outputs a first thread selection signal designating a hardware thread to be executed in the next execution cycle, a first selector that outputs an instruction generated by the selected hardware thread according to the first thread selection signal, and an execution pipeline that executes an instruction output from the first selector, wherein whenever a hardware thread is executed in the execution pipeline, the first thread scheduler updates the priority rank of the executed hardware thread and outputs the first thread selection signal in accordance with the updated priority rank.

Claims

1. A multi-thread processor comprising:

a plurality of hardware threads each of which generates an independent instruction flow;

a first thread scheduler that outputs a first thread selection signal, the first thread selection signal designating a hardware thread to be executed in a next execution cycle among the plurality of hardware threads according to a priority rank, the priority rank being established in advance for each of the plurality of hardware threads;

a first selector that selects one of the plurality of hardware threads according to the first thread selection signal and outputs an instruction generated by the selected hardware thread;

an execution pipeline that executes an instruction output from the first selector,

wherein whenever the hardware thread is executed in the execution pipeline, the first scheduler updates the priority rank for the executed hardware thread and outputs the first thread selection signal in accordance with the updated priority rank;

a second scheduler that specifies execution of at least one hardware thread selected in a fixed manner among the plurality of hardware threads in a predetermined first execution period, and outputs a second thread selection signal specifying execution of an arbitrary hardware thread in a second execution period other than the first execution period and a real-time bit signal indicating one of the first execution period and the second execution period; and

a second selector that receives the real-time bit signal, and when the real-time bit signal indicates the first execution period, provides the second thread selection signal to the first selector, and when the real-time bit signal indicates the second execution period, provides the first thread selection signal to the first selector.

2. A multi-thread processor comprising:

a plurality of hardware threads each of which generates an independent instruction flow;

a first thread scheduler that outputs a first thread selection signal, the first thread selection signal designating a hardware thread to be executed in a next execution cycle among the plurality of hardware threads according to a priority rank, the priority rank being established in advance for each of the plurality of hardware threads;

a first selector that selects one of the plurality of hardware threads according to the first thread selection signal and outputs an instruction generated by the selected hardware thread;

an execution pipeline that executes an instruction output from the first selector,

wherein whenever the hardware thread is executed in the execution pipeline, the first scheduler updates the priority rank for the executed hardware thread and outputs the first thread selection signal in accordance with the updated priority rank,

wherein the first thread scheduler comprises;

a plurality of dispatch counters each of which retains a dispatch count value corresponding to a priority rank for the corresponding hardware thread;

a priority rank decision unit that refers dispatch count values retained in the plurality of dispatch counters and determines the hardware thread having a highest priority rank; and

a thread number selection unit that outputs the first thread selection signal designating the hardware thread determined to have the highest priority rank in the priority rank decision unit,

wherein the plurality of dispatch counters receive a dispatch signal, and when the dispatch signal indicates a hardware thread corresponding to one of the dispatch counters, update the dispatch count value output from that dispatch counter, the dispatch signal being output whenever the hardware thread is executed in the execution pipeline and used to notify of the executed hardware thread, and

wherein each of the plurality of dispatch counters comprises;

a counter initialization value storage unit that stores a counter initialization value corresponding to a priority rank of the corresponding hardware thread;

a count value storage unit that stores the count initialization value as a initial value of a count value;

a decrementer that receives the dispatch signal and updates the count value stored in the count value storage unit; and

a third selector that receives a mask signal, selects one of the counter value and a mask value corresponding to the count value having a minimum priority rank according to the mask signal, and outputs the selected value as the dispatch count value, the mask signal being output from a pipeline control circuit for the hardware thread containing an instruction having a high dependency relation, the pipeline control circuit being configured to monitor a dependency relation between the instruction being executed in the execution pipeline and the instruction prepared in the plurality of hardware threads.

3. A multi-thread processor comprising:

a plurality of hardware threads each of which generates an independent instruction flow;

a first thread scheduler that outputs a first thread selection signal, the first thread selection signal designating a hardware thread to be executed in a next execution cycle among the plurality of hardware threads according to a priority rank, the priority rank being established in advance for each of the plurality of hardware threads;

a first selector that selects one of the plurality of hardware threads according to the first thread selection signal and outputs an instruction generated by the selected hardware thread;

an execution pipeline that executes an instruction output from the first selector,

wherein whenever the hardware thread is executed in the execution pipeline, the first scheduler updates the priority rank for the executed hardware thread and outputs the first thread selection signal in accordance with the updated priority rank; and

a second thread scheduler that specifies execution of at least one hardware thread selected in a fixed manner among the plurality of hardware threads in a predetermined first execution period, and outputs a second thread selection signal specifying execution of an arbitrary hardware thread in a second execution period other than the first execution period and a real-time bit signal indicating one of the first execution period and the second execution period, to provide between the first thread selection signal and the second thread selection signal to the first selector according to the real-time bit signal.

4. A multi-thread processor comprising:

a plurality of hardware threads each of which generates an independent instruction flow;

a first thread scheduler that outputs a first thread selection signal, the first thread selection signal designating a hardware thread to be executed in a next execution cycle among the plurality of hardware threads according to a priority rank, the priority rank being established in advance for each of the plurality of hardware threads;

a first selector that selects one of the plurality of hardware threads according to the first thread selection signal and outputs an instruction generated by the selected hardware thread; and

an execution pipeline that executes an instruction output from the first selector,

wherein whenever the hardware thread is executed in the execution pipeline, the first scheduler updates the priority rank for the executed hardware thread and outputs the first thread selection signal in accordance with the updated priority rank,

wherein the first thread scheduler comprises a plurality of dispatch counters each of which retains a dispatch count value corresponding to a priority rank for the corresponding hardware thread, and

wherein each of the plurality of dispatch counters comprises;

a counter initialization value storage unit that stores a counter initialization value corresponding to a priority rank of the corresponding hardware thread;

a count value storage unit that stores the count initialization value as an initial value of a count value;

a decrementer that receives a dispatch signal and updates the count value stored in the count value storage unit; and

a third selector that receives a mask signal, selects one of a counter value and a mask value corresponding to the count value having a minimum priority rank according to the mask signal, and outputs the selected value as the dispatch count value, the mask signal being output from a pipeline control circuit for the hardware thread containing an instruction having a high dependency relation, the pipeline control circuit being configured to monitor a dependency relation between the instruction being executed in the execution pipeline and the instruction prepared in the plurality of hardware threads.

5. A hardware thread scheduling method in a multi-thread processor, the multi-thread processor comprising a plurality of hardware threads and being configured to execute an instruction flow generated by the hardware thread while switching the hardware thread in accordance with a predefined schedule, the hardware thread scheduling method comprising:

selecting a hardware thread having a highest priority rank among the plurality of hardware threads;

executing an instruction generated by the selected hardware thread;

updating the priority rank of the hardware thread that generated the executed instruction; and

selecting the hardware thread having a highest priority rank among the updated priority ranks as the hardware thread that generates an instruction next;

retaining a dispatch count value corresponding to a priority rank for the corresponding hardware thread;

storing a counter initialization value corresponding to a priority rank of the corresponding hardware thread;

storing the count initialization value as an initial value of a count value;

receiving a dispatch signal and updating the count value stored;

receiving a mask signal to select one of a counter value and a mask value corresponding to the count value having a minimum priority rank according to the mask signal; and

outputting the selected value as the dispatch count value, the mask signal being output from a pipeline control circuit for the hardware thread containing an instruction having a high dependency relation, the pipeline control circuit being configured to monitor a dependency relation between the instruction being executed in the execution pipeline and the instruction prepared in the plurality of hardware threads.