Abstract:In software testing practice, usually, the software under test (SUT) experiences multiple iterative processes of testing and modification. With the influence of many uncertain factors, such as defect distribution in the software under test, iterative developing and testing processes, and testers’ capabilities of defect detection, the software defect discovery process shows that the sequential characteristics correspond with test cycles, i.e. periodicity, random oscillation, and attenuation. Through a deep analysis of the basic characters and key influencing factors of the controlled software testing process, the paper proposes an Accumulative Bi-Damped Oscillation Model (ABDOM), which describes periodicity, random oscillation, and attenuation for a sequential software defect discovery process. It verifies ABDOM’s validity with defect data gathered from 2 true software test projects, and discusses the application scope of ABDOM and the possible applications in test predication and evaluation.

Abstract:This paper extends the famous data reuse theory to a parallel domain and proposes parallel data reuse theories for OpenMP and OpenTM applications, respectively. Through studying the relationships between threads and transactions, the parallel data reuse theories systemically discuss how to classify, judge, and compute reuses in parallel programs. Meanwhile, the optimization framework for reducing OpenTM transactions rolled back is studied. Finally, the data reuses in SPEComp2001 benchmarks are analyzed. The parallel data reuse theories can be used to direct the analysis of parallel applications and the research of compiler optimization techniques on multi-core shared memory architecture.

Abstract:This paper proposes a risk driven project buffer allocation method which will allocate project buffer according to risks, schedule constrains and resource constrains between tasks. The result of simulation based experiments shows that compared with Critical Chain, the proposed method can remarkably reduce the frequency of plan change and minimize the negative impact to project duration. The method and the tool can help project managers to decide appropriate project buffer length and make better use of the limited buffer. The stability and trustworthiness of project plan schedule can be enhanced.

Abstract:In order to construct a trustworthy computing platform for the next Internet, there needs to be normalizing and promoting of autonomic elements in order to have them collaborate actively with on another. A novel penalty-incentive mechanism, named PETrust, based on a repeated game theory, is given in this paper. This paper aims at providing a set of mechanisms, which the behavior of autonomic elements is normalized and is promoted to take the expected strategy. PETrust adjusts the degree of penalty by changing the reputation status. Theoretical analysis and simulation results show that PETrust can distinguish the different features of behavior, effectively, can punish and stifle malicious behavior, can improve the system’s entire efficiency, can stimulate autonomic elements’ honest trade enthusiasm, and can provide a better capacity of resisting collusive deception. Furthermore, PETrust presents both low time complexity and few incurred packets, which is favourable for engineering deployment and implementation.

Abstract:Bytecode, which is widely used in network software and mass devices, is a kind of interpretive execution instruction and a favorable intermediate presentation, Bytecode can highly improve the reliability of relevant software and strongly support the construction of proof-preserved compilers, so it holds theoretical and practical value. Although some efforts have been made on building a logic system for the bytecode program, modular certification of bytecode still remains challenging because of the complexity of the abstract control stack and the lack of control over flow structure information. Moreover, the expression ability of the recent logic system is very limited. This paper presents a logic framework that supports modular certification of bytecode programs and is more expressive. FPCC technology is originally introduced into this framework for bytecode. This paper provides the formal definition of CBP (certifying bytecode program) logic system for the running environment of Bytecode. Also, this paper has also finished the proof of the theorem and a group of instance programs. This piece of work is not only a good solution for certifying Bytecode, which is run on a stack-based virtual machine, but also a significant improvement for the construction of a proof-preserved compiler environment. In addition, this system is useful in finding a deeper understanding and analysis of network application based on a virtual machine.

Abstract:To solve the degree-constrained spanning minimum tree (DCMST) problems with a large scale of nodes, an optimization algorithm based on grafting and pruning operator is proposed. Learning from the flower planting techniques, this paper establishes, an evolutionary computation framework containing accelerating and adjusting operators based on conventional genetic operators. The grafting and pruning are performed by a greedy strategy and gain maximization respectively. The collision caused by possible local minima is analyzed and detected, and several methods dealing with the collision are discussed. To tackle the complexity of DCMST problems, some strategies of grafting and pruning are proposed. The convergence of the proposed algorithm and the computation complexity are analyzed. For DCMST problems of Euclidean and uniform random non-Euclidean instances from 50 to 500 nodes, the experiments show that the quality and convergence rate of the proposed method are the best compared with the known results.

