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:

d₁₁ d₁₀ d₉ d₈ d₇ d₆ d₅ c₄ d₄ d₃ d₂ c₃ d₁ c₂ c₁

S₄ 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

S₃ 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0

S₂ 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

S₁ 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.