6342150
Frame based fair multiprocessor scheduler: a fast fair algorithm for real-time embedded systems
This paper presents frame based fair multiprocessor scheduler (FBFMS) which provides accurate real-time proportional fair scheduling for a set of dynamic tasks on a symmetric multiprocessor environment with O(1) scheduling overhead. FBFMS meets these seemingly contradictory goals by applying the benefits of virtual time round-robin scheduling mechanism along with a frame based scheduling approach. Simulation results show that the algorithm provides 2.5 to 26 times speedup (over O(lg n) complexity schedulers) with distortion in fairness less than 1% in most cases, and less than 15% in the worst case.
12472730
Frame-Based Proportional Round-Robin
All known real-time proportional fair scheduling mechanisms either have high scheduling overheads (O(lg n) per time-slot) or do not efficiently handle dynamic task sets. This paper presents frame-based proportional round-robin (FBPRR), a real-time fair scheduler providing high and bounded proportional fairness accuracy and O(1) scheduling overhead with the ability to efficiently handle a set of dynamic tasks. FBPRR achieves this by applying the benefits of virtual-time round-robin (VTRR) scheduling mechanism within a frame-based scheduling approach. Simulation results show that the algorithm gains a speedup of 5 to 20 times (over O(lg n) complexity schedulers) with fairly high fairness
6228281
AWA* - A Window Constrained Anytime Heuristic Search Algorithm
This work presents an iterative anytime heuristic search algorithm called Anytime Window A* (AWA*) where node expansion is localized within a sliding window comprising of levels of the search tree/graph. The search starts in depth-first mode and gradually proceeds towards A* by incrementing the window size. An analysis on a uniform tree model provides some very useful properties of this algorithm. A modification of AWA* is presented to guarantee bounded optimal solutions at each iteration. Experimental results on the 0/1 Knapsack problem and TSP demonstrate the efficacy of the proposed techniques over some existing anytime search methods.
2748426
Biobjective evolutionary and heuristic algorithms for intersection of geometric graphs
Wire routing in a VLSI chip often requires minimization of ire-length as well as the number of intersections among multiple nets. Such an optimization problem is computationally hard for which no efficient algorithm or good heuristic is known to exist. Additionally, in a biobjective setting, the major challenge to solve a problem is to obtain representative diverse solutions across the (near-) Pareto-front.In this work, we consider the problem of constructing spanning trees of two geometric graphs corresponding to two nets, each with multiple terminals, with a goal to minimize the total edge cost and the number of intersections among the edges of the two trees. We first design simple heuristics to obtain the extreme points in the solution space, which however, could not produce diverse solutions. Search algorithms based on evolutionary multiobjective optimization (EMO) are then proposed to obtain diverse solutions in the feasible solution space. Each element of this solution set is a tuple of two spanning trees corresponding to the given geometric graphs. Empirical evidence shows that the proposed evolutionary algorithms cover a larger range and are much superior to the heuristics.
26672259
A Novel Approach for Dynamic Slicing of Distributed Object-Oriented Programs
Program slicing has many applications such as program debugging, testing and maintenance We propose a new dynamic slicing technique for distributed object-oriented programs We introduce the notion of Distributed Program Dependence Graph (DPDG) Our dynamic slicing technique uses DPDG as the intermediate program representation and is based on marking and unmarking the edges in the DPDG as and when the dependencies arise and cease during run-time Our approach eliminates the use of trace files and is more efficient than the existing algorithms.
262403
Collaboration and multimedia authoring on mobile devices
This paper introduces adaptation-aware editing and progressive update propagation, two novel mechanisms that enable authoring multimedia content and collaborative work on mobile devices. Adaptation-aware editing enables editing content that was adapted to reduce download time to the mobile device. Progressive update propagation reduces the time for propagating content generated at the mobile device by transmitting either a fraction of the modifications or transcoded versions thereof.With application-aware editing and progressive update propagation, an object present at a mobile device is characterized not only by a particular version, as in conventional replication, but also by a particular fidelity. We demonstrate that replication models can be extended to account for fidelity independently of the mechanisms used for concurrency control and consistency maintenance. As a result, the two techniques described in this paper can easily be added to any replication protocol, whether optimistic or pessimistic.We report on our experience implementing adaptation-aware editing and progressive update propagation. Experiments with two multimedia applications, an email reader and a presentation software package, show that both mechanisms can be added with modest programming effort and achieve substantial reductions in upload and download latencies.
2076832
Iterative adaptation for mobile clients using existing APIs
Iterative adaptation is a novel approach to adaptation for resource-limited mobile and wireless environments that supports powerful application-specific adaptations without requiring modifications to the application's source code. Common productivity applications, such as browsers, word processors, and presentation tools, export APIs that allow external applications to control their operation. The novel premise in iterative adaptation is that these APIs are sufficient to support a wide range of adaptation policies for applications running on resource-limited devices. In addition to allowing adaptation without having to change the application's source code, this approach has a unique combination of advantages. First, it supports centralized management of resources across multiple applications. Second, it makes it possible to modify application behavior after the application has been deployed. This paper evaluates the extent to which existing APIs can be used for the purposes of adapting document-based applications to run on bandwidth-limited devices. In particular, we implement a large number of bandwidth adaptations for applications from the Microsoft Office and the OpenOffice productivity suites and for Internet Explorer. Although we find limitations in their APIs, we are able to implement many adaptation policies without much complexity and with good performance. Moreover, iterative adaptation achieves performance similar to an approach that implements adaptation by modifying the application, while requiring only a fraction of the coding effort.
7841699
Dynamic data fusion for future sensor networks
DFuse is an architectural framework for dynamic application-specified data fusion in sensor networks. It bridges an important abstraction gap for developing advanced fusion applications that takes into account the dynamic nature of applications and sensor networks. Elements of the DFuse architecture include a fusion API, a distributed role assignment algorithm that dynamically adapts the placement of the application task graph on the network, and an abstraction migration facility that aids such dynamic role assignment. Experimental evaluations show that the API has low overhead, and simulation results show that the role assignment algorithm significantly increases the network lifetime over static placement.
15931484
Optimal slope bin classification in gradient adjusted predictor for lossless compression of medical images
Gradient adjusted predictor (GAP) uses seven fixed range of slope quantization bins and different predictors associated with each bin, for prediction of pixels of all kinds of images. Criteria for range of slope in the bins and associated predictors are not reported in the literature. This paper presents a technique for slope quantization bins which are optimum for a given set of images. It also presents a technique for finding a statistically optimal predictor for a given range of slope bin. Simulation results, for medical images, using optimal slope bins and associated predictors show a significant better compression performance as compared to the other methods such as GAP and edge-directed prediction (EDP) method. The proposed method and GAP has same order of computational complexity while EDP is computationally much expensive.
7339641
Efficient beacon placement for network tomography
Recent interest in using tomography for network monitoring has raised the fundamental issue of whether it is possible to use only a small number of probing nodes (beacons) for monitoring all edges of a network in the presence of dynamic routing. Past work has shown that minimizing the number of beacons is NP-hard, and has provided approximate solutions that may be fairly suboptimal. In this paper, we use a two-pronged approach to compute an efficient beacon set: (i) we formulate the need for, and design algorithms for, computing the set of edges that can be monitored by a beacon under all possible routing states; and (ii) we minimize the number of beacons used to monitor all network edges. We show that the latter problem is NP-complete and use an approximate placement algorithm that yields beacon sets of sizes within 1+<i>ln</i>(|<i>E</i>|) of the optimal solution, where E is the set of edges to be monitored. Beacon set computations for several Rocketfuel ISP topologies indicate that our algorithm may reduce the number of beacons yielded by past solutions by more than 50%.