SHERIFF: Precise Detection and Automatic Mitigation of False Sharing

Sheriff: Precise Detection and Automatic Mitigation of False Sharing
Tongping Liu, Emery D. Berger, OOPSLA 2011

False sharing is an insidious problem for multithreaded programs running on multicore processors, where it can silently degrade performance and scalability. Previous tools for detecting false sharing are severely limited: they cannot distinguish false sharing from true sharing, have high false positive rates, and provide limited assistance to help programmers locate and resolve false sharing.

This paper presents two tools that attack the problem of false sharing: SHERIFF-DETECT and SHERIFF-PROTECT. Both tools leverage a framework we introduce here called SHERIFF. SHERIFF breaks out threads into separate processes, and exposes an API that allows programs to perform per-thread memory isolation and tracking on a per-page basis. We believe SHERIFF is of independent interest.

SHERIFF-DETECT finds instances of false sharing by comparing updates within the same cache lines by different threads, and uses sampling to rank them by performance impact. SHERIFF-DETECT is precise (no false positives), runs with low overhead (on average, 20%), and is accurate, pinpointing the exact objects involved in false sharing. We present a case study demonstrating SHERIFF-DETECT’s effectiveness at locating false sharing in a variety of benchmarks.

Rewriting a program to fix false sharing can be infeasible when source is unavailable, or undesirable when padding objects would unacceptably increase memory consumption or further worsen runtime performance. SHERIFF-PROTECT mitigates false sharing by adaptively isolating shared updates from different threads into separate physical addresses, effectively eliminating most of the performance impact of false sharing. We show that SHERIFF-PROTECT can improve performance for programs with catastrophic false sharing by up to 9x, without programmer intervention.

AluPen: Best iPad Stylus Yet (By Far)

If you have an iPad, and (like me) you’d like to be able to take handwritten notes on it, there is finally a decent stylus that does the job: the AluPen. It’s chunky and a little weird, with a round rubber tip that looks like half of a tiny racquetball, but it works great (unlike every other iPad stylus I have tried). Wired has a nice review. I bought mine on Amazon; it’s available in a wide range of colors, but I like the gold for its retro pencil look. I am using it in combination with NoteTaker HD, an app by Dan Bricklin of VisiCalc fame, though other note taking apps with a magnified writing area would be fine.

Boom: Crank up your Mac

I like my MacBook Air (my hands are soaking in it right now), but the speakers suck. I have never been able to get much volume out of them. Until now.

One of the winners of the MacWorld awards this year was Boom, a “volume booster” for your Mac. Works like a charm! It easily doubles the volume of the speakers, making it practical to use the Air to watch, say, The Daily Show, without having to don earphones. Well worth the $5 to crank your Mac up to 11.

The Evolution is Televised

I was just at POPL and got a very nice compliment on a talk I gave on Grace from someone who watched it on-line (!). That talk was the first in my on-going efforts to eliminate all text from my slides. My latest talk has no text whatsoever, except for the titles (not here, though – haven’t given it at MSR!). Anyway, thanks to Microsoft, you can watch the evolution (talks ordered from most recent to oldest).

Sheriff: Detecting and Eliminating False Sharing

Grace: Safe Multithreaded Programming for C/C++ (paper)

Exploiting Multiple Cores Today: Scalability and Reliability For Off-the-shelf Software (Flux, DieHard)

Garbage Collection without Paging (paper)

latexdiff: Superb diff tool for LaTeX

I am shepherding a paper for ASPLOS, and the authors kindly sent me a PDF highlighting all changes between the previous version and the next. They used latexdiff. I just used it to see some updates made by a student to a paper, and it is fantastic.

Here’s a sample of what the results look like:

(and no, this is not my paper or the ASPLOS paper).

If you are using a Mac, you can easily install it with MacPorts (just sudo port install latexdiff).

Generally, you will want to invoke latexdiff as follows (assuming you are in the directory with the latest version):

latexdiff --flatten /path/to/old/version/main.tex main.tex > diffs.tex

(the –flatten argument makes latexdiff recursively operate on any included .tex files.)

One trick: if, like me, you break your LaTeX documents into separate files, you need to put the preamble into your main document (it’s also automatically generated by latexdiff, but only for a main document). Reproduced here for your cut-n-paste convenience.


%DIF PREAMBLE EXTENSION ADDED BY LATEXDIFF
%DIF UNDERLINE PREAMBLE
\RequirePackage[normalem]{ulem}
\RequirePackage{color}\definecolor{RED}{rgb}{1,0,0}\definecolor{BLUE}{rgb}{0,0,1}
\providecommand{\DIFadd}[1]{{\protect\color{blue}\uwave{#1}}}
\providecommand{\DIFdel}[1]{{\protect\color{red}\sout{#1}}}
%DIF SAFE PREAMBLE
\providecommand{\DIFaddbegin}{}
\providecommand{\DIFaddend}{}
\providecommand{\DIFdelbegin}{}
\providecommand{\DIFdelend}{}
%DIF FLOATSAFE PREAMBLE
\providecommand{\DIFaddFL}[1]{\DIFadd{#1}}
\providecommand{\DIFdelFL}[1]{\DIFdel{#1}}
\providecommand{\DIFaddbeginFL}{}
\providecommand{\DIFaddendFL}{}
\providecommand{\DIFdelbeginFL}{}
\providecommand{\DIFdelendFL}{}
%DIF END PREAMBLE EXTENSION ADDED BY LATEXDIFF

CS Slogans for the Rally to Restore Sanity and/or Fear

Protestor
Sadly, I am not going to attend the Rally to Restore Sanity and/or Fear in DC tomorrow. I have seen some pretty good sign ideas: here are some CS-themed ones I came up with. Keep your eyes peeled: you might see one of my colleagues holding one of these up.

  • P and NP: Equality Now!
  • Hello World Peace!\n
  • Repeal Moore’s Law!
  • (or) Renew Moore’s Law!
  • End Race Conditions!
  • Free malloc!

Emery Berger's Blog

%d bloggers like this: