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.     

基于图卷积网络融合依存信息的事件检测方法

句子级别细粒度的事件检测任务旨在对触发词进行识别与分类。针对现有事件检测方法中存在的过度平滑及缺乏依存类型信息的问题,提出了一种基于图卷积网络融合依存信息的事件检测方法。该模型首先使用双向长短期记忆网络对句子进行编码,同时根据依存分析构建多阶句法图和依存句法图;然后利用图卷积网络融合句子的依存信息,从而有效地利用多跳信息和依存标签信息。在自动文本抽取数据集上进行实验,在触发词识别和分类这两个子任务中分别取得了81.7%和78.6%的F1值。结果显示,提出的方法能更加有效地捕获句子中的事件信息,提升了事件检测的效果。     

基于语义依存分析的图网络文本分类模型

针对目前已有的文本分类方法未考虑文本内部词之间的语义依存信息而需要大量训练数据的问题,提出基于语义依存分析的图网络文本分类模型TextSGN。首先对文本进行语义依存分析,对语义依存关系图中的节点（单个词）和边（依存关系）进行词嵌入和one-hot编码;在此基础上,为了对语义依存关系进行快速挖掘,提出一个SGN网络块,通过从结构层面定义信息传递的方式来对图中的节点和边进行更新,从而快速地挖掘语义依存信息,使得网络更快地收敛。在多组公开数据集上训练分类模型并进行分类测试,结果表明,TextSGN模型在短文本分类上的准确率达到95.2%,较次优分类法效果提升了3.6%。     

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.     

基于句法依存分析的图网络生物医学命名实体识别

现有的生物医学命名实体识别方法没有利用语料中的句法信息,准确率不高.针对这一问题,提出基于句法依存分析的图网络生物医学命名实体识别模型.首先利用卷积神经网络(CNN)生成字符向量并将其与词向量拼接,然后将其送入双向长短期记忆(BiLSTM)网络进行训练;其次以句子为单位对语料进行句法依存分析,并构建邻接矩阵;最后将Bi...     

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.     

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.     

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

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

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

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

基于异构动态图模型的社交网络节点分类方法

在机器学习领域,与传统的神经网络相比,图神经网络在社交推荐等任务中发挥着越来越重要的作用,但是目前工作中大多数都使用静态图.针对现有静态图神经网络方法难以考虑社交用户动态特性的问题,通过引入动态图模型提出了一种基于异构动态图模型的社交网络节点分类方法.该方法在动态图建模的基础上,通过基于点边交互的节点特征更新机制和基于循环神经网络的时序聚合方法,实现了高效的动态社交网络节点分类.在多个真实数据集上的实验结果表明,提出方法在动态社交网络数据的节点分类方面有较好的效果,对比静态图和动态图的基准方法有显著的提升.     

动态贝叶斯网络结构学习的依赖分析方法研究

针对现有动态贝叶斯网络结构学习方法具有低效率和低可靠性等问题,基于变量之间的基本依赖关系和依赖分析方法进行动态贝叶斯网络结构学习。建立变量之间依赖关系草图,通过条件独立行检验去除多余的边,使用碰撞识别和条件相对预测能力确定边的方向,便可得到构成动态贝叶斯网络结构的先验网和转换网。该方法在效率和可靠性方面均具有优势。     

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...     

基于二分图的两级动态异构网络选择方案

通信技术的发展,使多种接入技术并存的异构网络成为未来通信网络的发展趋势,随着用户业务QoS需求的提高和传输带宽的增加,现有的网络选择算法已经不能满足用户高质量的通信需求。针对异构无线网络频谱资源日益紧缺的问题,提出了由用户端和网络端共同参与的两级动态网络选择方案。该方案包括灰度关联分析法和二分图联合优化匹配算法,通过用户端和网络端的共同决策,算法在有效满足移动用户业务服务质量需求的前提下,优化了系统吞吐量,均衡了网络负载。仿真实验表明,相对传统算法,该方案极大地提高了异构网络频谱资源利用率并降低了用户在无线网络间的切换概率,实现了用户需求和网络资源的合理配置。