Abstract:Compared with the Genetic Algorithm, a multi-population genetic algorithm has an enhancement in performance, but for a job shop scheduling problem, which has a lot of local optima, it also has the shortcomings of an easy-to-fall into local optima and a poor ability of local search. Therefore, an effective algorithm is proposed to solve job shop scheduling problem. The proposed algorithm, based on multi-population genetic algorithm, involves the strategy of memory-base and a mechanism of the Lamarckian evolution. Not only does the memory-base make individuals between sub-populations exchange information, but it can maintain the diversity of the population. The local search operator, based on Lamarckian evolution, is adupted to enhance the individual’s ability of local search. The simulated annealing algorithm that has a stronger ability to jump out local optima than the genetic algorithm is used, thus, alleviated the problem and enhances the performance of the algorithm for job shop scheduling. The experimental results on the well-known benchmark instances show the proposed algorithm is very effective in solving job shop scheduling problems.

Abstract:In bioinformatics, a protein sequence comparison between two banks is one of most important algorithms. The sequence bank size is becoming larger and larger with the development of biotechnology, while the algorithm is also computation intensive. This leads to more and more consumption time and the single processor or multicore system, with only a few cores, are not powerful enough to reach a satisfying speed nowadays. Godson-T is a new kind of many-core architecture with lots of novel features. The parallelization of a protein sequence comparison algorithm on Godson-T is implemented. At the same time, the algorithm structure and architecture features of Godson-T are combined, and some optimization in three aspects are made: synchronization overhead, memory access contention, and load balance. The result shows that a close to linear speedup is obtained, and the performance is much better than that of the workstation platform based on the AMD Opteron processor.

Abstract:Enumerating convex connected subgraphs from data flow graphs of application hot-spots is required when designing instructions for a configurable processor. To achieve fast enumeration, properties of convex subgraphs of directed acyclic graph are studied. Based on the properties of convex subgraphs and adjacency of vertices, AS (adjacent search), a novel algorithm for enumerating convex connected subgraphs satisfying I/O constraints is presented. Results of experiments show that AS algorithm is more efficient than the existing algorithm, and rate is 10～1000X as fast. While the existing algorithm fails on large scale data-flow graphs, the AS algorithm is still able to accomplish enumeration successfully.

Abstract:In this paper, the termination of the following programs is analized. While x?Ω do {x:=f(x)} end. When x is the only program variable, Ω is an interval and f is a continuous function. These are called the Nonlinear Programs over Intervals. This paper shows that the necessary condition for non-termination of the above program is that there is a fixed point of f, either within the interval?Ω, or on the boundary of Ω. Furthermore, if there is a fixed point within Ω, the above condition is not only necessary, but also sufficient. In the case that all fixed points are on the boundary of Ω, it is also possible to construct the corresponding necessary and sufficient condition of non-termination by introducing more constraints for the continuous function f. A piecewise polynomial function meets these constraints, and a decision algorithm for continuous piecewise polynomial function is presented in the paper.

Abstract:In this paper, the sensing characteristics of randomly deployed sensor networks in the real environment are analyzed. The calculation model of the degree of redundancy of the sensors whose sensing ranges satisfy the normal distribution without location information is proposed, and the calculation model of the minimum number of working nodes, which can provide the desired quality of coverage (QoC), is also proposed. Based on the models, an Energy Efficient Coverage Conserving Protocol for Wireless Sensor Networks (EECCP) is presented, which enables the collaborative scheduling of distributed nodes and balances the energy consumption of each node. The purpose of energy conservation of the networks is achieved since the EECCP maintains the least number of nodes, as working nodes to provide the desired QoC. Simulation results show that the EECCP not only provides the desired QoC, but also reduces network energy consumption and prolongs network useful lifetime effectively.

Abstract:Based on analyzing the resource allocation model in wireless Ad Hoc networks, a QoS-aware cross layer resource allocation algorithm, CL-QARA (cross layer QoS aware resource allocation) algorithm, is proposed. The purpose of CL-QARA algorithm is to introduce price and QoS bandwidth to measure resource allocation. The dynamic resource allocation information in the network layer is combined with the CSMA/CA admission control in the MAC layer to improve the backoff algorithm. A new backoff algorithm and call admission control algorithm is designed to implement a cross layer technique between the MAC layer and network layer. The QoS-aware resource allocation algorithm cooperates with the cross layer technique to provide the QoS guarantee. The simulation results show that CL-QARA has good convergence and stability. Compared to other algorithms, CL-QARA provides better QoS guarantee. CL-QARA also improves the network utility and performance.

Abstract:In application layer multicast (ALM) tree, when a parent node quits or fails, all its descendent nodes must adjust their positions, which causes the interruptions of multicast connections. This problem is called stability problem of ALM trees, and it may affect the continuity of multicast data transmission and then degrade user experience seriously. This paper first analyzes the stability problem of ALM trees and proposes the instantaneous stability degree model (ISDM). An approach which takes advantage of the statistical properties of members’ join-leave behaviors is proposed to estimate the relative leave probability of member nodes in ISDM. Then, real-time transmission is one of the important aspects of ALM and one major objective of the ALM-based real-time transmissions is to determine multicast tree so as to guarantee the lower delay. This paper proposes the DDSD (the degree-and delay-bounded maximum instantaneous stability degree ALM tree) problem based on the ISDM. The DDSD problem is proved to be NP-Hard and an approximation algorithm (i.e. DDSD-H) is proposed to solve it. In addition, three heuristic policies are presented for the algorithm. Finally, the simulation results demonstrate the validity of the proposed algorithms and the comparison in the performance of the three heuristic policies is made.

