In this paper we consider filtering and processing large data streams in intelligent data acquisition systems.It is assumed that raw data arrives in discrete events from a single expensive sensor.Not all raw data, however, comprises records of interesting events and hence some part of the input must be filtered out.The intensity of filtering is an important design choice because it determines the complexity of filtering hardware and software and the amount of data that must be transferred to the following processing stages for further analysis.This, in turn, dictates needs for the following stages communication and computational capacity.In this paper we analyze the optimum intensity of filtering and its relationship with the capacity of the following processing stages.A set of generic filtering intensity, data transfer, and processing archetypes are modeled and evaluated.

In distributed computing frameworks like MapReduce, Spark, and Dyrad, a coflow is a set of flows transferring data between two stages of a job. The job cannot start its next stage unless all flows in the coflow finish. To improve the execution performance of such a job, it is crucial to reduce the completion time of a coflow, as it can contribute more than 50 percent of the job completion time. While several coflow schedulers have been proposed, we observe that routing, as a factor greatly impacting the Coflow Completion Time (CCT), has not been well considered. In this article, we focus on the coflow scheduling problem and jointly consider routing and bandwidth allocation. We begin by providing an analytical solution to the problem of optimal bandwidth allocation with pre-determined routes. In the following, we formulate the problem of scheduling a single coflow as a Non-linear Mixed Integer Programming problem and present its relaxed convex optimization problem. We further propose two algorithms, CoRBA and its simplified version: CoRBA-fast that solve the single coflow scheduling problem with a joint consideration of routing and bandwidth allocation. Lastly, to address multiple coflows in online scheduling, we propose an online scheduler named OnCoRBA. By comparing with the start-of-the-art algorithms and schedulers via simulations, we demonstrate that CoRBA and CoRBA-fast reduce the CCT by 30-400 percent and the OnCoRBA scheduler reduces the average online CCT by 20-230 percent. In addition, CoRBA-fast can be hundreds times faster than CoRBA with around 8 percent performance degradation compared to CoRBA, which makes the use of CoRBA-fast very appropriate in practice.

In cloud computing, with full control of the underlying infrastructures, cloud providers can flexibly place user jobs on suitable physical servers and dynamically allocate computing resources to user jobs in the form of virtual machines. As a cloud provider, scheduling user jobs in a way that minimizes their completion time is important, as this can increase the utilization, productivity, or profit of a cloud. In this paper, we focus on the problem of scheduling embarrassingly parallel jobs composed of a set of independent tasks and consider energy consumption during scheduling. Our goal is to determine task placement plan and resource allocation plan for such jobs in a way that minimizes the Job Completion Time (JCT). We begin with proposing an analytical solution to the problem of optimal resource allocation with pre-determined task placement. In the following, we formulate the problem of scheduling a single job as a Non-linear Mixed Integer Programming problem and present a relaxation with an equivalent Linear Programming problem. We further propose an algorithm named TaPRA and its simplified version TaPRA-fast that solve the single job scheduling problem. Lastly, to address multiple jobs in online scheduling, we propose an online scheduler named OnTaPRA. By comparing with the start-of-the-art algorithms and schedulers via simulations, we demonstrate that TaPRA and TaPRA-fast reduce the JCT by 40-430 percent and the OnTaPRA scheduler reduces the average JCT by 60-280 percent. In addition, TaPRA-fast can be 10 times faster than TaPRA with around 5 percent performance degradation compared to TaPRA, which makes the use of TaPRA-fast very appropriate in practice.

In this paper, we propose a novel analysis method for divisible load scheduling in mesh, torus and Gaussian network, a new type of interconnection network that has the same node degree as the mesh and torus, but shorter network diameter and shorter average hop distances under equal network size. The divisible scheduling in these three networks are uniformly formulated as the Maximum Finish Time Minimization (MFTM) problem. It involves minimizing the makespan of the load distribution and processing. The MTFM problem, a relaxed MFTM problem, a linear programming problem version and a heuristic algorithm are described and solved. The first three of these problems have identical solutions. The heuristic algorithm is close in performance to the optimal solution, significantly outperforms the previously described dimensional algorithm, and has much wider application range than the previously proposed phase algorithm.

