Advances in wireless technology have resulted in pervasive deployment of devices of a high variability in form factors, memory and computational ability. The need for maintaining continuous connections that deliver data with high reliability necessitate re-thinking of conventional design of the transport layer protocol. This paper investigates the use of Q-learning in TCP cwnd adaptation during the congestion avoidance state, wherein the classical alternation of the window is replaced, thereby allowing the protocol to immediately respond to previously seen network conditions. Furthermore, it demonstrates how memory plays a critical role in building the exploration space, and proposes ways to reduce this overhead through function approximation. The superior performance of the learning-based approach over TCP New Reno is demonstrated through a comprehensive simulation study, revealing 33.8% and 12.1% improvement in throughput and delay, respectively, for the evaluated topologies. We also show how function approximation can be used to dramatically reduce the memory requirements of a learning-based protocol while maintaining the same throughput and delay.

Bursty workloads are often observed in a variety of systems such as grid services, multi-tier architectures, and large storage systems. Studies have shown that such burstiness can dramatically degrade system performance because of overloading, increased response time, and unavailable service. Computing grids, which often use distributed, autonomous resource management, are particularly susceptible to load imbalances caused by bursty workloads. In this paper, we use a simulation environment to investigate the performance of decentralized schedulers under various intensity levels of burstiness. We first demonstrate a significant performance degradation in the presence of strong and moderate bursty workloads. Then, we describe two new hybrid schedulers, based on duplication-invalidation, and assess the effectiveness of these schedulers under different intensities of burstiness. Our simulation results show that compared to the conventional decentralized methods, the proposed schedulers achieve a 40% performance improvement under the bursty condition while obtaining similar performance in non-bursty conditions.

Cloud computing nowadays becomes quite popular among a community of cloud users by offering a variety of resources. However, burstiness in user demands often dramatically degrades the application performance. In order to satisfy peak user demands and meet Service Level Agreement (SLA), efficient resource allocation schemes are highly demanded in the cloud. However, we find that conventional load balancers unfortunately neglect cases of bursty arrivals and thus experience significant performance degradation. Motivated by this problem, we propose new burstiness-aware algorithms to balance bursty workloads across all computing sites, and thus to improve overall system performance. We present a smart load balancer, which leverages the knowledge of burstiness to predict the changes in user demands and on-the-fly shifts between the schemes that are “greedy” (i.e., always select the best site) and “random” (i.e., randomly select one) based on the predicted information. Both simulation and real experimental results show that this new load balancer can adapt quickly to the changes in user demands and thus improve performance by making a smart site selection for cloud users under both bursty and non-bursty workloads.

Cognitive radio (CR) ad hoc networks are composed of wireless nodes that may opportunistically transmit in licensed frequency bands without affecting the primary users of that band. In such distributed networks, gathering the spectrum information is challenging as the nodes have a partial view of the spectrum environment based on the local sensing range. Moreover, individual measurements are also affected by channel uncertainties and location-specific fluctuations in signal strength. To facilitate the distributed operation, this paper makes the following contributions: (i) First, an experimental study is undertaken to measure the signal characteristics for indoor and outdoor locations for the TV channels 21 – 51, and these results are used to identify the conditions under which nodes may share information. (ii) Second, a Cooperative reinforcement LearnIng scheme for Cognitive radio networKs (CLICK) is designed for combining the spectrum usage information observed by a node and its neighbors. (iii) Finally, CLICK is integrated within a MAC protocol for testing the benefits and overhead of our approach on a higher layer protocol performance. The proposed learning framework and the protocol design are extensively evaluated through a thorough simulation study in ns-2 using experimental traces of channel measurements.

Summary form only given. An input-queued switch with virtual output queuing is able to provide a maximum throughput of 100% in the supporting more sophisticated scheduling strategies. Switch scheduling can be cast as a maximum flow problem. We propose a maximum weight bipartite matching (MWBM) scheduling algorithm for input-queued switches. Our goal is to provide 100% throughput while maintaining fairness and stability. Our algorithm provides sublinear parallel run time complexity using a polynomial number of processing elements. We are able to obtain the MWBM for a time slot in sublinear time by using the matching produced in the previous time slot based on the observation that in input-queued cell-based switches, the weight of edges changes very little during successive time slots. To the best of our knowledge, our algorithm outperforms all previously proposed MWBM scheduling algorithms proposed for input-queued switches. We also describe a linear time complexity MWBM algorithm for a general bipartite graph which outperforms the best known sublinear MWBM algorithm for any bipartite graph with less than 10/sup 15/ number of nodes.

The combination of hardware acceleration and flexibility make FPGAs (field programmable gate arrays) important to image processing applications. There is also a need for efficient, flexible hardware/software codesign environments that can balance the benefits and costs of using FPGAs. Image processing applications often consist of pipeline of components where each component applies a different processing algorithm. Components can be implemented for FPGAs or software. Such systems enable an image analyst to work with either FPGA or software implementations of image processing algorithms for a given problem. The pipeline assignment problem chooses from alternative implementations of pipeline components to yield the fastest pipeline. Our codesign system solves the pipeline assignment problem to provide the most effective implementation automatically, so the image analyst can focus solely on choosing components, which make up the pipeline. However, the pipeline assignment problem is NP complete. An efficient, dynamic solution to the pipeline assignment problem is a desirable enabler of codesign systems which use both FPGA and software implementations. This paper is concerned with solving pipeline assignment in this context. Consequently, we focus on optimal and heuristic methods for fast (fixed time limit) runtime pipeline assignment are investigated. We present experimental finding for pipelines of twenty or fewer components, which show that in our environment, optimal runtime solutions are possible for smaller pipelines and nearly optimal heuristic solutions are possible for larger pipelines.

