Large language models (LLMs) are remarked by their substantial computational requirements. To mitigate the cost, researchers develop specialized CUDA kernels, which often fuse several tensor operations to maximize the utilization of GPUs as much as possible. However, those specialized kernels may still leave performance on the table as CUDA assembly experts show that manual optimization of GPU SASS schedules can lead to better performance, and trial-and-error is largely employed to manually find the best GPU SASS schedules. In this work, we employ an automatic approach to optimize GPU SASS schedules, which thus can be integrated into existing compiler frameworks. The key to automatic optimization is training an RL agent to mimic how human experts perform manual scheduling. To this end, we formulate an assembly game, where RL agents can play to find the best GPU SASS schedules. The assembly game starts from a -O3 optimized SASS schedule, and the RL agents can iteratively apply actions to mutate the current schedules. Positive rewards are generated if the mutated schedules get higher throughput by executing on GPUs. Experiments show that CuAsmRL can further improve the performance of existing specialized CUDA kernels transparently by up to 26%, and on average 9%. Moreover, it is used as a tool to reveal potential optimization moves learned automatically

Recent advancements in Large Language Models (LLMs) have led to increasingly diverse requests, accompanied with varying resource (compute and memory) demands to serve them. However, this in turn degrades the cost-efficiency of LLM serving as common practices primarily rely on homogeneous GPU resources. In response to this problem, this work conducts a thorough study about serving LLMs over heterogeneous GPU resources on cloud platforms. The rationale is that different GPU types exhibit distinct compute and memory characteristics, aligning well with the divergent resource demands of diverse requests. Particularly, through comprehensive benchmarking, we discover that the cost-efficiency of LLM serving can be substantially optimized by meticulously determining GPU composition, deployment configurations, and workload assignments. Subsequently, we design a scheduling algorithm via mixed-integer linear programming, aiming at deducing the most cost-efficient serving plan under the constraints of price budget and real-time GPU availability. Remarkably, our approach effectively outperforms homogeneous and heterogeneous baselines under a wide array of scenarios, covering diverse workload traces, varying GPU availablilities, and multi-model serving. This casts new light on more accessible and efficient LLM serving over heterogeneous cloud resources.

The scaling law for large language models (LLMs) depicts that the path towards machine intelligence necessitates training at large scale. Thus, companies continuously build large-scale GPU clusters, and launch training jobs that span over thousands of computing nodes. However, LLM pre-training presents unique challenges due to its complex communication patterns, where GPUs exchange data in sparse yet high-volume bursts within specific groups. Inefficient resource scheduling exacerbates bandwidth contention, leading to suboptimal training performance. This paper presents Arnold, a scheduling system summarizing our experience to effectively align LLM communication patterns to data center topology at scale. In-depth characteristic study is performed to identify the impact of physical network topology to LLM pre-training jobs. Based on the insights, we develop a scheduling algorithm to effectively align communication patterns to physical network topology in data centers. Through simulation experiments, we show the effectiveness of our algorithm in reducing the maximum spread of communication groups by up to $1.67$x. In production training, our scheduling system improves the end-to-end performance by $10.6\%$ when training with more than $9600$ Hopper GPUs, a significant improvement for our training pipeline.

Learned Index Structures (LIS) have significantly advanced data management by leveraging machine learning models to optimize data indexing. However, designing these structures often involves critical trade-offs, making it challenging for both designers and end-users to find an optimal balance tailored to specific workloads and scenarios. While some indexes offer adjustable parameters that demand intensive manual tuning, others rely on fixed configurations based on heuristic auto-tuners or expert knowledge, which may not consistently deliver optimal performance. This paper introduces LIT une , a novel framework for end-to-end automatic tuning of Learned Index Structures. LIT une employs an adaptive training pipeline equipped with a tailor-made Deep Reinforcement Learning (DRL) approach to ensure stable and efficient tuning. To accommodate long-term dynamics arising from online tuning, we further enhance LIT une with an on-the-fly updating mechanism termed the O2 system. These innovations allow LIT une to effectively capture state transitions in online tuning scenarios and dynamically adjust to changing data distributions and workloads, marking a significant improvement over other tuning methods. Our experimental results demonstrate that LIT une achieves up to a 98% reduction in runtime and a 17-fold increase in throughput compared to default parameter settings given a selected Learned Index instance. These findings highlight LIT une 's effectiveness and its potential to facilitate broader adoption of LIS in real-world applications.

