A theory for deadlock-free dynamic network reconfiguration. Part I

This paper develops theoretical support useful for determining deadlock properties of dynamic network reconfiguration techniques and also serves as a basis for the development of design methodologies useful for deriving deadlock-free reconfiguration techniques. It is applicable to interconnection networks typically used in multiprocessor servers, network-based computing clusters, and distributed storage systems, and also has potential application to system-on-chip networks. This theory builds on basic principles established by previous theories while pioneering new concepts fundamental to the case of dynamic network reconfiguration.     

A methodology for developing deadlock-free dynamic network reconfiguration processes. Part II

For pt.I see ibid., vol.16, no.5, p.412-427 (2005). Dynamic network reconfiguration is defined as the process of changing from one routing function to another while the network remains up and running. The main challenge is in avoiding deadlock anomalies while keeping restrictions on packet injection and forwarding minimal. Current approaches either require virtual channels in the network or they work only for a limited set of routing algorithms and/or fault patterns. In this paper, we present a methodology for devising deadlock free and dynamic transitions between old and new routing functions that is consistent with newly proposed theory [J. Duato et al., (2005)]. The methodology is independent of topology, can be applied to any deadlock-free routing function, and puts no restrictions on the routing function changes that can be supported. Furthermore, it does not require any virtual channels to guarantee deadlock freedom. This research is motivated by current trends toward using increasingly larger Internet and transaction processing servers based on clusters of PCs that have very high availability and dependability requirements, as well as other local, system, and storage area network-based computing systems.     

A protocol for deadlock-free dynamic reconfiguration in high-speedlocal area networks

High-speed local area networks (LANs) consist of a set of switches interconnected by point-to-point links, and hosts linked to those switches through a network interface card. High-speed LANs may change their topology due to switches being turned on/off, hot expansion, link remapping, and component failures. In these cases, a distributed reconfiguration protocol analyzes the topology, computes the new routing tables, and downloads them to the corresponding switches. Unfortunately, in most cases, user traffic is stopped during the reconfiguration process to avoid deadlock. These strategies are called static reconfiguration techniques. Although network reconfigurations are not frequent, static reconfiguration such as this may take hundreds of milliseconds to execute, thus degrading system availability significantly. Several distributed real-time applications have strict communication requirements; Distributed multimedia applications have similar, although less strict, quality of service (QoS) requirements. Both stopping packet transmission and discarding packets due to the reconfiguration process prevent the system from satisfying the above requirements. Therefore, in order to support hard real-time and distributed multimedia applications over a high-speed LAN, we need to avoid stopping user traffic and discarding packets when the topology changes. In this paper, we propose a new deadlock-free distributed reconfiguration protocol that is able to asynchronously update routing tables without stopping user traffic. This protocol is valid for any topology, including regular as well as irregular topologies. It is also valid for packet switching as well as for cut-through switching techniques and does not rely on the existence of virtual channels to work. Simulation results show that the behavior of our protocol is significantly better than for other protocols based on stopping user traffic     

Deadlock-free dynamic reconfiguration schemes for increased network dependability

Network-based parallel computing systems often require the ability to reconfigure the routing algorithm to reflect changes in network topology if and when voluntary or involuntary changes occur. The process of reconfiguring a network's routing capabilities may be very inefficient and/or deadlock-prone if not handled properly. We propose efficient and deadlock-free dynamic reconfiguration schemes that are applicable to routing algorithms and networks which use wormhole, virtual cut-through, or store-and-forward switching, combined with hard link-level flow control. One requirement is that the network architecture use virtual channels or duplicate physical channels for deadlock-handling as well as performance purposes. The proposed schemes do not impede the injection, transmission, or delivery of user packets during the reconfiguration process. Instead, they provide uninterrupted service, increased availability/reliability, and improved overall quality-of-service support as compared to traditional techniques based on static reconfiguration.     

Spatial-temporal dynamic semantic graph neural network

Neural Computing and Applications - Most existing methods based on graph neural network for traffic flow forecasting cannot effectively exploit potential semantic features, multiple features are...     

Research on the dynamic reconfiguration of Web application using two-phase compatibility verification