Abstract:Sumanta Sarkar, et al. give a class of rotation symmetric Boolean functions with maximum algebraic immunity, but only consider the nonlinearity of the functions and did not study other cryptographic properties. In this paper, other cryptographic properties of the class of Boolean functions are studied, such as, algebraic degree, linear structure, propagation, correlation immunity etc. The results, unfortunately, show that their other cryptographic properties are not good even though their algebraic immunity is optimum. Hence, the class of Boolean functions cannot be applied in cryptography.

Abstract:Large-Scale network storage systems are confronted with the big challenge of efficiently distributing data among storage devices. It’s necessary to design an efficient, fair and adaptive data placement algorithm. This paper has developed an algorithm CCHDP (clustering-based and consistent hashing-aware data placement) to distribute data over heterogeneous devices in the systems. It combines clustering algorithm and consistent hashing, saving much memory space by avoiding extra virtual devices. The analysis and experiments show that CCHDP can notonly assign data evenly among devices and adapt well with the additions or departures of devices for the number of data moved is nearly equal to the optimal amount in the events of devices changes. Moreover, CCHDP is time efficient with little memory overhead.

Abstract:To achieve on-demand software deployment in large-scale virtual machine (VM) environments, this paper presents a prefetch-based on-demand software deployment optimization mechanism to reduce the VM startup latency and to improve the VM running performance at user side. Based on the characteristics of user’s behavior of using software and fine-grained splitting of virtual disk (VD) image, the paper prefetches those small-sized being-used VD images at user side from server side by using an access frequency and priority-based prefetch target recognition algorithm—AFPTR and uses a dynamic adjustment mechanism to adjust the prefetch amount during the prefetching process so as to improve the local hit ratio of virtual disk accessing and then the VM running performance at user side. Based on QEMU virtual machine monitor and Linux system, a prototype is built to implement the prefetch mechanism. Experiments on the prototype show that the prefetch mechanism can effectively reduce the VM startup latency and improve the VM running performance at user side, supporting on-demand, fast software deployment in virtual machine environments.

Abstract:Timeouts are usually used for failure detection in RPC (remote produce call) based systems, which are typically reported on a per-call basis. During pressure testing, on a very large cluster system, it has been found that the traditional fixed timeout mechanism leads lots of unnecessary timeouts, especially when the server loading is involved. This paper proposes an Adaptive Scalable RPC Timeout (AST for short) mechanism that considers network conditions, server load, scalability, and performance. Under this control, the timeout value, set by clients, can be adapted and adjusted in a dynamic fashion, according to congestion of the network and the server. Moreover, the server can notify the client to modify the timeout value of the RPC. Via a series of simulations, it has been proved that the AST mechanism is a more suitable failure detection mechanism for RPC models with timeouts, and it enhances the system responsibility, reliability, and stability without negative impact on performance, even for large-scaled cluster systems.

Abstract:This paper studies the multiprocessor job scheduling problem, and describes the m processors system, and analyze the algorithm for the problem of the offline version, both P_m|fix|C_max of the scheduling problem with arbitrary process time jobs, and P_m|fix, p=1|C_max of the scheduling problem with unit processing time jobs. Severalvery simple and practical polynomial time approximation algorithm are constructed, a (√2m+1)-approximation algorithm for the problem P_m|fix, p=1|C_max and a 2√m -approximation algorithm for the problem P_m|fix|C_max , by usingthe Split Scheduling (SS), the First Fit (FF) and the Large Wide First (LWF) technique. The results are better than any seen in the literature at present.

Abstract:Web user reviews are the important information source for many popular applications (e.g. monitoring and analysis of public opinion), and they need to be extracted accurately from Web pages. Web user reviews belong to user-generated contents, whose presentation is not restricted by the Web page template. Therefore new challenges are raised. First, the inconsistency of review contents on both DOM tree and visual appearance impair the similarity between review records; second, the review content in a review record corresponds to a complicated subtree rather than one single node in the DOM tree. To tackle these challenges, a comprehensive solution is proposed to perform automatic extraction of Web reviews by employing sophisticated techniques. The review records are extracted from Web pages based on the level-weighted tree similarity algorithm first, and then, the pure review contents in records are extracted by comparing the node consistency. The experimental results on news Web sites and forum Web sites indicate that our solution can achieve high extraction accuracy and efficiency.