Models of parallel processing systems typically assume that one has$l$workers and jobs are split into an equal number of$k=l$tasks. Splitting jobs into$k > l$smaller tasks, i.e. using “tiny tasks”, can yield performance and stability improvements because it reduces the variance in the amount of work assigned to each worker, but as$k$increases, the overhead involved in scheduling and managing the tasks begins to overtake the performance benefit. We perform extensive experiments on the effects of task granularity on an Apache Spark cluster, and based on these, develop a four-parameter model for task and job overhead that, in simulation, produces sojourn time distributions that match those of the real system. We also present analytical results which illustrate how using tiny tasks improves the stability region of split-merge systems, and analytical bounds on the sojourn and waiting time distributions of both split-merge and single-queue fork-join systems with tiny tasks. Finally we combine the overhead model with the analytical models to produce an analytical approximation to the sojourn and waiting time distributions of systems with tiny tasks which include overhead. We also perform analogous tiny-tasks experiments on a hybrid multi-processor shared memory system based on MPI and OpenMP which has no load-balancing between nodes. Though no longer strict analytical bounds, our analytical approximations with overhead match both the Spark and MPI/OpenMP experimental results very well.

Parallel systems divide jobs into smaller tasks that can be serviced by many workers at the same time. Some parallel systems have blocking barriers that require all of their tasks to start and/or depart in unison. This is true of many parallelized machine learning workloads, and the popular Apache Spark processing engine has recently added support for Barrier Execution Mode, which allows users to add such barriers to their jobs. The drawback of these barriers is reduced performance and stability compared to equivalent non-blocking systems.We derive analytical expressions for the stability regions for parallel systems with blocking start and/or departure barriers. We extend results from queueing theory to derive waiting and sojourn time bounds for systems with blocking start barriers. Our results show that for a given system utilization and number of servers, there is an optimal degree of parallelism that balances waiting time and job execution time. This observation leads us to propose and implement a class of self-adaptive schedulers, we call "Take-Half", that modulate the allowed degree of parallelism based on the instantaneous system load, improving mean performance and eliminating stability issues.

Models of parallel processing systems typically assume that one has l servers and jobs are split into an equal number of k = l tasks. This seemingly simple approximation has surprisingly large consequences for the resulting stability and performance bounds. In reality, best practices for modern mapreduce systems indicate that a job's partitioning factor should be much larger than the number of servers available, with some researchers going to far as to advocate for a "tiny tasks" regime, where jobs are split into over 10,000 tasks. In this paper we use recent advances in stochastic network calculus to fundamentally understand the effects of task granularity on parallel systems' scaling, stability, and performance. For the split-merge model, we show that when one allows for tiny tasks, the stability region is actually much better than had previously been concluded. For the single-queue fork-join model, we show that sojourn times quickly approach the optimal case when l "big tasks" are subdivided into k≫ l "tiny tasks". Our results are validated using extensive simulations, and the applicability of the models used is validated by experPiments on an Apache Spark cluster.

Recently, the ubiquity of broadband wireless networks has encouraged the growth of real-time network applications. Their strict latency requirements present a challenge for traditional Internet protocols which tend to be designed to optimize mean performance. Two recent developments that show promise for addressing the challenges of real-time applications are QUIC, a UDP-based protocol that has many features of TCP, and multipath transmission, an extension allowing transport layer protocols to transmit data simultaneously over multiple network paths and interfaces. In this paper, we present MAppLE (MPQUIC Application Latency Evaluation platform), which provides the instrumentation needed to evaluate and develop MPQUIC stream multiplexers, stream schedulers, and multipath packet schedulers. We also present our NineTails scheduler, a multipath MPQUIC scheduler that utilizes selective multipath redundancy to control tail loss and near-tail loss latencies. Our experimental results show that in a lossy asymmetric heterogeneous wireless network, our proposed scheduler reduces outlier latencies compared to other existing scheduling algorithms, and improves Quality of Experience (QoE) in video streaming by inducing fewer playback rebuffering events.

Parallel computing has become a standard tool with architectures such as Google MapReduce, Hadoop, and Spark being broadly used in applications such as data processing and machine learning. Common to these systems are a fork operation, where jobs are first divided into tasks that are processed in parallel, and a join operation where completed tasks wait for the other tasks of the job before leaving the system. The synchronization constraint of the join operation makes the analysis of fork-join systems challenging, and few explicit results are known. In this work, we formulate a max-plus server model for parallel systems which allows us to derive performance bounds for a variety of systems in the GII GI and G I G cases. We contribute end-to-end delay bounds for multi-stage fork-join networks. We perform a detailed comparison of different multi-server configurations, including an analysis of single-queue fork-join systems that achieve a fundamental performance gain. We compare these results to both simulation and a live Spark system.

We consider an opportunistic wireless network where data repositories provide mobile users access to locally-cached data objects. In this setting using network/erasure coding to disseminate large data objects can greatly improve the performance and robustness of the network, but it becomes more difficult to plan, coordinate, and analyze the distribution of information. We introduce a simplicial data structure, the coverage complex, that captures enough of both the structure of the code and the geometry of the network that it can be used to draw conclusions about network coded data coverage. We give a distributed algorithm for computing the coverage complex based on local information, prove results on using it for coverage testing, and study more complicated cases where coverage testing can fail.

In order to better understand human and animal mobility and its potential effects on Mobile Ad-Hoc networks and Delay-Tolerant Networks, many researchers have conducted experiments which collect encounter data. Most analyses of these data have focused on isolated statistical properties such as the distribution of node inter-encounter times and the degree distribution of the connectivity graph.