In an iSCSI based storage area network, target hosts serve concurrent I/O requests from initiators to achieve both high throughput and low latency. Existing iSCSI leverages the OS page cache to ensure data sharing and reuse. However, the non-uniform memory access (NUMA) architecture introduces another dimension of complexity, i.e., asymmetric memory access in multi-core and many-core platforms. Within a NUMA platform, an iSCSI target often dispatches an access request with a cache hit to an I/O thread remote to cached data, and thus cannot fully utilize multi-core systems. We encounter this problem in the context of ultra high-speed data transfer between two iSCSI storage systems, during which inferior NUMA remote memory access lags behind available high network bandwidth, and thereby becomes a bottleneck of the entire end-to-end data transfer path. We design a NUMA-aware cache mechanism to align cache memory with local NUMA nodes and threads, and then schedule I/O requests to those threads that are local to the data being accessed. This NUMA-aware solution results in lower access latency and higher system throughput. We implement a cache system within the Linux SCSI target framework, and evaluated it on our NUMA-based iSCSI testbed. Experimental results show the NUMA-aware cache can significantly improve the performance of iSCSI as measured by several benchmark tools and confirm its viability in data intensive applications and real-life workloads.

A signature is a data pattern of interest in a large data file or set of large data files. Such signatures that need to be found arise in applications such as DNA sequence analysis, network intrusion detection, biometrics, large scientific experiments, speech recognition and sensor networks. Related to this is string matching. More specifically we envision a problem where long linear data files (i.e., flat files) contain multiple signatures that are to be found using a multiplicity of processors (parallel processor). This paper evaluates the performance of finding signatures in files residing in the nodes of parallel processors configured as trees, two dimensional meshes and hypercubes. We assume various combinations of sequential and parallel searching. A unique feature of this work is that it is assumed that data is pre-loaded onto processors, as may occur in practice, thus load distribution time need not be accounted for. Elegant expressions are found for average signature searching time and speedup, and graphical results are provided.

Data-intensive applications frequently rely on multicore computer systems, in which Non-Uniform Memory Access (NUMA) is a dominant architecture. To transfer data into and out from these high-performance computers becomes a bottleneck, and thus it is crucial to understand their I/O performance characteristics. However, the complexity in NUMA architecture presents a new challenge in modeling its I/O access cost, and thus lead to difficulties in configuring proper processor and memory affinity. In this paper, we show that existing NUMA experimental methods and metrics are inappropriate on contemporary high-end systems. We characterize a state-of-the-art NUMA host, and propose, to the best of our knowledge, the first methodology to simulate I/O operations using memory semantics, and model the I/O bandwidth performance. Our methodology is thoroughly tested and validated by mapping multiple parallel I/O streams to different sets of hardware components (CPU, memory, network cards, and SSDs) and by measuring the performance of each mapping. The experimental results and analysis reveal that our methodology can dramatically reduce characterization workload, accurately estimate the overall I/O performance, and effectively mitigate resource contention among I/O tasks.

Data-intensive applications place stringent requirements on the performance of both back-end storage systems and front-end network interfaces. However, for ultra high-speed data transfer, for example, at 100 Gbps and higher, the effects of multiple bottlenecks along a full end-to-end path, have not been resolved efficiently. In this paper, we describe our implementation of an end-to-end data transfer software at such high-speeds. At the back-end, we construct a storage area network with the iSCSI protocols, and utilize efficient RDMA technology. At the front-end, we design network communication software to transfer data in parallel, and utilize NUMA techniques to maximize the performance of multiple network interfaces. We demonstrate that our system can deliver the full 100 Gbps end-to-end data transfer throughput. The software product is tested rigorously and demonstrated applicable to supporting various data-intensive applications that constantly move bulk data within and across data centers.

