create new tag
view all tags


Intensive Computation - Calcolo Intensivo

Annalisa Massini

Office Hours: appointment by email

Dear students, this year I have updated the program of the course, making some changes to the order of the topics, making some additions, addressing some topics in more detail, and less in detail others that I had dealt with in-depth in previous years.

In particular, the course will start from the part dedicated to computer architectures, and will place greater emphasis on interconnection topologies for HPC and PD systems and the related communication problems. Quantum computing will be included as a new topic, with particular regard to quantum arithmetic circuits, in order to compare the classical solutions (which I will describe) with those currently being studied for quantum computers.

Theses will be proposed on the topics of this first part of the course.

In the second part of the course, the remaining topics will be treated (in previous years they were treated in the first period of the course): sparse matrices, errors, linear systems, eigenvalues and eigenvectors, molecular dynamics. Depending on how the course will proceed, it is possible that some of these latter topics are only mentioned or completely skipped.

Important information

  • The course will start regularly on Wednesday, 23 February 2022.
  • For in-person attendance, you should book an attendance spot through Prodigit, filling the form at the link: https://prodigit.uniroma1.it/
  • To get information on the lessons in streaming, access the course material and receive notices, you must register on Classroom for the imcilwm course using your Sapienza email address (surname.matricola@studentiNOSPAM.uniroma1.it).

  • Lessons are scheduled for:
    • Wednesday (11:00 am - 13.00 am)
    • Friday (10:00 am - 13.00 am)
    • in Room T1, Palazzina E (Building E) Regina Elena

Lectures 2021-2022

Lecture 1, February 23rd, 2022 Introduction to the course. Lecture1 - Introduction

Lecture 2, February 25th, 2022 Summary of computer organization and architecture. Lecture2 - Computer overview - Part1

Lecture 3, March 2nd, 2022 Circuits for arithmetic operations. Lecture 3 - Computer arithmetic - Slides 1-38

Lecture 4, March 16th, 2022 Pipelined addition. Pipelined unsigned and signed multiplication. Evaluation of circuit area and delay. Lecture 4 - Computer arithmetic - Slides 39-59
Representations for fast arithmetic. Introduction to Redundant Number systems. Lecture 4 - Redundant number systems - Slide 1-9

Lecture 5, March 18th, 2022 Redundant Number systems. Lecture 5 - Redundant number systems - Slide 10-52

Lecture 6, March 23rd, 2022 Residue Number systems. Lecture 6 - Residue Number System Slides are UPDATED

Lecture 7, March 25th, 2022 Motivation to parallel architectures. Classifications of (parallel) architectures. Lecture 7 - Motivation to parallel architectures.

Lecture 8, March 30th, 2022 The SIMD class: Vector architectures Lecture 8 - Vector Architectures - Slide 1-48

Lecture 9, April 1st, 2022 The SIMD class. Vector architectures continued. Lecture 8 - Vector Architectures - Slide 49-68 Graphics Processing Units. Lecture 9 - GPUs - Slide 1-41

Lecture 10, April 6th, 2022 Graphics Processing Units. Lecture 10 - GPUs - Slide 42-71

Lecture 11, April 8th, 2022 Graphics Processing Units. Exercises. Lecture 11 - GPUs - Slide 72-112

Lecture 12, April 13th, 2022 Speed-up and performance. Lesson 12 - Speed-up and Performance

Midterm - April 20th, April

Lecture 13, April 22nd, 2022 Performance. Lesson 13 - Performance Part2

Lecture 14, April 27th, 2022 Interconnection networks Lesson 14 - Interconnection networks - Slide 1-45

Lecture 15, April 29th, 2022 Interconnection networks Lesson 15 - Interconnection networks - Slide 46-109

Lecture 16, May 4th, 2022 Interconnection networks: Fat trees and exrcises. Lesson 16 - Interconnection networks - Slide 109-123

Lecture 17, May 6th, 2022 Introduction to Quantum Computing. Qubits and One-qubit gates Lesson 17 - Quantum Computing - Slide 1-52

Lecture 18, May 11th, 2022 Quantum Computing: Multiple-Qubit gates and Quantum circuits Lesson 18 - Quantum Computing - Slide 53-92 UPDATED slides after class. The last slides have been corrected (Bell state representation).

Lecture 19, May 13th, 2022 Quantum Computing: Adders. Lecture 19- Quantum Computing: adders UPDATED slides

Lecture 20, May 18th, 2022 Exercises on quantum circuits.

Lecture 21, May 20th, 2022 Sparse Matrices Lesson 21 - Sparse Matrices

Lecture 22, May 25th, 2022 Exercises on quantum circuits, sparse matrices and fat trees

Lectures 2020-2021

Lecture 1, February 24th, 2021 Introduction to the course. Lecture 1 - Introduction

Lecture 2, February 26th, 2021 Introduction to Matlab - Part 1 - Lecture 2 - Matlab
Laboratory, February 26th, 2021 Laboratory: Introductory exercises - Part 1

Lecture 3, March 3rd, 2021 Introduction to Matlab - Part 2 - Lecture 3 - Matlab
Laboratory, March 3rd, 2021 Laboratory: Introductory exercises - Part 2

Lecture 4, March 5th, 2021 Sparse matrices: definitions and motivation of compact formats. Compact storage methods for sparse matrix: Coordinate, Skyline, Compact Sparse Row CSR, Compact Sparse Column CSC, Modified Sparse Row MSR. Lecture 4 - SparseMatrices.pdf

  • Appendix of book Solving Numerical PDEs: Problems, Applications, Exercises - Formaggia, Saleri, Veneziani - 2012 - read pp. 395-409

Lecture 5, March 10th, 2021 Exercises on Sparse matrices.

