CS232 Section 5: Single-cycle datapaths and Pipelining October 2Single-cycle datapathsTo better understand datapaths, we’ll add a few new instructions.1. Consider a new load instruction lwd $rd, $rs, $rt that sets $rd = Mem[$rs + $rt]. In thedatapath shown below, show that only the control signals need to be modified to support thisoperation. Recall that bits 31–26 of an R-type instruction form the opcode, bits 25–21 form the rsregister, bits 20–16 form the rt register and bits 15–11 form the rd register.2. Add the jr instruction to the single-cycle datapath shown below. This is an R-type instruction,and the new PC value should be the value in register rs.1CS232 Section 5: Single-cycle datapaths and Pipelining October 2PipeliningA sandwich assembly process has 4 stages: ORD (order sandwich), TOS (toast sandwich, optional), ADD(add extras) and PAY. The table b elow indicates how long each stage takes:Stage Time (sec)ORD 8TOS 0 or 10ADD upto 10PAY 5One-at-a-time Deli: The average time to perform the ADD stage is 6 seconds, and 30% of the customerschoose to have their sandwich toasted. At any time, only one sandwich is being assembled. How longwill it take to assemble N sandwiches?Pipelined Deli: The pipelining approach is to work on multiple sandwiches at once, but at any onetime only one sandwich is in a particular stage of assembly. To make pipelining work properly:• each sandwich goes through every stage (the TOS stage is “idle” for untoasted sandwiches)• every stage takes the same amount of time (faster stages are idle for the extra time)1. How long does the first sandwich take to assemble?2. If the first sandwich gets completed at time t seconds, at what time will the next sandwich getcompleted? Assume that a new order is placed as soon as it can.3. What is the total time to assemble N sandwiches?4. “With four stages, the pipelined deli should be 4 times faster.” Why is this reasoning wrong?5. Which deli would be interested in buying a faster toaster?6. The shorter the time between placing the order and getting the sandwich, the happier the customerfeels. The more customers served per day, the happier the deli owner feels. Which kind of deliwould customers prefer? How about deli owners?2CS232 Section 5: Single-cycle datapaths and Pipelining October 2SolutionsSingle-cycle datapath1. No new hardware needs to be added – only the control needs to be modified. Set the control s ignalsas for an add instruction except set the MemRead control signal and set MemToReg = 1.2. Expand the PcSrc mux to take a third input (thus, it becomes a two-bit control signal). The thirdinput will b e from the Read data 1 line – see the diagram:PipeliningOne-at-a-time: On average, it takes 8 + 0.3 × 10 + 6 + 5 = 22 seconds to assemble a sandwich. Thus,N sandwiches take 22N seconds.Pipelined:1. The maximum time for a particular stage is 10 seconds. Hence, each stage must take 10 seconds.Since there are 4 stages and each sandwich goes through every stage, the first sandwich takes 40seconds to assemble.2. By the time the first sandwich has completed all 4 stages at time t, the next sandwich has completed3 stages (it has just completed its ADD stage). Thus, the next sandwich requires just 10 moreseconds to complete:t t + 10ORD TOS ADD PAYORD TOS ADD PAY3. After the first sandwich, each additional sandwich takes 10 more seconds to complete. Thus, thetotal time for N sandwiches is 40 + 10(N − 1) seconds.4. The reasoning doesn’t take into account the fact that stages have unequal length (this forces fasterstages to idle), and that the pip e line takes time to fill and drain (i.e. the pipeline isn’t always full).5. In the Pipelined deli, the time for each stage is determined by the slowest stage. The (original)TOS stage is a slowest stage (10 seconds), but the ADD stage can also take 10 seconds in the worstcase. Thus, even if the TOS stage could be made faster, the Pipelined deli would be forced tokeep every stage at 10 seconds. So, it would not benefit from a faster toaster. In contrast, theOne-at-a-time deli would benefit from a faster toaster: every second faster would cut the averagetime to assemble a sandwich by 0.3 seconds.6. The customer would obviously prefer the One-at-a-time deli, since the latency of each sandwichis lower. The owner would prefer the Pipelined deli, since the throughput is higher. In general,pipelining improves throughput at the expense of latency. This is sometimes called the “Pipeliningparadox”.3CS232 Section 5: Single-cycle datapaths and Pipelining October 2Bonus problems1. The single-cycle datapath we’ve discussed has two adders and sets the new PC value for branchesusing the following logic:PCSrc Meaning new PC0 branch not taken PC + 41 branch taken PC + 4 + (offset × 4)The implementation is changed to eliminate one adder, which changes the above table. The relevantportion of our modified datapath looks like this:(a) How does this new datapath update the PC?(b) The new implementation is inferior to the old implementation for branch instructions. Explainwhat the disadvantage is.(c) Modify the above datapath to eliminate this disadvantage. Do not add any extra hardware!2. In the Pipelined sandwich assembly, we chose to “idle” during the TOS stage for untoasted sand-wiches. What problems would o cc ur if we didn’t idle and instead moved on to the ADD stage forsuch sandwiches? What strategy would avoid these problems and avoid idling whenever
View Full Document
Unlocking...