• Author
    Posts
  • staff
    Keymaster
    Post count: 46
    #2898 |

    Talk by Ivan Godard – July 12, 2017, at the
    SFBay Association of C/C++ Users

    Slides: mill-cpu-switches.04 (.pptx)

    This is the eleventh topic publicly presented related to the Mill general-purpose CPU architecture.

    Multi-way branches, known as switches or case clauses in various languages, are a notorious pain for compiler writers and CPU architects. On the critical path in important applications from lexers to byte-code interpreters, switches often suffer from poor branch prediction performance. Short switches with few cases can use a chain of ifs but are hampered by the low rate at which branches issue on conventional hardware and may miss several times while working down the chain. A common alternative is to indirect-branch through a jump table, but that approach is subject to misses in the data cache as well a prediction miss. Some CPU architectures have taken the approach of putting the table in instruction space, but that adds expensive shifters and datapaths to the instruction fetch.

    This talk shows how the ultra-wide-issue Mill architecture responds to the switch challenge. The Mill is a family of wide-issue, statically scheduled, exposed pipeline CPUs. Some family members can issue up to 30 instructions every cycle, including up to five branches — and can retire instructions at the same rate. The talk works through the compiled code for an example with eight cases spanning 100 values. Spoiler: a mid-range Mill does the whole switch, including the action bodies for each case, in three instructions and no table. Which isn’t too bad, considering that hand-crafted Mill code can do it in two.

    NOTE: the slides may require genuine Microsoft Windows PowerPoint to view; many clones, and Mac native PowerPoint, are unable to show the animations correctly. If you do not have access to Windows PowerPoint then watch the video, which shows the slides as intended.

    • This topic was modified 6 months ago by  staff.
    • This topic was modified 6 months ago by  Will_Edwards.
    • This topic was modified 6 months ago by  Will_Edwards.
    • This topic was modified 6 months ago by  Will_Edwards.
    • This topic was modified 6 months ago by  staff.
    • This topic was modified 6 months ago by  staff.
    • This topic was modified 6 months ago by  Will_Edwards.
    • This topic was modified 6 months ago by  Will_Edwards.
    • This topic was modified 5 months, 3 weeks ago by  staff.
    • This topic was modified 5 months, 3 weeks ago by  staff.

You must be logged in to reply to this topic.