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 compuatation (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.

Students who regularly participate in course activities and successfully complete the course:

• have knowledge and understanding of fundamental principles and methods for the design and analysis of parallel algorithms; students are therefore able to keep track of current developments at the cutting edge of their field of knowledge

• are able to use knowledge and understanding they have acquired in a way that shows a professional approach to their work or profession, and appropriately skilled to appropriately use parallel computation and algorithms for various problems within their field

• have the ability to collect and interpret relevant data (typically within their field) to form judgments that include reflection on relevant social, scientific or ethical issues

• are able to communicate information, ideas, problems and solutions to specialized and non-specialized audience

• have developed knowledge acquisition skills necessary to further continue their studies with a high degree of autonomy

• have become familiar with computational thinking and are able to exploit its advantages in scientific, professional and practical issues

In particular, students who regularly participate in course activities and successfully complete the course:

1. have knowledge of fundamental principles and methods for the design and analysis of parallel algorithms

2. understand the concept and applications of parallel algorithms and computation

3. are able to apply principles and methods for the design and analysis of parallel algorithms

4. analyze problems / questions in order to gain understanding of their structure and insight regarding the use of parallelism fo their solution

5. suggest solutions to these problems exploiting parallelism

6. evaluate findings (solutions or hardness results) through analysis

are familiar with computational thinking