Critical Sections and Efficiency

Oops, I made an error when I wrote this post. The mathematical formula I'm using to make all them pretty graphs doesn't actually apply to critical sections.

Here's a followup posting with the correct graphs for critical sections!

It only applies to code that must run in parallel then must run sequentially. One step must finish completely before the other can begin. In our moving example below it would be like step 1 would be moving the furniture into the van (highly parallelizable), the second part would be driving the single van to the new location and step 3 would be moving the furniture into the new house. Steps 1 and 3 are parallel and step 2 is sequential (only one van and one driver. Everyone has nothing is just riding along in the van or their own cars or something. Maybe they teleported.) So in conclusion I'm trying to understand the math for critical sections and I'll write something on that later.

Modern computers tend to have more than one processor core. Each one of those processor cores is like an individual computer brain. This has led to something of a crisis in computing circles because figuring out how to make use of those two cores is hard. A big chunk of the problem is splitting up a computing task into pieces that can be done independently. For example, moving house is easy to parallelize because every person who shows up to help can grab a different box. Walking through doors is harder to paralyze because if all your moving buddies walked through the same door at the same time they're going to bump into each other. That would be funny be not very productive.

In the computer world, whenever you parallelize a task you end up with a bit of that task that must be done sequentially (one at a time). If people are helping you move they can each move a box but they can't go through the door at the same time. In the computing world things like doors are called a critical sections. A critical section is a piece of a task that cannot be done in parallel.

Ever since working on a project to improving the performance of InteleViewer's image decompression on multiple processor machines I've been wondering how critical sections affect performance. InteleViewer will often open a stack of something like 500 images and each image will need to be decompressed before it can be displayed. This is an easy task to split up since you can just give each core a different image to compress. The thing is, there's a very tiny amount of task co-ordination that needs to be done in a critical section. When we ran the code on a two core computer we notices that the cores were only being used at 98% efficiency.

First of all, that's an incredible loss in efficiency given that the critical section was doing practically nothing and secondly, how much will the CPUs be idle on computers with something like 12 or 16 cores? In our moving day analogy it's roughly analogous to wondering how many much time will be wasted while people wait for each other to walk through the door if a large number of people are helping you move.

Luckily I recently stumbled across Amdahl's law. Amdahls's law isn't a new courtroom drama series premiering this fall on Friday nights at 8pm (9 central). It's a mathematical model that deals with the efficiency of parallel task running the presence of critical sections. I took the formula and produced a graph to see what was going on.

This chart has the number of cores along the X axis and the factor speedup along the Y axis. The lines represent how much of the task can run in parallel. The blue line represents the ideal of a task where 100% of it can run in parallel. The orange line represents a task where 99% of it can run in parallel and the light blue line at the bottom represents a task where only 50% of it can run in parallel.

(To go back to our moving analogy, the orange line is a house with a door and the light blue line is a house with a door and a very long, narrow hallway that you have to pass through first. The dark blue line is a house with no door.. which would be kinda weird in real life but perfectly safe in a world populated only by math.)

(Click to enlarge, higher is faster)

Notice how the light blue line at the bottom never quite reaches the 2X speed up even when you put up to 16 cores on the problem.

I found it surprising how inefficient things get even when 90% of the task is able to run in parallel. At around six cores there's almost no point in adding more cores. They don't really speed up things that much.

I also have a graph of the % efficiency. This grap htells you how busy each processor core would be if you gave it a some task and some number of cores.

(Click to enlarge)

Here's what the graph looks like up to 100 processors:

(Click to enlarge)

Notice how even a task that runs in parallel 99% of the time only makes use of half the available computing power at 100 CPUs. We don't have computers with 100 cores yet but with the number of cores on a processor doubling every 18 months or so we could have that in less than ten years. The main problem is that the InteleViewer's image decompression example represents close to a best case scenario and even there we have code that's not going to scale up to that many cores. Making programs run efficiently on multiple processor cores is hard. It's all just a tad depressing.

The people who make processors have noticed this problem too. In the latest batch of chips they are opting to not add more cores but instead to put a video processor (GPU) and other task specific hardware on the processor die... but that's another blog post.

