{"id":206,"date":"2018-07-18T12:21:02","date_gmt":"2018-07-18T12:21:02","guid":{"rendered":"http:\/\/csp2.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=206"},"modified":"2018-08-03T09:56:12","modified_gmt":"2018-08-03T09:56:12","slug":"advanced-concepts-of-ilp-dynamic-scheduling","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/chapter\/advanced-concepts-of-ilp-dynamic-scheduling\/","title":{"rendered":"Advanced Concepts of ILP \u2013 Dynamic scheduling"},"content":{"raw":"
\r\n\r\n \r\n

The objectives of this module are to discuss about the advanced concepts used for exploiting ILP and to discuss the concepts of dynamic scheduling in particular.<\/p>\r\n \r\n

All processors since about 1985 have used pipelining to overlap the execution of instructions and improve the performance of the processor. This overlap among instructions is called Instruction Level Parallelism<\/em> since the instructions can be evaluated in parallel. There are two largely separable techniques to exploit ILP:<\/p>\r\n \r\n

\u2022 Dynamic and depend on the hardware to locate parallelism<\/p>\r\n \r\n

\u2022 Static and rely much more on software<\/p>\r\n \r\n

Static techniques are adopted by the compiler to improve performance. Processors that predominantly use hardware approaches use other techniques on top of these optimizations to improve performance. The dynamic, hardware-intensive approaches dominate processors like the PIII, P4, and even the latest processors like i3, i5 and i7.<\/p>\r\n \r\n\r\nWe know that,\r\n\r\n \r\n\r\nPipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control hazard stalls\r\n\r\n \r\n\r\nThe ideal pipeline CPI<\/em> is a measure of the maximum performance attainable by the implementation.\r\n\r\n \r\n

When we look at performing optimizations, and if we only consider the basic block, then, both the compiler as well as the hardware does not have too many options. A basic block is a straight-line code sequence with no branches in, except to the entry, and no branches out, except at the exit. With the average dynamic branch frequency of 15% to 25%, we normally have only 4 to 7 instructions executing between a pair of branches. Additionally, the instructions in the basic block are likely to depend on each other. So, the basic block does not offer too much scope for exploiting ILP. In order to obtain substantial performance enhancements, we must exploit ILP across multiple basic blocks. The simplest method to exploit parallelism is to explore loop-level parallelism, to exploit parallelism among iterations of a loop. Vector architectures are one way of handling loop level parallelism. Otherwise, we will have to look at either dynamic or static methods of exploiting loop level parallelism. One of the common methods is loop unrolling, dynamically via dynamic branch prediction by the hardware, or statically via by the compiler using static branch prediction.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

While performing such optimizations, both the hardware as well as the software must preserve program order. That is, the order in which instructions would execute if executed sequentially, one at a time, as determined by the original source program, should be maintained. The data flow, the actual flow of data values among instructions that produce results and those that consume them, should be maintained. Also, instructions involved in a name dependence can execute simultaneously only if the name used in the instructions is changed so that these instructions do not conflict. This is done by the concept of register renaming. This resolves name dependences for registers. This can again be done by the compiler or by hardware. Preserving exception behavior, i.e., any changes in instruction execution order must not change how exceptions are raised in program, should also be considered.<\/p>\r\n \r\n

So far, we have assumed static scheduling with in-order-execution and looked at handling all the issues discussed above using various techniques. In this module, we will discuss about the need for doing dynamic scheduling and how we execute instructions out-of-order.<\/p>\r\n \r\n

Dynamic Scheduling is a technique in which the hardware rearranges the instruction execution to reduce the stalls, while maintaining data flow and exception behavior. The advantages of dynamic scheduling are:<\/p>\r\n \r\n\r\n\u2022 It handles cases when dependences are unknown at compile time\r\n\r\n \r\n\r\n\u2013\u00a0\u00a0 (e.g., because they may involve a memory reference)\r\n\r\n \r\n\r\n\u2022 It simplifies the compiler\r\n\r\n \r\n\r\n\u2022 It allows code compiled for one pipeline to run efficiently on a different pipeline\r\n\r\n \r\n\r\n\u2022 Hardware speculation, a technique with significant performance advantages, builds on dynamic scheduling\r\n\r\n \r\n

In a dynamically scheduled pipeline, all instructions pass through the issue stage in order; however they can be stalled or bypass each other in the second stage and thus enter execution out of order. Instructions will also finish out-of-order.<\/p>\r\n \r\n

Score boarding <\/em>is a dynamic scheduling technique for allowing instructions to execute out of order when there are sufficient resources and no data dependences. But this technique has some drawbacks. The Tomasulo\u2019s algorithm is a more sophisticated technique that has several major enhancements over Score boarding. We will discuss the Tomasulo\u2019s technique here.<\/p>\r\n \r\n

The key idea is to allow instructions that have operands available to execute, even if the earlier instructions have not yet executed. For example, consider the following sequence of instructions:<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nDIV.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F0 , F2 , F4\r\n\r\n \r\n\r\nADD.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F10 , F0 , F8\r\n\r\n \r\n\r\nSUB.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F12 , F8 , F14\r\n\r\n \r\n

The DIV instruction is a long latency instruction and ADD is dependent on it. So, ADD cannot be executed without DIV finishing. But, SUB has all the operands available, and can be executed earlier than ADD. We are basically enabling out-of-order execution, which will lead to out-of-order completion. With floating point instructions, even with in-order execution, we might have out-of-order completion because of the differing latencies among instructions. Now, with out-of-order execution, we will definitely have out-of-order completion. We should also make sure that no hazards happen in the pipeline because of dynamic scheduling.<\/p>\r\n \r\n

In order to allow instructions to execute out-of-order, we need to do some changes to the decode stage. So far, we have assumed that during the decode stage, the MIPS pipeline decodes the instruction and also reads the operands from the register file. Now, with dynamic scheduling, we bring in a change to enable out-of-order execution. The decode stage or the issue stage only decodes the instructions and checks for structural hazards. After that, the instructions will wait until there are no data hazards, and then read operands. This will enable us to do an in order issue, out of order execution and out of order completion. For example, in our earlier example, DIV, ADD and SUB will be issued in-order. But, ADD will stall after issue because of the true data dependency, but SUB will proceed to execution.<\/p>\r\n \r\n\r\nThere are some disadvantages with dynamic scheduling. They are:\r\n\r\n \r\n\r\n\u2022 Substantial increase in hardware complexity\r\n\r\n \r\n\r\n\u2022 Complicates exception handling\r\n\r\n \r\n

\u2022 Out-of-order execution and out-of-order completion will create the possibility for WAR and WAW hazards. WAR hazards did not occur earlier.<\/p>\r\n \r\n

The entire book keeping is done in hardware. The hardware considers a set of instructions called the instruction window and tries to reschedule the execution of these instructions according to the availability of operands. The hardware maintains the status of each instruction and decides when each of the instructions will move from one stage\u00a0to another. The dynamic scheduler introduces register renaming in hardware and eliminates WAW and WAR hazards. The following example shows how register renaming can be done. There is a name dependence with F6.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\u2022 Example:\r\n\r\n \r\n\r\nDIV.DF0,F2,F4\r\n\r\n \r\n\r\nADD.DF6,F0,F8\r\n\r\n \r\n\r\nS.DF6,0(R1)\r\n\r\n \r\n\r\nSUB.DF8,F10,F14\r\n\r\n \r\n\r\nMUL.D\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 F6,F10,F8\r\n\r\n \r\n\r\nWith renaming done as shown below, only RAW hazards remain, which can be strictly ordered.\r\n\r\n \r\n\r\n\u2022 Example:\r\n\r\n \r\n\r\nDIV.DF0,F2,F4\r\n\r\n \r\n\r\nADD.DS,F0,F8\r\n\r\n \r\n\r\nS.DS,0(R1)\r\n\r\n \r\n\r\nSUB.D\u00a0 \u00a0T,F10,F14\r\n\r\n \r\n\r\nMUL.D\u00a0 \u00a0 \u00a0 F6,F10,T\r\n\r\n \r\n

In the Tomasulo\u2019s approach, the register renaming is provided by reservation stations (RSs). Associated with every functional unit, we have a few reservation stations. When an instruction is issued, a reservation station is allocated to it. The reservation station stores information about the instruction and buffers the operand values (when available). So, the reservation station fetches and buffers an operand as soon as it becomes available (not necessarily involving register file). This helps in avoiding WAR hazards. If an operand is not available, it stores information about the instruction that supplies the operand. The renaming is done through the mapping between the registers and the reservation stations. When a functional unit finishes its operation, the result is broadcast on a result bus, called the common data bus (CDB). This value is written to the appropriate register and also the reservation station waiting for that data. When two instructions are to modify the same register, only the last output updates the register file, thus handling WAW hazards. Thus, the register specifiers are renamed with the reservation stations, which may be more than the registers. For load\u00a0and store operations, we use load and store buffers, which contain data and addresses, and act like reservation stations.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nThe three steps in a dynamic scheduler are listed below:\r\n\r\n \r\n\r\n\u2022 Issue\r\n\r\n \r\n\r\n\u2022 Get next instruction from FIFO queue\r\n\r\n \r\n\r\n\u2022 If available RS, issue the instruction to the RS with operand values if available\r\n\r\n \r\n\r\n\u2022 If a RS is not available, it becomes a structural hazard and the instruction stalls\r\n\r\n \r\n\r\n\u2022 If an earlier instruction is not issued, then subsequent instructions cannot be issued\r\n\r\n \r\n\r\n\u2022 If operand values not available, stall the instruction\r\n\r\n \r\n\r\n\u2022 Execute\r\n\r\n \r\n\r\n\u2022 When operand becomes available, store it in any reservation station waiting for it\r\n\r\n \r\n\r\n\u2022 When all operands are ready, issue the instruction for execution\r\n\r\n \r\n\r\n\u2022 Loads and store are maintained in program order through the effective address\r\n\r\n \r\n

\u2022 No instruction allowed to initiate execution until all branches that proceed it in program order have completed<\/p>\r\n \r\n\r\n\u2022 Write result\r\n\r\n \r\n\r\n\u2022 Write result on CDB into reservation stations and store buffers\r\n\r\n \r\n\r\n\u2022 Stores must wait until address and value are received\r\n\r\n \r\n

The dynamic scheduler maintains three data structures - the reservation station, a register result data structure that keeps of the instruction that will modify a register and an instruction status data structure. The third one is more for understanding purposes. The reservation station components are as shown below:<\/p>\r\n \r\n\r\nName \u2014Identifying the reservation station\r\n\r\n \r\n\r\nOp\u2014Operation to perform in the unit (e.g., + or \u2013)\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0Vj, Vk\u2014Value of Source operands\r\n\r\n \r\n\r\n\u2013\u00a0 Store buffers have V field, result to be stored\r\n\r\n \r\n\r\nQj, Qk\u2014Reservation stations producing source registers (value to be written)\r\n\r\n \r\n\r\n\u2013 Store buffers only have Qi for RS producing result Busy\u2014Indicates reservation station or FU is busy\r\n\r\n \r\n

Register result status\u2014Indicates which functional unit will write each register, if one exists. It is blank when there are no pending instructions that will write that register. The instruction status gives the status of each instruction in the instruction window. All the three data structures are shown in Figure 16.1.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Figure 16.2 shows the organization of the Tomasulo\u2019s dynamic scheduler. Instructions are taken from the instruction queue and issued. During the issue stage, the instruction is decoded and allocated an RS entry. The RS station also buffers the operands if available. Otherwise, the RS entry marks the pending RS value in the Q field. The results are passed through the CDB and go to the appropriate register, as dictated by the register result data structure, as well as the pending RSs.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

Dependences with respect to memory locations will also have to be handled properly. A load and a store can safely be done out of order, provided they access different addresses. If a load and a store access the same address, then either<\/p>\r\n\r\n

    \r\n \t
  • the load is before the store in program order and interchanging them results in a WAR hazard, or<\/li>\r\n \t
  • the store is before the load in program order and interchanging them results in a RAW hazard.<\/li>\r\n<\/ul>\r\n \r\n

    Similarly, interchanging two stores to the same address results in a WAW hazard. Hence, to determine if a load can be executed at a given time, the processor can check whether any uncompleted store that precedes the load in program order shares the same data memory address as the load. Similarly, a store must wait until there are no unexecuted loads or stores that are earlier in program order and share the same data memory address.<\/p>\r\n \r\n

    To summarize, we have discussed the importance of dynamic scheduling, wherein the hardware does a dynamic reorganization of code at run time. We have discussed the Tomasulo\u2019s dynamic scheduling approach. The book keeping done and the various steps used have been elaborated.<\/p>\r\n \r\n\r\nWeb Links \/ Supporting Materials<\/strong>\r\n

      \r\n \t
    • Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\r\n \t
    • Computer\u00a0 Architecture\u00a0 -\u00a0 A\u00a0 Quantitative\u00a0 Approach\u00a0 ,\u00a0\u00a0\u00a0 John\u00a0 L.\u00a0 Hennessy\u00a0 and\u00a0 David\u00a0 A. Patterson, 5th Edition, Morgan Kaufmann, Elsevier, 2011.<\/li>\r\n<\/ul>\r\n<\/div>","rendered":"
      \n

       <\/p>\n

      The objectives of this module are to discuss about the advanced concepts used for exploiting ILP and to discuss the concepts of dynamic scheduling in particular.<\/p>\n

       <\/p>\n

      All processors since about 1985 have used pipelining to overlap the execution of instructions and improve the performance of the processor. This overlap among instructions is called Instruction Level Parallelism<\/em> since the instructions can be evaluated in parallel. There are two largely separable techniques to exploit ILP:<\/p>\n

       <\/p>\n

      \u2022 Dynamic and depend on the hardware to locate parallelism<\/p>\n

       <\/p>\n

      \u2022 Static and rely much more on software<\/p>\n

       <\/p>\n

      Static techniques are adopted by the compiler to improve performance. Processors that predominantly use hardware approaches use other techniques on top of these optimizations to improve performance. The dynamic, hardware-intensive approaches dominate processors like the PIII, P4, and even the latest processors like i3, i5 and i7.<\/p>\n

       <\/p>\n

      We know that,<\/p>\n

       <\/p>\n

      Pipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control hazard stalls<\/p>\n

       <\/p>\n

      The ideal pipeline CPI<\/em> is a measure of the maximum performance attainable by the implementation.<\/p>\n

       <\/p>\n

      When we look at performing optimizations, and if we only consider the basic block, then, both the compiler as well as the hardware does not have too many options. A basic block is a straight-line code sequence with no branches in, except to the entry, and no branches out, except at the exit. With the average dynamic branch frequency of 15% to 25%, we normally have only 4 to 7 instructions executing between a pair of branches. Additionally, the instructions in the basic block are likely to depend on each other. So, the basic block does not offer too much scope for exploiting ILP. In order to obtain substantial performance enhancements, we must exploit ILP across multiple basic blocks. The simplest method to exploit parallelism is to explore loop-level parallelism, to exploit parallelism among iterations of a loop. Vector architectures are one way of handling loop level parallelism. Otherwise, we will have to look at either dynamic or static methods of exploiting loop level parallelism. One of the common methods is loop unrolling, dynamically via dynamic branch prediction by the hardware, or statically via by the compiler using static branch prediction.<\/p>\n<\/div>\n

      \n

       <\/p>\n

      While performing such optimizations, both the hardware as well as the software must preserve program order. That is, the order in which instructions would execute if executed sequentially, one at a time, as determined by the original source program, should be maintained. The data flow, the actual flow of data values among instructions that produce results and those that consume them, should be maintained. Also, instructions involved in a name dependence can execute simultaneously only if the name used in the instructions is changed so that these instructions do not conflict. This is done by the concept of register renaming. This resolves name dependences for registers. This can again be done by the compiler or by hardware. Preserving exception behavior, i.e., any changes in instruction execution order must not change how exceptions are raised in program, should also be considered.<\/p>\n

       <\/p>\n

      So far, we have assumed static scheduling with in-order-execution and looked at handling all the issues discussed above using various techniques. In this module, we will discuss about the need for doing dynamic scheduling and how we execute instructions out-of-order.<\/p>\n

       <\/p>\n

      Dynamic Scheduling is a technique in which the hardware rearranges the instruction execution to reduce the stalls, while maintaining data flow and exception behavior. The advantages of dynamic scheduling are:<\/p>\n

       <\/p>\n

      \u2022 It handles cases when dependences are unknown at compile time<\/p>\n

       <\/p>\n

      \u2013\u00a0\u00a0 (e.g., because they may involve a memory reference)<\/p>\n

       <\/p>\n

      \u2022 It simplifies the compiler<\/p>\n

       <\/p>\n

      \u2022 It allows code compiled for one pipeline to run efficiently on a different pipeline<\/p>\n

       <\/p>\n

      \u2022 Hardware speculation, a technique with significant performance advantages, builds on dynamic scheduling<\/p>\n

       <\/p>\n

      In a dynamically scheduled pipeline, all instructions pass through the issue stage in order; however they can be stalled or bypass each other in the second stage and thus enter execution out of order. Instructions will also finish out-of-order.<\/p>\n

       <\/p>\n

      Score boarding <\/em>is a dynamic scheduling technique for allowing instructions to execute out of order when there are sufficient resources and no data dependences. But this technique has some drawbacks. The Tomasulo\u2019s algorithm is a more sophisticated technique that has several major enhancements over Score boarding. We will discuss the Tomasulo\u2019s technique here.<\/p>\n

       <\/p>\n

      The key idea is to allow instructions that have operands available to execute, even if the earlier instructions have not yet executed. For example, consider the following sequence of instructions:<\/span><\/p>\n<\/div>\n

      \n

       <\/p>\n

      DIV.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F0 , F2 , F4<\/p>\n

       <\/p>\n

      ADD.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F10 , F0 , F8<\/p>\n

       <\/p>\n

      SUB.D\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F12 , F8 , F14<\/p>\n

       <\/p>\n

      The DIV instruction is a long latency instruction and ADD is dependent on it. So, ADD cannot be executed without DIV finishing. But, SUB has all the operands available, and can be executed earlier than ADD. We are basically enabling out-of-order execution, which will lead to out-of-order completion. With floating point instructions, even with in-order execution, we might have out-of-order completion because of the differing latencies among instructions. Now, with out-of-order execution, we will definitely have out-of-order completion. We should also make sure that no hazards happen in the pipeline because of dynamic scheduling.<\/p>\n

       <\/p>\n

      In order to allow instructions to execute out-of-order, we need to do some changes to the decode stage. So far, we have assumed that during the decode stage, the MIPS pipeline decodes the instruction and also reads the operands from the register file. Now, with dynamic scheduling, we bring in a change to enable out-of-order execution. The decode stage or the issue stage only decodes the instructions and checks for structural hazards. After that, the instructions will wait until there are no data hazards, and then read operands. This will enable us to do an in order issue, out of order execution and out of order completion. For example, in our earlier example, DIV, ADD and SUB will be issued in-order. But, ADD will stall after issue because of the true data dependency, but SUB will proceed to execution.<\/p>\n

       <\/p>\n

      There are some disadvantages with dynamic scheduling. They are:<\/p>\n

       <\/p>\n

      \u2022 Substantial increase in hardware complexity<\/p>\n

       <\/p>\n

      \u2022 Complicates exception handling<\/p>\n

       <\/p>\n

      \u2022 Out-of-order execution and out-of-order completion will create the possibility for WAR and WAW hazards. WAR hazards did not occur earlier.<\/p>\n

       <\/p>\n

      The entire book keeping is done in hardware. The hardware considers a set of instructions called the instruction window and tries to reschedule the execution of these instructions according to the availability of operands. The hardware maintains the status of each instruction and decides when each of the instructions will move from one stage\u00a0to another. The dynamic scheduler introduces register renaming in hardware and eliminates WAW and WAR hazards. The following example shows how register renaming can be done. There is a name dependence with F6.<\/span><\/p>\n<\/div>\n

      \n

       <\/p>\n

      \u2022 Example:<\/p>\n

       <\/p>\n

      DIV.DF0,F2,F4<\/p>\n

       <\/p>\n

      ADD.DF6,F0,F8<\/p>\n

       <\/p>\n

      S.DF6,0(R1)<\/p>\n

       <\/p>\n

      SUB.DF8,F10,F14<\/p>\n

       <\/p>\n

      MUL.D\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 F6,F10,F8<\/p>\n

       <\/p>\n

      With renaming done as shown below, only RAW hazards remain, which can be strictly ordered.<\/p>\n

       <\/p>\n

      \u2022 Example:<\/p>\n

       <\/p>\n

      DIV.DF0,F2,F4<\/p>\n

       <\/p>\n

      ADD.DS,F0,F8<\/p>\n

       <\/p>\n

      S.DS,0(R1)<\/p>\n

       <\/p>\n

      SUB.D\u00a0 \u00a0T,F10,F14<\/p>\n

       <\/p>\n

      MUL.D\u00a0 \u00a0 \u00a0 F6,F10,T<\/p>\n

       <\/p>\n

      In the Tomasulo\u2019s approach, the register renaming is provided by reservation stations (RSs). Associated with every functional unit, we have a few reservation stations. When an instruction is issued, a reservation station is allocated to it. The reservation station stores information about the instruction and buffers the operand values (when available). So, the reservation station fetches and buffers an operand as soon as it becomes available (not necessarily involving register file). This helps in avoiding WAR hazards. If an operand is not available, it stores information about the instruction that supplies the operand. The renaming is done through the mapping between the registers and the reservation stations. When a functional unit finishes its operation, the result is broadcast on a result bus, called the common data bus (CDB). This value is written to the appropriate register and also the reservation station waiting for that data. When two instructions are to modify the same register, only the last output updates the register file, thus handling WAW hazards. Thus, the register specifiers are renamed with the reservation stations, which may be more than the registers. For load\u00a0and store operations, we use load and store buffers, which contain data and addresses, and act like reservation stations.<\/span><\/p>\n<\/div>\n

      \n

       <\/p>\n

      The three steps in a dynamic scheduler are listed below:<\/p>\n

       <\/p>\n

      \u2022 Issue<\/p>\n

       <\/p>\n

      \u2022 Get next instruction from FIFO queue<\/p>\n

       <\/p>\n

      \u2022 If available RS, issue the instruction to the RS with operand values if available<\/p>\n

       <\/p>\n

      \u2022 If a RS is not available, it becomes a structural hazard and the instruction stalls<\/p>\n

       <\/p>\n

      \u2022 If an earlier instruction is not issued, then subsequent instructions cannot be issued<\/p>\n

       <\/p>\n

      \u2022 If operand values not available, stall the instruction<\/p>\n

       <\/p>\n

      \u2022 Execute<\/p>\n

       <\/p>\n

      \u2022 When operand becomes available, store it in any reservation station waiting for it<\/p>\n

       <\/p>\n

      \u2022 When all operands are ready, issue the instruction for execution<\/p>\n

       <\/p>\n

      \u2022 Loads and store are maintained in program order through the effective address<\/p>\n

       <\/p>\n

      \u2022 No instruction allowed to initiate execution until all branches that proceed it in program order have completed<\/p>\n

       <\/p>\n

      \u2022 Write result<\/p>\n

       <\/p>\n

      \u2022 Write result on CDB into reservation stations and store buffers<\/p>\n

       <\/p>\n

      \u2022 Stores must wait until address and value are received<\/p>\n

       <\/p>\n

      The dynamic scheduler maintains three data structures – the reservation station, a register result data structure that keeps of the instruction that will modify a register and an instruction status data structure. The third one is more for understanding purposes. The reservation station components are as shown below:<\/p>\n

       <\/p>\n

      Name \u2014Identifying the reservation station<\/p>\n

       <\/p>\n

      Op\u2014Operation to perform in the unit (e.g., + or \u2013)<\/p>\n<\/div>\n

      \n

      \u00a0 \u00a0Vj, Vk\u2014Value of Source operands<\/p>\n

       <\/p>\n

      \u2013\u00a0 Store buffers have V field, result to be stored<\/p>\n

       <\/p>\n

      Qj, Qk\u2014Reservation stations producing source registers (value to be written)<\/p>\n

       <\/p>\n

      \u2013 Store buffers only have Qi for RS producing result Busy\u2014Indicates reservation station or FU is busy<\/p>\n

       <\/p>\n

      Register result status\u2014Indicates which functional unit will write each register, if one exists. It is blank when there are no pending instructions that will write that register. The instruction status gives the status of each instruction in the instruction window. All the three data structures are shown in Figure 16.1.<\/p>\n

       <\/p>\n

      \"\"<\/p>\n

       <\/p>\n

      Figure 16.2 shows the organization of the Tomasulo\u2019s dynamic scheduler. Instructions are taken from the instruction queue and issued. During the issue stage, the instruction is decoded and allocated an RS entry. The RS station also buffers the operands if available. Otherwise, the RS entry marks the pending RS value in the Q field. The results are passed through the CDB and go to the appropriate register, as dictated by the register result data structure, as well as the pending RSs.<\/p>\n<\/div>\n

      \n

      \"\"<\/p>\n

       <\/p>\n

      Dependences with respect to memory locations will also have to be handled properly. A load and a store can safely be done out of order, provided they access different addresses. If a load and a store access the same address, then either<\/p>\n

        \n
      • the load is before the store in program order and interchanging them results in a WAR hazard, or<\/li>\n
      • the store is before the load in program order and interchanging them results in a RAW hazard.<\/li>\n<\/ul>\n

         <\/p>\n

        Similarly, interchanging two stores to the same address results in a WAW hazard. Hence, to determine if a load can be executed at a given time, the processor can check whether any uncompleted store that precedes the load in program order shares the same data memory address as the load. Similarly, a store must wait until there are no unexecuted loads or stores that are earlier in program order and share the same data memory address.<\/p>\n

         <\/p>\n

        To summarize, we have discussed the importance of dynamic scheduling, wherein the hardware does a dynamic reorganization of code at run time. We have discussed the Tomasulo\u2019s dynamic scheduling approach. The book keeping done and the various steps used have been elaborated.<\/p>\n

         <\/p>\n

        Web Links \/ Supporting Materials<\/strong><\/p>\n

          \n
        • Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\n
        • Computer\u00a0 Architecture\u00a0 –\u00a0 A\u00a0 Quantitative\u00a0 Approach\u00a0 ,\u00a0\u00a0\u00a0 John\u00a0 L.\u00a0 Hennessy\u00a0 and\u00a0 David\u00a0 A. Patterson, 5th Edition, Morgan Kaufmann, Elsevier, 2011.<\/li>\n<\/ul>\n<\/div>\n","protected":false},"author":2,"menu_order":16,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-a-p-shanthi"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-206","chapter","type-chapter","status-publish","hentry","contributor-dr-a-p-shanthi"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/206","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/users\/2"}],"version-history":[{"count":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/206\/revisions"}],"predecessor-version":[{"id":453,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/206\/revisions\/453"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/206\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/media?parent=206"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapter-type?post=206"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/contributor?post=206"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/license?post=206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}