4.3 The relationship between the number of processes and the number of colorings

In this section, we show the performance difference as the number of colors changes.

By $n$ coloring, the single severely conflicting line in a current scheduler is distributed into $n$ lines. To minimize total cache conflicts, the number of colors should satisfy the following equation:

$$c \ge \frac{p}{(s/8 [KB])}$$ (3)

In this equation, c, p, and s are the number of colors, the number of processes, and the cache size in KB, respectively. 8KB is the Linux kernel stack size. Ideally, a cache memory can store $s/8$ kernel stacks. For example, in the case of 1024 processes running on the 512KB cache system, 16 or more colors can prevent conflicts.

Figure 8: The number of bus transactions and performance changing the number of colorings

To verify the model, we measured the performance varying both the number of colors (4, 8, 16, and 32) and the number of httpd processes (256, 512, and 1024). We used 512KB and 1024KB L2 cache system for the experiment. Figure 8 shows the result of web processing performance and the number of bus transactions. In these graphs, c $n$ denotes $n$-coloring kernel.

At first, we discuss the case of 512KB cache size. Using the equation (3), c = 4, 8, and 16 colors should be required as a minimum in the case of 256, 512 and 1024 running processes, respectively. As shown in Figure 8 (a), the result almost confirms this requirement: When the number of the coloring is less than the above requirement, the performance is not improved. As the number of coloring increase above the value $c$ of the equation (3), the number of bus transactions for the colored line sharply decreases and the performance improves.

The coloring effect on 1024 KB cache size showed a similar relation between the performance and the number of colorings. 2, 4, and 8 colorings should be used when 256, 512, and 1024 processes are running on a system, respectively. The graph in Figure 8 (b) shows that the number of bus transactions decreases significantly when more than 2, 4, and 8 coloring is used and the total performance improves.

In order for the coloring scheme to be effective, the number of colors must be larger than the threshold selected by equation (3). Otherwise, the effect of the coloring scheme is hindered by the side-effect of increasing bus transactions with higher cache conflicts.