Parallel Algorithms

Course Code: 
Spring Semester
Credit Points: 

Course outline

Parallel computation involves multiple processors (or computers) working together for a common problem. Each processor works for part of the problem assigned to it. Processors can exchange information. Sequential computation (i.e., when there is a single processor), on the other hand, follows the Von Neumann's stored program model.

Several processes in nature and everyday life involve parallelism, for example, weather phenomena, movement of tectonic plates, formation of galaxies, road traffic, car and aircraft construction, etc. Parallel computation is used in many areas of research and development (such as Computer Science , Mathematics, Electrical Engineering, Mechanics, Physics, Life Sciences, Biotechnology, Genetics, Chemistry, Geology, Seismology, etc.). Specifically, in Computer Science, parallel computing is used for tasks such as data mining, Web search, image processing, virtual reality, monetary and financial modeling, organization management, video and multimedia network technologies, collaborative work environments.

Parallel computation is used for overcoming the constraints imposed by sequential computation, and in particular for saving time and money, solving  problems of large size, ensuring simultaneous access to information / services as well as for exploiting non-local information (e.g. , SETI @ home).

In the context of this course, the concept, application and efficiency of parallelism in the design and execution of computational tasks (algorithms) are addressed. Problems and corresponding algorithms studied include computational tasks performed within a chip or a microprocessor such as sorting, counting, addition, multiplication, prefix counting, convolution, etc, computational tasks performed in a computer system, such as sorting, routing, etc., and other computational tasks related to communication in data networks, resource allocation, etc. Various models of fixed-connection networks, such as linear arrays, meshes, trees, hypercubes, butterflies, are studied. The proposed parallel algorithms are analyzed in terms of their speed-up against corresponding sequential algorithms, as well as in terms of their efficiency and work, i.e., how uniformly available resources are used. Asymptotic analysis is used to evaluate performance by providing upper and lower bounds. The analysis is mainly theoretical but can also be based on experimentation.

Lectures, problem solving and lab sessions proceed as follows:


Properties of the fixed-connection network model

Elementary sorting and counting

Integer arithmetic

Carry-lookahead addition

Prefix computation 

Carry-save addition

Multiplication and convolution


Odd-even transposition sort on a linear array

A simple sorting algorithm on a mesh 

Improved sorting algorithm for meshes

A tight lower bound

Packet routing

Greedy algorithms 

Average-case analysis of greedy algorithms

Routing packets to random destinations

Randomized routing algorithms

Deterministic routing algorithms with small queues

Off-line routing

Other routing models and algorithms 

Startup Growth Lite is a free theme, contributed to the Drupal Community by More than Themes.