Distributed training of Deep Learning (DL) models on resource-constrained devices has gained significant interest. Training data-driven DL models collaboratively using federated learning (FL) and split learning (SL) have become the most popular ways to do this task. We aim to optimize these techniques by reducing device computation during parallel model training and reducing high-communication costs due to the frequent exchange of models, data, and gradients. This article proposes efficient SL (ESL), a novel approach addressing these challenges through three key ideas: 1) a key-value store for caching and sharing intermediate activations across clients, significantly reducing redundant computations and communication during the training phase; 2) customization of state-of-the-art neural networks for SL context; and 3) personalized training allowing clients to learn individual models tailored to their specific data distributions. Existing communication-efficient FL/SL methods trade accuracy to reduce communication. In contrast, ESL achieves significant communication reduction while maintaining high accuracy. Extensive experimentation on real-world federated benchmarks for image classification and 3-D segmentation demonstrates significant improvements over baseline FL techniques: ESL achieves a reduction in computation by$1623 \times $for image classification and$23.9 \times $for 3-D segmentation on resource-constrained devices. Additionally, it reduces communication traffic, during training, between clients and the server by$3.92 \times $for image classification and$1.3 \times $for 3-D segmentation while improving average accuracy by 35% and 31%, respectively. Furthermore, when compared to the baseline SL approaches, ESL reduces communication traffic during training by$100 \times $and improves accuracy by an average of 34.8%.

The traditional framework of federated learning (FL) requires each client to re-train their models in every iteration, making it infeasible for resource-constrained mobile devices to train deep-learning (DL) models. Split learning (SL) provides an alternative by using a centralized server to offload the computation of activations and gradients for a subset of the model but suffers from problems of slow convergence and lower accuracy. In this paper, we implement PFSL, a new framework of distributed split learning where a large number of thin clients perform transfer learning in parallel, starting with a pre-trained DL model without sharing their data or labels with a central server. We implement a lightweight step of personalization of client models to provide high performance for their respective data distributions. Furthermore, we evaluate performance fairness amongst clients under a work fairness constraint for various scenarios of non-i.i.d. data distributions and unequal sample sizes. Our accuracy far exceeds that of current SL algorithms and is very close to that of centralized learning on several real-life benchmarks. It has a very low computation cost compared to FL variants and promises to deliver the full benefits of DL to extremely thin, resource-constrained clients.

Several distributed frameworks have been developed to scale Graph Neural Networks (GNNs) on billion-size graphs. On several benchmarks, we observe that the graph partitions generated by these frameworks have heterogeneous data distributions and class imbalance, affecting convergence, and resulting in lower performance than centralized implementations. We holistically address these challenges and develop techniques that reduce training time and improve accuracy. We develop an Edge-Weighted partitioning technique to improve the micro average F1 score (accuracy) by minimizing the total entropy. Furthermore, we add an asynchronous personalization phase that adapts each compute-host’s model to its local data distribution. We design a class-balanced sampler that considerably speeds up convergence. We implemented our algorithms on the DistDGL framework and observed that our training techniques scale much better than the existing training approach. We achieved a (2-3x) speedup in training time and 4% improvement on average in micro-F1 scores on 5 large graph benchmarks compared to the standard baselines.

With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop traffic and the one-hop interference model. The objective is twofold: 1) maximizing the throughput when the flow sources continuously inject packets into the network, and 2) minimizing the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we propose a novel Node-based Service-Balanced (NSB) online scheduling algorithm. NSB aims to give scheduling opportunities to heavily congested nodes in a balanced manner, by maximizing the total weight of the scheduled nodes in each scheduling cycle, where the weight of a node is determined by its workload and whether the node was scheduled in the previous scheduling cycle(s). We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.

Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop flows and the one-hop interference model. The objective is twofold: 1) maximize the throughput when the flow sources continuously inject packets into the network, and 2) minimize the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we adopt a novel node-based approach and propose a service-balanced online scheduling algorithm, called NSB, which gives balanced scheduling opportunities to the nodes with heavy workload. We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.