The InteleViewer example actually does have a happy ending. We decided to switch from using critical sections to using a magical technique called compare-and-swap. It's not always possible or wise to use this technique but for InteleViewer it worked great. We ended up making our 1% overhead disappear. Well, as far as we can measure on a 12 core (6 + 2X hyper threading) anyway.

There's no equivalent analogy I think of to compare-and-swap in the moving example. The closest I can get is if all your moving buddies decided to run through the door regardless of who else was trying to get through. So long as collisions don't have a large time penalty and so long as they are infrequent enough it might be faster. I don't recommend trying it for doorways but for InteleViewer it worked great.

So, in conclusion, buy InteleViewer.

We're done here.

Why Threading is Hard (link)

As someone who spends quite alot of time explaining and debugging multithreaded applications it's nice to see someone else take a go at it for a change.

Future Chips (Mmm chips) has an articles on what makes parallel programming hard. It goes over why not all programs get a speedup with more cores and why it's hard to write and debug multithreaded (MT) programs.

They have also posted a follow up article on writing and optimizing parallel programs; a complete example. Which is nice...

My Top Three User Interface Books

As far as I know there is still no course or university program to become a user interface designer. Part of me thinks this is a shame because I think there's a lot of things you can teach someone who wants to design user interfaces for computer programs or websites. Another part of me is happy because I can claim to know a thing or two about user interfaces without the bother of getting another degree.

I've been doing computer programming for a while now (that's an Imperial "while" you'll note. Multiply by 1.6 to get the more typical metric "while".) And just about all of that programming has involved some sort of GUI work on a desktop application. In my opinion there are many great books that can help you become better at this sort of thing. However, if you want to learn as much as possible in as little time as possible then I recommend three books.

The first book tells you how to know what to build. This is surprisingly difficult because you often aren't building a program for yourself you're building it for someone else and you don't know what they need. If you're a programmer this is even harder because programmers think in a very peculiar way with respect to computers. If you're a developer and you're building a user interface what you end up with an interface that doesn't do what it needs to and does it in a very strange and round about way.

The Inmates are Running the Asylum is a book by Alan Cooper. This is a book for programmers who want to write user interfaces. In the book he explains how developers think differently than your average man on the street. Specifically he points out how certain practices that work well if you're developing software get in the way if you're trying to write a user interface. For example, one of the easiest traps to fall into is to write a user interface that can deal with every single possible edge case that the user might ever have. Trying to deal with every single case is essential if you're writing computer software.In fact, if you don't do this your computer software will break. When writing user interfaces it's counter productive. Trying to do everything means you're not doing anything well. One warning, don't let your pointy haired manager get hold of this book or you might never be asked to program a UI again. This book is is written for developers and there's a lot of hyperbolic developer bashing. As a developer, it gets your attention, but may get miss-understood by others. Developers can code good interfaces.

If you're not a developer you should read About Face. About Face is also by Alan Cooper and contains the same material as the inmates are running the asylum but also contained additional chapters and give more detail on constructing processes in an organization to formalize interface development. This is useful if you have to convince the organization or even the developers on your team that's something you're suggesting make sense. Believe me you'll need to do this at some point. Probably before you actually get any real work done.

In both these books, Alan Cooper explains several methods you can use in order to figure out exactly what your software is supposed to do. Newcomers to the field often think that the way you figure out what your software should do is you ask the user. In practice this doesn't work very well unless the person you're asking is a user interface designer. Users are extremely bad at expressing what they want. For it to have any hope of working you'll need a tight feedback loop and lots of prototyping/trial and error. The tight feedback loop is almost never possible in practice and even when it is the results are still... average. To do better to do better you'll need to read the book.

Book 2 is GUI Bloopers. Actually, this book is a stand-in for simply knowing user interface guidelines and standards for the platforms and GUI widgets you be using. It's funny because Alan Cooper downplays the importance of sticking to interface guidelines and standards. In my opinion you absolutely have to know all the standards and interface guidelines for your platform. There are no excuses. You don't have to be totally pedantic about it but you really need to know the rules before you break them. It's important to know this stuff if you're a developer because UI designers don't always design to this level of detail.

