[The University of Leicester]

Department of Mathematics & Computer Science



Next: MC341 Group Theory Up: Year 3 Previous: MC315 Expert Systems and Deductive Databases

MC316 Parallel and Distributed Computing

MC316 Parallel and Distributed Computing

Credits: 20 Convenor: Professor Iain A. Stewart Semester: 1

Prerequisites: essential: MC103,MC104,MC111,MC204 desirable: MC116,MC117
Assessment: Continual assessment: 30% Three hour exam in May/June: 70%

Lectures: 36 Problem Classes: 6
Tutorials: none Private Study: 96
Labs: none Seminars: none
Project: none Other: none
Surgeries: 12 Total: 150

Explanation of Pre-requisites

Typical of the material assumed for this module are the basics of: computer architectures; computer networks; the design and analysis of algorithms; and discrete mathematics especially graph theory.

Course Description

It has been well documented that one way of increasing the power of computers is to utilise more than one processor, i.e., to compute in parallel. As to how one organises ones processors is a matter for choice. One can interconnect existing sequential machines (as is the case in the Internet), to obtain a distributed system, or one can build special purpose parallel machines, such as array processors, multiprocessors (i.e., shared memory machines) and multicomputers (i.e., distributed memory machines). This course will look at the different ways in which one can compute in parallel and at the different problems arising. The course will be a fusion of the theoretical and the practical.

Aims

The course aims to introduce students to the technologically important area of parallel and distributed computing, and to equip students with a knowledge of a number of different ways in which one can compute using more than one processor. Students will come to appreciate that the general topic is an exciting mix of theory and practice, and that there is a number of very difficult fundamental problems to overcome, both technological and theoretical, in order to build efficient parallel and distributed machines.

Objectives

The course objectives are to ensure that students understand a number of different models of parallel and distributed computing and how there are different problems associated with the realisation of these models, particularly with respect to communication and algorithm design.

Transferable Skills

Students will become more experienced in the application of discrete mathematics, especially graph theory, in computing, and will obtain a comprehensive grounding in the general area of parallel and distributed computing, a direction in which technology will proceed in future.

Syllabus

This course examines a variety of models for parallel and distributed computing including multiprocessor computers (shared-memory and distributed-memory) and computer networks. Architectural issues in the realisation of these models are considered such as synchronisation, cache consistency, network topologies, routing, flow control, switching and communication standards. Algorithms for fundamental problems in multiprocessor computers and computer networks are then developed, and new advances in distributed and parallel computing, including mobile computing and optical networks, are briefly studied.

Reading list

Essential:

H. El-Rewini and T.G. Lewis, Distributed and Parallel Computing, Manning, 1997.

Recommended:

M. Cosnard and D. Trystram, Parallel Algorithms and Architectures, International Thomsen Computer Press, 1995.

J.M. Crichlow, An Introduction to Parallel and Distributed Computing, Prentice-Hall, 1997.

J. Duato, S. Yalamanchili and L. Ni, Interconnection Networks: an Engineering Approach, IEEE Computer Society Press, 1997.

A.S. Tanenbaum, Distributed Operating Systems, Prentice Hall, 1995.

G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, 1994.

ed. A.Y.H. Zomaya, Parallel and Distributed Computing Handbook, McGraw-Hill, 1996.

Background:

V.C. Barbosa, An Introduction to Distributed Algorithms, MIT Press, 1996.

G. Coulouris, J. Dollimore and T. Kindberg, Distributed Systems: Concepts and Design, Addison-Wesley, 1994.

A. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge University Press, 1988.

V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms, Benjamin Cummings, 1994.

N.A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.

M.J. Quinn, Parallel Computing: Theory and Practice, McGraw-Hill, 1994.

Details of Assessment

The coursework for the continual assessment consists of at most 5 assignments staggered throughout the course at approximately one assignment every two weeks.

Next: MC341 Group Theory Up: Year 3 Previous: MC315 Expert Systems and Deductive Databases

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 10/4/2000
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.