{"id":91151,"date":"2015-08-07T07:00:00","date_gmt":"2015-08-07T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/20150807-00\/?p=91151\/"},"modified":"2019-03-13T12:18:14","modified_gmt":"2019-03-13T19:18:14","slug":"20150807-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20150807-00\/?p=91151","title":{"rendered":"The Itanium processor, part 10: Register rotation"},"content":{"rendered":"

Last time<\/a>, we looked at counted loops and then improved a simple loop by explicitly pipelining the loop iterations. This time, we’re going to take the pipelining to the next level. <\/p>\n

Let’s reorder the columns of the chart we had last time so the instructions are grouped not by the register being operated upon but by the operation being performed. Since no instructions within an instruction group are dependent on each other in our example, I can reorder them without affecting the logic. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
1<\/td>\n <\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n<\/td>\n <\/td>\n<\/td>\n <\/td>\n<\/td>\n <\/td>\n<\/td>\n;;<\/code><\/td>\n<\/tr>\n
2<\/td>\nld4 r33 = [r29], 4<\/code><\/td>\n <\/td>\n <\/td>\n <\/td>\n;;<\/code><\/td>\n<\/tr>\n
3<\/td>\nld4 r34 = [r29], 4<\/code><\/td>\n <\/td>\nadds r32 = r32, 1<\/code><\/td>\n <\/td>\n;;<\/code><\/td>\n<\/td>\n<\/tr>\n
4<\/td>\nld4 r35 = [r29], 4<\/code><\/td>\n <\/td>\nadds r33 = r33, 1<\/code><\/td>\nst4 [r28] = r32, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
5<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r33, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
6<\/td>\nld4 r33 = [r29], 4<\/code><\/td>\n <\/td>\nadds r35 = r35, 1<\/code><\/td>\nst4 [r28] = r34, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
7<\/td>\nld4 r34 = [r29], 4<\/code><\/td>\n <\/td>\nadds r32 = r32, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
8<\/td>\nld4 r35 = [r29], 4<\/code><\/td>\n <\/td>\nadds r33 = r33, 1<\/code><\/td>\nst4 [r28] = r32, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
9<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r33, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
10<\/td>\nld4 r33 = [r29], 4<\/code><\/td>\n <\/td>\nadds r35 = r35, 1<\/code><\/td>\nst4 [r28] = r34, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
11<\/td>\n <\/td>\n <\/td>\nadds r32 = r32, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
12<\/td>\n <\/td>\n<\/td>\nadds r33 = r33, 1<\/code><\/td>\nst4 [r28] = r32, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n
13<\/td>\n <\/td>\n <\/td>\n<\/td>\nst4 [r28] = r33, 4<\/code><\/td>\n;;<\/code><\/td>\n<\/tr>\n<\/table>\n

What an interesting pattern. Each column represents a functional unit, and at each cycle, the unit operates on a different register in a clear pattern: r32<\/var>, r33<\/var>, r34<\/var>, r35<\/var>, then back to r32<\/var>. The units are staggered so that each operates on a register precisely when its result from the previous unit is ready. <\/p>\n

Suppose you have to make 2000 sandwiches and you have four employees. You could arrange your sandwich factory with three stations. At the first station, you have the bread and the toaster. At the second station, you have the protein. At the third station, you have the toppings. Each employee goes through the stations in order: First they take two pieces of bread and put them in the toaster. When the toast is finished, they add the protein, then they add the toppings, and then they put the finished sandwich in the box. Once that’s done, they go back to the first station. You stagger the starts of the four employees so that at any moment, one is preparing the bread, one is waiting for the toaster, one is adding protein, and one is adding the toppings. <\/p>\n

That is how the original code was arranged. Each register is an employee that is at one of the four stages of sandwich construction. <\/p>\n

But another way to organize your sandwich factory is as an assembly line. You put one employee in charge of the bread, one in charge of the toaster, one in charge of the protein, and one in charge of the toppings. When a sandwich completes a stage in the process, it gets handed from one employee to the next. <\/p>\n

(And since there isn’t really anything for the toaster-boy to do, you can eliminate that position and create the same number of sandwiches per second with only three employees. The original version had each employee sitting idle waiting for the toaster 25% of the time. Switching to the assembly line model allowed us to squeeze out that idle time.) <\/p>\n

Let’s apply the assembly line model to our code. Handing a sandwich from one person to the next is done by moving the value from one register to the next. Let’s imagine than there is a slide<\/var> instruction that you can put at the end of an instruction group which copies r32<\/var> to r33<\/var>, r33<\/var> to r34<\/var>, and so on. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
1<\/td>\n <\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n<\/td>\n <\/td>\n<\/td>\n <\/td>\n<\/td>\n <\/td>\n<\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
2<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n <\/td>\n <\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
3<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\n <\/td>\nslide ;;<\/code><\/td>\n<\/td>\n<\/tr>\n
4<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
5<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
6<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
7<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
8<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
9<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
10<\/td>\nld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
11<\/td>\n <\/td>\n <\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
12<\/td>\n <\/td>\n<\/td>\nadds r34 = r34, 1<\/code><\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
13<\/td>\n <\/td>\n <\/td>\n<\/td>\nst4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n<\/table>\n

During the execution of the first instruction group, the first value is loaded into r32<\/var>, and the slide<\/var> instruction slides it into r33<\/var>. <\/p>\n

At the second instruction group, the second value is loaded into r32<\/var>, and the first value sits unchanged in r33<\/var>. (Technically, the value is waiting to be loaded into r33<\/var>.) The slide<\/var> instruction slides the second value into r33<\/var> and the first value into r34<\/var>. <\/p>\n

At the third instruction group, the third value is loaded into r32<\/var>, and the first value (now in r34<\/var>) is incremented. Then the slide<\/var> instruction slides the third value into r33<\/var>, the second value into r34<\/var>, and the first value into r35<\/var>. <\/p>\n

At the fourth instruction group, the fourth value is loaded into r32<\/var>, the second value (now in r34<\/var>) is incremented, and the first value (now in r35<\/var>) is stored to memory. Then the slide<\/var> instruction slides the fourth value into r33<\/var>, the third value into r34<\/var>, and the second value into r35<\/var>. (The first value slides into r36<\/var>, but we don’t really care.) <\/p>\n

And so on. At each instruction group, a fresh value is loaded into r32<\/var>, a previously-loaded value is incremented in r34<\/var>, and the incremented value is stored from r35<\/var>. And then the slide<\/var> instruction moves everything down one step for the next instruction group. <\/p>\n

When we reach the 11th instruction group, we drain out the last value and don’t bother starting up any new ones. <\/p>\n

Observe that the above code also falls into a prologue<\/i>\/kernel<\/i>\/epilogue<\/i> pattern. In the prologue, the assembly line starts up and gradually fills the registers with work. In the kernel, the assembly line is completely busy. And in the epilogue, the work of the final registers drains out. <\/p>\n

You can already see how br.cloop<\/var> would come in handy here: The kernel can be written as a single-instruction loop! But wait there’s more. <\/p>\n

Let’s add some predicate registers to the mix. Let’s suppose that the slide<\/code> instruction slides not only integer registers but also predicate registers. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
1<\/td>\n <\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n<\/td>\n <\/td>\n<\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n<\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\n<\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
2<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/font><\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
3<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/td>\n<\/tr>\n
4<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
5<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
6<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
7<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
8<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
9<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
10<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
11<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
12<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n<\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n
13<\/td>\n(p16) ld4 r32 = [r29], 4<\/code><\/td>\n <\/td>\n(p18) adds r34 = r34, 1<\/code><\/td>\n(p19) st4 [r28] = r35, 4<\/code><\/td>\nslide ;;<\/code><\/td>\n<\/tr>\n<\/table>\n

We can initally set p16 = true<\/var>, p17 = p18 = p19 = false<\/var>. That way, only the load executes from the first instruction group. And then the slide<\/var> instruction slides both the integer registers and the predicate registers, which causes p17<\/var> to become true<\/var>. <\/p>\n

In the second instruction group, again, only the load executes. And then the slide<\/var> instruction slides p17<\/var> into p18<\/var>, so now p18 = true<\/var> also. <\/p>\n

Since p18 = true<\/var>, the third instruction group both loads and increments. And then the slide<\/var> instruction slides p18<\/var> into p19<\/var>, so now all of the predicates are true. <\/p>\n

With all the predicates true, every step in instruction groups three through 10 execute. <\/p>\n

Now, with instruction group 11, we want to slide the predicates, but also set p16<\/var> to false<\/var>. That turns off the ld4<\/var> instruction. <\/p>\n

The p16 = false<\/var> then slides into p17<\/var> for instruction group 12, then into p18<\/var> for instruction group 13, which turns off the increment instruction. <\/p>\n

If we can get the slide<\/var> instruction to slide the predicates and set p16<\/var> to true<\/var> for the first 10 instructions, and set it to false<\/var> for the last three, then we can simply execute the same instruction 13 times! <\/p>\n

Okay, now I can reveal the true identity of the slide<\/var> instruction: It’s called br.ctop<\/var>. <\/p>\n

The br.ctop<\/var> instruction works like this: <\/p>\n

\n if (ar.lc != 0) { slide; p16 = true; ar.lc = ar.lc - 1; goto branch; }\n if (ar.ec != 0) { slide; p16 = false; ar.ec = ar.ec - 1;\n                  if (ar.ec != 0) goto branch; }\n else { \/* unimportant *\/ }\n<\/pre>\n
In words, the br.ctop<\/var> instruction first checks the ar.lc<\/var> register (loop counter<\/i>). If it is nonzero, then the registers slide over, the p16<\/var> register is set to true<\/var>, the loop counter is decremented, and the jump is taken. <\/p>\n
If ar.lc<\/var> is zero, then the br.ctop<\/var> instruction checks the ar.ec<\/var> register (epilogue counter<\/i>). If it is nonzero, then the register slide over, the p16<\/var> register is set to false<\/var>, and.the epilogue counter is decremented. If the decremented value of the epilogue counter is nonzero, then the jump is taken; otherwise we fall through and the loop ends. <\/p>\n
(If both ar.lc<\/var> and ar.ec<\/var> are zero, then the loop is finished before it even started. Some weird edge-case handing happens here which is not important to the discussion.) <\/p>\n
Code that takes advantage of the br.ctop<\/var> instruction goes like this: <\/p>\n
\n      alloc r36 = ar.pfs, 0, 8, 0, 4 \/\/ four rotating registers!\n      mov r37 = ar.lc         \/\/ preserve lc\n      mov r38 = ar.ec         \/\/ preserve ec\n      mov r39 = preds         \/\/ preserve predicates\n\n      addl r31 = r0, 1999 ;;  \/\/ r31 = 1999\n      mov ar.lc = r31         \/\/ ar.lc = 1999\n      mov ar.ec = 4\n      mov pr.rot = 1 << 16 \/\/ p16 = true, all others false\n      addl r29 = gp, -205584  \/\/ calculate start of array\n      addl r28 = r29, 0 ;;     \/\/ put it in both r28 and r29\n\nagain:\n(p16) ld4 r32 = [r29], 4      \/\/ execute an entire loop with\n(p18) adds r34 = r34, 1       \/\/ a single instruction group\n(p19) st4 [r28] = r35, 4      \/\/ using this one weird trick\n      br.ctop again ;;\n\n      mov ar.lc = r37         \/\/ restore registers we preserved\n      mov ar.ec = r38\n      mov preds = r39\n      mov ar.pfs = r36\n      br.ret.sptk.many rp     \/\/ return\n<\/pre>\n
We are now using the last parameter to the alloc<\/var> instruction. The 4<\/var> says that we want four rotating registers. The ar.lc<\/var> and ar.ec<\/var> register must be preserved across calls, so we save them here for restoration at the end. Predicate registers p16<\/var> through p63<\/var> must also be preserved, so we save all the predicate registers by using the preds<\/var> pseudo-register which grabs all 64 predicates into a single 64-bit value. <\/p>\n
Next, we set up the loop by setting the loop counter to the number of additional times we want to execute the loop (not counting the one execution we get via fall-through), the epilogue counter to the number of steps we need in order to drain the final iterations, and set the predicates so that p16 = true<\/var> and everything else is false<\/var>. We also set up r28<\/var> and r29<\/var> to step through the array. <\/p>\n
Once that is done, we can execute the entire loop in a single instruction group. <\/p>\n
And then we clean up after the loop by restoring all the registers to how we found them, then return. <\/p>\n
And there you have register rotation. It lets you compress the prologue, kernel, and epilogue of a pipelined loop into a single instruction group. <\/p>\n
I pulled a fast one here: The Itanium requires that the number of rotating registers be a multiple of eight. So our code really should look like this: <\/p>\n
\n      alloc r40 = ar.pfs, 0, 12<\/font>, 0, 8<\/font>\n      mov r41<\/font> = ar.lc         \/\/ preserve lc\n      mov r42<\/font> = ar.ec         \/\/ preserve ec\n      mov r43<\/font> = preds         \/\/ preserve predicates\n\n      addl r31 = r0, 1999 ;;  \/\/ r31 = 1999\n      mov ar.lc = r31         \/\/ ar.lc = 1999\n      mov ar.ec = 4\n      mov pr.rot = 1 << 16 \/\/ p16 = true, all others false\n      addl r29 = gp, -205584  \/\/ calculate start of array\n      addl r28 = r29, 0 ;;     \/\/ put it in both r28 and r29\n\nagain:\n(p16) ld4 r32 = [r29], 4      \/\/ execute an entire loop with\n(p18) adds r34 = r34, 1       \/\/ a single instruction group\n(p19) st4 [r28] = r35, 4      \/\/ using this one weird trick\n      br.ctop again ;;\n\n      mov ar.lc = r41<\/font>         \/\/ restore registers we preserved\n      mov ar.ec = r42<\/font>\n      mov preds = r43<\/font>\n      mov ar.pfs = r40<\/font>\n      br.ret.sptk.many rp     \/\/ return\n<\/pre>\n
Instead of four rotating registers, we use eight. The underlying analysis remains the same. We are just throwing more registers into the pot. <\/p>\n
Now, the loop we were studying happens to be very simple, with only one load and one store. For more complex loops, you may need to use things like the unconditional comparison<\/a>, or pipelining the iterations with a stagger of more than one cycle. <\/p>\n
There are other types of instructions for managing loops with register rotation. For example, br.cexit<\/var> is like br.ctop<\/var> except that it jumps when br.ctop<\/var> falls through and vice versa. This is handy to put at the start of your pipelined loop to handle the case where the number of iterations is zero. There are also br.wtop<\/var> and br.wexit<\/var> instructions to handle while<\/code> loops instead of counted loops. The basic idea is the same, so I won’t go into the details. You can read the Itanium manual to learn more. <\/p>\n
That’s the end of the whirlwind tour of the Itanium architecture. There are still parts left unexplored, but I tried to hit the most interesting sights. <\/p>\n","protected":false},"excerpt":{"rendered":"
Around and around.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-91151","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"
Around and around.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91151","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=91151"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91151\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=91151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=91151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=91151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}