Most people have been exposed to computer interfaces before and have an intuitive grasp of how buttons panels menu bars and the like should all work. GUI Bloopers is about the things that user interface designers often get wrong when they try and transfer this intuitive knowledge into an explicit design. The book is also extremely fun to read. It brings up examples of bloopers in real-life and often well-known applications with often funny results. Sometimes I read it as a form of therapy.

The end result of having an application that obeys platform conventions is that it feels very familiar and natural. The user can start using the application right from the start without feeling disoriented or having to think about what he's doing. In the past there were many people who had never used a computer before. These days most people interact with a computer every day. If you build an application in such a way that it works very similarly to other applications you will have drastically reduced the learning time and people will have a very warm fuzzy feeling of familiarity with your application right from the start. On the other hand if your application works in a completely weird and unexpected way it will make the user feel as if they're starting over from scratch again. It will be disorientating and confusing and that's not a a good first impression to make. Let's not be bush-league.

If you've mastered the other two books it's time to move on to the advanced stuff. The last book is all about flow. Jef Raskin's book The Humane Interface is an extremely detailed and often formal look at flow. Flow is the feeling you get when you're concentrating on what you're doing rather than how you're doing it. When you're in flow the computer disappears. Your mind melds with a computer and everything you want to do just suddenly and effortlessly just happens. You're still using a computer but it has become an extension of your being. In the same way that a painter's brush becomes an extension of the painter or a hockey players stick becomes an extension of the hockey player. It's where an idea or desire effortlessly flows into a series of actions to accomplish it. Jef Raskin's book is all about writing computer interfaces that encourage this feeling. I'll give you an example of what I mean: Dialog boxes suck for flow.

So those are my three books in roughly the order of importance. I think I'll end my post here. I'm sure you got a lot of reading to do.

My Pet Computer Mice

I always try to spare no expense when buying monitors, keyboards and mice but in the last few years it's been difficult to figure out which mouse to buy.

In the days of ball mice I tended to get a high-end Logitech mouse. I must admit that Logitech is my favorite brand-name for mice. I've had so many bad experiences with other mice that I just tend to ignore any other brand. That said, Microsoft occasionally makes a good mouse. The one major problem with Microsoft is they seem to have no common sense. Every time I use a Microsoft mouse I wonder what's gone wrong with the mouse wheel. Microsoft mice often don't have a clicky mouse wheel. Their mouse wheels are extremely smooth as if the mouse wheel was an analog device. There are many situations out there where you need that precise clicky control of the mouse wheel and for Microsoft to ignore this just makes me suspect their sanity.

On the other hand, Logitech does silly things with the mouse wheel as well. I have a Logitech MX Revolution mouse. Its mouse wheel is a mechanical marvel. It can either be a clicky style mouse wheel or smooth scrolling mouse wheel depending on how you configure it in the software. I'm not sure how exactly they do this but it's really cool. There's even a special mode where the mouse wheel will be clicky until spun fast enough where it'll become a free wheel and turn with no resistance whatsoever. As soon as the wheel stops spinning it becomes a clicky wheel again. This is extremely addictive behavior. You essentially think nothing of scrolling rapidly through documents and in my opinion I think every radiologist who uses InteleViewer should have one of these things. I've seen how much radiologist use the mouse wheel when they use our product. This mouse wheel would be a godsend.

The one major problem with the Logitech MX Revolution mouse wheel is it surprisingly hard to click. On most mice it is easy to click the middle mouse button (which is the mouse wheel itself) but on the MX the mouse wheel takes an unexpectedly large amount of force to click. Add to this a mouse wheel that rotates easily (even in clicky mode) and more often than not you'll accidentally scroll when you click.

The Logitech MX Revolution mouse is also quite heavy. This is because it's a wireless mouse with it's own battery, air supply and guest washroom. So that shouldn't be too surprising. I don't like heavy mice and almost took it back because of its sheer weight. On the other hand the weird shape of the MX Revolution mouse isn't just there to make it look like a spaceship. It's incredibly comfortable. Holding onto one is like putting your hand in glove. It's so very, very nice.

