CN102566974A - Instruction acquisition control method based on simultaneous multithreading - Google Patents

Abstract

The invention provides an instruction fetch control method based on simultaneous multithreading. In each clock cycle of the processor, the instruction fetching unit reads the PC value of the instruction according to the program counter, first selects two threads with higher priority as the instruction fetching thread, and then calculates the actual number of instructions required by each thread, Perform the operation of reading instructions; the dual-priority resource allocation mechanism calculates the system resources required by the thread in the fetching phase according to the two parameters of the thread IPC value and the Cache failure rate, and completes the dynamic allocation of resources; and the TBHBP branch predictor Cooperate with the fetching operation of the fetching component, by connecting the global historical information and local historical information read into the branch instruction Bi, as the index of the secondary pattern matching table PHT, to obtain the pattern matching bit Sc, and input the calculation result to Branch result output table BRT; when the branch instruction Bi is executed again, judge whether the CONF field is greater than or equal to 2 through the selector Selector, if so, directly output the recorded branch result, and finally put the fetched instruction into the instruction cache, Complete all operations of instruction fetch control.

Description

Instruction Fetching Control Method Based on Simultaneous Multithreading

technical field

The invention relates to an instruction fetch control method. Specifically, it is an instruction acquisition processing method based on simultaneous multithreading.

Background technique

With the development of computer architecture, in order to meet people's urgent needs for high-performance processors, multi-thread processors emerged as the times require, and have become the mainstream microprocessor structure. Various researches on simultaneous multi-threaded processors have become very active, and at the same time, the instruction fetch control method of multi-threaded processors has attracted much attention as a research hotspot in the field of high-performance processors.

In recent years, many experts, scholars and scientific research institutions at home and abroad have carried out active research and exploration on it. In terms of fetching strategies, Professor Tullsen of the University of Washington in the United States proposed the currently recognized fetching strategy ICOUNT with better performance. The ICOUNT policy grants higher priority to fast-running threads, effectively preventing a certain thread from blocking the instruction queue, maximizing the parallelism of instructions in the instruction queue, and it is also the best instruction fetch performance in traditional processors, but due to its The shortcomings of unbalanced instruction fetch bandwidth utilization and high instruction queue conflict rate greatly limit the full performance of simultaneous multi-threaded processors. In terms of branch predictors, the Gshare predictor proposed by McFarling, through the "XOR" processing of the high address and the historical low, makes the branch instructions that appear to be interfered be mapped to different prediction entries, effectively alleviating the inter-thread instructions. Mutual interference occurs, but it may introduce new branch alias interference into branch instructions that do not conflict originally, so the branch prediction performance needs to be improved.

Contents of the invention

The object of the present invention is to provide an instruction fetching control method based on simultaneous multi-threading that can improve the instruction throughput rate of the processor, uniformly utilize the instruction fetch bandwidth, reduce the instruction queue conflict rate and improve the branch prediction performance.

The purpose of the present invention is achieved like this:

Step 1: In each clock cycle of the processor, the fetching component reads the PC value of the instruction according to the program counter;

Step 2: Select two threads with the smallest counter values of the number of command queue items through the T selection 2 multiplexer to output, assuming that the priority of thread 1 is higher than that of thread 2;

Step 3: The count value of thread 1 first performs the operation of multiple expressions through the adder and multiplier, and then performs a bitwise inversion and modulo 16 operation on the result value, and passes the output value through the 2-to-1 selector and Compare the instruction fetch bandwidth and take the smaller value; except for the calculation of reading instructions, the execution process of thread 2 is the same as that of 1. For thread 2, the number of instructions read is the difference between thread 1's index fetch and instruction fetch bandwidth ;

Step 4: Send the output results of the two threads into the register of the instruction fetch unit to complete the division of the instruction fetch bandwidth;

Step 5: The dual-priority resource allocation mechanism calculates the system resources required by the thread in the instruction fetching phase according to the two parameters of the thread IPC value and the cache failure rate, and completes the dynamic allocation of resources.

Step 6: Determine whether there is a branch instruction; if so, index the branch prediction information table BPIT according to the PC value of the branch instruction Bi, and read the thread index number TID to which the branch instruction belongs; otherwise, send the read instruction into the instruction cache;

Step 7: Index the thread branch history register information table TBHRIT through the obtained TID number, read the branch history information BPHI predicted by the thread, as the global history information of the branch prediction; at the same time, index the branch target address history register information through the obtained instruction PC value Table BTAHRIT, reads the target address BPTA of the branch instruction, and reads the local history information used for branch prediction according to the instruction address;

Step 8: Combine the branch history information BHR of each thread and the history information BHT read according to the target address through a hash function as an index of the secondary pattern matching table PHT;

Step 9: Obtain the mode history bit Sc of the branch instruction through the concatenated historical information index PHT table, and use it for the actual branch prediction operation;

Step 10: Input the obtained mode history bit Sc into the prediction decision function to complete the calculation operation of the branch prediction result. At the same time, complete the update operation of the mode history bit through the state transition function δ. The updated mode history bit will be replaced by the original Ri , c-k Ri, c-k+1...Ri, c-1 becomes Ri, c-k+1Ri, c-k+2...Ri, c;

