Introduction to Multiprocessors - Fundamentals of Computer Organization and Architecture - page 256

(c) An MIMD computer system having 64 independent elements accessing
a shared memory through an interconnection network. Ignore the
communication time.
(d) Repeat (b) and (c) above if the communication time takes two time units.
9. Provide a concise discussion on the suitability of each of the four attributes of
interconnection networks (mode of operation, control strategy, switching
mechanism, and topology) for each of the four different interconnection net-
works shown in Figure 11.1. Make sure that you justify the suitability of a
given attribute to a given interconnection network.
10. Consider the case of a multiprocessor system consisting of N processors.
Assume that the time needed for each processor to execute a given critical
section is t and that f represents the fraction of operations that can be paral-
lelized. Assume also that a single processor will need a time T to execute the
same task. Show that the total execution time using N processors is given by

f T
N þ t :

T N ¼

f ) T þ

(1

What is the number of processors, N, needed in order to minimize the total
execution time T N .

REFERENCES AND FURTHER READING

S. Abraham and K. Padmanabhan, Performance of the direct binary n-cube network for multi-
processors, IEEE Trans. Comput., 38(7), 1000-1011 (1989).
P. Agrawal, V. Janakiram and G. Pathak, Evaluating the performance of multicomputer
configurations, IEEE Trans. Comput., 19(5), 23-27 (1986).
G. Almasi and A. Gottlieb, Highly Parallel Computing, Benjamin Cummings, Redwood City,
CA, USA, 1989.
K. Al-Tawil, M. Abd-El-Barr and F. Ashraf, A survey and comparison of wormhole routing
techniques in mesh networks, IEEE Network, 11(2), 38-45 (1997).
L. Bhuyan, Q. Yang and D. Agrawal, Performance of multiprocessor interconnection net-
works, IEEE Comput., 22(2), 25-37 (1989).
W.-T. Chen and J.-P. Sheu, Performance analysis of multiple bus interconnection networks
with hierarchical requesting model, IEEE Trans. Comput., 40(7), 834-842 (1991).
S. Dasgupta, Computer Architecture: A Modern Synthesis, Vol. 2: Advanced Topics, John
Wiley, New York, 1989.
A. Decegama, The Technology of Parallel Processing: Parallel Processing Architectures and
VLSI Hardware Volume 1, Prentice-Hall, NJ, 1989.
J. Dongarra, Experimental Parallel Computing Architectures, North-Holland, Amsterdam,
1987.
A. Goyal and T. Agerwala, Performance analysis of future shared storage systems,
IBM J. Res. Devel., 28(1), 95-107 (1984).