In the past, programmers have had the benefit that each successive generation of microprocessors makes their code run much faster. However, microprocessor design is reaching problems; too much heat, power consumption, voltage leakage, and space on a single chip. The best new solution for improving performance is parallelism. To make use of parallelism in new computer architectures, new algorithms must be developed.
Benefits of multithreading include improved application responsiveness, between program structure, efficient use of multiple processors, and using fewer system resources. Matrix multiplication is one example of an algorithm with a high degree of parallelism that can run much faster when implemented on a multiprocessor.

In Matrix factorizations, methods that use block partitioned algorithms to parallel linear algebra are being developed. Blocking can be used in a wide number of problems including methods covered in class such as least squares and singular value decomposition.

Matrix multiplication and LU factorization are two good examples of problems where multiple threads can be very beneficial. Algorithms often include solving smaller linear algebra problems or sub-matrices and synchronizing the threads so that they work on separate problems.

Operations in parallel systems are usually performed as a sequence of smaller tasks. One way used to represent this execution flow is through a Directed Acyclic Graph where nodes represent sub-tasks and the edges represent dependencies between them. The DAG technique has been shown to be a good solution to the synchronization problem.

Both papers emphasized minimizing the communication between threads to reduce overhead. In one algorithm, the speedup was not seen after increasing the number of threads past 2 due to the need for more communication. In the future, techniques for multiprocessor programming will become more and more important and the possibility for increasing the speed of many algorithms will grow. This increase in speed has already been shown in matrix algebra.

(see code and result graphs in pdfs listed in references)

References

Alfredo Buttari, Multithreading for synchronization tolerance in matrix factorization

http://www.iop.org/EJ/article/1742-6596/78/1/012028/jpconf7_78_012028.pdf

Leonardo Jelenković, Goran Omrčen-Čeko, EXPERIMENTS WITH MULTITHREADING IN

PARALLEL COMPUTING

http://www.zemris.fer.hr/~leonardo/unofficial/radovi/iti97.pdf