Lecture 6, March 12th, 2021 Lecture by Dr. Viviana Arrigoni. Linear systems. Gaussian elimination for solving systems of linear equations. Pivoting. Methods to avoid pivoting. Random Butterfly Transformations and Transpose methods. Lecture 7 - Linear Systems Part 1

Lecture 7, March 17th, 2021 Lecture by Dr. Viviana Arrigoni. Linear systems. Cholesky factorization. Jacobi iterative method. Gauss-Seidel iterative method. Lecture 7 - Linear Systems Part 2

Lecture 8, March 19th, 2021 Errors: Computational errors, Data errors, Truncation errors, Rounding errors. Forward error and backward error. Sensitivity and condition number. Stability and accuracy. Errors in floating-point representation. Uncertainty in measurements. Lecture 8 - Errors
Exercises on linear systems: Exercise 3 from Midterm exam 18 April 2018 (to be continued).

Lecture 9, March 24th, 2021 Discussion on Homework 1: student's solutions. Exercises on linear systems and errors: Exercise 3 from Midterm exam 18 April 2018 (continued); Exercise 3 from Midterm exam 17 April 2019.

Lecture 10, March 26th, 2021 Eigenvalues and eigenvectors. The Power method. The Deflation methods. Applications: Gould Index - Eigenvector Centrality in a Graph; the Fiedler Eigenvector and the Graph Partitioning; the Steady State of a Markov Chain using eigenvalues and eigenvectors; covariance matrix and eigenvectors. Lecture 10 - Eigenvalues, Eigenvectors and applications

Lecture 11, March 31st, 2021 Molecular Dynamics: Introduction, Hooke's Law Model, Lennard-Jones Model, Motion Equations. Lecture11 - MolecularDynamicsMolecular Dynamics - L. Fosdick.

Lecture 12, April 7th, 2021 Molecular Dynamics: Euler's method and Verlet's method for Hooke's Law Model and Lennard-Jones Model. Solution of motion equations for the 1D Hard Sphere Model. Lecture12 - Molecular Dynamics Part 2 - slide 1-37 Exact solution for Hooke's Law Model. Molecular Dynamics - L. Fosdick.

Lecture 13, April 9th, 2021 Molecular dynamics: Solution of motion equations for the 1D Hard Sphere Model. Exact solution of motion equations for the Hooke's Law Model. Lecture12 - Molecular Dynamics Part 2 - slide 38-65
Discussion on Homework 2: student's solutions.

Midterm test - April 16th, 2021

Lecture 15, April 23rd, 2021 Circuits for arithmetic operations. Pipeline of arithmetic operations. Circuit evaluation: delay and area. Lecture15 - Computer arithmetic

Lecture 16, April 28th, 2021 Representations for Fast Arithmetic. Redundant number representations for carry-free addition. Modified Signed Digit (MSB) and Redundant Binary. Lecture16 - Representations for Fast Arithmetic - Slides 1-31

Lecture 17, April 30th, 2021 Representations for Fast Arithmetic: Residue number system. Lecture17 - Representations for Fast Arithmetic - Slides 32-55

Lecture 18, May 5th, 2021 SIMD class: vector architecture. Lecture 18 - Vector Architectures

Lecture 19, May 7th, 2021 Graphics Processing Units. Matrix multiplication on GPUs. Lecture19 - GPUs

Lecture 20, May 12th, 2021 Interconnection networks. Lecture 20 - Interconnection networks - Slides 1 - 39

Lecture 21, May 14th, 2021 Interconnection networks: Equivalence of log N stage and (2log N -1) stage MINs; all-to-all personalized communication on log N stage and (2log N -1) stage MINs - Lecture 20 - Interconnection networks - Slides 40 - 102

Lecture 22, May 19th, 2021 Exercises on Interconnection networks and GPUs.

Lecture 23, May 21st, 2021 Performance evaluation of computer architectures. Amdahl law. Performance equation. Lesson 23 - Performance

Lecture 24, May 26st, 2021 Exercises on GPUs, Amdahl law, and Performance equation. Discussion on Projects and Homework.

Some papers proposed for past exam projects - Articoli proposti per esami passati

Past year lectures


The exam consists of two parts:

  • Written exam. Students attending the lessons can take a mid-term exam and a final exam (or a whole exam). Mid-term and final exam (or whole exam) consist in a written test and exercises.
  • One of the following, at the choice of the student: oral exam/presentation of one-two papers/project.

There will also be homework assignments. Homeworks will contribute to the final grade.

Text of exams


Textbooks - Testi di riferimento

  • Introduction to High-Performance Scientific Computing, Lloyd D. Fosdick, Elizabeth R. Jessup, Carolyn J. C. Schauble and Gitta Domik, The MIT Press, 1996, ISBN 0-262-06181-3
  • Programming Massively Parallel Processors: A Hands-on Approach, David B. Kirk and Wen-mei W. Hwu, Morgan Kaufmann, 2010
  • Introduction to scientific computing: A Matrix-Vector Approach Using MATLAB, Charles F. Van Loan, Prentice Hall , 1997
  • Manuale di MATLAB. Consultare il sito: http://www.mathworks.com/help/techdoc/learn_matlab/bqr_2pl.html
  • Matlab. Concetti e progetti, Giovanni Naldi e Lorenzo Pareschi, Apogeo, 2007
  • Calcolo Scientifico: Esercizi e Problemi Risolti Con MATLAB e Octave, Alfio Quarteroni, Fausto Saleri, 2008


-- AnnalisaMassini

Edit | Attach | Watch | Print version | History: r326 < r325 < r324 < r323 < r322 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r326 - 2022-05-26 - AnnalisaMassini

Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback