关键词 > CSCI-UA.0480-051

CSCI-UA.0480-051: Parallel Computing Midterm Exam

发布时间：2023-03-11

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI-UA.0480-051: Parallel Computing

Midterm Exam (Mar 9th, 2023)

Total: 100 points

Important Notes- READ BEFORE SOLVING THE EXAM

• If you perceive any ambiguity in any of the questions, state your assumptions clearly and solve the problem based on your assumptions. We will grade both your solutions and your assumptions.

• This exam is take-home.

• The exam is posted on Brightspace, assignments section, at the beginning of the Mar 9th lecture.

• You have up to 23 hours and 59 minutes from the beginning of theMar 9th lecture to submit on Brightspace (in the assignments section). That is, you must submit before 2pm Friday March 10th.

• You are allowed only one submission, unlike assignments and labs.

• Your answers must be very focused. You may be penalized for wrong answers and for putting irrelevant information in your answers.

• You must upload a pdf file.

• Your answer sheet must have a cover page (as indicated below) and one problem answer per page (e.g. problem 1 in separate page, problem 2 in another separate page, etc).

• This exam has 3 problems totaling 100 points.

• The very first page of your answer is the cover page and must ONLY contain:

- You Last Name

- Your First Name

- Your NetID

- Copy and paste the honor code showed in the rectangle at the bottom of this page.

Honor code (copy and paste to the first page of your exam)

• You may use the textbook, slides, and any notes you have. But you may not use the internet.

• You may NOT use communication tools to collaborate with other humans. This includes but is not limited to G-Chat, Messenger, E-mail, etc.

• Do not try to search for answers on the internet it will show in your answer and you will earn an immediate grade of 0.

• Anyone found sharing answers or communicating with another student during the exam period will earn an immediate grade of 0.

• “I understand the ground rules and agree to abide by them. I will not share answers or assist another student during this exam, nor will I seek assistance from another student or attempt to view their answers.”

Problem 1

a. [10] State five reasons why two threads, executing the same piece of code but on different data, starting execution at the same time on two different cores may not finish at the same time.

b. [8] Suppose we have a sixteen-core processor. Fill-in the following table for each scenario.

If each one of the 16 cores is	The maximum number of *threads* that can execute simultaneously on the whole processor (i.e. on all the cores together) is:	The maximum number of *processes* that can execute simultaneously on the whole processor (i.e. on all the cores together) is:
Only pipeline
Superscalar with no hyperthreading and each core has eight execution units
Two-way hyperthreading without branch prediction
Two-way hyperthreading with branch prediction

c. [7] “Dealing with critical sections among different processes, in MPI for example, can bring the performance down” . Is this statement true or false? Justify.

Problem 2

Assume we have the following task flow graph where every node is a task and an arrow from a task to another means dependencies. For example, task B cannot start before task A is done.

The following table shows the time taken by each task in cycles as well as the total number of machine code instructions executed by each task. An arrow, which indicates dependence, implies a communication between the two tasks.

Task	Total time taken (in cycles)	#instructions executed
A	10	100
B	5	50
C	15	40
D	10	80
E	5	30

a. [8] Cite all spans in the above DAG., and for each one, specify the number of tasks in the span, total number of instructions in the span, and total time (in cycles) of the span.

b. [13] Calculate the CPI for each task in the DAG. Then specify which task is the best in terms of CPI. Show all calculations to get full credit.

c. [5] Suppose we have four identical cores. What is the best assignment of tasks to cores to achieve the best speedup relative to sequential execution? Use as few cores as possible to get the highest possible speedup. That is, you may or may not have to use all the available cores. Your answer must be like (task x assigned to core 1 and tasks y assigned to core 2, etc.). Assume the cores have a fixed frequency, that does not change, of 4 GHz.

d. [5] What is the efficiency achieved using the assignment you specified in question c above? Show the steps.

e. [4] We know that a four-way hyperthreading core can execute four threads at the same time. With four cores each one is just a superscalar (i.e. with no hyperthreading) we can also execute four threads at the same time. State two conditions that make the four-way hyperthreading core performs better than the four cores. Assume we have four threads.

Problem 3

A programmer is developing a program for a company. The programmer has parallelized 80% of the program. For this problem 3, assume the number of threads = number of cores. Also, assume each core is just pipelined with no superscalar or hyperthreading capabilities.

a. [10] The programmer has been informed that the problem size will remain the same no matter how many cores will be used. What is the expected speedup on 8 cores? Show your steps. Make any needed assumptions if any. Round the speedup to the nearest single digit after the floating point.

b. [10] Keeping the assumption that the problem size will remain fixed, if we increase the number of cores from 8 to 16, what will be efficiency with 16 and with 8? What is your interpretation of the change of efficiency?

c. [10] For the 20% of the program that the programmer couldn’t parallelize, is there anything that we can do to make those 20% a bit faster? If yes, specify how. If not, explain why not.

d. [10] Since Amdahl’s law is just an approximation. Then, we may wonder why it is useful for. Specify two scenarios showing the usefulness of Amdahl’s law.