Implemented by dynamic service composition and integration, Web application has significantly affected our daily life, such as e-commerce and e-government. However, the open and ever-changing environment makes Web users more vulnerable to the usability problem, i.e. unreachable pages and reduced responsiveness. Accordingly, there is a need to deliver reliable Web application with attributes that cover the correctness and reliability. For the efficient handling of failures, the compatibility verification of dynamic reconfiguration strategies is attached great importance since it can guarantee the robustness and high quality of Web-based software. This paper extends the classical finite state machine (FSM) to formalize the behaviour of Web application, namely the extended FSM for Web applications (EFSM4WA) model. This model is also suitable to formally describe the interaction behaviours of dynamic reconfiguration when Web application encountered failure. Then, the compatibility verification of dynamic reconfiguration is carried out in two phases. During the first phase, it adopts the trace projection approach to check the compatibility against the synchronized product model in a qualitative way, which will select a set of candidate Web applications. During the second phase, it takes performance into consideration to choose a high-reliability Web application in a quantitative way. Finally, a case study is demonstrated to show the applicability of our approach.     

PDR: A protocol for dynamic network reconfiguration based on deadlock recovery scheme

Dynamic network reconfiguration is described as the process of replacing one routing function with another while the network keeps running. The main challenge is avoiding deadlock anomalies while keeping limitations on packet injection and forwarding minimal. Current approaches which have a high complexity and as a result have a limited practical applicability either require the existence of extra network resources, or they will affect the network performance during the reconfiguration process. In this paper we present a simple, fast and efficient mechanism for dynamic network reconfiguration which is based on regressive deadlock recovery instead of avoiding deadlock. The mechanism which is referred to as PDR guarantees a deadlock-free reconfiguration based on wormhole switching. In PDR, a particular approach is taken to handle both deadlocks and performance degradation. We propose the use of a packet injection restriction mechanism that prevents performance degradation near the saturation by controlling the network traffic. Further, in this approach, to accurately detect deadlocks, the deadlock detection mechanism is implemented and also improved by using only the local information, thereby considerably reducing false deadlock detections. In the rare cases when deadlocks are suspected, we propose a new technique that absorbs the deadlocked packet at the current node instead of dropping deadlocked packets and re-injects it later into the network. The main advantage of this method is its simplicity and also it does not require any additional buffers in intermediate nodes to handle deadlocks. It requires only some buffer space in the local node to temporarily hold the deadlocked packets removed from the network. Evaluating results reveal that the mechanism shows substantial performance improvements over the other methods and it works efficiently in different topologies with various routing algorithms.     

GC-LSTM: graph convolution embedded LSTM for dynamic network link prediction

Applied Intelligence - Dynamic network link prediction is becoming a hot topic in network science, due to its wide applications in biology, sociology, economy and industry. However, it is a...     

Cube connected Mobius ladders: an inherently deadlock-free fixeddegree network

The authors introduce a multiprocessor interconnection network, known as cube-connected Mobius ladders, which has an inherently deadlock-free routing strategy and hence has none of the buffering and computational overhead required by deadlock-avoidance message passing algorithms. The basic network has a diameter φ of 4n-1 for n2ⁿ⁺² nodes and has a fixed node degree of 4. The network can be interval routed in two stages and can be represented as a Cayley graph. This is the only practical fixed degree topology of size O(2^φ) which has an inherently deadlock-free routing strategy, making it ideally suited for medium and large sized transputer networks     

A regularized graph layout framework for dynamic network visualization

Many real-world networks, including social and information networks, are dynamic structures that evolve over time. Such dynamic networks are typically visualized using a sequence of static graph layouts. In addition to providing a visual representation of the network structure at each time step, the sequence should preserve the mental map between layouts of consecutive time steps to allow a human to interpret the temporal evolution of the network. In this paper, we propose a framework for dynamic network visualization in the on-line setting where only present and past graph snapshots are available to create the present layout. The proposed framework creates regularized graph layouts by augmenting the cost function of a static graph layout algorithm with a grouping penalty, which discourages nodes from deviating too far from other nodes belonging to the same group, and a temporal penalty, which discourages large node movements between consecutive time steps. The penalties increase the stability of the layout sequence, thus preserving the mental map. We introduce two dynamic layout algorithms within the proposed framework, namely dynamic multidimensional scaling and dynamic graph Laplacian layout. We apply these algorithms on several data sets to illustrate the importance of both grouping and temporal regularization for producing interpretable visualizations of dynamic networks.     

基于FPGA动态重构的卷积神经网络硬件架构设计