Step 11: Write the prediction result of the branch instruction Bi into the branch result output table BRT; when the same branch instruction is predicted next time, if the prediction result is the same as the value of PRED in the BRT table, add 1 to CONF; otherwise, CONF does minus 1 operation;

Step 12: through the update circuit of the TBHRIT table, the obtained branch output results Ri, c are left shifted into the last bit in the thread history register, and the predicted historical information is updated to the historical information submitted by the branch instruction;

Step 13: Through the update circuit of the BTAHRIT table, move the history information of the target address corresponding to the obtained branch output result Ri, c to the left into the last bit in the address history register, and update the predicted target address of the branch instruction to the branch instruction Physical address information at the time of submission;

Step 14: When the branch predictor performs branch prediction on the next branch instruction Bi+1, it first indexes the CONF field in the BRT table according to its PC value; if CONF is greater than or equal to 2, then the TAG field in the BPIT table is recorded as 1 , the branch prediction circuit will not perform the branch prediction operation on the instruction Bi+1, but directly output the stored branch result; on the contrary, if CONF is less than 2, the TAG field in the BPIT table will be recorded as 0, and the branch instruction will re-execute the branch prediction operation , and compare the prediction result with the data in the BRT table, and complete the update operation of the CONF field and the PRED field; finally, inform the fetching unit of the prediction result;

Step 15: If a branch misprediction phenomenon occurs during the whole process of branch prediction, the processor will start the misprediction processing mechanism to stop the remaining operations immediately, and cancel all instructions running in the pipeline belonging to the same thread after the mispredicted branch instruction , the PC value of the thread is adjusted to the correct target instruction address after the branch, and then restarts reading instruction execution from the new address; at the same time, adjusts the CONF field and PRED of the corresponding entry in the branch result output table BRT according to the actual execution result of the branch field for use when the branch instruction is executed again.

The present invention may also include:

1. Among the system resources required by the calculation thread in the instruction fetch phase, the system resources include: instruction fetch bandwidth, instruction queue length, reserved station queue length,

The specific method of resource allocation is as follows:

$\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}}{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Tj</span>}}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}$

Wherein, P _Ti and P _Tj respectively represent the resource allocation priorities of threads Ti and Tj, Ni represents the number of resources allocated to thread Ti, and R represents the total number of system resources;

In the case where the primary priority and secondary priority are different, the ratio of the IPC value of the thread to the secondary priority is used as the basis for resource allocation evaluation. The specific method of resource allocation is as follows:

$\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}}{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; TLj</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CL</span>}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}$

Among them, TLi and TLj represent the main priority of threads Ti and Tj respectively; CLi and CLj represent the sub-priority numbers of threads Ti and Tj respectively, and their values can be 1, 2, 3; Ni represents the number of resources allocated to thread Ti, R represents the total number of system resources.

BHR+BHT和BHT+BHR三种历史信息的连接方式进行分支预测性能的测试，确定两种历史信息最佳的连接方式；对于二级模式匹配表PHT的索引，采取线程历史信息和地址历史信息拼接的方式。2. In the process of combining the branch history information BHR of each thread and the history information BHT read according to the target address through a hash function as the indexing process of the secondary pattern matching table PHT, respectively

BHR+BHT and BHT+BHR are used to test the branch prediction performance of three historical information connection methods, and determine the best connection method of the two historical information; for the index of the secondary pattern matching table PHT, thread historical information and address historical information are used The way of splicing.

The present invention aims to design an instruction fetch control method FCMBSMT which combines an instruction fetch strategy and a branch predictor. The specific improvements are as follows: designing the IFSBSMT instruction fetch strategy to control the working sequence of the instruction fetch components and improve the instruction fetch efficiency of the processor. At the same time, the TBHBP branch predictor is designed to assist instruction fetching components to improve the availability and effectiveness of fetching instructions, and more effectively improve the processor's instruction throughput and branch prediction performance, which has good application prospects and application value.

The present invention mainly comprises following characteristics:

The entire implementation process of IFSBSMT fetching strategy includes three stages: thread selection, fetching bandwidth division and system resource allocation.

The so-called thread selection refers to how many threads are selected by the instruction fetching unit and which threads are fetched in each clock cycle. Here, the IFSBSMT strategy adopts the ICOUNT 2.8 thread selection method, that is, two threads are selected for instruction fetching in each clock cycle, and a maximum of eight instructions are read each time, which effectively avoids the fine division of the instruction fetch bandwidth and causes some threads to fail due to instruction cache Instruction fetching cannot be performed due to failure or other reasons.

