LiiT
Laboratory for Internet and Innovative Technologies
Abstract

Amdahl has shown that multiprocessor execution performance is not proportional to the number of processors. Gustafson has found a way to show that there are algorithms which can have almost linear speedup. In this article we have found algorithms which can achieve a superlinear speedup. The idea is not based on changing the algorithm or executing smaller number of operations like in the parallel search. It is based on characteristics of using an structure persistent algorithm which efficiently exploits the cache in a shared multiprocessor and avoids cache misses as much as possible. Our experimental research shows results of superlinear speedup for algorithms which run on modern multicore and multi-chip architectures and perform beyond expectations of maximum linear speedup.

Authors

Marjan Gusev, and Sasko Ristov

Keywords

Amdahl’s law, Gustafson’s law, L2 cache, high performance computing, matrix multiplication, shared memory multiprocessor, superlinear speedup

Full Paper

The paper is published in Proceedings of the ITI 2012 34th Int Conf on. Information Technology Interfaces, IEEE Conference proceedings, 2012

Download