18-548/15-548 Fall 1998

Homework 11:

Due MONDAY November 30, 1998


Problem 1: Error Coding

A Hamming SEC code includes 11 data bits and 4 check bits according to the below table:

d11 d10 d9 d8 d7 d6 d5 c4 d4 d3 d2 c3 d1 c2 c1
S4 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
S3 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0
S2 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
S1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

What are the syndrome equations?


Problem 2:

Which of the following two approaches to spin locks will result in better overall system performance, and why? Assume that you are running on a system which has 16 single-CPUscalar-issue processor boards plugged into a backplane. Each processor has its own cache, with snoopy coherence done over the single shared bus with sequential consistency. Both routines use a common test_and_set subroutine as follows:

int test_and_set(volatile int *addr)
{ /* sets address to 1, returns previous value 
   *   1 is locked, 0 is written elsewhere to free lock
   */
  int old_value; 
  old_value = swap_atomic(addr, 1); 
  return(old_value); } 

Approach 1:

void lock_a(volatile int *lock_status) 
{ while (test_and_set(lock_status) == 1); }

Approach 2:

void lock_b(volatile int *lock_status)
{ while (test_and_set(lock_status) == 1)
   { while (*lock_status) == 1); }


18-548/15-548 home page.