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.
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.
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%.
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.
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.
5908339
Intelligent Hierarchical Intrusion Detection System for Secure Wireless Ad Hoc Network
The nature of mobile ad hoc network (MANETs) makes them vulnerable to security attacks. Intrusion detection is a vital secure scheme for wireless mobile ad hoc networks (MANETs). However, the generalizing ability of current IDS is poor when given less priori knowledge, and a centralized intrusion detection network security solution does not work well in MANETs. In this paper we discuss the characters of security issues in ad hoc networks and propose a Support Vector Machine (SVM) based distributed hierarchical intrusion detection system that adapt to the characters of current ad hoc networks. Performance evaluations based on simulation experiment manifested our proposed approach is efficient and effective.
16539998
Lossy to lossless image compression based on reversible integer DCT
A progressive image compression scheme is investigated using reversible integer discrete cosine transform (RDCT) which is derived from the matrix factorization theory. Previous techniques based on DCT suffer from bad performance in lossy image compression compared with wavelet image codec. And lossless compression methods such as IntDCT, I2I-DCT and so on could not compare with JPEG-LS or integer discrete wavelet transform (DWT) based codec. In this paper, lossy to lossless image compression can be implemented by our proposed scheme which consists of RDCT, coefficients reorganization, bit plane encoding, and reversible integer pre- and post-filters. Simulation results show that our method is competitive against JPEG-LS and JPEG2000 in lossless compression. Moreover, our method outperforms JPEG2000 (reversible 5/3 filter) for lossy compression, and the performance is even comparable with JPEG2000 which adopted irreversible 9/7 floating-point filter (9/7F filter).
2862393
Online Constrained Pattern Detection over Streams
Online pattern detection poses a challenge in many data-intensive applications, including network traffic management, trend analysis, intrusion detection, and various intelligent sensor networks. These applications have to be time and space efficient while providing high quality answers. Meanwhile, far less attention has been paid for detecting constrained patterns, that cannot be simply matched because there is no available pattern for prediction. This paper presents our research effort in efficient pattern detection with constraint. We propose a new method named Online Pattern Detection with Constraint (OPDC) to detect constrained patterns over evolving data stream, taking into account various user-defined constraints. To ensure that the constrained patterns are representative, we extend regular expression in a simple but powerful way. Our experimental results on real data sets demonstrate the feasibility and effectiveness of the proposed scheme.
16738561
Defect-tolerant digital filtering with unreliable molecular electronics
Molecular electronics such as silicon nanowires (NW) and carbon nanotubes (CNT) are considered to be the future computational substrates due to their ultra-high density and superior energy efficiency. However, excessive defects from bottom-up self-assembly fabrication pose a major technological barrier to achieving reliable computing at the molecular scale. Existing solutions targeting absolute correctness introduce high cost and complexity in post-fabrication testing and defect diagnosis. In this paper, we propose a new approach exploiting algorithm level enhancements for defect-insensitive signal processing. By deliberately allowing molecular-scale integrated systems to bear defects, the proposed design framework achieves reliable signal processing while significantly reduces the cost of defect tolerance.
9617216
Achieving Scalable Parallel Molecular Dynamics Using Dynamic Spatial Domain Decomposition Techniques
To achieve scalable parallel performance in molecular dynamics simulations, we have modeled and implemented several dynamic spatial domain decomposition algorithms. The modeling is based upon the bulk synchronous parallel architecture model (BSP), which describes supersteps of computation, communication, and synchronization. Using this model, we have developed prototypes that explore the differing costs of several spatial decomposition algorithms and then use this data to drive implementation of our molecular dynamics simulator,Sigma. The parallel implementation is not bound to the limitations of the BSP model, allowing us to extend the spatial decomposition algorithm. For an initial decomposition, we use one of the successful decomposition strategies from the BSP study and then subsequently use performance data to adjust the decomposition, dynamically improving the load balance. The motivating reason to use historical performance data is that the computation to predict a better decomposition increases in cost with the quality of prediction, while the measurement of past work often has hardware support, requiring only a slight amount of work to modify the decomposition for future simulation steps. In this paper, we present our adaptive spatial decomposition algorithms, the results of modeling them with the BSP, the enhanced spatial decomposition algorithm, and its performance results on computers available locally and at the national supercomputer centers.