The Logitech MX Revolution 's wireless reception isn't so nice, though. I'm in a apartment block where there's quite a lot of radio traffic. The wireless reception of the mouse is so bad that I had to get a USB extension cord to bring the wireless receiver within 30 cm of the mouse itself. Only then could I get decent performance. With the transmitter any further away the mouse tended to pause while being used. This is annoying while doing ordinary office tasks and completely infuriating when playing StarCraft II.

The Logitech MX Revolution doesn't work very well for games either. I'm not sure what Logitech did. I figure it's either the latency added by the wireless link or some sort of smoothing system in the mouse itself. The pointer just doesn't feel connected to the mouse. It sort of, lazily wallows around the screen in some sort of pot-like daze. It's quite a shame too because it tracks quite well otherwise. I couldn't get the mouse to skip or jump when moved quickly like some of the cheaper optical mice.

Speaking of cheaper optical mice I also have a Logitech Optical Mouse. This one doesn't have a spcial name. It's essentially the cheapest optical mouse that Logitech makes. It's a fantastic mouse! It's light, has a good mouse wheel and a great shape. What's more, the cursor feels like it's connected to the mouse unlike the Logitech MX Revolution. The only thing bad about this mouse is if you move it really fast the cursor gets confused and shoots off in the opposite direction. This makes it completely useless for games. I like this mouse so much and it's so cheap that I buy many of them and give them to my friends. Many of them have terrible mice that are so bad that I just take pity on them. If you want me to fix your computer you should at least get a decent mouse for me to use.

Between the lazy, disconnected performance of the Logitech MX Revolution and the Logitech optical mouse's unsuitability for games I was left with a hole in my life. I needed a mouse for StarCraft II! I think I might have found it in the steelseries XAI Laser Mouse.

I just got this mouse recently and its been consistently impressing me. The cursor feels connected to the mouse to an extent I don't think I've ever experienced. It's also light and has a shape very similar to the Logitech optical mouse. It is a bit bigger than the Logitech but it's also more comfortable. I must admit I am a complete addict of this mouse shape and while the MX Revolution is capable of giving me an orgasm every time I grab a hold of it I still keep going back to the traditional shape. Though at $99 I'm not going to give it away to friends for free. It's also not wireless. Which I like but might be a dealbreaker to some people.

Steelseries, the manufacturer, seem to take their mice extremely seriously. They don't ship any software in the box. You have to go and download it. I suspect this is because they don't want their clients to have out-of-date software although at $99 I expect to see some obsolete software in the box. Give me a CD you cheap bastards!

To be fair, the mouse will work fine out of the box. Steelseries actually advertises it as a driverless mouse. That is, a mouse that doesn't need drivers rather than a mouse that doesn't actually ship with the drivers. When you download the "driver" software, however, things start to get interesting.


The software is pretty well done on the whole although I noticed a repaint error or two. The software contains many delightful settings as well as an extremely informative manual attached to the side of the window. This is a good thing as I had no idea what any of the settings did until I read the manual. A full review of all the different settings is way beyond what I'm prepared to do but thankfully there are others to fill that gap. My only complaint, if it is a complaint, is that the software was done using anesthetic that a hard-core gamer would love. Black and orange! Yes! We could probably do that for InteleViewer. The radiologists would love it. Peow peow.

This mouse has made me very happy. It was made to the exacting standards of gamers but also works incredibly well for office work. Most importantly, it actually tracks properly! Hooray! I think I found a new favorite.

Using my psychic powers I can guess that someone's about to ask me if I've ever used any of Logitech's gaming mice. To be fair, I've never had the courage. They look massive! I'm not sure I would like using a mouse that big. To be sure I grabed a large potato and dragged it across the mouse pad a few times clicking on its eyes. It made a mess as I'm sure the gaming mouse would do. Want to clean up the mess? What better way than to use a mouse that looks like a bar of soap. That's my philosophy.