Backfilling is a widely used scheduling technique in High-Performance Computing (HPC) systems to improve resource utilization. However, traditional approaches like EASY Backfill were devised for mono-core homogeneous environments, without considering the implications of multi-core architectures or the individual characteristics of nodes in heterogeneous clusters. This article proposes two refinements of EASY called Heterogeneous Backfill (HB) and Heterogeneous Reordering Backfill (HRB). These algorithms adapt the backfilling strategy to heterogeneous multi-core environments by incorporating node properties into the scheduling process. The HB algorithm sorts nodes based on a given criterion, such as power consumption or performance, to improve resource allocation. The HRB algorithm extends this approach by incorporating job reordering criteria, allowing for more efficient backfilling decisions. An evaluation of these algorithms shows that they can significantly reduce energy consumption and improve scheduling efficiency in heterogeneous clusters. The results demonstrate that the proposed algorithms outperform traditional backfilling methods, such as EASY Backfill, in terms of energy consumption, waiting time or makespan. By embracing the heterogeneity of modern HPC systems, these algorithms enable more efficient resource utilization and contribute to the overall performance of large-scale computing environments.

Abstract In recent years, energy consumption has become a limiting factor in the evolution of high-performance computing (HPC) clusters in terms of environmental concern and maintenance cost. The computing power of these clusters is increasing, together with the demands of the workloads they execute. A key component in HPC systems is the workload manager, whose operation has a substantial impact on the performance and energy consumption of the clusters. Recent research has employed machine learning techniques to optimise the operation of this component. However, these attempts have focused on homogeneous clusters where all the cores are pooled together and considered equal, disregarding the fact that they are contained in nodes and that they can have different performances. This work presents an intelligent job scheduler based on deep reinforcement learning that focuses on reducing energy consumption of heterogeneous HPC clusters. To this aim it leverages information provided by the users as well as the power consumption specifications of the compute resources of the cluster. The scheduler is evaluated against a set of heuristic algorithms showing that it has potential to give similar results, even in the face of the extra complexity of the heterogeneous cluster.

Abstract This article delves into the critical realm of modern computer cluster management. It focuses on the effect that the increasing heterogeneity of the clusters has on the workload managers. The proposed schedulers consider node properties instead of job properties to make decisions, which is something not currently done by mainstream scheduling algorithms. In order to increase the knowledge in this topic, this paper proposes two novel algorithms whose main task is to choose the best compute nodes to schedule the incoming jobs. To this effect, they exclusively take into account the properties of the nodes, instead of the common trend of considering the properties of the jobs. The experimental results show that these algorithms outperform well-known heuristic algorithms found in the literature.

Modern High Performance Computing (HPC) clusters often comprise a huge amount of computing resources of different capabilities, making them heterogeneous and difficult to manage. In addition, they must deal with a wide range of applications with different requirements. All this poses a great challenge to the workload managers that assign applications to resources. There are many new proposals to overcome this challenge, including some that employ Deep Reinforcement Learning (DRL) techniques. This paper proposes a novel simulation framework for the study of workload managers, that has been conceived to foster the study of workload managers based on DRL techniques. Its main features include the simulation of heterogeneous clusters based on multicore architectures, taking into account the contention in shared memory access and the energy consumption. A validation of the accuracy and performance of the simulator was made, compared with a real environment based on Slurm. This shows good accuracy of the results, with a relative error below 5% in makespan and 10% in energy consumption, and speedups up to 200.

A challenge that heterogeneous system programmers face is leveraging the performance of all the devices that integrate the system. This paper presents Sigmoid, a new load balancing algorithm that efficiently co-executes a single OpenCL data-parallel kernel on all the devices of heterogeneous systems. Sigmoid splits the workload proportionally to the capabilities of the devices, drastically reducing response time and energy consumption. It is designed around several features; it is dynamic, adaptive, guided and effortless, as it does not require the user to give any parameter, adapting to the behaviour of each kernel at runtime. To evaluate Sigmoid's performance, it has been implemented in Maat, a system abstraction library. Experimental results with different kernel types show that Sigmoid exhibits excellent performance, reaching a utilization of 90%, together with energy savings up to 20%, always reducing programming effort compared to OpenCL, and facilitating the portability to other heterogeneous machines.