In this paper, we focus on the scheduling problem in multichannel wireless networks, e.g., the downlink of a single cell in fourth-generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of O(n2.5log n)-complexity hybrid scheduling policies is recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a lower complexity 2n2+2n, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, the rate-function of the delay-violation probability attained by D-SSG for any fixed integer delay threshold b > 0 is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Thus, we are able to achieve a reduction in complexity (from O(n2.5logn) of the hybrid policies to 2n2+ 2n) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the O(·) notation. Finally, we conduct simulations to validate our theoretical results in various scenarios. The simulation results show that in all scenarios we consider, D-SSG not only guarantees a near-optimal rate-function, but also empirically has a similar delay performance to the rate-function delay-optimal policies.

Emerging trends in computer design and use are likely to make exceptions, once rare, the norm, especially as the system size grows. Due to exceptions, arising from hardware faults, approximate computing, dynamic resource management, etc., successful and error-free execution of programs may no longer be assured. Yet, designers will want to tolerate the exceptions so that the programs execute completely, efficiently and without external intervention.

Future multicore processors will be heterogeneous, be increasingly less reliable, and operate in dynamically changing operating conditions. Such environments will result in a constantly varying pool of hardware resources which can greatly complicate the task of efficiently exposing a program's parallelism onto these resources. Coupled with this uncertainty is the diverse set of efficiency metrics that users may desire. This paper proposes Varuna, a system that dynamically, continuously, rapidly and transparently adapts a program's parallelism to best match the instantaneous capabilities of the hardware resources while satisfying different efficiency metrics. Varuna is applicable to both multithreaded and task-based programs and can be seamlessly inserted between the program and the operating system without needing to change the source code of either.

In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n2.5log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n5). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.

The ubiquity of parallel machines will necessitate time- and energy-efficient parallel execution of a program in a wide range of hardware and software environments. Prevalent parallel execution models can fail to be efficient. Unable to account for dynamic changes in operating conditions, they may create non-optimum parallelism, leading to underutilization or contention of resources. We propose ParallelismDial (PD), a model to dynamically, continuously and judiciously adapt a program's degree of parallelism to a given dynamic operating environment. PD uses a holistic metric to measure system-efficiency. The metric is used to systematically optimize the program's execution.

In this paper, we focus on the scheduling problem in multi-channel wireless networks, e.g., the downlink of a single cell in fourth generation (4G) OFDM-based cellular networks. Our goal is to design efficient scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a recently developed scheduling policy, called Delay Weighted Matching (DWM), has been shown to be both rate-function delay-optimal (in the many-channel many-user asymptotic regime) and throughput-optimal (in general non-asymptotic setting), it has a high complexity O(n5), which makes it impractical for modern OFDM systems. To address this issue, we first develop a simple greedy policy called Delay-based Queue-Side-Greedy (D-QSG) with a lower complexity O(n3), and rigorously prove that D-QSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically, the rate-function attained by D-QSG for any fixed integer threshold b>0, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n2), and show that D-SSG achieves the same performance as D-QSG. Thus, we are able to achieve a dramatic reduction in complexity (from O(n5) of DWM to O(n2)) with a minimal drop in the delay performance. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that our proposed greedy policies not only guarantee a near-optimal rate-function, but also empirically are virtually indistinguishable from the delay-optimal policy DWM.

LTE is the next generation of all-IP mobile communication system designed and developed by 3GPP. It offers unprecedented data transmission speed and low latency to support a variety of applications and services. However, compared to wireline networks, efficient QoS provisioning for diversified applications in wireless access networks such as LTE is challenging due to unreliable and resource-constrained radio interface. In this paper, we investigate an important problem of downlink resource allocation in recently enhanced LTE-Advanced systems where a newly added feature carrier aggregation provides more flexibility in radio resource management in addition to the existing resource block level packet scheduling. The resource allocation problem can be formulated as a complex combinatorial problem with multiple constraints and is solved every time slot. We decompose this highly complex optimization problem and construct a two-tier resource allocation framework which incorporates dynamic component carrier assignment and backlog based scheduling schemes with intelligent link adaptation. An efficient algorithm is developed to dynamically allocate component carriers to users to achieve load balancing. We also present novel backlog based scheduling policies and weighted-CQI based link adaptation scheme to obtain significantly better throughput and delay fairness. Performance of the proposed schemes is evaluated against the static round-robin component carrier assignment, the well-known proportional fairness scheduling rule and the existing link adaptation scheme. Extensive simulation results demonstrate that our schemes offer both better throughput and delay performance as well as user fairness.