The real-world effectiveness of deep neural networks often depends on their latency, thereby necessitating optimization techniques that can reduce a model’s inference time while preserving its performance. One popular approach is to sequentially rewrite the input computation graph into an equivalent but faster one by replacing individual subgraphs. This approach gives rise to the so-called phase-ordering problem in which the application of one rewrite rule can eliminate the possibility to apply an even better one later on. Recent work has shown that equality saturation, a technique from compiler optimization, can mitigate this issue by first building an intermediate representation (IR) that efficiently stores multiple optimized versions of the input program before extracting the best solution in a second step. In practice, however, memory constraints prevent the IR from capturing all optimized versions and thus reintroduce the phase-ordering problem in the construction phase. In this paper, we present a tensor graph rewriting approach that uses Monte Carlo tree search to build superior IRs by identifying the most promising rewrite rules. We also introduce a novel extraction algorithm that can provide fast and accurate runtime estimates of tensor programs represented in an IR. Our approach improves the inference speedup of neural networks by up to 11% compared to existing methods.

We explore the feasibility of combining Graph Neural Network-based policy architectures with Deep Reinforcement Learning as an approach to problems in systems. This fits particularly well with operations on networks, which naturally take the form of graphs. As a case study, we take the idea of data-driven routing in intradomain traffic engineering, whereby the routing of data in a network can be managed taking into account the data itself. The particular subproblem which we examine is minimising link congestion in networks using knowledge of historic traffic flows. We show through experiments that an approach using Graph Neural Networks (GNNs) performs at least as well as previous work using Multilayer Perceptron architectures. GNNs have the added benefit that they allow for the generalisation of trained agents to different network topologies with no extra work. Furthermore, we believe that this technique is applicable to a far wider selection of problems in systems research.

The past few years have seen significant developments in Single Board Computer (SBC) hardware capabilities. These advances in SBCs translate directly into improvements in SBC clusters. In 2018 an individual SBC has more than four times the performance of a 64-node SBC cluster from 2013. This increase in performance has been accompanied by increases in energy efficiency (GFLOPS/W) and value for money (GFLOPS/$). We present systematic analysis of these metrics for three different SBC clusters composed of Raspberry Pi 3 Model B, Raspberry Pi 3 Model B+ and Odroid C2 nodes respectively. A 16-node SBC cluster can achieve up to 60 GFLOPS, running at 80 W. We believe that these improvements open new computational opportunities, whether this derives from a decrease in the physical volume required to provide a fixed amount of computation power for a portable cluster; or the amount of compute power that can be installed given a fixed budget in expendable compute scenarios. We also present a new SBC cluster construction form factor named Pi Stack; this has been designed to support edge compute applications rather than the educational use-cases favoured by previous methods. The improvements in SBC cluster performance and construction techniques mean that these SBC clusters are realising their potential as valuable developmental edge compute devices rather than just educational curiosities.

No abstract available.

Until recently, cluster computing was too expensive and too complex for commodity users. However the phenomenal popularity of single board computers like the Raspberry Pi has caused the emergence of the single board computer cluster. This demonstration will present a cheap, practical and portable Raspberry Pi cluster called Pi Stack. We will show pragmatic custom solutions to hardware issues, such as power distribution, and software issues, such as remote updating. We also sketch potential use cases for Pi Stack and other commodity single board computer cluster architectures.

Current commodity Single Board Computers (SBCs) are sufficiently powerful to run mainstream operating systems and workloads. Many of these boards may be linked together, to create small, low-cost clusters that replicate some features of large data center clusters. The Raspberry Pi Foundation produces a series of SBCs with a price/performance ratio that makes SBC clusters viable, perhaps even expendable. These clusters are an enabler for Edge/Fog Compute, where processing is pushed out towards data sources, reducing bandwidth requirements and decentralizing the architecture. In this paper we investigate use cases driving the growth of SBC clusters, we examine the trends in future hardware developments, and discuss the potential of SBC clusters as a disruptive technology. Compared to traditional clusters, SBC clusters have a reduced footprint, are low-cost, and have low power requirements. This enables different models of deployment—particularly outside traditional data center environments. We discuss the applicability of existing software and management infrastructure to support exotic deployment scenarios and anticipate the next generation of SBC. We conclude that the SBC cluster is a new and distinct computational deployment paradigm, which is applicable to a wider range of scenarios than current clusters. It facilitates Internet of Things and Smart City systems and is potentially a game changer in pushing application logic out towards the network edge.

