Search

A random walk-based method is proposed to efficiently compute the solution of a large class of fractional in time linear systems of differential equations (linear F-ODE systems), along with the derivatives with respect to the system parameters. Such a method is unbiased and unconditionally stable, and can therefore be used to provide an unbiased estimation of individual entries of the solution, or the full solution. By using stochastic differentiation techniques, it can be used as well to provide unbiased estimators of the sensitivities of the solution with respect to the problem parameters without any additional computational cost. The time complexity of the algorithm is discussed here, along with suitable variance bounds, which prove in practice the convergence of the algorithm. Finally, several test cases were run to assess the validity of the algorithm.

The Kaczmarz algorithm is an iterative technique designed to solve consistent linear systems of equations. It falls within the category of row-action methods, focusing on handling one equation per iteration. This characteristic makes it especially useful in solving very large systems. The recent introduction of a randomized version, the Randomized Kaczmarz method, renewed interest in the algorithm, leading to the development of numerous variations. Subsequently, parallel implementations for both the original and Randomized Kaczmarz method have since then been proposed. However, previous work has addressed sparse linear systems, whereas we focus on solving dense systems. In this paper, we explore in detail approaches to parallelizing the Kaczmarz method for both shared and distributed memory for large dense systems. In particular, we implemented the Randomized Kaczmarz with Averaging (RKA) method that, for inconsistent systems, unlike the standard Randomized Kaczmarz algorithm, reduces the final error of the solution. While efficient parallelization of this algorithm is not achievable, we introduce a block version of the averaging method that can outperform the RKA method.

The Kaczmarz algorithm is an iterative method that solves linear systems of equations. It stands out among iterative algorithms when dealing with large systems for two reasons. First, at each iteration, the Kaczmarz algorithm uses a single equation, resulting in minimal computational work per iteration. Second, solving the entire system may only require the use of a small subset of the equations. These characteristics have attracted significant attention to the Kaczmarz algorithm. Researchers have observed that randomly choosing equations can improve the convergence rate of the algorithm. This insight led to the development of the Randomized Kaczmarz algorithm and, subsequently, several other variations emerged. In this paper, we extensively analyze the native Kaczmarz algorithm and many of its variations using large-scale dense random systems as benchmarks. Through our investigation, we have verified that, for consistent systems, various row sampling schemes can outperform both the original and Randomized Kaczmarz method. Specifically, sampling without replacement and using quasirandom numbers are the fastest techniques. However, for inconsistent systems, the Conjugate Gradient method for Least-Squares problems overcomes all variations of the Kaczmarz method for these types of systems.

We propose a novel stochastic algorithm that randomly samples entire rows and columns of the matrix as a way to approximate an arbitrary matrix function using the power series expansion. This contrasts with existing Monte Carlo methods, which only work with one entry at a time, resulting in a significantly better convergence rate than the original approach. To assess the applicability of our method, we compute the subgraph centrality and total communicability of several large networks. In all benchmarks analyzed so far, the performance of our method was significantly superior to the competition, being able to scale up to 64 CPU cores with remarkable efficiency., Comment: Published in the Journal of Scientific Computing

We present a stochastic method for efficiently computing the solution of time-fractional partial differential equations (fPDEs) that model anomalous diffusion problems of the subdiffusive type. After discretizing the fPDE in space, the ensuing system of fractional linear equations is solved resorting to a Monte Carlo evaluation of the corresponding Mittag-Leffler matrix function. This is accomplished through the approximation of the expected value of a suitable multiplicative functional of a stochastic process, which consists of a Markov chain whose sojourn times in every state are Mittag-Leffler distributed. The resulting algorithm is able to calculate the solution at conveniently chosen points in the domain with high efficiency. In addition, we present how to generalize this algorithm in order to compute the complete solution. For several large-scale numerical problems, our method showed remarkable performance in both shared-memory and distributed-memory systems, achieving nearly perfect scalability up to 16,384 CPU cores.