As multicore processors become the default, researchers are aggressively looking for program execution models that make it easier to use the available resources. Multithreaded programming models that rely on statically-parallel programs have gained prevalence. Most of the existing research is directed at adapting and enhancing such models, alleviating their drawbacks, and simplifying their usage. This paper takes a different approach and proposes a novel execution model to achieve parallel execution of statically-sequential programs. It dynamically parallelizes the execution of suitably-written sequential programs, in a dataflow fashion, on multiple processing cores. Significantly, the execution is race-free and determinate. Thus the model eases program development and yet exploits available parallelism.

We analyze the delay performance of a multihop wireless network with a fixed route between each source–destination pair. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multihop nature of the flows. A general set-based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample-path delay-optimal. For the tandem queue network, where the delay-optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. We conduct extensive numerical studies to suggest that the average delay of the back-pressure scheduling policy can be made close to the lower bound by using appropriate functions of queue length.

Network contention has a significantly adverse effect on the performance of parallel applications with increasing size of parallel machines. Machines of the petascale era are forcing application developers to map tasks intelligently to job partitions to achieve the best performance possible. This paper presents a framework for automated mapping of parallel applications with regular communication graphs to two and three dimensional mesh and torus networks. This framework will save much effort on the part of application developers to generate mappings for their individual applications. One component of the framework is a process topology analyzer to find regular patterns and if found, to determine the dimensions of the communication graphs of applications. The other component is a suite of heuristic techniques for mapping 2D object grids to 2D and 3D processor meshes. The framework chooses the best heuristic from the suite for a given object grid and processor mesh pair based on the hop-bytes metric. We show performance improvements using the framework, for a 2D Stencil benchmark in MPI and the Weather Research and Forecasting model running on the IBM Blue Gene/P. We also compare our algorithms with others discussed in literature.

Predicting sequential execution blocks of a large scale parallel application is an essential part of accurate prediction of the overall performance of the application. When simulating a future machine, or a prototype system only available at a small scale, it becomes a significant challenge. Using hardware simulators may not be feasible due to excessively slowed down execution times and insufficient resources. The difficulty of these challenges increases proportionally with the scale of the simulation. In this paper, we propose an approach based on statistical models to accurately predict the performance of the sequential execution blocks that comprise a parallel application. We deployed these techniques in a trace-driven simulation framework to capture both the detailed behavior of the application as well as the overall predicted performance. The technique is validated using both synthetic benchmarks and the NAMD application.

We analyze the delay performance of a multi-hop wireless network with a fixed route between each source-destination pair. There are arbitrary interference constraints on the set of links that can be served simultaneously at any given time. These interference constraints impose a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a methodology to derive such lower bounds. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. We conduct extensive numerical studies to suggest that the average delay of the back-pressure scheduling policy can be made close to the lower bound by using appropriate functions of queue length.

We develop a class of schemes called GMWM that guarantee optimal throughput for queuing systems with arbitrary constraints on the set of jobs that can be served simultaneously. We obtain an analytical upper bound on the expected queue length. To further tighten the upper bound, we formulate it as a convex optimization problem. We also show that whenever the arrival process is stabilizable, the scheme is guaranteed to achieve an expected queue length that is no larger than the expected queue length of any stationary randomized policy.

We develop a level set estimation algorithm for a novel low cost sensor network architecture, where sensors are mounted on agents moving without an explicit objective of sensing. A level set in a planar scalar field is the set of points with field values greater than or equal to a specified threshold. The distributed algorithm uses opportunistic information exchange to estimate level set boundaries locally at nodes selected using leader election. Such estimates are aggregated at the base station. Effectiveness of the proposed scheme is evaluated using simulations with data from both synthetic and measured fields. Random way point mobility model is used for node motion and accuracy and trade off of coverage with communication costs is studied.

We address the problem of estimating controller delay from high-level specifications during behavioral synthesis. Typically, the critical path of a synthesised behavioral design goes through both the datapath and the control logic; yet most scheduling algorithms account only for datapath and ignore control delay, leading to timing uncertainties in the resulting designs. We present an estimation technique for computing a fast, robust, scalable, and reasonably accurate approximation of the control delay from behavioral specifications. The delay estimate is formulated in terms of the properties of the input specification and other inputs to the synthesis process such as resource constraints.