The second stage of the IFSBSMT strategy is the division of the fetch bandwidth, which is also a key stage for the implementation of the entire strategy. At this stage, the fetching component calculates the number of instructions to be read in this period according to the flow rate of thread instructions and the number of instructions of the thread in the instruction queue. If there are enough instructions in the instruction queue to be executed, the instruction will not be read. Otherwise, a certain number of instructions will be read as required. The maximum number of read instructions is the initially set instruction fetch bandwidth, and the instruction fetch bandwidth is 8. The number of instructions executed by a thread in a certain clock cycle is about the square root of the number of instructions in the instruction queue of the thread, so the calculation formula for the required number of instructions should be formula (1).

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; fs</span>}}<span\; class="notranslate">\; -</span>\sqrt{{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

In the formula (1), I is the number of instructions that the thread needs to read in a certain clock cycle, Ifs is the instruction flow rate of the thread during the running process, and its value should be the product of the thread IPC and a certain coefficient, and I' is the thread The number of instructions in the instruction queue. Bring the command flow rate calculation method into formula (1) and rewrite it as formula (2).

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; IPC</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; -</span>\sqrt{{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

During the actual operation of the processor, due to the existence of factors such as cache failure and branch misprediction, the thread IPC value actually obtained by the system is often lower than the estimated value, so it needs to be multiplied by a coefficient P to correct this error, that is, the above Mentioned command flow rate calculation method.

In the case of system initialization, Cache failure, and branch misprediction, the instruction fetch unit does not read instructions, so the thread IPC value at this time is 0, and the instruction speed of the thread is correspondingly 0, which seriously affects For the execution speed of the thread, in order to avoid this phenomenon, the IPC of the thread is increased by 1, then the formula (2) will be rewritten as (3).

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; IPC</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; -</span>\sqrt{{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

In the specific hardware implementation process of the IFSBSMT strategy, the calculation of the thread IPC value not only requires additional hardware overhead, but also needs to correct the IPC value through thread pre-execution and sampling, which seriously affects the execution speed of instructions. Therefore, by inverting the parameter I bit by bit and moduloing the factor P to simplify the cumbersome thread IPC value calculation, the hardware overhead required by the IFSBSMT strategy is effectively reduced. See formula (4) for the new formula expression.

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\sqrt{{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}}\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

In formula (4), it is necessary to carry out the root number operation on the instruction number I′ of the thread in the instruction queue, and the complexity of its hardware implementation is too high. By using the second-order Taylor formula to process the root number, the formula (4 ) is rewritten as (5).

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

Although the result obtained by using the second-order Taylor formula to optimize formula (5) is an approximate value, it does not affect the correctness of instruction fetching, and compared with the actual number of fetched instructions, this error can be ignored.

In each clock cycle, the maximum number of instructions fetched by a certain thread should not exceed the preset instruction fetch bandwidth N. Therefore, the number of instructions to be read by a thread should be the smaller value of the calculation result of formula (5) and the instruction fetch bandwidth, and the optimal value of the parameter P should be 16, and the preset instruction fetch bandwidth is 8. Then, the formula for calculating the number of instructions fetched by the thread per cycle is shown in (6).

$\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; MIN</span>}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 16.8</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

In the second stage, only the division of instruction fetch bandwidth is designed. However, due to frequent occurrence of L2 Cache failure during thread instruction fetching, shared resources may be monopolized by a certain thread, which affects the smooth execution of other subsequent threads and limits SMT. (Simultaneous Multithreading) The improvement of the overall performance of the processor. Therefore, it is also necessary to reasonably allocate shared resources of threads to solve this problem.

The final stage of the IFSBSMT strategy is the allocation of system resources. The dual priority method of thread IPC and L2 Cache failure rate is used to dynamically allocate thread shared resources. The basic principle of its realization is: resource allocation set according to thread IPC value The priority is the main priority; the priority set according to the L2Cache failure rate is the secondary priority, and the secondary priority is divided into CLevel 1, CLeve2, and CLeve3 from high to low. The evaluation standard: the thread does not have L1 data Cache and L2 Cache invalidation is CLevel 1, thread L1 data Cache invalidation, L2 Cache not invalidation is CLevel 2, thread L2 Cache invalidation is CLevel 3. When the main priority is different and the secondary priority is the same, the main priority will be used as the basis for resource allocation, and threads with higher main priority have higher resource allocation rights. In the case of the same main priority and different sub-priorities, the sub-priority will be used as the basis for resource allocation, and threads with higher sub-priority have higher resource allocation rights. The specific formula of resource allocation is shown in (7).

$\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}}{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Tj</span>}}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

In formula (7), PTi and PTj represent the resource allocation priorities of threads Ti and Tj respectively, Ni represents the number of resources allocated to thread Ti, and R represents the total number of system resources.

In the case where the primary priority and secondary priority are not the same, the ratio of the thread's IPC value to the number of secondary priorities will be used as the basis for resource allocation evaluation. The specific formula of resource allocation is shown in (8).

$\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}}{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; TLj</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CL</span>}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

In formula (8), TLi and TLj represent the main priority of threads Ti and Tj respectively, CLi and CLj represent the secondary priorities of threads Ti and Tj respectively, and their values can be 1, 2, 3, and Ni represents the Ti resource number, R represents the total number of system resources.

The TBHBP branch predictor is based on a two-level adaptive branch predictor. Threads use independent branch history registers and address history registers. For the pattern matching table, thread sharing is adopted, and the branch result output table is used to check the result of the branch instruction. to store. Its specific hardware structure is shown in Figure 1.