Collective operations are common features of parallel programming models that are frequently used in High-Performance (HPC) and machine/ deep learning (ML/ DL) applications. In strong scaling scenarios, collective operations can negatively impact the overall application performance: with the increase in core count, the load per rank decreases, while the time spent in collective operations increases logarithmically. In this article, we propose a design for eventually consistent collectives suitable for ML/ DL computations by reducing communication in Broadcast and Reduce, as well as by exploring the Stale Synchronous Parallel (SSP) synchronization model for the Allreduce collective. Moreover, we also enrich the GASPI ecosystem with frequently used classic/ consistent collective operations -- such as Allreduce for large messages and AlltoAll used in an HPC code. Our implementations show promising preliminary results with significant improvements, especially for Allreduce and AlltoAll, compared to the vendor-provided MPI alternatives.

As persistent memory (PM) technologies emerge, hybrid memory architectures combining DRAM with PM bring the potential to provide a tiered, byte-addressable main memory of unprecedented capacity. Nearly a decade after the first proposals for these hybrid architectures, the real technology has finally reached commercial availability with Intel Optane(TM) DC Persistent Memory (DCPMM). This raises the challenge of designing systems that realize this potential in practice, namely through effective approaches that dynamically decide at which memory tier should pages be placed. In this paper, we are the first, to our knowledge, to systematically analyze tiered page placement on real DCPMM-based systems. To this end, we start by revisiting the assumptions of state-of-the-art proposals, and confronting them with the idiosyncrasies of today's off-the-shelf DCPMM-equipped architectures. This empirical study reveals that some of the key design choices in the literature rely on important assumptions that are not verified in present-day DRAM-DCPMM memory architectures. Based on the lessons from this study, we design and implement HyPlacer, a tool for tiered page placement in off-the-shelf Linux-based systems equipped with DRAM+DCPMM. In contrast to previous proposals, HyPlacer follows an approach guided by two main practicality principles: 1) it is tailored to the performance idiosyncrasies of off-theshelf DRAM+DCPMM systems; and 2) it can be seamlessly integrated into Linux with minimal kernel-mode components, while ensuring extensibility to other HMAs and other data placement policies. Our experimental evaluation of HyPlacer shows that it outperforms both solutions proposed in past literature and placement options that are currently available in off-the-shelf DCPMM-equipped Linux systems, reaching an improvement of up to 11x when compared to the default memory policy in Linux.

Recently, task-based programming models have emerged as a prominent alternative among shared-memory parallel programming paradigms. Inherently asynchronous, these models provide native support for dynamic load balancing and incorporate data flow concepts to selectively synchronize the tasks. However, tasking models are yet to be widely adopted by the HPC community and their effective advantages when applied to non-trivial, real-world HPC applications are still not well comprehended. In this paper, we study the parallelization of a production electromagnetic particle-in-cell (EM-PIC) code for kinetic plasma simulations exploring different strategies using asynchronous task-based models. Our fully asynchronous implementation not only significantly outperforms a conventional, synchronous approach but also achieves near perfect scaling for 48 cores., Comment: Published on the 27th European Conference on Parallel and Distributed Computing (Euro-Par 2021)

The COVID-19 pandemic has caused a strong effect on higher education institutions with the closure of classroom teaching activities. In this unprecedented crisis, of global proportion, educators and families had to deal with unpredictability and learn new ways of teaching. This short essay aims to explore the challenges posed to Portuguese higher education institutions and to analyze the challenges posed to evaluation models. To this end, the relevance of formative and summative assessment models in distance education is explored and the perception of teachers and students about the practices adopted in remote assessment is discussed. On the teachers' side, there is a high concern about adopting fraud-free models, and an excessive focus on the summative assessment component that in the distance learning model has less preponderance when compared to the gradual monitoring and assessment processes of the students, while on the students' side, problems arise regarding equipment to follow the teaching sessions and concerns about their privacy, particularly when intrusive IT solutions request the access to their cameras, audio, and desktop., Comment: 8 pages, 10 references