Due to their complexity, modern systems expose many configuration parameters which users must tune to maximize performance. Auto-tuning has emerged as an alternative in which a black-box optimizer iteratively evaluates configurations to find efficient ones. Unfortunately, for many systems, such as distributed systems, evaluating performance takes too long and the space of configurations is too large for the optimizer to converge within a reasonable time.

Today, web performance is primarily governed by round-trip latencies between end devices and cloud services. To improve performance, services need to minimize the delay of accessing data. In this paper, we propose a novel approach to low latency that relies on existing content delivery and web caching infrastructure. The main idea is to enable application-independent caching of query results and records with tunable consistency guarantees, in particular bounded staleness. Q uaestor (Query Store) employs two key concepts to incorporate both expiration-based and invalidation-based web caches: (1) an Expiring Bloom Filter data structure to indicate potentially stale data, and (2) statistically derived cache expiration times to maximize cache hit rates. Through a distributed query invalidation pipeline, changes to cached query results are detected in real-time. The proposed caching algorithms offer a new means for data-centric cloud services to trade latency against staleness bounds, e.g. in a database-as-a-service. Q uaestor is the core technology of the backend-as-a-service platform Baqend, a cloud service for low-latency websites. We provide empirical evidence for Q uaestor 's scalability and performance through both simulation and experiments. The results indicate that for read-heavy workloads, up to tenfold speed-ups can be achieved through Q uaestor 's caching.

This paper presents the first distributed triangle listing algorithm with provable CPU, I/O, Memory, and Network bounds. Finding all triangles (3-cliques) in a graph has numerous applications for density and connectivity metrics, but the majority of existing algorithms for massive graphs are sequential, while distributed versions of algorithms do not guarantee their CPU, I/O, Memory, or Network requirements. Our Parallel and Distributed Triangle Listing (PDTL) framework focuses on efficient external-memory access in distributed environments instead of fitting sub graphs into memory. It works by performing efficient orientation and load-balancing steps, and replicating graphs across machines by using an extended version of Hu et al.'s Massive Graph Triangulation algorithm. PDTL suits a variety of computational environments, from single-core machines to high-end clusters, and computes the exact triangle count on graphs of over 6B edges and 1B vertices (e.g. Yahoo graphs), outperforming and using fewer resources than the state-of-the-art systems Power Graph, OPT, and PATRIC by 2x to 4x. Our approach thus highlights the importance of I/O in a distributed environment.

Mining large graphs has now become an important aspect of multiple diverse applications and a number of computer systems have been proposed to provide runtime support. Recent interest in this area has led to the construction of single machine graph computation systems that use solid state drives (SSDs) to store the graph. This approach reduces the cost and simplifies the implementation of graph algorithms, making computations on large graphs available to the average user. However, SSDs are slower than main memory, and making full use of their bandwidth is crucial for executing graph algorithms in a reasonable amount of time. In this paper, we present PrefEdge, a prefetcher for graph algorithms that parallelises requests to derive maximum throughput from SSDs. PrefEdge combines a judicious distribution of graph state between main memory and SSDs with an innovative read-ahead algorithm to prefetch needed data in parallel. This is in contrast to existing approaches that depend on multi-threading the graph algorithms to saturate available bandwidth. Our experiments on graph algorithms using random access show that PrefEdge not only is capable of maximising the throughput from SSDs but is also able to almost hide the effect of I/O latency. The improvements in runtime for graph algorithms is up to 14× when compared to a single threaded baseline. When compared to multi-threaded implementations, PrefEdge performs up to 80% faster without the program complexity and the programmer effort needed for multi-threaded graph algorithms.

This paper presents a technique for analysis of dynamic contact networks aimed at extracting periods of time during which the network changes behaviour. The technique is based on tracking the eigenvectors of the contact network in time (efficiently) using a technique called Joint Diagonalisation (JD). Repeated application of JD then shows that real-world networks naturally break into several modes of operation which are time dependent and in one real-world case, even periodic. This shows that a view of real-world contact networks as realisations from a single underlying static graph is mistaken. However, the analysis also shows that a small finite set of underlying static graphs can approximate the dynamic contact graphs studied. We also provide the means by which these underlying approximate graphs can be constructed.