As shown in Figure 1, the TBHBP branch predictor mainly includes six parts: branch prediction information table BPIT (Branch Predict Information Table), thread branch history register information table TBHRIT (Thread Branch History Register Information Table), branch target address history register information table BTAHRIT (Branch Target Address HistoryRegister Information Table), pattern matching table PHT (Pattern History Table), branch result output table BRT (Branch Result Table), and the logic update circuit of the other three tables except the branch prediction information table and PHT table.

The branch prediction information table BPIT is indexed according to the PC value of the branch instruction. Each thread corresponds to a set of independent entries. Each entry contains 4 fields: the TID field is the index number of the thread, which is used to index TBHRIT table; the PC field is used for the index of the BTAHRIT table; the TAG field is used to compare with the PC value of the branch result table to determine whether the branch instruction needs to perform branch prediction; the CONF field is used as the threshold of the branch prediction to determine whether to apply the BRT table The branch prediction results in . When a certain branch instruction of the thread enters the pipeline, the branch prediction circuit uses its PC value to index a certain entry of the BPIT table.

The thread branch history register information table TBHRIT is indexed through the TID field in the BPIT table. Each thread corresponds to a set of independent entries, and each entry contains 3 fields: the TID field is the index number of the thread; PC The field is used to index the branch instruction; the BPHI field is the predicted branch history information, which is used for splicing the branch history information bits, and is updated when the branch instruction is submitted. When a certain instruction of the thread enters the decoding stage of the pipeline, the branch prediction circuit uses its PC value to index a certain entry of the TBHRIT table.

The branch target address history register information table BTAHRIT is indexed through the PC field in the BPIT table. Each thread corresponds to a set of independent entries, and each entry contains 3 fields: the TID field is the index number of the thread; The PC field is used to index the branch instruction; the BPTA field is the target address information of the branch instruction, which is used to read the local branch history information of the target address of each branch instruction, and then complete the splicing of the branch history information bits, and in the branch instruction Update when submitted. When a branch instruction of a thread enters the decoding stage of the pipeline, the branch prediction circuit uses its PC value to index a certain entry of the BTAHRIT table.

The pattern matching table PHT is indexed through the comprehensive branch history of the thread. The comprehensive historical information is spliced from the thread branch historical information recorded in the TBHRIT table and the local branch historical information read according to the branch instruction target address in the BTAHRIT table. The application of the PHT table adopts the method of multi-thread sharing.

The branch result output table BRT is indexed through the PC field in the BPIT table. Each thread corresponds to a set of independent entries, and each entry contains 4 fields: the TID field is the index number of the thread; the PC field is used for For the index of the branch instruction; PRED is used to store the prediction result of the branch instruction; CONF is used as the threshold of the branch prediction. When a certain branch instruction of the thread enters the write-back stage of the pipeline, the branch result update circuit uses its PC value to index all entries of the BRT table to complete its update operation. At the same time, the relevant update circuit will also be applied to the TBHRIT table and the BTAHRIT table to complete the update operation of the entries.

The present invention has unique advantages in the fetching control of the processor. The IFSBSMT fetching strategy and the TBHBP branch predictor are effectively combined through the fetching unit, which not only enables it to give full play to its own technical advantages, but also makes the two seamless Seam fusion further improves the superiority of the FCMBSMT method.

In the process of fetching instructions of the processor, the IFSBSMT strategy controls the operation of reading instructions of the fetching parts through three implementation stages of thread selection, fetching bandwidth division and dynamic resource allocation, so as to make the utilization of the fetching bandwidth of the processor more efficient. For balance, the average length of the command queue occupied by threads is significantly reduced, and the conflict rate of the command queue is close to 0, which greatly improves the command throughput rate of the processor. But the fly in the ointment is that the branch prediction performance of the processor shows an obvious downward trend because the number of index fetches in each clock cycle of the SMT processor is significantly higher than that of the traditional processor.

The implementation of the TBHBP branch predictor effectively solves this problem. By combining the global history information and local history information of threads into comprehensive history information, which is used as the index of the pattern matching table PHT, it effectively reduces the obsolescence and confusion of branch information in SMT processing. problem arises. At the same time, the mode that threads independently share branch prediction resources greatly reduces the probability of branch alias conflicts and capacity conflicts under the SMT processor, and improves the correctness of branch execution. Compared with traditional branch predictors, the newly added branch prediction result output table BRT, a hardware structure, improves the predicted execution speed of branch instructions by recording the prediction results of commonly used branch instructions, avoids the phenomenon of branch instruction queue accumulation, and promotes The smooth execution of subsequent instructions.

While the two independently exert their own technical advantages, they also complement each other with functions so that their respective performances can be fully utilized. The accuracy prediction of the TBHBP predictor enables the normal execution of branch instructions in the pipeline, effectively alleviates the impact of branch instructions on instruction fetch operations, and promotes the further improvement of IFSBSMT strategy in instruction fetch performance. At the same time, the IFSBSMT strategy reduces the number of index fetches of high-priority threads through reasonable use of the fetch bandwidth, so that the number of branch instructions read is relatively reduced, which reduces the branch prediction pressure of the TBHBP predictor and improves the prediction accuracy of the branch predictor. and accuracy.

