Summary A new efficient implementation of the multithreaded quicksort algorithm called CPP11sort is presented. This implementation is built exclusively upon the threading primitives of the C++ programming language itself. The performance of CPP11sort is evaluated and compared with its mainstream competitors provided by GNU, Intel, and Microsoft. It is shown that out of the considered implementations, CPP11sort mostly yields the shortest sorting times and is the only one that is portable to any conforming C++ implementation without a need of external libraries or nonstandard compiler extensions. The experimental evaluation with various input data distributions resulted in parallel speedup between 16.1 and 44.2 on a 56‐core server and between 6.8 and 14.5 on a 10‐core workstation with enabled hyperthreading.

Computations with tensors are widespread in many scientific areas. Usually, the used tensors are very large but sparse, i.e., the vast majority of their elements are zero. The space complexity of sparse tensor storage formats varies significantly. For overall efficiency, it is important to reduce the execution time and additional space requirements of the initial preprocessing (i.e., converting tensors from common storage formats to the given internal format).

Frequent dynamic memory allocations (DyMAs) can significantly hinder the scalability of parallel multi-threaded programs. As the number of threads grows, DyMAs can even become the main performance bottleneck. We introduce modern tools and methods for evaluating the impact of DyMAs and present techniques for its reduction, which include scalable heap implementations, small buffer optimization, and memory pooling. Additionally, we provide a survey of state-of-the-art implementations of these techniques and study them experimentally by using a benchmark program, server simulator software, and a real-world high-performance computing application. As a result, we show that relatively small modifications in parallel program's source code or a way of its execution may substantially reduce the runtime overhead associated with the use of dynamic data structures.

The presented study analyses 563 representative benchmark sparse matrices with respect to their partitioning into uniformly-sized blocks.The aim is to minimize memory footprints of matrices.Different block sizes and different ways of storing blocks in memory are considered and statistically evaluated.Memory footprints of partitioned matrices are additionally compared with lower bounds and the CSR storage format.The average measured memory savings against CSR in case of single and double precision are 42.3 and 28.7 percents, respectively.The corresponding worst-case savings are 25.5 and 17.1 percents.Moreover, memory footprints of partitioned matrices were in average 5 times closer to their lower bounds than CSR.Based on the obtained results, we provide generic suggestions for efficient partitioning and storage of sparse matrices in a computer memory.

Finding an optimal block size for a given sparse matrix forms an important problem for storage formats that partition matrices into uniformly-sized blocks.Finding a solution to this problem can take a significant amount of time, which, effectively, may negate the benefits that such a format brings into sparse-matrix computations.A key for an efficient solution is the ability to quickly iterate, for a particular block size, over matrix nonzero blocks.This work proposes an efficient parallel algorithm for this task and evaluate it experimentally on modern multi-core and many-core high performance computing (HPC) architectures.

Many storage formats for sparse matrices have been developed.Majority of these formats can be parametrized, so the algorithm for finding optimal parameters is crucial.For overall efficiency, it is important to reduce the execution time of this preprocessing.In this paper, we propose a new algorithm for the determination of the number of nonzero blocks of the given size in a sparse matrix.The proposed algorithm requires relatively a small amount of auxiliary memory.Our approach is based on the Morton reordering and bitwise manipulations.We also present a parallel (multithreaded) version and evaluate its performance and space complexity.

When authors present new storage formats for sparse matrices, they usually focus mainly on a single evaluation criterion, which is the performance of sparse matrix-vector multiplication (SpMV) in FLOPS. Though such an evaluation is essential, it does not allow to directly compare the presented format with its competitors. Moreover, in case that matrices are within an HPC application constructed in different formats, this criterion alone is not sufficient for the key decision whether or not to convert them into the presented format for the SpMV-based application phase. We establish ten evaluation criteria for sparse matrix storage formats, discuss their advantages and disadvantages, and provide general suggestions for format authors/evaluators to make their work more valuable for the HPC community.

An algorithm for parallel generation of a random permutation of a large set of distinct integers is presented. This algorithm is designed for massively parallel systems with distributed memory architectures and the MPI-based runtime environments. Scalability of the algorithm is analyzed according to the memory and communication requirements. An implementation of the algorithm in a form of a software library based on the C++ programming language and the MPI application programming interface is further provided. Finally, performed experiments are described and their results discussed. The biggest of these experiments resulted in a generation of a random permutation of 2 41 integers in slightly more than four minutes using 131072 CPU cores.

Clusters of workstations are a promising platform for high-performance computing. Most of such clusters are built of dedicated workstations that cannot be used for other purposes. Even though these clusters offer good price/performance ratio, their costs are not negligible. On the other hand, there exist many idle workstations connected via computer networks. The idea of exploiting such idle resources is obvious. In this paper, we describe an architecture of clusters made of non-dedicated idle workstations. These clusters aim at providing a single-system-image Linux environment. The main innovative feature is that a cluster administration is separate from administration of individual workstations. We discuss issues of security, availability, performance, and administration of such clusters. We also describe a pilot implementation and give promising experimental results.