Providing high-speed data transfer is vital to various data-intensive applications.While there have been remarkable technology advances to provide ultra-high-speed network bandwidth, existing protocols and applications may not be able to fully utilize the bare-metal bandwidth due to their inefficient design.We identify the same problem remains in the field of Remote Direct Memory Access (RDMA) networks.RDMA offloads TCP/IP protocols to hardware devices.However, its benefits have not been fully exploited due to the lack of efficient software and application protocols, in particular in wide-area networks.In this paper, we address the design choices to develop such protocols.We describe a protocol implemented as part of a communication middleware.The protocol has its flow control, connection management, and task synchronization.It maximizes the parallelism of RDMA operations.We demonstrate its performance benefit on various local and wide-area testbeds, including the DOE ANI testbed with RoCE links and InfiniBand links.

A monetary network cost problem involving a homogeneous multi-level tree of processors and links is discussed. The monetary network cost of processing a divisible load, which is linearly dependent on the amount of divisible workload, is basically composed of a communication cost and a computing cost. A monetary network analysis is performed by aggregating the network speed parameters and network cost parameters. This allows one to obtain a closed form solution for the total monetary network cost with maintaining a minimum total parallel processing finish time. Through a mathematical derivation of the ratio of total computing time variation to total network cost variation against changes in network size, insights on trends of network performance against network cost are achieved.

Optimal data scheduling strategies in a hierarchical wireless sensor network (WSN) are considered. Data aggregation in clusterheads is considered to find a closed form solution for the optimal amount of data that is to be reported by each sensor node using a newly introduced parameter, information utility. The optimal conditions for the feasible measurement instruction assignment time and for the minimum round time are derived and examined. Based on the optimal conditions, a performance evaluation is demonstrated via simulation study.

In this paper, we propose distributed algorithms referred to as resource-aware dynamic incremental scheduling (RADIS) strategies. Our strategies are specifically designed to handle large volumes of computationally intensive arbitrarily divisible loads submitted for processing at cluster/grid systems involving multiple sources and sinks (processing nodes). We consider a real-life scenario, wherein the buffer space (memory) available at the sinks (required for holding and processing the loads) varies over time, and the loads have deadlines and propose efficient "pull-based" scheduling strategies with an admission control policy that ensures that the admitted loads are processed, satisfying their deadline requirements. The design of our proposed strategies adopts the divisible load paradigm, referred to as the divisible load theory (DLT), which is shown to be efficient in handling large volume loads. We demonstrate detailed workings of the proposed algorithms via a simulation study by using real-life parameters obtained from a major physics experiment.

A paper by Nick Comino and V. Lakshmi Narasimhan is related to existing literature on divisible load scheduling theory. This includes the use of a Gantt-chart to illustrate timing relationships, basic model assumptions common to the divisible load scheduling literature, allowing time for the reporting back to the originator node of solutions the inclusion of fixed costs (charges) in the model, a proof that such load distribution can be optimized the product form solution for optimal load allocation of the first equation of page and the matrix multiplication application.

A computer configuration design problem where the objective is to configure a parallel processor to do processing in a cost effective manner is examined. The application envisioned is a specialized on-line service that rents time on its machine. The combinatorial optimization problem involved is examined analytically and a heuristic algorithm for its solution is provided. Lessons learned in this work appear in the conclusion.

A bus oriented network where there is a charge for the amount of divisible load processed on each processor is investigated. A cost optimal processor sequencing result is found which involves assigning load to processors in nondecreasing order of the cost per load characteristic of each processor. More generally, one can trade cost against solution time. Algorithms are presented to minimize computing cost with an upper bound on solution time and to minimize solution time with an upper bound on cost. As an example of the use of this type of analysis, the effect of replacing one fast but expensive processor with a number of cheap but slow processors is also discussed. The type of questions investigated here are important for future computer utilities that perform distributed computation for some charge.

A new distributed global queueing strategy and medium access protocol that users employ to schedule their transmissions to avoid receiver collisions is introduced for an optical fiber network. The network uses wavelength division multiplexing (WDM) for the data channels. The medium access control utilizes TDMA on the control channel to allow users to implement a global reservation scheme to send data packets. The data channels operate under a distributed demand assignment scheme that allows receiver collision-free operation and efficient scheduling. An analytical solution is obtained via equilibrium point analysis (EPA). It was shown that the maximum throughput obtained is approximately 42% which exceeds the maximum throughput of ALOHA based medium access protocols. The delay is shown to be relatively constant for a wide range of operation.