The invention has the advantages of effectively overcoming the disadvantages of insufficient optimization of the instruction fetching strategy and low branch prediction performance existing in the traditional method. Multiple instance analysis and performance test results show that compared with the traditional ICG method, the FCMBSMT instruction fetching control method increases the instruction throughput by 59.3%, reduces the average length of the instruction queue by 17.33%, and leads to branch misprediction rate and misprediction path fetching. The rate drops by 2.16% and 3.28% respectively, which greatly promotes the improvement of processor instruction throughput and branch prediction performance, and has good application prospects and research value.

Description of drawings

Fig. 1 is a hardware structural diagram of the TBHBP branch predictor of the present invention.

Fig. 2 is a hardware structural diagram of the FCMBSMT fetching control method of the present invention.

Fig. 3 is the realization flowchart of the FCMBSMT fetching control method of the present invention.

Fig. 4 is a comparison chart of processor IPC performance test of the present invention.

FIG. 5 is a comparison chart of the single-thread IPC performance test of the present invention.

Fig. 6 is a comparison chart of the performance test of the average length of the instruction queue in the present invention.

Fig. 7 is a comparison chart of branch misprediction rate performance test of the present invention.

Fig. 8 is a comparison chart of performance test of branch misprediction path instruction fetch rate in the present invention.

Detailed ways

The present invention is described in more detail below in conjunction with accompanying drawing example:

The entire implementation process of the FCMBSMT instruction fetching control method is divided into two stages: reading instructions, branch prediction of instructions, and the execution order of the two is not sequential, and the simultaneous multi-threaded processor is completed through the interaction of the two. Fetch operation. The specific implementation process of the FCMBSMT based on simultaneous multi-threaded instruction fetching control invented in conjunction with Fig. 2 and Fig. 3 is as follows:

Step 1: In each clock cycle of the processor, the fetching unit reads the PC value of the instruction according to the program counter.

Step 2: Select the two threads with the smallest counter values of the number of items in the instruction queue through the T selection 2 multiplexer for output, assuming that the priority of thread 1 is higher than that of thread 2 .

Step 3: The count value of thread 1 first performs the operation of multiple expressions through the adder and multiplier, and then performs a bitwise inversion and modulo 16 operation on the result value, and passes the output value through the 2-to-1 selector and Fetch the bandwidth for comparison and choose the smaller value.

Step 4: Except for the calculation of the read instruction, the execution process of thread 2 is the same as that of 1. For thread 2, the number of read instructions should be the difference between thread 1's index fetch and instruction fetch bandwidth.

Step 5: Send the output results of the two threads into the registers of the instruction fetch unit to complete the division of the instruction fetch bandwidth.

Step 6: The dual-priority resource allocation mechanism calculates the system resources required by the thread in the instruction fetching phase through formulas (7) and (8) according to the two parameters of thread IPC value and cache failure rate, such as: fetching bandwidth, Command queue length, reserved station queue length, etc., to complete the dynamic allocation of resources.

Step 7: Determine whether there is a branch instruction. If yes, index the branch prediction information table BPIT according to the PC value of the branch instruction Bi, and read the index number TID of the thread to which the branch instruction belongs. Otherwise, the read instruction is sent to the instruction cache.

Step 8: Index the thread branch history register information table TBHRIT through the obtained TID number, read the branch history information BPHI predicted by the thread, and use it as the global history information of the branch prediction. At the same time, index the branch target address history register information table BTAHRIT through the obtained instruction PC value, read the target address BPTA of the branch instruction, and read the local history information for branch prediction according to the instruction address.

Step 9: combine the branch history information BHR of each thread and the history information BHT read according to the target address through a hash function, and use it as an index of the secondary pattern matching table PHT. Here, respectively for BHR+BHT and BHT+BHR are three connection methods of historical information to test the branch prediction performance to determine the best connection method of the two kinds of historical information. The experiment runs three sets of two-thread workload programs, art-perlbmk, craft-mcf, and bip2-lucas, to analyze the branch misprediction rate and branch misprediction path index fetch rate under different connection modes. The specific analysis results are shown in Table 1.

Table 1 Comparison table of branch prediction performance of different historical information connection methods

From the analysis in Table 1, it can be seen that BHR+BHT has certain advantages in branch prediction performance compared to the other two connection methods of historical information. Therefore, for the index of the secondary pattern matching table PHT, the stitching method of thread history information and address history information is adopted.

Step 10: Obtain the mode history bit Sc of the branch instruction through the concatenated historical information index PHT table, which is used for the actual branch prediction operation.

Step 11: Input the obtained pattern history bit Sc into the prediction decision function to complete the calculation operation of the branch prediction result. At the same time, the update operation of the mode history bits is completed through the state transition function δ, and the updated mode history bits will have the original Ri, c-k Ri, c-k+1...Ri, c-1 become Ri , c-k+1Ri, c-k+2...Ri, c.

Step 12: Write the prediction result of the branch instruction Bi into the branch result output table BRT. When the same branch instruction is predicted next time, if the prediction result is the same as the PRED value in the BRT table, then CONF will be incremented by 1; otherwise, CONF will be decremented by 1.

