Técnicas de Computação Paralela

Ficha de Unidade Curricular – 2º Ciclo

Unidade Curricular / Curricular Unit
Técnicas de Computação Paralela / Parallel Computing Techniques

Ciclo de Estudos / Study Cycle
Mestrado em Eng-ª Informática e Sistemas de Infomração / Master in Computer Science and Information Systems

Nome do Docente Responsável
José Luís de Azevedo Quintino Rogado

Objectivos de aprendizagem (conhecimentos, aptidões e competências a desenvolver pelos estudantes)
O objectivo desta Unidade Curricular é o de apresentar os princípios fundamentais da Computação Paralela e das tecnologias utilizadas no desenvolvimento e optimização de aplicações paralelas que permitem a sua operacionalização nas plataformas de suporte hardware e software mais actuais.
No final da cadeira, os alunos deverão:
• Utilizar as técnicas de programação paralela e as respectivas plataformas de execução para desenvolver sistemas e aplicações capazes de tirar partido da evolução recente do hardware (multicore, GPUs);
• Compreender os conceitos fundamentais da computação paralela
• Identificar a existência de tarefas independentes em algoritmos computacionais;
• Decompô-los em vários fluxos de execução paralela;
• Determinar o grau de paralelismo óptimo e prever os ganhos de desempenho.

Intended learning outcomes (knowledge, skills and competences to be developed by the students)
The goal of this course is to present the fundamental principles of parallel computing and the technologies used in the development and optimization of parallel applications and their deployment on state of the art hardware and software supporting platforms.
At the end of course, students should:
• Use parallel programming techniques and execution platforms to develop systems and applications that benefit from the recent hardware evolution (multicore, GPUs);
• Understand the key concepts of parallel computing
• Identify the existence of independent tasks in computational algorithms;
• Decompose them into multiple streams of parallel execution;
• Determine the optimal degree of parallelism and predict performance gains.

Conteúdos programáticos
1. Introdução
Motivações para o Paralelismo
Aplicações Científicas e Comerciais
2. Arquitecturas para Computação Paralela
Evolução e Limitações das Arquitecturas
Modelos de Computadores Paralelos
Modelo de Programação Paralela
Computação, Controle e Comunicação
Estrutura Física das Plataformas
Processamento vs. Comunicação
3. Desenho de Algoritmos Paralelos
Introdução
Técnicas de Decomposição e Aglomeração
Mapeamento e Balanceamento de Carga
Comunicação Inter Tarefas
Minimização de interacções
Modelos de Algoritmos Paralelos
4. Modelos e Plataformas de Programação Paralela
Programação em Memória Partilhada: Modelo de Threads
Programação baseada em directivas (OpenMP, Fork/Join, Streams)
Programação de GPUs: OpenCL
Programação por Mensagens: MPI

Syllabus
1. Introduction
Motivations for Parallelism
Engineering, Scientific and Industrial Applications
2. Architectures for Parallel Computing
Evolution and Limitations of Architectures
Parallel Computers Models
Parallel Programming Model
Computing, Control and Communication
Physical Structure of Platforms
Processing vs. Communication
3. Design of Parallel Algorithms
Introduction
Decomposition and Clustering Techniques
Mapping and Load Balancing
Inter Task Communication
Minimizing Interactions
Models of Parallel Algorithms
4. Models and Platforms for Parallel Programming
Shared Memory Programming: Threads Model
Directived Based Programming (OpenMP, Fork/Join, Streams)
GPU Programming: OpenCL
Messaging Programming: Message Passing Interface

Demonstração da coerência dos conteúdos programáticos com os objectivos de aprendizagem da unidade curricular
Em certas áreas da ciência, os problemas a resolver são de grande complexidade e implicam transferência, armazenamento e tratamento de quantidades massivas de informação  (Big Data). As capacidades fornecidas pelos meios computacionais clássicos não são suficientes para dar resposta aos requisitos agregados que lhes estão associados.
O recurso a técnicas de computação paralela, baseadas na agregação de recursos de processamento e/ou armazenamento (multicores, clusters e Grids) aparece como uma forma económica e escalável de tratar esses problemas. A engenharia associada à aplicação destas tecnologias constitui tema extremamente relevante e fecundo, que abre caminho à implementação de soluções inovadoras em áreas de reconhecido valor científico e tecnológico. O conteúdo programático proposto, ao fornecer uma abordagem actual e orientada para a implementação dos princípios fundamentais da Computação Paralela insere-se nos objectivos anunciados para esta Unidade Curricular.