A recent topic of research in the network science community is combined or composite networks - these are two or more interacting networks that must be characterized jointly rather than individually. For example, a social network and a communication network sharing some nodes (corresponding to users) may be modeled together as a composite network. This may be useful since the aggregate performance of a composite network may often depend on how the individual networks influence each other. Information may travel faster or slower through composite networks depending on how they are coupled. The above vision was captured in the Call for Papers for this special issue in the IEEE Journal On Selected Areas In Communications, and it was published in June 2012. As a result of this solicitation, we received 62 submissions by the deadline of August 15, 2012. Papers were selected after two rigorous rounds of review. The first round of notifications were sent out on December 17, 2012 to the authors whose papers passed the first round of review. Revised versions of the papers were submitted on January 31, 2013. Finally, after a second round of review, the Guest Editorial board decided on March 12, 2013 to accept 16 high quality papers for publication in this competitive special issue. Papers appearing in this special issue belong to five broad themes, which are not necessarily mutually exclusive: (1) fundamental principles in network science, (2) information propagation models in networks, (3) bringing insights from other genres of networks, (4) economic and game theoretic models, and (5) application of network science principles to communications networking problems.

In modern politics, parties and individual candidates must have an online presence and usually have dedicated social media coordinators. In this context, we study the usefulness of analysing Twitter messages to identify both the characteristics of political parties and the political leaning of users. As a case study, we collected the main stream of Twitter related to the 2010 UK General Election during the associated period -- gathering around 1,150,000 messages from about 220,000 users. We examined the characteristics of the three main parties in the election and highlighted the main differences between parties. First, Lab our members were the most active and influential during the election while Conservative members were the most organized to promote their activities. Second, the websites and blogs that each political party's members supported are clearly different from those that all the other political parties' members supported. From these observations, we develop a simple and practical classification method which uses the number of Twitter messages referring to a particular political party. The experimental results showed that the proposed classification method achieved about 86% classification accuracy and outperforms other classification methods that require expensive costs for tuning classifier parameters and/or knowledge about network topology.

The problem of maximizing information diffusion through a network is a topic of considerable recent interest. A conventional problem is to select a set of any arbitrary k nodes as the initial influenced nodes so that they can effectively disseminate the information to the rest of the network. However, this model is usually unrealistic in online social networks since we cannot typically choose arbitrary nodes in the network as the initial influenced nodes. From the point of view of an individual user who wants to spread information as much as possible, a more reasonable model is to try to initially share the information with only some of its neighbours rather than a set of any arbitrary nodes; but how can these neighbours be effectively chosen? We empirically study how to design more effective neighbours selection strategies to maximize information diffusion. Our experimental results through intensive simulation on several real- world network topologies show that an effective neighbours selection strategy is to use node degree information for short-term propagation while a naive random selection is also adequate for long-term propagation to cover more than half of a network. We also discuss the effects of the number of initial activated neighbours. If we particularly select the highest degree nodes as initial activated neighbours, the number of initial activated neighbours is not an important factor at least for long-term propagation of information.

A variety of personal backup services now allow users to synchronise their files across multiple devices such as laptops and smartphones. These applications typically operate by synchronising each device with a centralised storage service across the Internet. However, access to the Internet may occasionally not be available, leaving any unsynchronised content in a vulnerable state. To address this, applications could alternatively make use of storage capacity provided by other devices within close proximity, using ad-hoc or local network connectivity. Such devices can provide a secondary storage tier in case of Internet connectivity issues, and could also be used to forward files to central storage at a later time. In our proposed design, we delegate the task of propagating information across locally networked devices to a lower layer, by making use of a content-centric opportunistic network platform (Haggle). This allows our application, Mistify, to treat the neighbourhood of peers as a single distributed content repository (or “mist”), in a manner similar to the way in which existing applications interface with the cloud. Mistify employs a differentiated replication strategy, with the aim of improving the safety of items in the mist. In our evaluation of the prototype, we have found that in a simulated network of locally-connected peers, the prototype was able to achieve a high level of availability for stored content, without resorting to flooding. Furthermore, Mistify was able to deliver a high proportion of content to the cloud, even when only a small proportion of nodes were given Internet connectivity.

