• CSF@JHU
• Home
• Syllabus
• Schedule
• Assignments
• Resources

Exam 2 practice questions

A: x86-64

A1)

Consider the following C function prototype:

void str_tolower(char *s);

The str_tolower function modifies a C character string so that each upper case letter is converted to lower case.

Show an x86-64 assembly language implementation of this function. Note that the ASCII codes for upper case letters are in the range 65–90, and the ASCII codes for lower case letters are the range 97–122. Characters that aren’t letters should not be modified.

B: Code optimization, performance

B1)

Consider the following function:

// combine a collection of strings into a single string
char *combine(const char *strings[], unsigned num_strings) {
  // determine amount of space needed
  size_t total_size = 0;
  for (unsigned i = 0; i < num_strings; i++) {
    total_size += strlen(strings[i]);
  }

  // allocate buffer large enough for all strings
  char *result = malloc(total_size + 1);

  // copy the data into the buffer
  result[0] = '\0';
  for (unsigned i = 0; i < num_strings; i++) {
    strcat(result, strings[i]);
  }

  return result;
}

Explain the performance problem with this function and how to fix it.

B2)

Consider the following C code (assume that all variables have the type uint64_t):

a = b * c;
d = e * f;
g = h * i;
j = a * d * g;

Assume that

• the CPU is superscalar
• all of the variables refer to CPU registers
• the CPU has two integer multipliers, each of which is fully pipelined
• a single multiplication requires 3 cycles

What is the mininum number of cycles required for the computation to complete? Justify your answer.

C: Caches

C1)

Assume a system with 32 bit addresses has a direct mapped cache with 256 KB total capacity (2¹⁸ bytes) and a 32 byte block size. Show the format of an address, indicating which bits are offset, index, and tag.

C2)

Assume a system with 32 bit addresses has a 4-way set associative cache with 512 KB total capacity (2¹⁹ bytes) and a 64 byte block size. Show the format of an address, indicating which bits are offset, index, and tag.

C3)

Assume a system with 32 bit addresses and a fully associative cache with 512 KB total capacity (2¹⁹ bytes) and a 64 byte block size. Show the format of an address, indicating which bits are offset, index, and tag.

C4)

Consider use of a 2-way associative cache that addresses blocks of 4 bytes, with 4 sets in a 8-bit address space.

(a) How are the 8 bits of the address used as tag, index, and offset for the cache?

(b) Consider a following sequence of requests to the cache. Enter the tag for each cache slot after each request in the table below. Assume FIFO as caching strategy (do not worry about internal bookkeeping of timestamps). Note: use " to indicate that the value in the slot is identical to the previous value.