Heterogeneous systems have a very high potential performance but present difficulties in their programming. OmpSs is a well known framework for task based parallel applications, which is an interesting tool to simplify the programming of these systems. However, it does not support the co-execution of a single OpenCL kernel instance on several compute devices. To overcome this limitation, this paper presents an extension of the OmpSs framework that solves two main objectives: the automatic division of datasets among several devices and the management of their memory address spaces. To adapt to different kinds of applications, the data division can be performed by the novel HGuided load balancing algorithm or by the well known Static and Dynamic. All this is accomplished with negligible impact on the programming. Experimental results reveal that there is always one load balancing algorithm that improves the performance and energy consumption of the system.

In the late years many different interconnection networks have been used with two main tendencies. One is characterized by the use of high-degree routers with long wires while the other uses routers of much smaller degree. The latter rely on two-dimensional mesh and torus topologies with shorter local links. This paper focuses on doubling the degree of common 2D meshes and tori while still preserving an attractive layout for VLSI design. By adding a set of diagonal links in one direction, diagonal networks are obtained. By adding a second set of links, networks of degree eight are built, named king networks. This research presents a comprehensive study of these networks which includes a topological analysis, the proposal of appropriate routing procedures and an empirical evaluation. King networks exhibit a number of attractive characteristics which translate to reduced execution times of parallel applications. For example, the execution times NPB suite are reduced up to a 30 percent. In addition, this work reveals other properties of king networks such as perfect partitioning that deserves further attention for its convenient exploitation in forthcoming high-performance parallel systems.

Many current VLSI on-chip multiprocessors and systems-on-chip employ point-to-point switched interconnection networks. Rings and 2D-meshes are among the most popular interconnection topologies for these increasingly important onchip networks. Nevertheless, rings cannot scale beyond dozens of nodes and meshes are asymmetric. Two of the key features of square 2D-tori are their scalability and symmetry. As higher scalability is demanded by the increasing number of cores (or specialized units) integrated on a chip and symmetry is critical for high-performance and load balancing, we concentrate on 2D-tori. However, most popular deadlock-free routing mechanisms are based on Dimension Order Routing (DOR) which breaks the torus symmetry when managing adversarial traffic patterns. This paper analyzes this problem and its consequences. After that, it proposes a new deadlock-free fully adaptive minimal routing, denoted as σDOR, that preserves tori symmetry under any load. It uses just two virtual channels to avoid DOR-induced asymmetry, the same as in previous competitive proposals. σDOR exhibits better behavior than any of previous solutions as it allows packets to dynamically adapt to local congestion. Experimental results evidence the superior performance of our mechanism, confirming the negative impact of DOR asymmetry.

In order to propose a new metric over QAM constellations, diagonal Gaussian graphs defined over quotients of the Gaussian integers are introduced in this paper. Distance properties of the constellations are detailed by means of the vertex-to-vertex distribution of this family of graphs. Moreover, perfect codes for this metric are considered. Finally, notable subgraphs of diagonal Gaussian graphs are studied which leads to relate the proposed metric to other well-known graph-based metrics such as the Lee distance.

In this paper we consider a broad family of toroidal networks, denoted as Gaussian networks, which include many previously proposed and used topologies. We will define such networks by means of the Gaussian Integers, the subset of the Complex numbers with integer real and imaginary parts. Nodes in Gaussian networks are labeled by Gaussian integers, which confer these topologies an algebraic structure based on quotient rings of the Gaussian integers. In this sense, Gaussian integers reveal themselves as the appropriate tool for analyzing and exploiting any type of toroidal network. Using this algebraic approach, we can characterize the main distance-related properties of Gaussian networks, providing closed expressions for their diameter and average distance. In addition, we solve some important applications, like unicast and broadcast packet routing or the perfect placement of resources over these networks.

Cayley graphs over quotients of the quaternion integers are going to be used to define a new metric over four dimensional lattices. We will consider perfect 1-error correcting codes according to this metric space. We will show that, in some cases, these lattices can be represented as two-dimensional constellations, which allow us to state a relation between the Lee metric and this new Lipschitz metric.