Train Tracks and Confluent Drawings

Confluent graphs capture the connection properties of train tracks, offering a very natural generalization of planar graphs, and—as the example of railroad maps shows—are an important tool in graph visualization. In this paper we continue the study of confluent graphs, introducing strongly confluent graphs and tree-confluent graphs. We show that strongly confluent graphs can be recognized in NP (the complexity of recognizing confluent graphs remains open). We also give a natural elimination ordering characterization of tree-confluent graphs, and we show that this class coincides with the (6,2)-chordal bipartite graphs. Finally, we define outerconfluent graphs and identify the bipartite permutation graphs as a natural subclass.     

Optimal configuration of Energy-Efficient Ethernet

The IEEE 802.3az standard provides a new low power mode that Ethernet network interfaces can use to save energy when there is no traffic to transmit. Simultaneously with the final standard approval, several algorithms were proposed to govern the physical interface state transition between the normal active mode and the new low power mode. In fact, the standard leaves this sleeping algorithm unspecified to spur competition among different vendors and achieve the greatest energy savings. In this paper, we try to bring some light to the most well known sleeping algorithms, providing mathematical models for the expected energy savings and the average packet delay inflicted on outgoing traffic. We will then use the models to derive optimum configuration parameters for them under given efficiency constraints.     

Mapping streaming applications on multiprocessors with time-division-multiplexed network-on-chip

This paper addresses mapping of streaming applications (such as MPEG) on multiprocessor platforms with time-division-multiplexed network-on-chip. In particular, we solve processor selection, path selection and router configuration problems. Given the complexity of these problems, state of the art approaches in this area largely rely on greedy heuristics, which do not guarantee optimality. Our approach is based on a constraint programming formulation that merges a number of steps, usually tackled in sequence in classic approaches. Thus, our method has the potential of finding optimal solutions with respect to resource usage under throughput constraints. The experimental evaluation presented in here shows that our approach is capable of exploring a range of solutions while giving the designer the opportunity to emphasize the importance of various design metrics.     

Salt and pepper noise filtering with fuzzy-cellular automata

A new image denoising algorithm is proposed to restore digital images corrupted by impulse noise. It is based on two dimensional cellular automata (CA) with the help of fuzzy logic theory. The algorithm describes a local fuzzy transition rule which gives a membership value to the corrupted pixel neighborhood and assigns next state value as a central pixel value. The proposed method removes the noise effectively even at noise level as high as 90%. Extensive simulations show that the proposed algorithm provides better performance than many of the existing filters in terms of noise suppression and detail preservation. Also, qualitative and quantitative measures of the image produce better results on different images compared with the other algorithms.     

多核程序交互理论及应用

多核处理器上共享缓存使用效率,即程序局部性是影响并行程序性能的关键因素之一。提出了以足迹为基础的局部性理论。介绍了缺失率、重用距离和足迹之间的转化关系,并利用足迹可组合性特征建立了并行程序局部性预测模型。     

Studying re-opened bugs in open source software

Bug fixing accounts for a large amount of the software maintenance resources. Generally, bugs are reported, fixed, verified and closed. However, in some cases bugs have to be re-opened. Re-opened bugs increase maintenance costs, degrade the overall user-perceived quality of the software and lead to unnecessary rework by busy practitioners. In this paper, we study and predict re-opened bugs through a case study on three large open source projects—namely Eclipse, Apache and OpenOffice. We structure our study along four dimensions: (1) the work habits dimension (e.g., the weekday on which the bug was initially closed), (2) the bug report dimension (e.g., the component in which the bug was found) (3) the bug fix dimension (e.g., the amount of time it took to perform the initial fix) and (4) the team dimension (e.g., the experience of the bug fixer). We build decision trees using the aforementioned factors that aim to predict re-opened bugs. We perform top node analysis to determine which factors are the most important indicators of whether or not a bug will be re-opened. Our study shows that the comment text and last status of the bug when it is initially closed are the most important factors related to whether or not a bug will be re-opened. Using a combination of these dimensions, we can build explainable prediction models that can achieve a precision between 52.1–78.6 % and a recall in the range of 70.5–94.1 % when predicting whether a bug will be re-opened. We find that the factors that best indicate which bugs might be re-opened vary based on the project. The comment text is the most important factor for the Eclipse and OpenOffice projects, while the last status is the most important one for Apache. These factors should be closely examined in order to reduce maintenance cost due to re-opened bugs.     

High level information fusion for tracking and projection of multistage cyber attacks

The use of computer networks has become a necessity for government, industry, and personal businesses. Protection and defense against cyber attacks on computer networks, however, are becoming inadequate as attackers become more sophisticated and as the networks and systems become more complex. Drawing analogies from other application domains, this paper introduces information fusion to provide situation awareness and threat prediction from massive volumes of sensed data. An in-depth discussion is provided to define fusion tasks for cyber defense. A novel cyber fusion system is proposed to address specifically the tracking and projection of multistage attacks. Critical assessments of the developed attack tracking and threat projection sub-components are provided with simulation results. This pioneering work elaborates the benefits, limitations, and future challenges of high level information fusion for cyber security.     

Generalized modal satisfiability

It is well known that modal satisfiability is PSPACE-complete (Ladner (1977) [21]). However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an infinite number of propositional operators, since a propositional operator is simply a Boolean function. We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., in contrast to previous work, we classify an infinite number of problems. We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P. We obtain this trichotomy not only for modal formulas, but also for their more succinct representation using modal circuits. We consider both the uni-modal and the multi-modal cases, and study the dual problem of validity as well.     

Provide Virtual Distributed Environments for Grid computing on demand

Grid users always expect to meet some challenges to employ Grid resources, such as customized computing environment and QoS support. In this paper, we propose a new methodology for Grid computing – to use virtual machines as computing resources and provide Virtual Distributed Environments (VDE) for Grid users. It is declared that employing virtual environment for Grid computing can bring various advantages, for instance, computing environment customization, QoS guarantee and easy management. A light weight Grid middleware, Grid Virtualization Engine, is developed accordingly to provide functions of building virtual environment for Grids. We also present a typical use case, on-demand build a virtual e-Science infrastructure to justify the methodology.