Parallel Processing Letters

In general, efficient non-blocking interconnection networks can be derived from sorting networks, and to this end, one may either follow the merge-based or the radix-based sorting paradigm. Both paradigms require special modifications to handle partial permutations. In this article, we present a general lemma about half cleaner modules that were introduced as building blocks in Batcher’s bitonic sorting network. This lemma is the key to prove the correctness of many known optimizations of interconnection networks. In particular, we first show how to use any ternary sorter and a half cleaner for implementing an efficient split module as required for radix-based sorting networks for partial permutations. Second, our lemma formally proves the correctness of another known optimization of the Batcher-Banyan network.

Self-stabilizing, but non-silent, distributed algorithms, for center finding in chain and tree networks are presented in the link register model. We assume that there exists a designated root in a chain and a tree. Under this assumption, both algorithms find the unique center or one of the two centers of the network within O(diam) rounds under the unfair daemon, where diam is the diameter of the network. Both algorithms use constant space, both per process and per link register. The basic strategy of the chain algorithm is based on two synchronized waves of different speeds; one wave is three times faster than the other. The tree algorithm uses the fact that a center of the longest path in the tree is also a center of the tree itself. It first finds one of the longest paths in the tree, then finds the unique center or one of the two centers of the path using the chain algorithm.

Porting scientific key algorithms to HPC architectures requires a thorough understanding of the subtle balance between gain in performance and introduced overhead. Here we continue the development of our recently proposed technique that uses plain execution times to predict the extent of parallel overhead. The focus here is on an analytic solution that takes into account as many data points as there are unknowns, i.e. model parameters. A test set of 9 applications frequently used in scientific computing can be well described by the suggested model even including atypical cases that were originally not considered part of the development. However, the choice about which particular set of explicit data points will lead to an optimal prediction cannot be made a-priori.

Implementing parallel software for QR factorizations to achieve scalable performance on massively parallel manycore systems requires a comprehensive design that includes algorithm redesign, efficient runtime systems, synchronization and communication reduction, and analytical performance modeling. This paper presents a piece of tiled communication-avoiding QR factorization software that is able to scale efficiently for matrices with general dimensions. We design a tiled communication-avoiding QR factorization algorithm and implement it with a fully distributed dynamic scheduling runtime system to minimize both synchronization and communication. The whole class of communication-avoiding QR factorization algorithms uses an important parameter of D (i.e., the number of domains), whose best solution is still unknown so far and requires manual tuning and empirical searching to find it. To that end, we introduce a simplified analytical performance model to determine an optimal number of domains D${}^{\ast }$. The experimental results show that our new parallel implementation is faster than a state-of-the-art multicore-based numerical library by up to 30%, and faster than ScaLAPACK by up to 30 times with thousands of CPU cores. Furthermore, using the new analytical model to predict an optimal number of domains is as competitive as exhaustive searching, and exhibits an average performance difference of 1%.

Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of applying a computational interventional calculus based on the principles of algorithmic probability to chemical structure networks. We profile the sensitivity of the elements and covalent bonds in a chemical structure network algorithmically, asking whether reprogrammability affords information about thermodynamic and chemical processes involved in the transformation of different compound classes. We arrive at numerical results suggesting a correspondence between some physical, structural and functional properties. Our methods are capable of separating chemical classes that reflect functional and natural differences without considering any information about atomic and molecular properties. We conclude that these methods, with their links to chemoinformatics via algorithmic, probability hold promise for future research.