\"Consider an omega network that connects p processors. Define a function f that
ID: 3809380 • Letter: #
Question
"Consider an omega network that connects p processors. Define a function f that maps p = [0, 1, …, p-1] onto a permutation P’ of P (that is, P’[i] = f(P[i]) and P’[i] P for all 0 i < p). Think of this function as mapping communication requests by the processors so that processor P[i] requests communication with processor P’[i]."
(1) How many distinct permutation function exist?
(2) How many of these functions result in non-blocking communication?
(3) What is the probability that an arbitrary function will result in non-blocking communication?
Explanation / Answer
a)
Number of input-output mapping : p! [p factorial]
b) Number of switch for each stage : p/2
Number of permutation each stage : 2p/2
Number of stage : log2p
Number of non-blocking communication : 2(p/2)*(log2p).
c)
Probability of non-blocking communication : (2(p/2)*(log2p)) / (p!)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.