Step 13: Through the update circuit of the TBHRIT table, shift the obtained branch output results Ri, c to the left to the last bit in the thread history register, and update the predicted history information to the history information submitted by the branch instruction.

Step 14: Through the update circuit of the BTAHRIT table, move the history information of the target address corresponding to the obtained branch output result Ri, c to the left into the last bit in the address history register, and update the predicted target address of the branch instruction to the branch instruction Physical address information at the time of submission.

Step fifteen: When the branch predictor performs branch prediction on the next branch instruction Bi+1, it first indexes the CONF field in the BRT table according to its PC value. If CONF is greater than or equal to 2, the TAG field in the BPIT table is recorded as 1, and the branch prediction circuit will not perform branch prediction operation on instruction Bi+1, but directly output the stored branch result. Conversely, if CONF is less than 2, the TAG field in the BPIT table is recorded as 0, and the branch instruction will re-execute the branch prediction operation according to the above eight steps, and compare the prediction result with the data in the BRT table to complete the CONF field and the update operation of the PRED field. Finally, the prediction result is notified to the fetching unit so that it can correctly complete the fetching operation.

Step 16: If a branch misprediction phenomenon occurs during the whole process of branch prediction, the processor will start the misprediction processing mechanism to stop the remaining operations immediately, and cancel all the programs running in the pipeline belonging to the same thread after the mispredicted branch instruction. Instructions, the PC value of the thread is adjusted to the correct target instruction address after the branch, and then the instruction execution is restarted from the new address. At the same time, the CONF field and the PRED field of the corresponding entry in the branch result output table BRT are adjusted according to the actual execution result of the branch, so as to be used when the branch instruction is executed again.

Taking the SPEC 2000 benchmark test program as an example to illustrate the process of FCMBSMT method fetch control, this experiment also needs to set the performance test benchmark program parameters, simultaneous multi-thread simulator, performance reference object and performance parameter indicators. The specific parameter configuration is as follows:

(1) Set the performance test benchmark program parameters. The experiment will select 7 fixed-point programs and 5 floating-point programs from the SPEC 2000 test set, and randomly combine them into 6 dual-thread load sets for performance evaluation. At the same time, because it takes a lot of time to complete the simulation test program in the experiment, sometimes it is even impossible to complete, so the number of running instructions for different test programs is also specifically configured. The specific test program parameters and the configuration of the number of operating instructions are shown in Table 2, and the unit of the number of operating instructions is one billion.

Table 2 FCMBSMT method performance test benchmark program parameter configuration table

(2) Simultaneous multithreading simulator. The experiment uses the SMISIM simulator developed by Dean.M.Tullsen et al. in the Western Laboratory for experimental research. The SMISIM simulator is developed based on the SPIM simulator written by James Lames. It can run 8 threads at the same time, and each thread can run up to 300M instructions. At the same time, the SMTSIM simulator also supports the operation of the Alpha executable program, and the running speed is the fastest among the current SMT simulators. The basic configuration of simulator parameters is shown in Table 3.

Table 3 Basic configuration table of SMTSIM simulator parameters

(3) Performance reference object. The performance reference will use the ICG method which combines the ICOUNT2.8 with the best index fetching performance and the Gshare branch predictor for performance comparison. Through the performance comparison with the high-performance instruction fetch control method, it can better show the performance of the FCMBSMT method in fetching instructions. Performance superiority and usability.

(4) Performance parameter index. According to the characteristics of the SMT processor architecture and the implementation principle of the FCMBSMT method, considering the influence of various factors, the evaluation parameters used in the performance test experiment include: processor IPC, instruction queue length and queue conflict rate, branch misprediction rate and misprediction rate. Prediction path fetch rate.

The IPC value of a processor refers to the number of instructions the processor executes in each clock cycle, and is an important performance indicator for measuring the instruction throughput and speedup ratio of the processor.

The instruction queue length refers to the sum of the lengths of the fixed-point queue, floating-point queue and memory access queue occupied by the benchmark test program. The instruction queue conflict rate refers to the arithmetic average of the fixed-point queue conflict rate, floating-point queue conflict rate and memory access queue conflict rate occupied by the benchmark test program.

The branch misprediction rate refers to the ratio of the number of mispredicted branch instructions to the total number of branch instructions. The instruction fetch rate of the mispredicted path refers to the ratio of the number of instructions read by the mispredicted path to the total number of read instructions.

At the same time, in order to make the test environment closer to the actual program running state, the experiment adopts the random combination of 12 workload programs, and finally forms 6 composite test programs for performance testing. The specific performance test results are shown in Figure 4.

From the analysis of Figure 4, it can be seen that compared with the traditional ICG instruction fetch control method, the instruction throughput rate of the processor is greatly improved under the FCMBSMT method. Under the condition of two-thread load running, the processor's IPC performance reaches 2.95, while under the ICG method, the processor's IPC performance is only 1.89, and the average weighted speedup ratio of the workload program performance is about 26.1%, which is an improvement compared to the single Both the IFSBSMT strategy and the TBHBP predictor are improved. The improvement of the processor instruction throughput is achieved under the joint promotion of the IFSBSMT strategy and the TBHBP predictor. The IFSBSMT strategy greatly improves the instruction throughput of the processor by rationally utilizing the instruction fetch bandwidth and dynamically allocating the system resources required for thread execution. Rate. At the same time, the high-precision TBHBP branch predictor improves the quality and efficiency of instruction fetching by reducing the alias conflicts and capacity conflicts of branch instructions, thereby promoting the improvement of instruction throughput performance.

