CS 533 Name:                                   

Spring 2024

Homework 4 NetID:                                   

Assigned: 4/4/2024

Due: 4/30/2024 UIN:                                   

This homework contains 5 pages (including this cover page) and 4 questions.

Please clearly print or typeset your answers.

Note: up to 5 points (out of 50) may be deducted for illegible submissions

Problem Breakdown

1. ‌(14 points) Software Reliability

   1. (2 points) Your lab partner claims that on-the-fly bug detection schemes are overkill when it comes to debugging parallel programs. If you know the program inputs at the time a bug occurred, you can feed them into a static tester to perform diagnosis, he states. Is he right? (Consider different bug types to evaluate his statement).

   2. (12 points) The following questions relate to paper 9d 1

      1. In this system the main memory is protected by parity. Why is it still necessary to create checkpoints? Why is it necessary to perform two step checkpointing?

      2. Why does the system have to maintain multiple checkpoints?

      3. What types of applications incur the most overhead on ReVive? What types of applications have the least amount of overhead?

      4. Why does distributed memory mirroring have less performance overheads than using distributed parity?

      5. After phase 3 of the recovery from an error is complete, what are the ways performance can still be hurt (assuming that no more errors occur)?

      6. Explain why if no logging bits are included in the cacheline recovery, logs have to be processed in reverse order?

2. ‌(9 points) Operating System/Database

   1. (2 points) What sort of architectural support help or hurt the following:

      1. OLTP

      2. DSS

   2. (7 points) Refer to paper 10e 2 when answering the following questions:

      1. What are the three application characteristics that determine the effectiveness of cache affinity? Explain the rationale for each.

      2. Give the details of the affinity scheduling algorithm the paper describes. What is the complex version of their algorithm?

      3. Why is their affinity scheduler no better than increasing the time quantum for scientific applications?

      4. What are some drawbacks the authors mention about their scheduler?

      5. What is the difference between time quantum and effective time slice? How does the scheduler usually handle this discrepancy?

3. ‌(13 points) Interconnection Networks/MPI

   1. (2 points) Which interconection architectures are possible in a direct network if each router has

      1. 1 input channel and 1 output channel?

      2. 2 input channels and 2 output channels?

   2. (2 points) Discuss the main sources of overhead in emulating message passing on a shared memory machine with a write-invalidate cache coherence protocol.

   3. (2 points) Cannon’s algorithm is message-passing based matrix multiplication al- gorithm for 2D torus systems. Is it more efficient than shared-memory based algo- rithms? Please explain.

   4. (7 points) Several architectures have been proposed which embed the fundamentals of message passing directly in hardware. One of the more notable designs is the J-machine 3

      1. Why is tagged memory helpful in the J-Machine?

      2. What are futures? How are they supported in the J-Machine?

      3. Describe the network used in this system. How is deadlock prevented?

      4. How does the J-Machine try to elminate the usual overhead associated with

4. (14 points) Dataflow Architectures

   1. (7 points) The following questions relate to paper 12a 4

      1. What are the two fundamental issues with using Von Neumann machines for parallel processing? Explain the ways dataflow machines solve these problems.

      2. How can deadlock occur on the hybrid machine?

      3. Why is the hybrid machine considered a mixture of a Dataflow and Von Neu- mann Architecture?

      4. Describe the author’s approach for preventing deadlock with using scheduing quanta.

      5. How does the hybrid architecture enable fast context switching?

   2. (5 points) The following questions relate to paper 12b 5

      1. How does one program a dataflow machine?

      2. If a code is reentrant (loops, recursion), what are ways to ensure correct exe- cution? What are the overheads associated with each technique?

      3. What are ways the author suggests to limit the amount of tags needed?

      4. Describe the matching unit and fetching unit operations in the Manchester Datflow Machine.

‌4Robert A. Iannucci “Toward A Dataflow/Von Neumann Hybrid Architecture” ISCA, 1998.‌

5Arthur H. Veen “Dataflow Machine Architecture”, ACM Computing Surveys, 1986