39741624
An Efficient Technique for Dynamic Slicing of Concurrent Java Programs
Program slice has many applications such as program debugging, testing, maintenance and complexity measurement. We propose a new dynamic program slicing technique for concurrent Java programs that is more efficient than the related algorithms. We introduce the notion of Concurrent Program Dependence Graph (CPDG). Our algorithm uses CPDG as the intermediate representation and is based on marking and unmarking the edges in the CPDG 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.
537233
Evolutionary Multimodal Optimization Revisited
We revisit a class of multimodal function optimizations using evolutionary algorithms reformulated into a multiobjective framework where previous implementations have needed niching/sharing to ensure diversity. In this paper, we use a steady-state multiobjective algorithm which preserves diversity without niching to produce diverse sampling of the Pareto-front with significantly lower computational effort.
5790802
Object-oriented symbol management in syntax-directed compiler systems
Each symbol in a source program has a series of attributes that govern the operations performed on it. In this paper, we explore object-oriented techniques for representing the attributes of symbols and translating the operations performed on them. This approach is shown superior in memory and run-time speed to the procedural style traditionally used for writing compilers. We demonstrate object-oriented symbol management in a compiler for an arithmetic subset of C. We have used C++ --- a single-dispatching language --- to implement the same, but we emphasize the need for multiple dispatching to develop programs in a heavily-object-oriented style.
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.
16795084
Analysis of a Multiobjective Evolutionary Algorithm on the 0-1 knapsack problem
Multiobjective Evolutionary Algorithms (MOEAs) are increasingly being used for effectively solving many real-world problems, and many empirical results are available. However, theoretical analysis is limited to a few simple toy functions. In this work, we select the well-known knapsack problem for the analysis. The multiobjective knapsack problem in its general form is NP-complete. Moreover, the size of the set of Pareto-optimal solutions can grow exponentially with the number of items in the knapsack. Thus, we formalize a (1 + e)-approximate set of the knapsack problem and attempt to present a rigorous running time analysis of a MOEA to obtain the formalized set. The algorithm used in the paper is based on a restricted mating pool with a separate archive to store the remaining population; we call the algorithm a Restricted Evolutionary Multiobjective Optimizer (REMO). We also analyze the running time of REMO on a special bi-objective linear function, known as LOTZ (Leading Ones : Trailing Zeros), whose Pareto set is shown to be a subset of the knapsack. An extension of the analysis to the Simple Evolutionary Multiobjective Optimizer (SEMO) is also presented. A strategy based on partitioning of the decision space into fitness layers is used for the analysis.
24684227
Adaptive Control of Anytime Algorithm Parameters
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.
9633354
Real-time personalized sports video filtering and summarization
We demonstrate a real-time fully automated software system for filtering important events in sports video. Events represent occurrences of actions or state changes in video content. In the current prototype, we demonstrate detection of pitching in baseball and serving in tennis. For wireless video applications, we propose and apply a unique notion of content-based adaptive streaming,in which video encoding rate and media modality is dynamically varied according to the event filtering results. Our system includes an event detection module, an adaptive encoding module, and a buffer management module for adaptive streaming. We achieve the real-time performance by exploring compressed-domain techniques and multi-stage multi-resolution content-analysis processes.
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.
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%.
9294393
Decentralized control of discrete event systems with specializations to local control and concurrent systems
The decentralized supervisory control problem of discrete event systems under partial observation is studied in this paper. The main result of the paper is a necessary and sufficient condition for the existence of decentralized supervisors for ensuring. That the controlled behavior of the system lies in a given range. The contribution of the paper is (1) our setting of decentralized control generalizes the prior ones; (2) we present an alternative approach for solving the decentralized control problem, which leads to computational saving for concurrent systems and certain other systems; and (3) our generalized formulation and its solution lets us extend several of the existing results reported previously. The results of our paper are illustrated by an example of a simple manufacturing system.