Both the IFSBSMT strategy and the TBHBP branch predictor have a certain fairness in fetching instructions during the implementation process, so the FCMBSMT fetching control method combined with the two will also have the same advantages, that is, in improving the overall instruction throughput performance of the processor. At the same time, the single-threaded instruction throughput performance should be improved. The following will test the IPC performance of 12 single-threaded workloads among the 6 two-threaded workloads in the previous experiment. The specific performance test results are shown in Figure 5.

From the analysis in Figure 5, it can be seen that compared with the ICG method, the instruction throughput rates of the 12 workload programs under the FCMBSMT method all show different degrees of increase. The statistics of the performance test results show that the average IPC value of a single thread under the FCMBSMT method is 1.45, while that of the ICG method is only 0.91, and the average weighted speedup ratio is about 29.3%. It can be seen that the FCMBSMT instruction fetch control method fully inherits the advantages of the IFSBSMT strategy and the fairness of the TBHBP predictor, and compared with the two, the single-threaded instruction throughput performance has a more obvious improvement.

The IFSBSMT fetching strategy reduces the index fetching of high-priority threads by reasonably dividing the fetching bandwidth, thereby effectively reducing the average length of the instruction queue occupied by threads and greatly improving the utilization of system resources. By increasing the branch result output table BRT, the TBHBP branch predictor effectively avoids the accumulation of branch instructions in the instruction queue, speeds up the predicted execution speed of branch instructions, promotes the smooth execution of subsequent instructions, and effectively reduces the number of threads. Occupancy of system resources such as instruction queues. Under the common impetus of the two factors, the average length of the instruction queue under the FCMBSMT method should be reduced. The specific test results are shown in Figure 6.

From the statistical analysis of the test result data in Figure 6, it can be seen that, except for the applu-sixtrack program load, the length of the instruction queue occupied by other program loads is all reduced. This is mainly due to the increase in the number of available instructions read by the applu-sixtrack program load. The length of the instruction queue it occupies has increased, but it is ultimately reflected in the improvement of workload IPC performance. Overall, the average occupied instruction queue length of the program load under the ICG method is 36.83, while that of the FCMBSMT method is only 19.50, and the average decrease is about 47.05%.

The improvement of the accuracy of the TBHBP branch predictor effectively improves the branch prediction hit rate of the FCMBSMT instruction fetching control method, thereby reducing the branch misprediction rate of the processor. The specific performance test results are shown in Figure 7.

From the analysis in Figure 7, it can be seen that except for the bzip2-lucas and applu-sixtrack program loads due to their own reasons, the branch misprediction rates of other program loads show a downward trend. Overall, the branch misprediction rate under the ICG method is 6.03%, while the branch misprediction rate under the FCMBSMT method is only 3.87%, with an average drop of nearly 2.16 percentage points.

It can be seen that the improvement of the branch prediction performance of the processor by the FCMBSMT method is very significant.

At the same time, the reduction of the branch misprediction rate effectively reduces the index fetching of the instruction fetching unit on the misprediction path, and the index fetching rate of the processor on the misprediction path also decreases accordingly. The specific performance test results are shown in Figure 8.

From the analysis in Figure 8, it can be seen that the branch misprediction path index fetch rate and the branch prediction misprediction rate are basically consistent, that is, except for the bzip2-lucas and applu-sixtrack program load due to its own reasons, the branch misprediction rate of other program loads The index fetch rate of the rate path has decreased. Overall, the branch misprediction path index retrieval rate under the ICG method is 10.64%, while the branch misprediction path index retrieval rate under the FCMBSMT method is only 7.42%, with an average drop of nearly 3.28 percentage points. The reduction of the branch misprediction rate and the misprediction path instruction fetch rate effectively improves the branch prediction performance of the processor, and promotes the improvement of the processor instruction throughput performance.

The above are the preferred embodiments of the present invention, and any changes made according to the technical solution of the present invention, and the resulting functional effects do not exceed the scope of the solution of the present invention, all belong to the protection scope of the present invention.

Claims (3)

