29918508
Round-Robin with VirtualClock Scheduling Algorithm in Multiservice Packet Networks
In this paper, we present a scheduler that incorporates round robin service within a VirtualClock discipline. Time-stamp based scheduling algorithms attain a low local delay bound and performance guarantee, but are computationally complex. On the other hand, round robin schemes are simple to implement and have computational complexity of O(1) but they are well known for their output burstiness and short-term unfairness. In order to overcome this problem, we combine round robin with VirtualClock in an algorithm we call VCRR. VCRR possesses better fairness than simple round robin, low jitter and a good scheduling delay bound. At the same time, VCRR preserves the O(1) time complexity of round robin. Simulation experiments show VCRR's efficiency in terms of delay performance, jitter and fairness..
8970759
Linux kernels as complex networks: A novel method to study evolution
In recent years, many graphs have turned out to be complex networks. This paper presents a novel method to study Linux kernel evolution — using complex networks to understand how Linux kernel modules evolve over time. After studying the node degree distribution and average path length of the call graphs corresponding to the kernel modules of 223 different versions (V1.1.0 to V2.4.35), we found that the call graphs of the file system and drivers module are scale-free small-world complex networks. In addition, both of the file system and drivers module exhibit very strong preferential attachment tendency. Finally, we proposed a generic method that could be used to find major structural changes that occur during the evolution of software systems.
45075264
Multi-path GEM for Routing in Wireless Sensor Networks
Wireless sensor networks are expected to be used in many different applications such as disaster relief and environmental control. Efficient routing protocols need to be thoroughly studied before wireless sensor networks are widely deployed. GEM is an ingenious routing algorithm that is based on the idea of graph embedding. Using a well designed virtual coordinate system, GEM provides a remarkably simple route selection mechanism. However, GEM does not survive edge failures well. In this paper, we propose R-GEM and S-GEM that use the idea of GEM and improve its reliability performance significantly. Both of them outperform GEM in all of the experimental scenarios. Specifically, in the case that 2% of all edges in the network fail to transfer packets, when only disjoint pairs are taken into consideration, GEM leads to a path error rate of 10% while R-GEM and S-GEM only result in a path error rate of 2%.
14387828
Escape analysis for synchronization removal
In this paper we introduce our escape analysis framework for Java, which is a kind of flow-insensitive, inter-procedural, and context-sensitive data flow analysis. And we present an efficient static intra-procedural algorithm for inferring the set of types that can occur at runtime for each object. With intra-procedural type information, virtual method resolution, callee-stub inline, exception analysis, and thread allocation site analysis are implemented. Virtual method resolution and callee-stub inline effectively reduce the call graph and SCC (strongly connected components). In exception analysis, we present a more precise analysis algorithm, especially in the inter-procedural exception in SCC.Our escape analysis can be applied to the whole Java program and Java libraries to identify unnecessary synchronization in Java and remove them. We have developed an implementation on Intel's Open Runtime Platform. For our benchmarks, 7.3% to 99% (with an average of 54%) of synchronization operations are eliminated.
15438049
DECF: A Coarse-Grained Data-Parallel Programming Framework for Seismic Processing
In this paper, we present a distributed execution control framework (DECF) for seismic processing. The DECF framework employs a coarse-grained data-parallel execution model within a cluster environment and achieves high throughput. The DECF schedules processing modules written as sequential programs to run simultaneously on multiple computers, or multiple CPU cores. The DECF hides the messy details of scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between processing modules.We also introduce a parallel implementation of 3D pre-stack kirchhoff time migration algorithm using MPI and share the practical lessons learned from the process of designing, implementing, and maintaining it, which are of great help to the future work of the DECF.
15857630
Eliminating Redundant Communication of Code Generation for Distributed Memory Machines
How to eliminate redundant communications is a key issue in developing parallelizing compilers for distributed memory machines. An important way to improve the performance of the code generated by parallelizing compiler in distributed memory systems is to eliminate as much communications as possible. This paper investigates algorithms for generating communications code from previously published work and modifies them to eliminate redundant communications. Based on the mathematical model of symbolic coefficient linear inequalities the revisited formal specification of communications sets are presented and the corresponding improved algorithms are given. Experimental results indicate that the new algorithms can reduce communication messages and improve the performance of parallelized code significantly.
33446676
Voronoi Tessellation Based Rapid Coverage Decision Algorithm for Wireless Sensor Networks
The coverage problem is a fundamental issue in the research of sensor network. A novel Voronoi tessellation based rapid coverage decision algorithm is proposed, in which the region of interest is partitioned into some square grids firstly, and then the complex area coverage problem is transformed into simple vertices coverage problem, on the basis of the good characteristics of Voronoi tessellation such as being able to divide the planner area into a set of simple geometric simplexes. Theoretical analysis and simulation results show that, the new algorithm can decrease the computation complexity of networks, especially for sensor networks with n different sensors, it can solve the coverage problem correctly for any given region of interest with time costs of O(nlogn) only.
34094601
DNA-Based Algorithm for 0-1 Planning Problem
Biochemical reaction theory based DNA computation is of much better performance in solving a class of intractable computational problems such as NP-complete problems, it is important to study the DNA computation. A novel algorithm based on DNA computation is proposed, which solves a special category of 0-1 planning problem by using the surface-based fluorescence labeling technique. The analysis show that our new algorithm is of significant advantages such as simple encoding, low cost and short operating time, etc.
30689090
Modeling and simulation for crosstalk aggravated by weak-bridge defects between on-chip interconnects
This paper presents comprehensive analytic models that consider both the case of a weak bridge, and the combination of a weak bridge and crosstalk between two interconnects. Our models capture the induced signal delay and pulse as a function of the parameters of the circuit and input signals. Our results are compared with HSPICE and shown to be accurate. A simulator is developed that implements our models and accurately captures timing (delay) characteristics of a circuit. We contrast our results with others, and show the benefits of this new model as well as the ability to predict the range of resistance that leads to delay errors.
32146489
Cycle Period Analysis and Optimization of Timed Circuits
In this paper, a method is proposed to analyze the minimum average cycle period of the timed circuits. Timed Petri net is used to model timed circuits. Our method is focus on structural analysis of the Petri net model of the timed circuits, which is another way to reduce the state space of the analyzed model. Then an algorithm is proposed to optimize the performance of timed circuit by asynchronous retiming technique. The algorithm balances the asynchronous pipelines to gain the target cycle period while minimize the area at the same time. Experimental results demonstrate the computational feasibility and effectiveness of both approaches.
8984253
Recognizing Chinese Proper Nouns with Transformation-Based Learning and Ontology
This paper proposes an approach based on the Ontology and transformation-based error-driven learning (TBL) to recognize Chinese proper nouns. Firstly, our approach redefines the label set and tags Chinese words according to the usage of proper nouns and their context, and then it extracts Characteristic Information (CI) of the proper noun from the text and merges them based on the Ontology. Secondly, it tags the training corpus following the new definition of Multi-dimension Attribute Points (MAP), and then extracts rules using the TBL approach. Finally, it recognizes proper nouns by utilizing the rule set and Ontology. The experimental results in our open test show that the precision is 92.5% and the recall is 86.3%.