Synchronization, Communication, and Scheduling in Parallel Systems

• Synchronization Algorithms (MCS paper)
  • There is a bug in MCS barrier algorithm on Page 19 of the paper. First 10 folks to (independently) report the bug and the fix correctly (no credit if the bug reported OR the fix reported is incorrect) correctly to David Hilley will get 1% credit towards the course total of 100%.
  • The MCS paper claims that the MCS algorithm may be the best for large-scale cache coherent multiprocessors. Argue why this may not be necessarily true. [Hint: See the discussion of barrier algorithm implementation and resulte in pages 8-10 of the "scalability study of KSR-1" paper which is a suggested reading for project 2.
  • MCS paper shows results that MCS barrier does better than tournament on a bus-based shared memory machine like the Sequent Symmetry. Explain why this is so.
• LRPC paper
  • Come up with the data structures and pseudo code that the kernel has to maintain for LRPC.
  • Assume a server exports a function:

    int foo(int a[30]; float b[20]);

    The server allows a max of 10 simultaneous calls per client.
    • a) Sketch the details of an import call from a client with respect to foo assuming the call succeeds
    • b) Sketch the details of an actual call from the client to the procedure foo clearly detailing what interaction goes through the kernel and what interactions go directly happen between the client and the server.
  • LRPC on a multiprocessor suggests having multiple domains pre-loaded into different processors of an SMP to service client calls. Why was this a good choice for the platform (Firefly multiprocessor) that they targeted for their implementation.
  • Tornado paper argues that the LRPC approach (server domains on multiple processors waiting for work) would be prohibitive for today's multiprocessors. Justify their argument quantitatively assuming a modern SMP (larger caches, larger disparity between cache and memory access times) with an invalidation-based cache coherence protocol. Present your own arguments why this may still be a good decision in modern multiprocessors.

    [Hint: Come up with pathological examples where the LRPC results in performance win and performance loss assuming an SMP with an invalidation-based cache coherence protocol.]

• Scheduling
  • Assume a multiprocessor with 4 processors; 10 tasks ready to run; Using the notation

    A{superfix task}{suffix processor}

    to denote affinity for a particular task to a particular processor,
    • (a) come up with an execution history for tasks on each processor that would result in a different schedule under each of FCFS, FP, LP, MI, LMI (with only 2 associations per task), and LMR schedules.
    • (b) rank the scheduled you come up with in terms of increasing variance for response times of the schedules.
  • Come up with data structures and pseudo-code for each of FCFS, FP LP, MI, LMI, and LMR schedulers.
• Tornado
  • Starting with Figure 3, first discuss for each object in the path of the memory manager which clustering strategy (a single shared object, partial replication, full replication, partitioned reps) is most appropriate.
  • Building on Q1, develop the high level data structures and pseudo-code for each of the clustered objects that implement a memory manager. Explicitly state the level of contention for the reps in your design (i.e. is it across the entire system, a cluster or processors, threads running on the same processor, etc.)? Based on this discussion argue the scalability of your implementation.