A wide variety of deflection routing strategies using packet state information are compared in terms of delay performance using a toroidal network with uni-directional links. It is found that deflection strategies based on packet age, the number of deflections experienced or path length prediction work equally well and are superior to random deflection. Strategies based on source to destination shortest path distance or current location to destination shortest path distance were significantly inferior to random deflection. This ranking was found to hold with or without the inclusion of nodal input buffers.

Optimal load allocation for load sharing a divisible job over processors interconnected in either a bus or a tree network is considered. The processors are either equipped with front-end processors or not so equipped. Closed form solutions for the minimum finish time and the optimal data allocation for each processor are obtained. The performance of large symmetric tree networks is examined by aggregating the component links and processors into a single equivalent processor. This allows an easy examination of large tree networks. In addition, it becomes possible to find a closed form solution for the optimal amount of data that is to be assigned to each processor in the tree network in order to achieve the minimum finish time.>

Optimal load allocation for load sharing a divisi ble job over processors interconnected in either a bus or a tree network is considered. The processors are either equipped with front-end processors or not so equipped. Closed form solutions for the minimum fin ish time and the optimal data allocation for each pro cessor are obtained. The performance of large sym metric tree networks is examined by aggregating the component links and processors into a single equiv alent processor. This allows an easy examination of large tree networks. In addition it becomes possible to find a closed form solution for the optimal amount of data that is to be assigned to each processor in the tree network in order to achieve the minimum finish time.

The generation of transmission schedules for self-organizing radio networks by traffic-sensitive algorithms is described. A centralized 'Traffic' algorithm that can be used as a performance benchmark is presented. Also described is a distributed 'degree' algorithm that is a traffic-sensitized version of an algorithm developed by A. Ephremides and T. Truong (1990). Two performance measures for comparing schedules and simulation results are also presented.>

A load-sharing problem involving the optimal allocation of measurement data among n sensor-driven processors interconnected through a bus-type communication medium is considered for three distinct architectural configurations. It is found that a minimal-time solution can be achieved if the computations by the processors end simultaneously. Simple recursions for the determination of the optimal allocation of load are presented. It is shown that for this problem a small number of processors can be almost as effective as a larger number.>

Consideration is given to the exact computation of the equilibrium state probabilities of a class of non-product-form queueing networks that is of interest for communication systems. It is shown that a specific structure in the state transition lattice leads to a sequential method of solution. The method is sequential either in terms of individual states or in terms of subsets of states. In the former case, algebraic recursions for the state probabilities can be developed. In both cases, substantial computational savings are possible.>

Two classes of non-product-form protocol models where the equilibrium probabilities of state may be computed recursively are described. An algorithm is presented for the computer generation of these recursions. The use of the algorithm is described for manufacturing nets, a class of Petri type networks. These are useful for modeling a linear process where one must wait for components to arrive before one can move to the next step of the process. Aside from the manufacturing context, they are useful for modeling certain communication processes such as multihop radio transmission and layered architecture communications.>

The percolation of a broadcast in a multihop radio network modeled by a spatial Poisson process is studied. The effect of station density and transmission radius on the extent of broadcast percolation is examined. For broadcast percolation in one spatial dimension, analytical expressions for the average extent of percolation are derived. A model for two-dimensional spatial percolation is presented along with related simulation results. The results suggest that in optimizing transmission radius as a function of communication performance measures, the choice of radius may be bounded from below by the need to maintain a desired network connectivity. The connectivity constraint can be relaxed to some extent in certain non-Poisson spatial models.>

This correspondence examines the influence of the summation order on the numerical accuracy of the resulting sum when the addition is performed using floating-point, finite-precision arithmetic. A simple statistical model is used to find the relative performance of various addition procedures. It is shown that phrasing the question in terms of finding a best ordering is overly restrictive since the most natural and accurate procedures for performing the addition utilize the storage of intermediate sums as well as performing orderings.

An annotated bibliography of interconnection of local communication systems is presented. The interconnection of local area networks and interconnection by means of metropolitan area networks are emphasized.