为了解决卷积神经网络硬件实现阶段的资源限制问题,提出了基于FPGA动态重构的卷积神经网络加速器设计。首先,设计了卷积神经网络加速器的整体并行策略和VLSI架构,并针对卷积神经网络的功能模块进行了流水线设计。其次,对卷积神经网络加速器进行动态重构设计,建立动态重构区域及其模块功能划分;并选用BPI Flash存储配置文件,通过内部配置端口读取配置文件对动态重构区域进行动态配置。实验结果表明,针对Lenet-5手写体识别网络,基于动态重构设计的加速器与相应的静态设计相比,使用的Slice LUTs、Slice Registers与DSP资源分别减少44%、27. 8%与71%。与基于软件平台实现作对比,系统执行时间大幅度降低。但是由于内部配置端口的带宽限制,重构配置时间延长了整个卷积网络的执行时间。     

用有向图法解决公式循环依赖问题

用户使用报表系统时,在自定义的公式集合中可能存在公式循环依赖问题,用一种有效的方法发现这一隐藏错误是设计报表系统的一项关键技术。研究了用有向图法解决报表系统中的公式循环依赖问题,提出了报表系统中的公式循环依赖问题;引用有向图和集合论上的关系等概念对公式循环依赖进行了形式定义,证明了公式循环依赖的判定方法;给出了公式依赖关系图的构造算法和用有向图法解决公式循环依赖的算法。     

Totally blind channel identification by exploiting guard intervals

Blind identification techniques estimate the impulse response of a channel by exploiting known finite alphabet or statistical properties of the transmitted symbols. Alternatively, oversampling the output is known to introduce dependencies also exploitable for channel identification. This paper proves the feasibility of estimating the channel by relying instead on the short sequences of zeros, known as guard intervals or zero padding, introduced between transmitted blocks by a number of communication protocols. Since no property of the transmitted information symbols is assumed, the method is called totally blind channel identification. It is proved that totally blind channel identification requires only two received blocks to estimate the channel.     

A novel dynamic graph evolution network for salient object detection

Applied Intelligence - The advanced deep convolution neural networks (CNNs) based salient object detection (SOD) models still suffer from the coarse object edge. The traditional graph-based SOD...     

Name disambiguation in scientific cooperation network by exploiting user feedback

Name disambiguation is a very critical problem in scientific cooperation network. Ambiguous author names may occur due to the existence of multiple authors with the same name. Despite much research work has been conducted, the problem is still not resolved and becomes even more serious. In this paper, we focus ourselves on such problem. A method of exploiting user feedback for name disambiguation in scientific cooperation network is proposed, which can make use of user feedback to enhance the performance. Furthermore, to make the user feedback more effective, we divide user feedback into three types and assign different weights to them. To evaluate the effectiveness of our proposed method, experiments are conducted with standard public collections. We compare the performance of our proposal with baseline methods. Results show that the proposed algorithm outperforms the previous methods without introducing user interactions. Besides, we investigate into how different types of user feedback can affect the disambiguation results.     

QoS contract preservation through dynamic reconfiguration: A formal semantics approach

The increasing pervasiveness of computing services in everyday life, combined with the dynamic nature of their execution contexts, constitutes a major challenge in guaranteeing the expected quality of such services at runtime. Quality of Service (QoS) contracts have been proposed to specify expected quality levels (QoS levels) on different context conditions, with different enforcing mechanisms. In this paper we present a definition for QoS contracts as a high-level policy for governing the behavior of software systems that self-adapt at runtime in response to context changes. To realize this contract definition, we specify its formal semantics and implement it in a software framework able to execute and reconfigure software applications, in order to maintain fulfilled their associated QoS contracts. The contribution of this paper is threefold. First, we extend typed-attributed graph transformation systems and finite-state machines, and use them as denotations to specify the semantics of QoS contracts. Second, this semantics makes it possible to systematically exploit design patterns at runtime by dynamically deploying them in the managed software application. Third, our semantics guarantees self-adaptive properties such as reliability and robustness in the contract satisfaction. Finally, we evaluate the applicability of our semantics implementation by integrating and executing it in FraSCAti, a multi-scale component-based middleware, in three case studies.     

Facial action unit recognition by exploiting their dynamic and semantic relationships

A system that could automatically analyze the facial actions in real time has applications in a wide range of different fields. However, developing such a system is always challenging due to the richness, ambiguity, and the dynamic nature of facial actions. Although a number of research groups attempt to recognize facial action units (AUs) by either improving facial feature extraction techniques, or the AU classification techniques, these methods often recognize AUs or certain AU combinations individually and statically, ignoring the semantic relationships among AUs and the dynamics of AUs. Hence, these approaches cannot always recognize AUs reliably, robustly, and consistently.In this paper, we propose a novel approach that systematically accounts for the relationships among AUs and their temporal evolutions for AU recognition. Specifically, we use a dynamic Bayesian network (DBN) to model the relationships among different AUs. The DBN provides a coherent and unified hierarchical probabilistic framework to represent probabilistic relationships among various AUs and to account for the temporal changes in facial action development. Within our system, robust computer vision techniques are used to obtain AU measurements. And such AU measurements are then applied as evidence to the DBN for inferring various AUs. The experiments show that the integration of AU relationships and AU dynamics with AU measurements yields significant improvement of AU recognition, especially for spontaneous facial expressions and under more realistic environment including illumination variation, face pose variation, and occlusion.     

