2376990
Power-aware processor scheduling under average delay constraints
In this paper, voltage scaling strategies for scheduling aperiodic tasks under average delay constraints are studied. Dynamic voltage scaling in single processor systems is formulated as a constrained stochastic optimization problem for which the optimal solution can be obtained using a combination of Lagrange relaxation and the value iteration method. For multiprocessor systems, we present a two-phase approach. In the first phase, the speed settings and static workload distribution of the processors are optimized to minimize the total power dissipation. Dynamic voltage scaling techniques are then applied to each individual processor in the second phase. Both homogeneous and heterogeneous systems have been investigated. Based on queueing theory, the proposed algorithms guarantee conformity to the average delay constraint. Moreover, our simulation experiments have shown they are effective for minimizing power consumption.
1083190
Streaming media caching algorithms for transcoding proxies
Streaming media is expected to become one of the most popular types of Web content in the future. Due to increasing variety of client devices and the range of access speeds to the Internet, multimedia contents may be required to be transcoded to match the client's capability. With transcoding, both the network and the proxy CPU are potential bottlenecks for streaming media delivery. This paper discusses and compares various caching algorithms designed for transcoding proxies. In particular we propose a new adaptive algorithm that dynamically selects an appropriate metric for adjusting the management policy. Experimental results show that the proposed algorithm significantly outperforms those that cache only untranscoded or only transcoded objects. Moreover motivated by the characteristics of many video compression algorithms, we investigate partitioning a video object into sections based on frame type and handling them individually for proxy caching. It is found that partitioning improves performance when CPU power rather than network bandwidth is the limiting resource, particularly when the reference pattern is not highly skewed.
9404547
Blocking-aware processor voltage scheduling for real-time tasks
As mobile computing is getting popular, there is a growing need for techniques that minimize energy consumption on battery-powered mobile devices. Processor voltage scheduling can effectively reduce processor energy consumption by lowering the processor speed. In this paper, we study voltage scheduling for real-time periodic tasks with non-preemptible sections. Three schemes are proposed: The static speed algorithm derives the minimum static feasible speed based on the stack resource policy. Due to blocking, this static speed is usually higher than the speed required for scheduling fully preemptible tasks (called the utilization speed). Two dynamic speed algorithms are then introduced to further reduce energy consumption. The novel dual speed algorithm operates the processor at the utilization speed whenever possible and switches to the higher static speed only when blocking occurs. The dual speed dynamic reclaiming algorithm reserves time budget for each job, reclaims the unused time budget from completed jobs and redistributes it to subsequent jobs so they can run at a lower speed whenever possible. Feasibility conditions for real-time task sets have been derived and proved mathematically. Simulation results show that the proposed voltage scheduling algorithms dramatically reduce processor energy consumption over non-power-aware scheduling algorithms. Furthermore, the two dynamic speed algorithms consistently outperform the static speed scheme in a wide range of system and workload conditions.
13865930
Proxy-Assisted Scheduling for Energy-Efficient Multimedia Streaming over Wireless LAN
Energy is a critical resource for battery-driven mobile and wireless devices. The power-saving mode (PSM) provided by the 802.11 standard is not adequate for mobile clients running streaming media applications. We propose new power-aware scheduling strategies that enhance existing traffic shaping schemes for the purpose of minimizing the communication energy consumption of mobile clients. Scheduling decisions are made by the local proxy and executed at the access point. We consider two cases. In the first case, the proxy is unaware of the power characteristics of the clients. We present an optimal scheduling scheme that minimizes the time that mobile clients stay in high-power modes. This scheme achieves significant energy savings compared to using traffic shaping alone. In the second case, the power profiles and the residual battery capacities of the clients are taken into account in generating the schedule. Unlike most existing work, we believe these factors should be considered in the performance metric. We propose a dynamic programming approach that computes the optimal transmission schedule based on the new metric. We also present an efficient heuristic which exhibits near-optimal performance in the simulation experiments.
21190705
Evolving Spanning Trees Using the Heat Equation
This paper explores how to use the heat kernel to evolve the minimum spanning tree of a graph with time. We use the heat kernel to weight the edges of the graph, and these weights can be computed by exponentiating the Laplacian eigensystem of the graph with time. The resulting spanning trees exhibit an interesting behaviour as time increases. Initially, they are bushy and rooted near the centre of graph, but as time evolves they become string-like and hug the boundary of the graph. We characterise this behaviour using the distribution of terminal nodes with time, and use this distribution for the purposes of graph clustering and image segmentation.
30156477
Examination of load-balancing methods to improve efficiency of a composite materials manufacturing process simulation under uncertainty using distributed computing
Process simulations play an important role in guiding process understanding and development, without requiring costly manufacturing trials. For process design under uncertainty, a large number of simulations is needed for an accurate convergence of the moments of the output distributions, which renders such stochastic analysis computationally intensive. This paper discusses the application of a basic distributed computing approach to reduce the computation time of a composite materials manufacturing process simulation under uncertainty. Specifically, several load-balancing methods are explored and analyzed to determine the best strategies given heterogeneous tasks and heterogeneous networks, especially when the individual task times cannot be predicted.
34749580
Plane elementary bipartite graphs
A connected graph is called elementary if the union of all perfect matchings forms a connected subgraph. In this paper we mainly study various properties of plane elementary bipartite graphs so that many important results previously obtained for hexagonal systems are treated in a unified way. Firstly, we show that a plane bipartite graph G is elementary if and only if the boundary of each face (including the infinite face) is an alternating cycle with respect to some perfect matching of G. For a plane bipartite graph G all interior vertices of which are of the same degree, a stronger result is obtained; namely, G is elementary if and only if the boundary of the infinite face of G is an alternating cycle with respect to some perfect matching of G. Second, the concept of the Z-transformation graph Z(G) of a hexagonal system G (whose vertices represent the perfect matchings of G) is extended to a plane bipartite graph G and some results analogous to those for hexagonal systems are obtained. A peripheral face f of G is called reducible if the removal of the internal vertices and edges of the path that is the intersection of f and the exterior face of G results in a plane elementary bipartite graph. Thirdly, we obtain the reducible face decomposition for plane elementary bipartite graphs. Furthermore, sharp upper and lower bounds for the number of reducible faces are derived. Conversely, we can construct any plane elementary bipartite graphs by adding new peripheral faces one by one. As applications of this approach, we give simple construction methods for several types of plane elementary bipartite graphs G that contain a forcing edge (which belongs to exactly one perfect matching of G) and whose Z-transformation graphs Z(G) contain vertices of degree one.
5788058
Heredity of the index of convergence of the line digraph
Let D be a digraph, and let Ln(D) and k(D) denote the nth iterated line digraph of D and the index of convergence of D, respectively. We prove that if D contains neither sources nor sinks, then: (1) k(Ln(D))=k(D)=0 if every connected component of D is a directed cycle. (2) k(Ln(D))=k(D)+n if there exists at least one connected component of D that is not a directed cycle. Finally, we prove that if D has no sources or no sinks then k(D) ≤ k(L(D)) ≤ k(D)+1.
41496800
Intra-Organizational Logistics Management Through Multi-Agent Systems
Compared to inter-organizational logistics management, the goal of intra-organizational logistics management is to maximize the profits of the whole company sometimes at the cost of its individual units' profits. While many agent-based models have been proposed for logistics management, most of these models use an auction approach. Thus, they are not suitable for intra-organizational logistics management. In this paper, we first formulate logistics management as a distributed resource allocation problem. Then, we present our ongoing work on developing a multi-agent model for intra-organizational logistics management and using Lagrangian relaxation to decompose the problem into a set of subproblems. Our initial experimental results are very promising. We provide a detailed analysis of our results.