Since instruction level parallelism in basic blocks is often limited, compilers increase performance by creating superblocks that allow operations to be issued speculatively. This is difficult in general because each branch competes for the processor's limited resources. Previous work manages the performance trade-offs that exist between branches only indirectly. We show here that dependence and resource constraints can be used to gather explicit knowledge about scheduling trade-offs between branches. This paper's first contribution is a set of new, tighter lower bounds on the execution times of superblocks that specifically account for the dependence and resource conflicts between pairs of branches. This paper's second contribution is a novel superblock scheduling heuristic that finds high performance schedules by determining the operations that each branch needs to be scheduled early and selecting branches with compatible needs that favor beneficial branch trade-offs. Performance evaluations for superblocks from SPECint95 indicate that our bounds are very tight and that our scheduling heuristic outperforms well-known superblock scheduling algorithms.

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 86.5% of the time over a synthetic benchmark. We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.

We describe an algorithm that finds a minimum cost schedule, including spill code, for a register-constrained machine that can issue up to one arithmetic operation and one memory access operation at a time, under the restrictions that the dependence graph is a full binary tree, all arithmetic and store operations have unit latency, and all load operations have a latency of 1 or all load operations have a latency of 2. This problem is a generalization of two problems whose efficient solutions are well understood: optimaldual-issue scheduling without spills for binary expression trees, solved by Bernstein, Jaffe, and Rodeh [SIAM J. Comput., 18 (1989), pp. 1098--1127], and optimal single-issue scheduling with spill code and delayed loads, solved by Kurlander, Proebsting, and Fischer [ ACM Transactions on Programming Languages and Systems, 17 (1995), pp. 740--776], both assuming a fixed number of registers. We show that the algorithm's complexity is O(nk) where n is the number of operations to be scheduled and k is the number of spills in the schedule. The cost of a "contiguous" schedule (i.e., its length) is shown to be $\rho + 2k + g + |A|$, where $\rho$ is the number of registers used, |A| is the number of arithmetic operations, k is the number of spills, and g is the number of empty slots in the associated single processor schedule. Therefore all contiguous schedules formed from optimal single processor schedules have minimum cost.

Since there is generally insufficient instruction level parallelism within a single basic block, higher performance is achieved by speculatively scheduling operations in superblocks. This is difficult in general because each branch competes for the processor's limited resources. Previous work manages the performance tradeoffs that exist between branches only indirectly. We show here that dependence and resource constraints can be used to gather explicit knowledge about scheduling tradeoffs between branches. The first contribution of this paper is a set of new, tighter lower bounds on the execution times of superblocks that specifically accounts for the dependence and resource conflicts between pairs of branches. The second contribution of this paper is a novel superblock scheduling heuristic that finds high performance schedules by determining the operations that each branch needs to be scheduled early and selecting branches with compatible needs that favor beneficial branch tradeoffs. Performance evaluations for superblocks from SPECint95 indicate that our bounds are very tight and that our scheduling heuristic outperforms well known superblock scheduling algorithms.

In this paper, we examine temporal-based program interaction in order to improve layout by reducing the probability that program units will conflict in an instruction cache. In that context, we present two profile-guided procedure reordering algorithms. Both techniques use cache line coloring to arrive at a final program layout and target the elimination of first generation cache conflicts (i.e., conflicts between caller/callee pairs). The first algorithm builds a call graph that records local temporal interaction between procedures. We will describe how the call graph is used to guide the placement step and present methods that accelerate cache line coloring by exploring aggressive graph pruning techniques. In the second approach, we capture global temporal program interaction by constructing a Conflict Miss Graph (CMG). The CMG estimates the worst-case number of misses two competing procedures can inflict upon one another and reducing higher generation cache conflicts. We use a pruned CMG graph to guide cache line coloring. Using several C and C++ benchmarks, we show the benefits of letting both types of graphs guide procedure reordering to improve instruction cache hit rates. To contrast the differences between these two forms of temporal interaction, we also develop new characterization streams based on the Inter-Reference Gap (IRG) model.

This paper presents an algorithm that allocates registers optimally for straight-line code running on a generic multi-issue computer. On such a machine, an optimal register allocation is one that minimizes the number of issue slots that the code requires. Optimal spill selection and load/store placement are used to minimize the number of additional issue slots needed, given a schedule for the non-memory reference instructions and a fixed number of available physical registers. The generic multi-issue machine model closely models the operation of vector and VLIW processors, and could be extended to model super-scalar processors. The algorithm uses dynamic programming to search the state space of feasible register allocations; implicit and explicit state pruning are used to make the problem tractable without sacrificing optimality. The optimal allocation produced by the algorithm for a substantial example is presented.