Topic
16 replies Latest Post - ‏2011-03-06T09:51:16Z by mikee111
mikee111
mikee111
13 Posts
ACCEPTED ANSWER

Pinned topic branch histories

‏2008-12-29T04:31:59Z |
Hi,
I have a problem with using branch and hint histories which I got out of the cell simulator. I was able to get to a branch which is mispredicted (ran spu-gdb on ps3 and disas'd to the address) .. but I dont really know what to do now ;] because I have no idea how to "link" this branch in asm with a branch in my code ..

thanks for any hint
michal

ps. i am finishing my diploma thesis now, a part of it was implementing a ray-tracer with different acc. structures on Cell (currently BIH and KDT) ... let's say that me not being a linux guru (I am a game programmer, a windows person usually :]) really made be bang my head against the wall a lot in the last few months ;] lots of times I felt that the documentation just presumed that people are linux experts (this ps is not about the branch histories in particular, this is just my first post here, so I felt a need to say this :])
Updated on 2011-03-06T09:51:16Z at 2011-03-06T09:51:16Z by mikee111
  • mikee111
    mikee111
    13 Posts
    ACCEPTED ANSWER

    Re: branch histories

    ‏2008-12-29T07:23:16Z  in response to mikee111
    I've managed to get help from my roomie, who happens to know his way around *nix .. anyhow, through gdb disas and info line I can look at which branch is where in code ... now, what's weird is this

    my histories look like this: http://www.pastebin.cz/13657

    I am wondering, shouldn't there be always a branch for every hint?
    on line 109 you can find

    line 109 hbrr 0x00f4c: 0x00f8c 0x00c68 9716 0 9716

    there's a branch there (on f8c), but it is not listed in branch history .... instead on line 75 is 0x00d80, which does not point to a line with a branch (which is kinda confusing for me, why is there a wrong address) ... but the stats correspond to the while cycle happening on f8c

    line 75 brhnz 0x00d80: 9716 3928 5788 0 3928

    (well I know that hbrr cannot be a hint for brhnz .. but that's the only thing I can pair it with) ...

    anybody encountered a hint for a branch that was not in the branch history? when can this happen? anything in docs I've overlooked?

    thanks
    michal
  • mikee111
    mikee111
    13 Posts
    ACCEPTED ANSWER

    Re: branch histories

    ‏2008-12-30T08:04:06Z  in response to mikee111
    well, according to surrounding posts everybody's busy with actually starting the simulator (or running it) .. so, can anyone at least point me to a place in the documentation (or anywhere on the internet) regarding branch and hint histories dumped from systemsim? I was unable to find any docs or at least a FAQ ..
    thanks a lot :]

    i wrote an x86 raytracer, ported it on cell, then tweaked the software caches, then put some branch hints in, then wrote a branchless version of my algos, then put in async cache access, now I want to tweak branch hints a little so I have something more to write about in my thesis.. it's still dead slow though and all those optimizations did not really help (branchless will spent all those saved cycles on more computation it has to do, and so on) ... you have to admire those guys who wrote that fully fledged RT on Cell, no idea how they did that :] well .. after its all written I'll post it here so you guys can rip my Cell results apart ;]

    michal
    • mkistler
      mkistler
      551 Posts
      ACCEPTED ANSWER

      Re: branch histories

      ‏2008-12-30T12:49:49Z  in response to mikee111
      There is some information on branch and hint statistics in the slides at

      http://www.princeton.edu/~asplos06/T4.pdf

      In particular, slides 50-51 and 110-113 may be helpful.

      Mike Kistler
      • mikee111
        mikee111
        13 Posts
        ACCEPTED ANSWER

        Re: branch histories

        ‏2008-12-30T16:13:41Z  in response to mkistler
        thanks mike, anyhow I forgot to mention I found this particular one (first one on google for "hint histories", I UTFG, yes :])

        what is bothering me is a glitch of some sorts which is happening and I described it in my second post
        basically there's a hint instruction that is not paired with a branch (the one on line 109) and there should be one for the branch on line 75 (i put it there) and there isn't ..
        so I guess that those 9716 stall equal the 9716 hbrr instruction that execute in vain, not having a valid branch to hint ... and I have NO idea why is this happening .. it kinda ruins my statistics, as I don't know how to interpret this :(

        thanks
        michal
        • mkistler
          mkistler
          551 Posts
          ACCEPTED ANSWER

          Re: branch histories

          ‏2009-01-01T11:36:10Z  in response to mikee111
          Michal,

          This is curious. I think it might be helpful to see the instructions near this hint ... say from 0xf00 to 0x1000. It would be even better if you could post enough of your code to be able to recreate this problem, but I know sometimes this is not possible or easy to do.

          Mike Kistler
          • mikee111
            mikee111
            13 Posts
            ACCEPTED ANSWER

            Re: branch histories

            ‏2009-01-01T23:54:46Z  in response to mkistler
            okay, i've posted parts of my C++ code, asm output you've requested from gdb and info lines on pastebin here http://www.pastebin.cz/13758

            i've forgotten to include

            #define likely(_c) __builtin_expect((_c), 1)
            #define unlikely(_c) __builtin_expect((_c), 0)

            though its pretty selfexplanatory :]

            ....

            the situation is thus this:


            hbrr 0x00f4c: 0x00f8c 0x00c68 9716 0 9716
            0x00000f4c hbrr 0xf8c,0xc68
            0x00000f8c brnz $80,0xc68

            this hint is indeed in asm and points to a branch that does exist in the code (but does not appear in branch histories for some reason) and it is the while cycle line

            Line 695 of "../bih.cpp" starts at address 0xf8c and ends at 0xf90
            695 while(likely(indexStack != 0 && !currNode.isLeaf()))

            I've no idea why there are 9716 stalls, when this hint looks perfectly ok to me ... (and as it's branch is not listed in branch histories, I can't really know how does the branch itself perform)


            what does appear in branch histories is this branch

            brhnz 0x00d80: 9716 3928 5788 0 3928
            0x00000d80 brhnz $3,0xda0

            but

            Line 719 of "../bih.cpp" starts at address 0xd7c and ends at 0xd84
            719 bool secondTest = !SIMD_IS_FALSE(valid_iimax_t) && !SIMD_IS_FALSE(valid_iimax_s);

            there's no branch on line 719, and

            Line 724 of "../bih.cpp" starts at address 0xda0 <_ZN7BIH_SPE33Trace4PacketBranchlessWCacheAsyncER9RayPacket+952>
            and ends at 0xda4 <_ZN7BIH_SPE33Trace4PacketBranchlessWCacheAsyncER9RayPacket+956>.

            724 indexStack += firstTest;

            there's nothing to jump to on line 724 either (no loop start, line just after a loop/if or something like that)


            i've also checked the other frequented branch in branch histories
            brnz 0x00ebc: 9716 7591 2125 0 7591
            Line 163 of "../cache/cache-4way.h" starts at address 0xeb0 and ends at 0xec0

            159 static inline int
            160 __cache_line_lookup (unsigned int set, unsigned int ea)
            161 {
            162 // return (CACHELINE_ISTAG(set, ea) ? (int)set : -1);
            163 if( unlikely( !CACHELINE_ISTAG(set, ea) ) )
            164 return -1;
            165 else
            166 return (int)set;
            167 }

            (there was likely and no not inside, i've tried what will happen if there's unlikely there, nothing changed though, no hint)

            this is cache code and yes, there's a branch there .. but it was supposed to be hinted, and it is not ... (the hint does not appear in hint histories, I've checked the code before 0x00ebc manually and there's no hint hinting this branch either)

            considering the code, If necessary, I can upload my complete cell code and pinpoint the problematic locations, it is a raytracer, hence I would have to include some testing scene also . anyhow, I have a few that are smaller than 1MB, so that should not pose a problem :]

            thanks a lot and have a happy new year! :] .. i am off writing my thesis text, kinda fed up with coding ;]
            michal
            • mkistler
              mkistler
              551 Posts
              ACCEPTED ANSWER

              Re: branch histories

              ‏2009-01-03T04:23:59Z  in response to mikee111
              Michal,

              Now that we know there is a branch a 0xf8c, I would be suspicious that the hint does not appear early enough to avoid a stall when the branch is reached. The CBE Handbook (Section 24.3.3) says that:

              An HBR instruction should be placed at least 11 cycles followed by four instruction pairs
              before the branch instructions being hinted by the HBR instruction.

              Looking at the assembler, it looks like the hbrr might be a little too late. It is very close -- depending on when the cycle counting actually starts and stops, it could be right on or it could be one cycle off. And the hint history seems to imply a one cycle stall each time the branch is encountered, so it seems possible that the hint is just one cycle to late. Of course, it could also be the case that the simulator could be off by a cycle and inserts a stall when there really should not be one.

              I don't know why 0xf8c does not show up in the branch history.

              Regarding line 719 ... you say there is no branch on that line, but I think you need to look at the disassembly for that line to know for sure. Did you do that?

              If it's not a problem, it would be great if you could post enough of your code so that we can compile and run it ... that will be the best way to uncover what is going on here.

              Mike Kistler
              • mikee111
                mikee111
                13 Posts
                ACCEPTED ANSWER

                Re: branch histories

                ‏2009-01-03T12:45:38Z  in response to mkistler
                a] regarding the f8c branch, there's a lnop instruction on 0x00000f88, so this can possibly be viewed as a stall by the stats ..
                b] 719 well I looked on disassembly paired with that line, and there is one ... but I don't see why is it compiled like this, because line 719 looks like this:

                bool secondTest = !SIMD_IS_FALSE(valid_iimax_t) && !SIMD_IS_FALSE(valid_iimax_s);

                where #define SIMD_IS_FALSE(a) (a == sse_zero_i)

                this is supposed to be on of the precomputed bools to avoid having branches :]

                anyways, I am gonna pack my code together and post it here as soon as possible
              • mikee111
                mikee111
                13 Posts
                ACCEPTED ANSWER

                Re: branch histories

                ‏2009-01-03T13:41:39Z  in response to mkistler
                http://www.nantuko.cz/mikee/dip/mikeecellcode.tar.gz

                small FAQ

                a] settings.h are set as I had it when stats I showed were made (BIH structure used, branchless code, asyn cache, simulator mode, debug mode)
                normally, cell works as a TCP server for x86 image client application, with debug mode it will raytrace a scene and stop
                eclipse generated makefiles are included (my toolchain path is /opt/cell/toolchain/ .. you will have to change the path to code though, as it is set to /home/mikee/dip_cell/)

                b] I've also included my testing setup with tlc file with my few added lines at the end for the cell simulator and shell script to run the simulator (just to pack it all)

                c] there's a testing scene included (f15 fighter jet ;], f15.obj). As scene path is now hardcoded, you have to change the path in ppu/main.cpp:line 31 depending on where you actually have the scene

                d] code we were talking about here is in function Trace4PacketBranchlessWAsyncCaches in bih.cpp: lines 667 to 784, with the profiled code between 697 and 740 (this function will be used for hierarchy traversal when settings.h as they are now are used)
              • mikee111
                mikee111
                13 Posts
                ACCEPTED ANSWER

                Re: branch histories

                ‏2009-01-03T13:43:16Z  in response to mkistler
                oh, and I totally forgot to thank you for the time you're investing in this. thanks a lot, mike!
              • mikee111
                mikee111
                13 Posts
                ACCEPTED ANSWER

                Re: branch histories

                ‏2009-01-03T20:09:54Z  in response to mkistler
                well, we had lunch with my *nix guru roomie, who basically slapped me and told me that trying to find anything with debug info in optimized (-O3) code is pure lunacy and he added something about woe on windows programmers and their children ;] .. well, it does make sense
                we came to the conclusion that the branch on line 719 (in code there's no branch there) is made by optimizations and there's no hint for it because it's made up by g++ in some form of cycle decomposition into outer and inner loop (there's a hint for the outer loop, which I put there, but not for the inner)
                is this a possible answer to what's happening?
                I've compiled my code with -Os -finline-functions and ran it in the simulator, the same thing happened (apparent inconsistency between debug info and real code) .. so I've tried -O0, this was OK as far as debug info to code mapping is concerned, but of course there were lot of branch and links and also the while hint had dissapeared http://www.pastebin.cz/13821
                I've tried to check man pages for spu-g++ and spu-gdb, only to find that these were identical to g++ and gdb mans, so I don't really have an idea how spu-g++ fools with those hints ...
              • mikee111
                mikee111
                13 Posts
                ACCEPTED ANSWER

                Re: branch histories

                ‏2009-01-03T23:30:34Z  in response to mkistler
                another friend pointed out that as while compiles to two branches, and as I can't get my hint through, it can be beneficial to do this by myself .. so I did, and apparently it helped. I've changed

                while(hint(x)) { }

                to

                if(hint(x)) do { } while(hint(x);

                I've gained 0.13 CPI and saved some 150K cycles. I was suspicious of this, so I checked if the image is still raytraced correctly, and apparently it is :]

                here's the new code and stats from simulator http://www.pastebin.cz/13833
                • mikee111
                  mikee111
                  13 Posts
                  ACCEPTED ANSWER

                  Re: branch histories

                  ‏2009-01-03T23:49:29Z  in response to mikee111
                  forgot to point out this:
                  hbrr 0x014bc: 0x01500 0x011e0 9716 0 0
                  no stalls and 0x01500 is the address of the do { } while cycle, so this is basically what I wanted to achieve (to hint the inner branch) .. though still there's no 0x01500 branch in branch histories ..

                  brnz 0x0142c: 9716 7591 2125 0 7591
                  unfortunately no hint for cache access (this branch) ...
                  • mkistler
                    mkistler
                    551 Posts
                    ACCEPTED ANSWER

                    Re: branch histories

                    ‏2009-01-04T00:18:20Z  in response to mikee111
                    I find it interesting that this shows the hint as 17 instructions away from the branch, rather than the 16 instructions in the prior version of the code. I would conclude that, at least as far as the simulator is concerned, the prior version had the hint one instruction too late.

                    Now the interesting question is whether the simulator is correct in it's interpretation of the required distance from hint to branch. Have you tried running this on actual hardware and measured the performance? If so, is it consistent with what is shown by the simulator?

                    Mike Kistler
                    • mikee111
                      mikee111
                      13 Posts
                      ACCEPTED ANSWER

                      Re: branch histories

                      ‏2009-01-04T14:08:53Z  in response to mkistler
                      well, the previous one was one instruction off as there was a lnop inserted by the compiler (that is a pipeline stall, is it) but it was also a different branch .. if I am presuming correctly that the while cycle is decomposed into two branches, outer and inner, then hint in the previous code was on the outer branch .. I've succeeded to have it on the inner branch by decomposing it manually as I mentioned in my last post
                      Regarding performance, I have remote access to a PS3 (placed at my faculty's building) with user rights only, and I was advised that for performance counters (like branch/hint stats, pipeline stats and so on) to work correctly kernel has to be patched and you have to have root rights of course (which I don't have). I can use SPE timer though, so I'll get the timings as soon as possible.
                      • mikee111
                        mikee111
                        13 Posts
                        ACCEPTED ANSWER

                        Re: branch histories

                        ‏2011-03-06T09:51:16Z  in response to mikee111
                        with all the submission rush i had no time to get back to this particular problem (and I was not able to find the timings now, they probably are somewhere in the bazillion measured files I had ..) and was working on different projects since, anyhow here's the complete thesis (in english) http://dip.felk.cvut.cz/browse/pdfcache/hapalm1_2009dipl.pdf
                        It's been two years now, but well, someone may still find it interesting ... I am still doing ray tracing, but not on Cell :)