Efficient and Scalable Routing Algorithms for Collective Communication Operations on 2D All-Port Torus Networks

Collective Communication Algorithms for 2D torus networks have been investigated quite extensively in the literature and two broad approaches, namely direct methods and indirect (message combining) methods are recognized in the field. While direct methods minimize the volume of data, the indirect methods reduce the number of message start-ups. Consequently, either a suite of algorithms must be employed for efficiency over a wide range of message lengths and communication operations or algorithms should be able to adapt themselves to the current case, possibly by switching between direct and indirect routing modes as appropriate. In this paper, we propose adaptive routing algorithms for all-port, wormhole routed, synchronous, 2D torus networks optimized for one-to-all broadcast,  gossiping and complete exchange collective communication operations. The proposed algorithms employ completely-connected subnetworks where complete exchange amongst the nodes in the subnetwork can be accomplished in one step only. Combined with suitable 2D plane tiling techniques, the proposed algorithms share the same set of primitive operations and yield superior performance compared to previously proposed methods, either pure or hybridized.     

Efficient, Scalable Congestion Management for Interconnection Networks

Compared to the overdimensioned designs of the past, current interconnection networks operate closer to the point of saturation and run a higher risk of congestion. Among proposed strategies for congestion management, only the regional explicit congestion notification (RECN) mechanism achieves both the required efficiency and the scalability that emerging systems demand     

Efficient and Scalable Algorithms for Inferring Likely Invariants in Distributed Systems

Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms.     

一种高效可扩展的传感器网络系统状态监测协议

具备一种底层基础设施来指示网络运行时的失效节点、资源消耗以及系统综合性能,对于传感器网络这样的分布式系统相当重要.研究了用于系统状态监测的数据分发与收集网络协议,提出了基于最大连通度的分簇模型,并通过仿真对其有效性进行了验证,在该模型基础上设计与实现了用于系统状态监测的层次型数据分发与收集网络协议,仿真证明该协议与现有数据分发与收集协议相比具有更好的可扩展性与能量有效性.     

Efficient and Scalable Hardware-Based Multicast in Fat-Tree Networks

This article presents an efficient and scalable mechanism to overcome the limitations of collective communication in switched interconnection networks in the presence of faults. Considering that current trends in supercomputing are moving toward massively parallel computers, with many thousands of components, reliability becomes a challenge. In such scenario, fat-tree networks that provide hardware support for collective communication suffer from serious performance degradation due to the presence of, even, a single faulty node. This paper describes a new mechanism to provide high-performance collective communication in such situations. The feasibility of the proposed technique is formally demonstrated. We present the design of a new hardware-based routing algorithm for multicast, that is at the base of our proposal. The proposed mechanism is implemented and experimentally evaluated. Our experimental results show that hardware-based multicast trees provide an efficient and scalable solution for collective communication in fat-tree networks, significantly outperforming traditional solutions.     

Efficient EREW PRAM algorithms for parentheses-matching

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log² n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms     

Efficient Multicast Algorithms for Multichannel Wireless Mesh Networks

The wireless mesh network is an emerging technology that provides high quality service to end users as the "last mile” of the Internet. Furthermore, multicast communication is a key technology for wireless mesh networks. Multicast provides efficient data distribution among a group of nodes. However, unlike other wireless networks, such as sensor networks and MANETs, where multicast algorithms are designed to be energy efficient and to achieve optimal route discovery among mobile nodes, wireless mesh networks need to maximize throughput. This paper proposes two multicast algorithms: the Level Channel Assignment (LCA) algorithm and the Multichannel Multicast (MCM) to improve the throughput for multichannel and multi-interface mesh networks. The algorithms build efficient multicast trees by minimizing the number of relay nodes and total hop count distances of the trees. The algorithms use dedicated channel assignment strategies to reduce the interference to improve the network capacity. We also demonstrate that using partially overlapping channels can further diminish the interference. Furthermore, additional interfaces help to increase the bandwidth, and multiple gateways can further shorten the total hop count distance. Simulations show that those algorithms greatly outperform the single-channel multicast algorithm. We also observe that MCM achieves better throughput and shorter delay while LCA can be realized in distributed manner.     

Metafile-Based Scalable Caching and Dynamic Replacing Algorithms for Multiple Videos Over Quality-of-Service Networks

This paper presents metafile-based scalable caching and dynamic replacing algorithms for multiple videos over quality-of-service networks. A metafile for each video includes the cached-frame sequence, which is made by scalable caching algorithm minimizing client's buffer size and channel bandwidth under the general video traffic condition. Based on the metafiles, we propose a caching algorithm for multiple videos to effectively reduce both the buffer size and the required bandwidth and replacing algorithm to dynamically update the cached frames when user access pattern changes. Finally, experimental results are provided to compare the proposed algorithms with various existing caching and replacing algorithms.     

有效的光传送网路由及波长分配算法

研究了光传送网路由及波长分配问题，对于虚波长网络以波长优化为目的，给出了两种启发式算法，并提出了波长数减一代价，作为对算法另一评判依据，通过对仿真结果的分析，来研究所提出算法的有效性。     

Bounded Consensus Algorithms for Multi‐Agent Systems in Directed Networks

