# PARALLEL AND DISTRIBUTED COMPUTING

## Learning outcomes of the course unit

At the end of the course, it is expected that the student is able to:

- know the main types of abstract machines

- know the main computational complexity classes

- create models of computing systems, in particular to study their performance

- know the features of parallel architectures

- know the main techniques for describing and evaluate parallel algorithms

- design and implement parallel programs

- know the features of autonomic systems

- design autonomic computing systems

- know the working principles of discrete event simulators

- implement discrete event simulators

- know the principles of quantum computing

- design quantum algorithms and protocols

The main goal of the course is to define and characterize computing systems.

In particular, the student will be provided with the ability to understand:

- abstract machines and computational complexity

- parallel programming models

- autonomic systems

- simulation techniques

- quantum computing

The student will learn to apply such a knowledge to:

- develop computing systems models, in particular for performance analysis

- design and implement parallel programs

- design autonomic systems

- implement discrete event simulations

- design quantum algorithms and protocols

## Course contents summary

1. Abstract machines and computational complexity

2. Parallel computing

3. Autonomic systems

4. Discrete event simulation

5. Quantum computing

1. Abstract machines and computational complexity

2. Parallel computing

3. Autonomic systems

4. Simulation techniques

5. Quantum computing

## Course contents

1. Computing systems (5 hours)

1.1. Information theory; 1.2. Taxonomy of computing systems; 1.3. Abstract machines; 1.4. Computational complexity

2. Parallel computing (13 hours)

2.1. Parallel architectures; 2.2. Parallel algorithms; 2.3. Performance evaluation; 2.4. Message Passing Interface (MPI); 2.5. MapReduce; 2.6. Multicore systems, OpenMP; 2.7. General Purpose GPU Programming, CUDA

3. Autonomic computing (3 hours)

3.1. The four principles of autonomic computing; 3.2. MAPE-K model; 3.3. NAM, NAM4J, DRF frameworks

4. Simulation techniques (5 hours)

4.1. General concepts about simulation; 4.2. Discrete event simulation; 4.3. DEVS models; 4.4. DEUS simulation platform

5. Quantum computing (16 hours)

5.1. History of quantum computing; 5.2. Review of linear algebra; 5.3. Postulates of Quantum Mechanics; 5.4. Quantum bit; 5.5. Quantum circuits; 5.6. Quantum algorithms; 5.7. Quantum security protocols

Lectures on Parallel and Distributed Computing (42 hours)

1. Computing systems

1.1. Information theory; 1.2. Taxonomy of computing systems; 1.3. Abstract machines; 1.4. Computational complexity

2. Parallel computing

2.1. Parallel architectures; 2.2. Performance evaluation; 2.3. Parallel programming models; 2.4. Message Passing Interface (MPI); 2.5. MapReduce; 2.6. Multicore systems, General Purpose GPU Programming, CUDA, OpenCL

3. Autonomic computing

4.1. The four principles of autonomic computing; 3.2. MAPE-K; 3.3. NAM, NAM4J, Distributed Remodeling Framework

4. Simulation techniques

4.1. General concepts about simulation; 4.2. Discrete event simulation

5. Quantum computing

5.1. History of quantum computing; 5.2. Linear algebra; 5.3. The postulates of Quantum Mechanics; 5.4. Quantum bit; 5.5. Quantum circuits; 5.6. Quantum algorithms; 5.7. Quantum security protocols

## Recommended readings

M. Amoretti, lecture notes in english.

C. Ghezzi, D. Mandrioli, "Informatica Teorica", Città Studi, 1989.

S. Arora, B. Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009.

G. Hager, G. Wellein, "Introduction to High Performance Computing for Scientists and Engineers", CRC Press, 2010.

B.P. Zeighler, H. Praehofer, T.G. Kim, "Theory of Modeling and Simulation", 2nd Ed., Academic Press, 2000.

M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2011.

M. Amoretti, lecture notes in english.

C. Ghezzi, D. Mandrioli, "Informatica Teorica", Città Studi, 1989.

D. E. Culler, J. Pal Singh, “Parallel Computer Architecture: A Hardware/Software Approach”, Morgan Kaufman, 1999.

B.P. Zeighler, H. Praehofer, T.G. Kim, "Theory of Modeling and Simulation", Second Edition, Academic Press, 2000.

M. Nielsen, I. Chuang, “Quantum Computation and Quantum Information”, Cambridge University Press, 2011.

## Teaching methods

Teaching activities will be mostly performed in terms of lectures given by the teacher, showing slides and writing on the blackboard.

Some hours will be devoted to the practice of parallel programming and discrete event simulation.

Teaching materials (including slides, lecture notes, source code, scientific articles) will be weekly uploaded on the Elly platform.

To download teaching materials, on line subscription to the course is mandatory.

Students that won't attend the lectures are invited to check the available teachning materials and recommendations provided by the teacher through the Elly platform.

Lectures are given by the teacher, which illustrates the topics with the support of slides, or by writing on the blackboard. Some hours are devoted to parallel programming practice. Lectures about simulation techniques are completed by a tutorial on the DEUS simulation environment.

## Assessment methods and criteria

The learning evaluation consists of two moments:

1) a written exam lasting 3 hours, with open questions related to the theoretical topics of the course;

2) a project to be selected between the implementation of a parallel software, the implementation of a discrete event simulator, the deep study of a quantum computing paper; it is mandatory to write a short report and to make an oral presentation of the work done.

The written exam is evaluated on a 0-30 scale. The project is evaluated on a 0-4 scale. The final grade is the sum of the two partial grades. There won't be midterm exams.

There will not be exams during the course.

There will be a written exam (3 hours), with 6-7 open questions related to theoretical part of the course.

Every student will have to work on a small project, requiring: the use/development of a software or the study of a quantum computing paper; the writing of a report; a final presentation (supported by slides).

## Other informations

Lecture notes, slides and exercises are available on http://elly.dii.unipr.it