Dept. of Systems & Computer Eng. Carleton University
SYSC 5207 Distributed Systems Engineering (Fall 2021)

Assignment 1

Answer to the point. Show your work and justify your answers.

1. Consider the following computation described by a process set P and a set of
precedence relationship <.

P = {P1, P2, P3, P4, P5, P6, P7, P8, P9}

<. = {(P1, P3), (P1, P4), (P4, P5), (P2, P6), (P2, P7), (T8, T9)}

Draw the precedence graph for the computation.

2. Consider the precedence graph described in question 1 with the following domains and
ranges for its processes:

Domain Range
P1 Φ {M1, M3}
P2 Φ (M2}
P3 {M1} {M3}
P4 {M1} Φ
P5 {M1} {M3}
P6 {M2} Φ
P7 {M2} {M1}
T8 {M4} {M5}
T9 Φ {M5}

Is the computation determinate? If yes, is it maximally parallel?
If it is not determinate, identify at least one process pair that leads to the computation not
being determinate and explain why (be brief).

3. Consider the following precedence graph











T1
T2
T4
T3

T5
T7
T6
T8




The task execution times are:


Task T1 T2 T3 T4 T5 T6 T7 T8
Execution
Time
5 5 5 5 10 10 10 10


(i) Draw the parallelism profile
(ii) Determine the pi and Pi values for the computation for all relevant values of i. Plot
the shape function.
(iii) What is the speedup for the no. of processors = 2 and a Processor Sharing scheduling
discipline?

[For (i) and (ii) in addition to the graph you must provide a table containing all the x and
y axis values for the respective graph]

Instructions: Please submit a PDF file. Type written assignments are preferred. A scanned copy
(converted into PDF) of a neatly hand written document is acceptable. Put your name and
student number on every page (including the cover page) of the assignment. Please remember that
your marks will depend on the quality of your presentation.

DUE: October 21, 4:00 PM



















































































学霸联盟