In this paper, the consensus problem is investigated via bounded controls for the multi‐agent systems with or without communication. Based on the nested saturation method, the saturated control laws are designed to solve the consensus problem. Under the designed saturated control laws, the transient performance of the closed‐loop system can be improved by tuning the saturation level. First of all, asymptotical consensus algorithms with bounded control inputs are proposed for the multi‐agent systems with or without communication delays. Under these consensus algorithms, the states’ consensus can be achieved asymptotically. Then, based on a kind of novel nonlinear saturation functions, bounded finite‐time consensus algorithms are further developed. It is shown that the states’ consensus can be achieved in finite time. Finally, two examples are given to verify the efficiency of the proposed methods.     

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

Efficient Algorithms for p-Self-Protection Problem in Static Wireless Sensor Networks

Wireless sensor networks have been widely used in many surveillance applications. Due to the importance of sensor nodes in such applications, certain level of protection need to be provided to them. We study the self protection problem for static wireless sensor networks in this paper. Self protection problem focuses on using sensor nodes to provide protection to themselves instead of the target objects or certain target area, so that the sensor nodes can resist the attacks targeting on them directly. A wireless sensor network is p-self-protected, if at any moment, for any wireless sensor (active or non-active), there are at least p active sensors that can monitor it. The problem finding minimum p-self-protection is NP-complete and no efficient self protection algorithms have been proposed. In this paper, we provide efficient centralized and distributed algorithms with constant approximation ratio for minimum p-self-protection problem in sensor networks with either homogeneous or heterogeneous sensing radius. In addition, we design efficient distributed algorithms to not only achieve p-self-protection but also maintain the connectivity of all active sensors. Our simulation confirms the performances of proposed algorithms.     

Efficient Algorithms for Optimal Uneven Protection of Single and Multiple Scalable Code Streams Against Packet Erasures

we study algorithmic approaches for rate-fidelity optimal packetization of a single and multiple scalable source code streams with uneven erasure protection (UEP). A new algorithm is developed to obtain the globally optimal solution for scalable source codes of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing packets is monotonically nonincreasing in , and independent erasure channels with packet erasure rate smaller than 0.5. This is achieved at linear space complexity and near-linear time complexity in the transmission budget, representing significant improvement over the known globally optimal algorithm. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the global optima. The above success is also extended to UEP packetization of multiple scalable code streams. We improve the existing algorithms in both speed and performance.     

Scalable Parallel Algorithms for FPT Problems

Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and various forms of parallel algorithms are devised, implemented, and compared. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. Target problems need only be amenable to reduction and decomposition. Applications in high throughput computational biology are also discussed.     

Energy Efficient Backoff Hierarchical Clustering Algorithms for Multi-Hop Wireless Sensor Networks

Compared with flat routing protocols, clustering is a fundamental performance improvement technique in wireless sensor networks, which can increase network scalability and lifetime. In this paper, we integrate the multi-hop technique with a backoff-based clustering algorithm to organize sensors. By using an adaptive backoff strategy, the algorithm not only realizes load balance among sensor node, but also achieves fairly uniform cluster head distribution across the network. Simulation results also demonstrate our algorithm is more energy-efficient than classical ones. Our algorithm is also easily extended to generate a hierarchy of cluster heads to obtain better network management and energy-efficiency.     

Dynamic Algorithms for Graphs of Bounded Treewidth

The formalism of monadic second-order (MS) logic has been very successful in unifying a large number of algorithms for graphs of bounded treewidth. We extend the elegant framework of MS logic from static problems to dynamic problems, in which queries about MS properties of a graph of bounded treewidth are interspersed with updates of vertex and edge labels. This allows us to unify and occasionally strengthen a number of scattered previous results obtained in an ad hoc manner and to enable solutions to a wide range of additional problems to be derived automatically. As an auxiliary result of independent interest, we dynamize a data structure of Chazelle for answering queries about products of labels along paths in a tree with edges labeled by elements of a semigroup.     

Event Counting of Partially-Observed Discrete-Event Systems with Uniformly and Nonuniformly Bounded Diagnosis Delays

We present an approach dealing with repeated fault events in the framework of model-based monitoring of discrete-event systems (DES). Various notions of diagnosability reported in the literature deal with uniformly bounded finite detection of counting delays over all faulty behaviors (uniform delays for brevity). The situation where the diagnosability notion of interest fails to hold under a given observation configuration leads typically to the deployment of more observational devices (e.g., sensors), which may be costly or infeasible. As an alternative to the additional deployment of observational devices, one might want to relax the uniformity of delays, while delays remain finite. To this end, we introduce a notion of diagnosability characterized with nonuniformly bounded finite counting delays (nonuniform counting delays for brevity), where finite delay bounds can vary on faulty behaviors. To evaluate the introduced notion of diagnosability with nonuniform counting delays, a polynomial-time verification algorithm is developed. Notably, the developed verification technique can readily be modified to construct a computationally superior verification algorithm for diagnosability under uniformly bounded finite counting delays (uniform counting delays for brevity) as compared to an algorithm previously reported in the literature. We also develop a novel on-line event counting algorithm that improves the time and space complexities of the currently available algorithms for the counting of special events.