Archive for the ‘Uncategorized’ Category

How many cores do we really need

Sunday, November 2nd, 2008

After CPU manufacturers have hit the frequency wall, adding cores became the new way of making “better” processors. However, there does not seem to be much discussion on whether additional cores actually improve performance for common, real-life use cases. After a release of a new CPU we see a slew of performance reports most of which use synthetic benchmarks. If those benchmarks are able to take advantage of additional cores then we often see significant performance improvements as the number of cores increase.

While it may be hard to conduct a precise performance comparison of real use cases (e.g., how does one measure the performance of a word processor?), we can determine a set of common applications used in a particular setting. We can then analyze the typical load for each of these applications and reason whether additional cores will improve their performance.

It seems natural to divide all computer use-cases into three broad categories: Desktops (including laptops), Workstations, and Servers. I am intentionally ignoring the high-performance computing (HPC) as being too specialized. Typical applications for a desktop machine include office suite, email client, web browser, instant messenger, audio/video player, and a photo management application. Desktops for home use normally also include games.

The common property of most of these applications is that they are user input and/or network-bound. That is, most of their time they are waiting for user input or data arriving over the network. The few applications that have a CPU-intensive workload (e.g., audio/video player and photo management application) are not easily parallelizable. Only the photo management application and games have the potential for performing several CPU-intensive tasks concurrently (e.g., enhancing or resizing a bunch of photos). For games, however, a more powerful graphics card is often a more effective and cheaper way to increase the performance.

From this analysis it becomes quite obvious that a typical desktop CPU usage pattern consists of a mostly idle state with some bursts of activity usually associated with responding to user input or availability of network data. It is also clear that adding a second or any subsequent core to a desktop won’t improve the performance of its common applications while a better-performing single-core CPU probably would. A second core might be beneficial to a few applications and can also improve the responsiveness of the system in the case of a CPU-intensive task running on the background (e.g., batch photo processing). Furthermore, having extra cores in a power-constrained machine (e.g., laptop) can actually be a disadvantage unless extra cores can be completely shut down.

Some of the alternative paths used to improve the performance of desktop systems include the higher-performance memory subsystem, such as faster memory buses and larger caches as well as specialized processors. An example of the latter approach is the use of the modern GPU’s stream processing capabilities in general applications.

Besides the desktop applications mentioned above, workstations usually include one or more specialized applications, such as compilers, CAD applications, or graphics/video/sound editing software, which normally have CPU-intensive workloads. Having additional CPUs and/or cores in a workstation often improves the performance of the specialized application but to which degree depends on how well the workload can be processed in parallel. For example, C and C++ compilation can often be performed in parallel and, on big projects, one can add extra cores and achieve better build times until a memory or disk subsystem becomes a bottleneck. On the other hand, single-stream video encoding can be a lot harder to parallelize.

Servers are where multi-core CPUs have the most potential. Server applications are naturally parallelizable since they often need to perform the same or similar tasks concurrently. However, some server applications, for example database management software, may have a hard time scaling to a truly large number of CPU/cores because of the need for exclusive access to shared resources. Other applications, for example web servers and stateless application servers, can take advantage of truly massively-parallel systems. Virtualization software is another class of applications which can benefit greatly from multi-core CPUs.

Intuitive explanation of the Monty Hall problem

Sunday, May 11th, 2008

Yesterday I went to see 21 where one of the scenes brings up the Monty Hall problem: there are three doors behind which there are a car and two goats. You choose a door with the goal of winning the car. Then the host opens one of the remaining doors which hides a goat. The question is whether it is to your advantage to switch your choice to the other door. The answer is yes (and yes, I thought it does not matter while watching the movie). When asked to explain why it is a good idea to change the door the main character utters some gibberish about all the variables being changed, etc. Afterwards I checked this problem out on Wikipedia (follow the link above) which gave a few strict proofs making it clear that indeed changing the door increases your chances of winning the car by 1/3. While the formal proofs do their jobs just fine I always prefer to have an intuitive feeling of why a seemingly counter-intuitive answer is actually correct. In this case I wanted to understand what changes once the host opens one of the doors, what extra information is added that makes the difference.

The part of the rule which says that the host has to reveal the other goat brings in the extra information. This happens in the case when you initially selected the door with a goat behind it. In this situation the host is forced to eliminate the other goat: he cannot open the door you have selected and he cannot reveal where the car is. In other words we have two possible outcomes:

  • if you selected a goat then the remaining door hides the car
  • if you selected the car then the remaining door hides a goat

The probability of initially selecting the goat is 2/3 (two doors out of three hide goats) and the car — 1/3. Thus it is more likely that you will first select a goat instead of the car. And in this more likely case the host is forced to single-out the door which hides the car. Thus changing your selection gives you a better chance of winning the car.

Note also that the probability of your initial choice being the car remains 1/3 even after the host opened one of the doors. It is the probability of the other remaining door hiding the car that has changed (from 1/3 to 2/3) due to the rules of the game forcing the host not to reveal the car.