Volume-based large dynamic graph analysis supported by evolution provenance

We present an approach for the visualization and interactive analysis of dynamic graphs that contain a large number of time steps. A specific focus is put on the support of analyzing temporal aspects in the data. Central to our approach is a static, volumetric representation of the dynamic graph based on the concept of space-time cubes that we create by stacking the adjacency matrices of all time steps. The use of GPU-accelerated volume rendering techniques allows us to render this representation interactively. We identified four classes of analytics methods as being important for the analysis of large and complex graph data, which we discuss in detail: data views, aggregation and filtering, comparison, and evolution provenance. Implementations of the respective methods are presented in an integrated application, enabling interactive exploration and analysis of large graphs. We demonstrate the applicability, usefulness, and scalability of our approach by presenting two examples for analyzing dynamic graphs. Furthermore, we let visualization experts evaluate our analytics approach.

     

Remote dynamic partial reconfiguration: A threat to Internet-of-Things and embedded security applications

The advent of the Internet of Things has motivated the use of Field Programmable Gate Array (FPGA) devices with Dynamic Partial Reconfiguration (DPR) capabilities for dynamic non-invasive modifications to circuits implemented on the FPGA. In particular, the ability to perform DPR over the network is essential in the context of a growing number of Internet of Things (IoT)-based and embedded security applications. However, the use of remote DPR brings with it a number of security threats that could lead to potentially catastrophic consequences in practical scenarios. In this paper, we demonstrate four examples where the remote DPR capability of the FPGA may be exploited by an adversary to launch Hardware Trojan Horse (HTH) attacks on commonly used security applications. We substantiate the threat by demonstrating remotely-launched attacks on Xilinx FPGA-based hardware implementations of a cryptographic algorithm, a true random number generator, and two processor based security applications - namely, a software implementation of a cryptographic algorithm and a cash dispensing scheme. The attacks are launched by on-the-fly transfer of malicious FPGA configuration bitstreams over an Ethernet connection to perform DPR and leak sensitive information. Finally, we comment on plausible countermeasures to prevent such attacks.     

A non-homogeneous dynamic Bayesian network with a hidden Markov model dependency structure among the temporal data points

In the topical field of systems biology there is considerable interest in learning regulatory networks, and various probabilistic machine learning methods have been proposed to this end. Popular approaches include non-homogeneous dynamic Bayesian networks (DBNs), which can be employed to model time-varying regulatory processes. Almost all non-homogeneous DBNs that have been proposed in the literature follow the same paradigm and relax the homogeneity assumption by complementing the standard homogeneous DBN with a multiple changepoint process. Each time series segment defined by two demarcating changepoints is associated with separate interactions, and in this way the regulatory relationships are allowed to vary over time. However, the configuration space of the data segmentations (allocations) that can be obtained by changepoints is restricted. A complementary paradigm is to combine DBNs with mixture models, which allow for free allocations of the data points to mixture components. But this extension of the configuration space comes with the disadvantage that the temporal order of the data points can no longer be taken into account. In this paper I present a novel non-homogeneous DBN model, which can be seen as a consensus between the free allocation mixture DBN model and the changepoint-segmented DBN model. The key idea is to assume that the underlying allocation of the temporal data points follows a Hidden Markov model (HMM). The novel HMM–DBN model takes the temporal structure of the time series into account without putting a restriction onto the configuration space of the data point allocations. I define the novel HMM–DBN model and the competing models such that the regulatory network structure is kept fixed among components, while the network interaction parameters are allowed to vary, and I show how the novel HMM–DBN model can be inferred with Markov Chain Monte Carlo (MCMC) simulations. For the new HMM–DBN model I also present two new pairs of MCMC moves, which can be incorporated into the recently proposed allocation sampler for mixture models to improve convergence of the MCMC simulations. In an extensive comparative evaluation study I systematically compare the performance of the proposed HMM–DBN model with the performances of the competing DBN models in a reverse engineering context, where the objective is to learn the structure of a network from temporal network data.