Question

In this exercise we show the definition of a web server log and examine code optimizations to improve log processing speed. The data structure for the log is defined as follows:

struct entry {

int srcIP; // remote IP address

char URL[128]; // request URL (e.g., “GET index.html”)

long long refTime; // reference time

int status; // connection status

char browser[64]; // client browser name

} log [NUM_ENTRIES];

Assume the following processing function for the log:

topK_sourceIP (int hour);

5.19.1 Which fields in a log entry will be accessed for the given log processing function? Assuming 64-byte cache blocks and no prefetching, how many caches misses per entry does the given function incur on average?

5.19.2 How can you reorganize the data structure to improve cache utilization and access locality? Show your structure definition code.

5.19.3 Give an example of another log processing function that would prefer a different data structure layout. If both functions are important, how would you rewrite the program to improve the overall performance? Supplement the discussion with code snippets and data.

For the problems below, use data from “Cache performance for SPEC CPU2000 Benchmarks”(http://www.cs.wisc.edu/multifacet/misc/spec2000cache-data/) for the pairs of benchmarks shown in the following table.

a.	Mesa/gcc
b.	mcf/swim

5.19.4 For 64KiB data caches with varying set associativities, what are the miss rates broken down by miss types (cold, capacity, and conflict misses) for each benchmark?

5.19.5 Select the set associativity to be used by a 64KiB L1 data cache shared by both benchmarks. If the L1 cache has to be directly mapped, select the set associativity for the 1 MiB cache.

5.19.6 Give an example in the miss rate table where higher set associativity increases the miss rate. Construct a cache configuration and reference stream to demonstrate this.

Short answer

5.19.1 srcIP and refTime fields. 2 misses per entry.

5.19.2 Group the srcIP and refTime fields into a separate array.

5.19.3 peak_hour (int status);

5.19.4 Conflict and compulsory misses are not affected by associativity. And the selection varies with the data set used.

5.19.5 The set associativity will vary with the data set used.

5.19.6 The“Cache performance for SPEC CPU2000”has many examples like apsi/mesa/ammp/mcf.

Cache:4-block caches, direct-mapped vs 2-way LRU.

Reference stream: 1 2 2 6 1

Step-by-step solution

Determine the code optimization to improve the log processing speed.

In a multiprocessor system or a system with larger data, the log processing is difficult with lesser code.

The log instruction will be optimized in a way that they get the process log sooner.

By comparing and merging the fields of the log table, the data can be accessed.

Determine which fields in a log entry will be accessed and how many cache misses occur.

5.19.1 Given log structure is as follows:

struct entry {

int srcIP; // remote IP address

char URL[128]; // request URL (e.g., “GET index.html”)

long long refTime; // reference time

int status; // connection status

char browser[64]; // client browser name

} log [NUM_ENTRIES];

The srcIP and the refTime fields will be used to access the given log processing function.

Here, assuming a 64-byte cache block, and no prefetching 2 misses per entry occur.

Determine how the data structure can be reorganized to improve cache utilization and access locality.

5.19.2 To improve the cache utilization and the access locality, group the srcIP and refTime fields into a separate array.

The struct code with srcIP and the refTime into separate array as follows:

struct entry {

long long srcIP refTime [1000][1000000]; // remote IP address and reference time grouped

char URL[128]; // request URL (e.g., “GET index.html”)

int status; // connection status

char browser[64]; // client browser name

} log [NUM_ENTRIES];

In the above structure, the srcIP and the refTime fields are grouped as a two-dimensional array. This improves the cache utilization and the access locality by providing the index for each field. In an array, data can be accessed faster by the array index, which improves the access locality.

Determine how the code can be rewritten to improve overall performance.

5.19.3

Given pairs of benchmarks are:

a.	Mesa/gcc
b.	mcf/swim

The array is the data structure that can be used as a log processing function.

peak_hour (int status);

peak_hour will provide the peak time in which the data is accessed and this will improve the correctness of the result.

The above code will return the peak hours of the given status. Group srcIP, refTime, and status together.

Code snippet:

struct entry {

long long srcIP refTime [1000][1000000];

char URL[128]; // request URL (e.g., “GET index.html”)

peak_hour(int status);// connection status

char browser[64]; // client browser name

} log [NUM_ENTRIES];

Determine the miss rate.

5.19.4

Conflict miss and compulsory misses do not occur and get affected by full associative caches.

The capacity miss rate is computed by subtracting the compulsory miss rate and the fully associative miss rate from the total miss rate. Conflict miss rate can be computed by subtracting the cold and newly computed capacity miss rate from the total miss rate.

The values will be reported as per the miss rate per instruction.

The miss rate will vary depending on which data set is used.

Determine set associativity.

5.19.5

Set associativity will be determined based on the dataset used. Since no specific dataset is given, it cannot be found. It will vary depending upon the data set used.

Determine the miss rate table, cache configuration, and reference stream

5.19.6

The“Cache performance for SPEC CPU2000”has many examples like apsi/mesa/ammp/mcf for miss rate table. They can’t be fit into the document since they are larger.

Cache:4-block caches, direct-mapped vs 2-way LRU.

Reference stream: 1 2 2 6 1