1. A method for fetching instructions based on simultaneous multithreading, characterized in that: Step 1: In each clock cycle of the processor, the fetching component reads the PC value of the instruction according to the program counter; Step 2: Select two threads with the smallest counter values of the number of command queue items through the T selection 2 multiplexer to output, assuming that the priority of thread 1 is higher than that of thread 2; Step 3: The count value of thread 1 first performs the operation of multiple expressions through the adder and multiplier, and then performs a bitwise inversion and modulo 16 operation on the result value, and passes the output value through the 2-to-1 selector and Compare the instruction fetch bandwidth and take the smaller value; except for the calculation of reading instructions, the execution process of thread 2 is the same as that of 1. For thread 2, the number of instructions read is the difference between thread 1's index fetch and instruction fetch bandwidth ; Step 4: Send the output results of the two threads into the register of the instruction fetch unit to complete the division of the instruction fetch bandwidth; Step 5: The dual-priority resource allocation mechanism calculates the system resources required by the thread in the instruction fetching phase according to the two parameters of the thread IPC value and the cache failure rate, and completes the dynamic allocation of resources. Step 6: Determine whether there is a branch instruction; if so, index the branch prediction information table BPIT according to the PC value of the branch instruction Bi, and read the thread index number TID to which the branch instruction belongs; otherwise, send the read instruction into the instruction cache; Step 7: Index the thread branch history register information table TBHRIT through the obtained TID number, read the branch history information BPHI predicted by the thread, as the global history information of the branch prediction; at the same time, index the branch target address history register information through the obtained instruction PC value Table BTAHRIT, reads the target address BPTA of the branch instruction, and reads the local history information used for branch prediction according to the instruction address; Step 8: Combine the branch history information BHR of each thread and the history information BHT read according to the target address through a hash function as an index of the secondary pattern matching table PHT; Step 9: Obtain the mode history bit Sc of the branch instruction through the concatenated historical information index PHT table, and use it for the actual branch prediction operation; Step 10: Input the obtained mode history bit Sc into the prediction decision function to complete the calculation operation of the branch prediction result. At the same time, complete the update operation of the mode history bit through the state transition function δ. The updated mode history bit will be replaced by the original Ri , c-k Ri, c-k+1...Ri, c-1 becomes Ri, c-k+1Ri, c-k+2...Ri, c; Step 11: Write the prediction result of the branch instruction Bi into the branch result output table BRT; when the same branch instruction is predicted next time, if the prediction result is the same as the value of PRED in the BRT table, add 1 to CONF; otherwise, CONF does minus 1 operation; Step 12: through the update circuit of the TBHRIT table, the obtained branch output results Ri, c are left shifted into the last bit in the thread history register, and the predicted historical information is updated to the historical information submitted by the branch instruction; Step 13: Through the update circuit of the BTAHRIT table, move the history information of the target address corresponding to the obtained branch output result Ri, c to the left into the last bit in the address history register, and update the predicted target address of the branch instruction to the branch instruction Physical address information at the time of submission; Step 14: When the branch predictor performs branch prediction on the next branch instruction Bi+1, it first indexes the CONF field in the BRT table according to its PC value; if CONF is greater than or equal to 2, then the TAG field in the BPIT table is recorded as 1 , the branch prediction circuit will not perform the branch prediction operation on the instruction Bi+1, but directly output the stored branch result; on the contrary, if CONF is less than 2, the TAG field in the BPIT table will be recorded as 0, and the branch instruction will re-execute the branch prediction operation , and compare the prediction result with the data in the BRT table, and complete the update operation of the CONF field and the PRED field; finally, inform the fetching unit of the prediction result; Step 15: If a branch misprediction phenomenon occurs during the whole process of branch prediction, the processor will start the misprediction processing mechanism to stop the remaining operations immediately, and cancel all instructions running in the pipeline belonging to the same thread after the mispredicted branch instruction , the PC value of the thread is adjusted to the correct target instruction address after the branch, and then restarts reading instruction execution from the new address; at the same time, adjusts the CONF field and PRED of the corresponding entry in the branch result output table BRT according to the actual execution result of the branch field for use when the branch instruction is executed again. 2. The instruction fetching control method based on simultaneous multithreading according to claim 1, characterized in that: among the system resources required by the computing thread in the fetching stage, the system resources include: fetching bandwidth, instruction queue length, reserved station queue length, The specific method of resource allocation is as follows: $\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}}{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Ti</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; Tj</span>}}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}$ Wherein, P _Ti and P _Tj respectively represent the resource allocation priorities of threads Ti and Tj, Ni represents the number of resources allocated to thread Ti, and R represents the total number of system resources; In the case where the primary priority and secondary priority are different, the ratio of the IPC value of the thread to the secondary priority is used as the basis for resource allocation evaluation. The specific method of resource allocation is as follows: $\mathrm{<span\; class="notranslate">\; Ni</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}}{\mathrm{<span\; class="notranslate">\; TL</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CLi</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; TLj</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; CL</span>}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; R</span>}$ Among them, TLi and TLj represent the main priority of threads Ti and Tj respectively; CLi and CLj represent the sub-priority numbers of threads Ti and Tj respectively, and their values can be 1, 2, 3; Ni represents the number of resources allocated to thread Ti, R represents the total number of system resources. 3. The instruction fetching control method based on simultaneous multithreading according to claim 1 or 2, characterized in that: the branch history information BHR of each thread is combined with the history information BHT read according to the target address through a hash function Together, as the indexing process of the secondary pattern matching table PHT, respectively

BHR+BHT and BHT+BHR are used to test the branch prediction performance of three historical information connection methods, and determine the best connection method of the two historical information; for the index of the secondary pattern matching table PHT, thread historical information and address historical information are used The way of splicing.

Images