The increasing penetration of smart devices with networking capability form novel networks. Such networks, also referred as pocket switched networks (PSNs), are intermittently connected and represent a paradigm shift of forwarding data in an ad hoc manner. The social structure and interaction of users of such devices dictate the performance of routing protocols in PSNs. To that end, social information is an essential metric for designing forwarding algorithms for such types of networks. Previous methods relied on building and updating routing tables to cope with dynamic network conditions. On the downside, it has been shown that such approaches end up being cost ineffective due to the partial capture of the transient network behavior. A more promising approach would be to capture the intrinsic characteristics of such networks and utilize them in the design of routing algorithms. In this paper, we exploit two social and structural metrics, namely centrality and community, using real human mobility traces. The contributions of this paper are two-fold. First, we design and evaluate BUBBLE, a novel social-based forwarding algorithm, that utilizes the aforementioned metrics to enhance delivery performance. Second, we empirically show that BUBBLE can substantially improve forwarding performance compared to a number of previously proposed algorithms including the benchmarking history-based PROPHET algorithm, and social-based forwarding SimBet algorithm.

There is substantial interest in the effect of human mobility patterns on opportunistic communications. Inspired by recent work revisiting some of the early evidence for a Lévy flight foraging strategy in animals, we analyse datasets on human contact from real world traces. By analysing the distribution of inter-contact times on different time scales and using different graphical forms, we find not only the highly skewed distributions of waiting times highlighted in previous studies but also clear circadian rhythm. The relative visibility of these two components depends strongly on which graphical form is adopted and the range of time scales. We use a simple model to reconstruct the observed behaviour and discuss the implications of this for forwarding efficiency.

We envision new communication paradigms, using physical dynamic interconnectedness among people. Delay Tolerant Networks (DTNs) are a new communication paradigm to support such network environments, and our focus is a type of DTN that provides intermittent communication for humans carrying mobile devices: the Pocket Switched Network (PSN). Information propagation in PSNs is highly influenced by human connectivity networks, i.e. social networks. In our previous work, we have exploited constructing weighted networks using characteristics of pair connections such as the duration of contact time and frequency of contacts from time series of human connectivity network traces. The approach we took is based on empirical and heuristic and the focus is finding a single aggregated logical network structure. The physical network topology in the real world is time dependent and it is a complex task to describe its dynamics. This paper aims to identify dynamics of meeting groups in human connectivity traces, where meeting groups are expected to be a group interacting among the nodes in physical space. Thus, we define dasiameeting grouppsila differently from dasiacommunitypsila. We exploit statistical approach that provides quantitative attributes to uncover meeting groups. We identify the power law behavior of meetings that is important for supporting to understanding dynamics of information flow between meeting groups and building group oriented communication protocol.

In this paper we seek to improve our understanding of human mobility in terms of social structures, and to use these structures in the design of forwarding algorithms for Pocket Switched Networks (PSNs). Taking human mobility traces from the real world, we discover that human interaction is heterogeneous both in terms of hubs (popular individuals) and groups or communities. We propose a social based forwarding algorithm, BUBBLE, which is shown empirically to improve the forwarding efficiency significantly compared to oblivious forwarding schemes and to PROPHET algorithm. We also show how this algorithm can be implemented in a distributed way, which demonstrates that it is applicable in the decentralised environment of PSNs.

The emergence of Delay Tolerant Networks (DTNs) has culminated in a new generation of wireless networking. We focus on a type of human-to-human communication in DTNs, where human behaviour exhibits the characteristics of networks by forming a community. We show the characteristics of such networks from extensive study of real-world human connectivity traces. We exploit distributed community detection from the trace and propose a Socio-Aware Overlay over detected communities for publish/subscribe communication. Centrality nodes have the best visibility to the other nodes in the network. We create an overlay with such centrality nodes from communities. Distributed community detection operates when nodes (i.e. devices) are in contact by gossipping, and subscription propagation is performed along with this operation. We validate our message dissemination algorithms for publish/subscribe with connectivity traces.

Event broker grids, that deploy the publish/subscribe communication paradigm, extend the capabilities of seamless messaging in heterogeneous network environments. In order to support such mixed network environments, we integrate publish/subscribe semantics with multicast routing in mobile ad hoc networks. Dynamic construction of an event dissemination structure to route events from event publishers to subscribers is especially important to support highly dynamic, self-organizing, mobile peer-to-peer systems. The proposed approach aggregates content-based subscriptions in a compact data format (Bloom filters), and ODMRP (on-demand multicast routing protocol) is extended to use this context from the middleware-tier to construct an optimized dynamic dissemination mesh. Thus, dynamic multicast groups are created by aggregating subscriptions, applying K-means clustering and other methods. Cooperation between the middleware-tier and network components allows fine-grained subscriptions to be represented.