Evidence of the syllabus coherence with the curricular unit’s intended learning outcomes
In certain areas of science, the nature of problems to solve is of great complexity and involves transfer, storage and processing of massive amounts of information (Big Data). The capabilities provided by the classical computational resources are not sufficient to meet their complete requirements.
The use of parallel computing techniques, based on the aggregation of processing and / or storage resources (multicores, clusters and grids) appears as an economical and scalable solution to address these problems. The engineering associated with the application of these technologies is an extremely relevant and fruitful theme, which paves the way for the implementation of innovative solutions in areas of recognized scientific and technological value. The proposed syllabus, by providing an contemporary approach, targeted to the implementation of the fundamental principles of Parallel Computing fits into the objectives stated for this Curricular Unit.

Metodologias de ensino (avaliação incluída)
Os conceitos fundamentais de computação paralela são introduzidos através de metodologia expositiva, privilegiando de seguida a utilização de métodos exploratórios na análise de algoritmos paralelos e sua decomposição em fluxos de execução independentes. Finalmente é utilizada a auto-aprendizagem na realização de exemplos baseadas nos modelos de programação abordados, e avaliação crítica na sua análise de desempenho e optimização. A implementação é realizada em computadores configurados em rede independente, utilizando plataformas de computação paralela (OpenMP) ou de clustering (MPI). A aprendizagem tem igualmente uma forte componente de pesquisa individual realizada pelos alunos, complementada por apresentações dos temas abordados.
A avaliação é constituída por uma apresentação individual (40%) e um projecto de grupo de no máximo 2 alunos (60%). A aprovação na cadeira é obtida com uma nota mínima de 10 valores na média ponderada das duas componentes.

Teaching methodologies (including assessment)
The fundamental concepts of parallel computing are introduced through expository methodology and following exploratory methods in the analysis of parallel algorithms and their decomposition into independent streams of execution. Finally self-learning is used for the implementation of examples based on the programming models addressed, and critical applied in the evaluation in their performance analysis and optimization. Implementation is performed on independent computing networks, using parallel (OpenMP) or clustering (MPI). Learning has also a strong component of research work carried out individually or in pairs, complemented by the presentation of the topics covered.
The assessment consists of an individual presentation (40%) and a project group of 2 students max. (60%). The approval is obtained in the chair with a minimum score of 10 on the weighted average values of the two components.

Demonstração da coerência das metodologias de ensino com os objectivos de aprendizagem da unidade curricular
Nesta unidade curricular o ensino é realizado através de aulas teórico-práticas, o que permite utilizar, por um lado, metodologias expositivas na apresentação dos princípios fundamentais da Computação Paralela e por outro, metodologias exploratórias baseadas em pesquisa e descoberta, para promover a aquisição efectiva de conhecimentos sobre as formas como esses princípios podem ser utilizados para aumentar o desempenho de diversos tipos de algoritmos e aplicações. O ensino é complementado por sessões de auto-aprendizagem em que os candidatos adquirem o domínio de plataformas e tecnologias utilizadas no desenvolvimento e optimização de aplicações paralelas. Por outro lado, a realização de apresentações individuais promove a atitude crítica e avaliação por pares relativamente aos conhecimentos adquiridos. Desta forma, as metodologias utilizadas enquadram-se nos objectivos enunciados para esta Unidade Curricular.

Evidence of the teaching methodologies coherence with the curricular unit’s intended learning outcomes
In this curricular unit, teaching is performed in theoretical-practical classes, which allows, on one hand, the usage of expository methodologies to present the fundamental principles of parallel computing, and on the other hand, the usage of exploratory methodologies based on research and discovery, to promote the effective acquisition of knowledge of how to use these principles to increase the performance of various types of algorithms and applications. Teaching is complemented by self-learning sessions where candidates learn how to master the platforms and technologies used in the development and optimization of parallel applications. Besides, performing individual presentations promotes a critical attitude and the opportunity for peer reviewing with respect to the knowledge acquired. Therefore, the methodologies used address all the objectives stated for this curricular unit.

Bibliografia Principal / Main Bibliography
“Parallel Programming for Multicore and Cluster Systems” (2nd Ed.), by Thomas Rauber & Gudula Rünger, 2013, Ed. Springer, ISBN-10: 3642378005

“Heterogeneous Computing with OpenCL” by Benedict R. Gaster, Lee Howes, David R. Kaeli, Perhaad Mistry & Dana Schaa, 2011, Ed. Morgan Kaufmann, ISBN-10 0123742609

“Introduction to Parallel Computing (2nd Edition)”, 2003, by Ananth Grama, George Karypis, Anshul Gupta, ed. Addison Wesley, ISBN-10: 0201648652

“Introduction to Parallel Computing”, by Blaise Barney (LLC), available on-line:
https://computing.llnl.gov/tutorials/parallel_comp