Multimodal Sentiment Analysis (MSA) is a challenging research area that studies sentiment expressed from multiple heterogeneous modalities. Given those pre-trained language models such as BERT have shown state-of-the-art (SOTA) performance in multiple NLP disciplines, existing models tend to integrate these modalities into BERT and treat the MSA as a single prediction task. However, we find that simply fusing the multimodal features into BERT cannot well establish the power of a strong pre-trained model. Besides, the classification ability of each modality is also suppressed by single-task learning. In this paper, we propose a multimodal framework named Two-Phase Multi-task Sentiment Analysis (TPMSA), which applies a two-phase training strategy to make the most of the pre-trained model and a novel multi-task learning strategy to investigate the classification ability of each representation. We conduct experiments on two multimodal benchmark datasets CMU-MOSI and CMU-MOSEI, the results show that our TPMSA model significantly outperforms the current SOTA method on both datasets across all the metrics, which clearly show the effectiveness of our proposed method. Our code is available at \url{https://github.com/TPMSA/TPMSA}.

In this paper, we present a graph-based Transformer for semantic parsing. We separate the semantic parsing task into two steps: 1) Use a sequence-to-sequence model to generate the logical form candidates. 2) Design a graph-based Transformer to rerank the candidates. To handle the structure of logical forms, we incorporate graph information to Transformer, and design a cross-candidate verification mechanism to consider all the candidates in the ranking process. Furthermore, we integrate BERT into our model and jointly train the graph-based Transformer and BERT. We conduct experiments on 3 semantic parsing benchmarks, ATIS, JOBS and Task Oriented semantic Parsing dataset (TOP). Experiments show that our graph-based reranking model achieves results comparable to state-of-the-art models on the ATIS and JOBS datasets. And on the TOP dataset, our model achieves a new state-of-the-art result.

In this paper, we present a multi-level alignment pretraining method in a unified architecture for multi-lingual semantic parsing.In this architecture, we use an adversarial training method to align the space of different languages and use sentence level and word level parallel corpus as supervision information to align the semantic of different languages.Finally, we jointly train the multi-level alignment and semantic parsing tasks.We conduct experiments on a publicly available multi-lingual semantic parsing dataset ATIS and a newly constructed dataset.Experimental results show that our model outperforms state-of-the-art methods on both datasets.

Bo Shao, Yeyun Gong, Weizhen Qi, Nan Duan, Xiaola Lin. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Semantic parsing is a challenging and important task which aims to convert a natural language sentence to a logical form. Existing neural semantic parsing methods mainly use (Q-L) pairs to train a sequence-to-sequence model. However, the amount of existing Q-L labeled data is limited and hard to obtain. We propose an effective method which substantially utilizes labeling information from other tasks to enhance the training of a semantic parser. We design a multi-task learning model to train question type classification, entity mention detection together with question semantic parsing using a shared encoder. We propose a weakly supervised learning method to enhance our multi-task learning model with paraphrase data, based on the idea that the paraphrased questions should have the same logical form and question type information. Finally, we integrate the weakly supervised multi-task learning method to an encoder-decoder framework. Experiments on a newly constructed dataset and ComplexWebQuestions show that our proposed method outperforms state-of-the-art methods which demonstrates the effectiveness and robustness of our method.

With the wide adoption of SOA (Service Oriented Architecture), a massive amount of innovative applications emerge in the Internet. One of the popular representations is mashup. It is a new application created by combining different kinds of services. There exist multiple typed objects (e.g., mashup, service, category, tag, provider and description) and relations (e.g., compose and composed by relation between mashups and services, provide and provided by relation between services and providers), which constitute a heterogeneous information network (HIN) naturally. Several approaches already exist for recommending services for users but they are limited to consider only one or two kinds of relations between mashups and services. To apply the rich semantics and enhance recommendation performance, in this paper, we propose a Factorization Machine based service Recommendation approach, called FMRec, on HIN. Specifically, we firstly apply counting-based similarities for meta paths to capture the multiple semantic meanings between mashups and services. And then, we employ matrix factorization to the similarity matrices built by different kinds of meta paths to obtain the mashup latent features and service latent features. Finally, we leverage factorization machine model with a group lasso regularization term to learn the ratings between mashups and services. Comprehensive experiments are conducted on a real-world dataset, indicating that our proposed service recommendation approach significantly improves the quality of the recommendation results compared with existing methods.

Summary In this paper, we study the issue of improving the performance of Markov chain Monte Carlo method to solve local PageRank problem under General Purpose Graphics Processing Unit environment. As a large number of dangling vertices cause large storage space of dangling vertices and thus slow down the Markov chain procession, we propose a reordering strategy to compress the storage space and reduce the computational complexity of Markov chain procession. In our performance study, by parallelizing and optimizing the proposed algorithm based on GPU, the reordering strategy can be up 12× faster compared with basic method, where the graphs have high‐proportion dangling vertices. According to our investigation on this issue, the variance of random walks determines the number of random walks in the computation; we thus introduce low‐discrepancy sequences to enhance the performance. Moreover, the low‐discrepancy sequences are organized to load in the on‐chip shared memory to accelerate fetching with a wise warp scheduling for bank conflict schema. A series of experiments have been conducted to evaluate the optimization efficiency. Compared with fetching data from off‐chip global memory, the shared‐memory‐based strategy can have over 10× speedup ratio performance. The experiments indicate that the size of shared memory has a significant impact on the parallelism of the proposed method as well.

For 2D mesh based Network-on-Chip (NoC), the prohibited turns of routing algorithms should be repetitively distributed in order for the routing algorithms to be implemented by logic-based circuit. In this paper, we aim to exploit the designing space for logicbased routing algorithms, and propose new logic-based routing algorithms that outperform the state-of-the-art counterparts. Toward this direction, we firstly construct all routing algorithms for 5 x 5 2D mesh topology. Then we select those routing algorithms which have repetitive prohibited turns across both the network rows and columns. In addition, we chose those routing algorithms that have smaller routing pressures than Odd-Even routing algorithm. Then the routing algorithms for 2D mesh topology ranging from 6 x 6 to 15 x 15 are respectively constructed according to the prohibited turns distribution of the selected routing algorithms. Two routing algorithms that have smaller routing pressures than Odd-Even routing algorithm are obtained for all considered networks. The obtained logic-based routing algorithms are called as Repetitive Turn Model (RTM). Simulation results show that RTM could achieve up to 51% performance improvement as compared to Odd-Even routing algorithm.

Summary Matrix factorization is one of the leading techniques for many applications such as social network‐based recommendation systems. As of today, many parallel stochastic gradient descent (SGD) methods have been proposed to address the matrix factorization issue on shared‐memory (multi‐core) systems and distributed systems. However, these methods cannot be improved significantly on graphics processing unit (GPU) because the serious over‐writing problem and thread divergence may occur. The fundamental reason for such undesired results is that GPU is a parallel single instruction multiple data device, which only can greatly improve the applications with fine‐grained parallelism. In this paper, we propose an efficient GPU algorithm, named GPUSGD, to solve the matrix factorization problem based on SGD method. The major advantage of the proposed GPUSGD is that such method not only can handle the over‐writing problem but also can avoid the performance loss caused by the thread divergence. The experimental results show that GPUSGD performs much better in accelerating the matrix factorization compared with the existing state‐of‐the‐art parallel methods. To the best of our knowledge, this is the first work that develops a parallel SGD method to improve the matrix factorization on GPU. Copyright © 2015 John Wiley & Sons, Ltd.

Wireless energy transfer technology based on magnetic resonant coupling has been emerging as a promising technology for wireless sensor networks (WSNs) by providing controllable yet perpetual energy to sensors. In this article, we study the deployment of the minimum number of mobile charging vehicles to charge sensors in a large-scale WSN so that none of the sensors will run out of energy, for which we first advocate a flexible on-demand charging paradigm that decouples sensor energy charging scheduling from the design of sensing data routing protocols. We then formulate a novel optimization problem of scheduling mobile charging vehicles to charge life-critical sensors in the network with an objective to minimize the number of mobile charging vehicles deployed, subject to the energy capacity constraint on each mobile charging vehicle. As the problem is NP-hard, we instead propose an approximation algorithm with a provable performance guarantee if the energy consumption of each sensor during each charging tour is negligible. Otherwise, we devise a heuristic algorithm by modifying the proposed approximation algorithm. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimal ones. To the best of our knowledge, this is the first approximation algorithm with a nontrivial approximation ratio for a novel scheduling problem of multiple mobile charging vehicles for charging sensors.

Network-on-Chip (NoC) has been made the communication infrastructure for many-core architecture. NoC are subject to congestion, which is claimed to be avoided by many researchers. However, there is no completely understanding of congestion in literature, which hinders its solution. Toward this direction, we firstly carry out study on congestion in this paper. We find that congestion usually occurs at a portion of nodes in a local network region. Moreover, local congestion will significantly decrease system performance and mostly impact some particular communication pairs. Then we attempt to solve local congestion by addressing different local region size, based on Divide-Conquer approach and routing pressure. It avoids congestion in every local region by keeping routing pressure of every local region minimum. Using different local region size will create different routings. Our study shows that the local region size is closely related with the routing performance. When local region size is 5 × 5 the optimal routing performance of large size network could be achieved.

Smartphones now become an indispensable part of our daily life. However, their continuing operations consume lots of battery energy. For example, a fully-charged smartphone usually cannot support its continuing operation for a whole day. A fundamental problem related to this energy issue is how to prolong the smartphone lifetime so that it can last as long as possible to meet its user needs. Wireless energy transfer has been demonstrated as a promising technique to address this challenge. In this paper, we study the smartphone charging problem, using wireless chargers deployed on public commuters, e.g., subway trains, to charge energy-critical smartphones when their users take subway trains to work or go home. Since the residual energy of different smartphones are significantly different, the charging satisfactions of different users are essentially different too. In this paper we formulate this charging problem as a novel optimization problem that allocates limited wireless chargers on subway trains to charge energy-critical smartphones such that the overall charging satisfaction of mobile users is maximized, for a given monitoring period (e.g., one day). Specifically, we first devise a 1 over 3-approximation algorithm if the travel trajectory of each smartphone user in the monitoring period is given; otherwise, we devise an online algorithm dealing with dynamic energy-critical smartphone charging requests. We finally evaluate the performance of the proposed algorithms through experimental simulations with a real dataset of subway-taking in San Francisco. The experimental results show that the proposed algorithms are very promising, and 93.9% of energy-critical user smartphones can be satisfactorily charged in one-day monitoring period.

As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph$G$and an integer$k>0$, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in$G$with an aim to find$k$rootless (or rooted) edge-disjoint cycles covering the vertices in$V$such that the maximum cycle weight among the$k$cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a$(5{ 1\over 3} +\epsilon)$-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a$(6{ 1\over 3} +\epsilon)$-approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a$(7+\epsilon)$-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems$6+\epsilon$,$7+\epsilon$, and$13+\epsilon$, respectively, where$\epsilon$is a constant with$0< \epsilon <1$. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.

As a scalable substitute of on-chip bus, network-on-chip (NoC) is proposed as the communication infrastructure in modern multi/many-core system-on-chip (SoC). Efficient communication in NoC is critical to the overall SoC performance. Although local congestion has an important impact on communication delay, it is barely taken into account when designing routing algorithms. In this paper, we propose an offline methodology of designing routing algorithm based on channel pressure model to address the local congestion issue. Specifically, the proposed methodology uses divide-conquer with the aim of generating high performance routing algorithms, which are able to balance the load over the network with a consequent reduction of local congestion. By using the proposed methodology, the obtained routing could achieve up to 37% performance improvement (in terms of average communication delay) as compared to the well-known odd-even routing algorithm for 15 × 15 network.

How to precisely measure performance of routing algorithm is an important issue when studying routing algorithm of network-on-chip (NoC). The degree of adaptiveness is the most widely used metric in the literature. However, our study shows that the degree of adaptiveness cannot precisely measure performance of routing algorithm. It cannot account for why routing algorithm with high degree of adaptiveness may have poor performance. Simulation has to be carried out to evaluate performance of routing algorithm. In this paper, we propose a new metric of routing pressure for measuring performance of routing algorithm. It has higher precision of measuring routing algorithm performance than the degree of adaptiveness. Performance of routing algorithm can be evaluated through routing pressure without simulation. It can explain why congestion takes place in network. In addition, where and when congestion takes place can be pointed out without simulation.

In this paper, we study the use of multiple mobile charging vehicles to charge sensors in a large-scale wireless sensor network for a given monitoring period, where sensors can be charged by the vehicles with wireless power transfer. Since each sensor may experience multiple charges to avoid its energy expiration for the period, we first consider a charging problem of scheduling the multiple mobile vehicles to collaboratively charge sensors so that none of the sensors will run out of its energy and the sum of traveling distance (referred to as the service cost) of these vehicles can be minimized. Due to NP-hardness of the problem, we then propose a novel approximation algorithm for it, assuming that sensor energy consumption rates do not change over time. Otherwise, we devise a heuristic algorithm through minor modifications to the approximation algorithm. We finally evaluate the performance of the proposed algorithms via simulations. Experimental results show that the proposed algorithms are very promising, which can reduce upto 45% of the service cost in comparison with the service cost delivered by a greedy algorithm.

The emerging wireless energy transfer technology based on magnetic resonant coupling is a promising technology for wireless sensor networks as it can provide a controllable and perpetual energy source to sensors. In this paper we study the use of minimum number of wireless charging mobile vehicles to charge sensors in a sensor network so that none of the sensors runs out of its energy, subject to the energy capacity imposed on mobile vehicles, for which we first advocate an flexible on-demand wireless charging paradigm that decouples sensor energy charging scheduling from data routing protocols design. We then formulate an optimization problem of scheduling mobile vehicles to charge lifetime-critical sensors with an objective to minimize the number of mobile vehicles deployed, subject to the energy capacity constraint on each mobile vehicle. As the problem is NP-hard, we devise an approximation algorithm with a provable performance guarantee for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, and the solution obtained is fractional of the optimal.

In this paper, we study the use of a wireless charging vehicle (WCV) to replenish energy to sensors in a wireless sensor network so that none of the sensors will run out of its energy, where sensor batteries can be recharged. Specifically, we first propose a flexible on-demand sensor energy charging paradigm that decouples sensor energy replenishment and data collection into separate activities. We then formulate an optimization problem of wireless charging with an aim to maximize the ratio of the amount of energy consumed for charging sensors to the amount of energy consumed on traveling of the WCV as the WCV consumes its energy on both traveling and sensor charging. We also devise a novel algorithm for scheduling the tours of the WCV by jointly considering the residual lifetimes of sensors and the charging ratio of charging tours. We finally evaluate the performance of the proposed algorithm by conducting simulation. Experimental results show that the proposed algorithm is promising, and can improve the energy charging ratio of the WCV significantly.

Dynamic network is the abstraction of networks with frequent topology changes arising from node mobility or other reasons. With the model of dynamic network, fundamental distributed computing problems can be formally studied with rigorous correctness. In this work, we study the counting problem, which plays a significant role in many applications, such as all-to-all information dissemination. Existing counting algorithms for dynamic networks are mostly estimation based and randomized, and cannot achieve accurate results deterministically. To address this problem, we adopt the diffusing computation approach in this paper. Although this approach has been widely used to solve different distributed computing problems, due to dynamic topology changes, existing diffusing computation algorithms cannot work under dynamic network models. To address such challenge, we firstly define a new dynamicity model, named (Q, S)-distance, which is used to describe dynamic changes of information propagation time. Based on (Q, S)-distance, we design two different counting algorithms. The first algorithm focuses on extending typical diffusing computation approach by handling topology changes. Different from existing algorithms, which have two phases, our algorithms contain three phases and the new phase is used to determine and notify the termination of tree growing, which the major challenge is caused by topology dynamicity. The second algorithm further extends the first one by incorporating a cluster-based hierarchy to reduce communication cost. The correctness of both the algorithms is formally proved and their performances in time cost and communication cost are analyzed.

Cooperative caching is a desirable approach to achieve efficient data access in multi-hop wireless networks. Existing cooperative caching algorithms mostly focus on cache placement. Another key issue, cache consistency, has not been adequately addressed. In this paper, we propose CACC, a cooperative approach to maintain cache consistency for wireless mesh networks. CACC combines push and pull by making use of the hierarchical architecture of mesh networks. The key contribution of CACC lies in two techniques that introduce cooperation among network nodes in delivering invalidation reports (IRs) so as to reduce communication cost and tolerate message losses. The first technique, IR integration, buffers and merges IRs at gateway nodes and periodically broadcasts them. The second technique, cooperative IR re-sending, lets intermediate nodes resend missed IR messages upon request. The interval of IR broadcast is optimized to achieve the optimal tradeoff between push and pull. We conduct numerical analysis to find optimal values for different scenarios. We also perform simulation to confirm our analysis results and compare with existing approaches. The results show that CACC can save message cost significantly (50-70 percent).

The training of SVM can be viewed as a Convex Quadratic Programming (CQP) problem which becomes difficult to be solved when dealing with the large scale data sets. Traditional methods such as Sequential Minimal Optimization (SMO) for SVM training is used to solve a sequence of small scale sub-problems, which costs a large amount of computation time and is hard to be accelerated by utilizing the computation power of GPU. Although Interior Point Method (IPM) such as primal-dual interior point method (PDIPM) can be also addressed SVM training well and has favourable potential for parallelizing on GPU, it contains comparatively high time complexity O(l^3) and space complexity O(l^2), where l is the number of training instances. Fortunately, by invoking low-rank approximation methods such as Incomplete Cholesky Factorization (ICF) and Sherman Morrison Woodbury formula (SMW), the requirements of both storage and computation of PDIPM can be reduced significantly. In this paper, a parallel PDIPM method (P-PDIPM) along with a parallel ICF method (P-ICF) is proposed to accelerate the SVM training on GPU. Experimental results indicate that the training speed of P-PDIPM on GPU is almost 40x faster than that of the serial one (S-PDIPM) on CPU. Besides, without extensive optimization, P-PDIPM can obtain about 8x speedup over the state of the art tool LIBSVM while maintaining high prediction accuracy.

The fact that the on-chip network will suddenly get saturated indicates that it is necessary to devise an effective flow control strategy. Through tracing the status of the network buffer space we found that the payload of the on-chip network can not get beyond an upper bound to avoid vicious congestion. Specifically, quarter of the total network buffer space is such a threshold, which is termed Quarter Load Threshold (QLT). Based on this fact we present the Quarter Load Threshold (QLT) flow control strategy. The performance of the proposed strategy is evaluated by the open source simulator Noxim [2]. Simulation results show that the on-chip network runs smoothly and no serious congestion is encountered any more.

Desktop virtualization is a new delivery method in which desktop operating systems execute in a data center and users access their applications using stateless "thin-client" devices. This paradigm promises significant benefits in terms of data security, flexibility, and reduction of the total cost of ownership. It is important to further improve this approach while maintaining good user experience, decreasing the propelled desktop's granularity and optimizing the protocol utilized between clients and servers. In this paper, we build a feasible cloud computing system, in which application streaming technology is used to break the bottleneck between clients and computing resources, and at the server side, virtualization technology is utilized to help achieve better physical resource management, as well as the high performance virtualized storage system. Simulations show that the proposed system greatly improves the QoS of users and efficiently allocates resources among all clients.

This paper proposes a novel orthogonal algorithm and protocol of efficient group key management for secure multicast in distributed systems. In the proposed method, the sever only requires to multicast to update the group key after a subgroup or a user left and therefore bandwidth is reduced effectively. The nice features of the proposed scheme include few messages required in updating and almost instant reception of the new key information. Performance evaluation for the proposed scheme is also presented to show the superiority of the proposed method.

A fundamental challenge in peer-to-peer (P2P) Video-on-Demand (VoD) streaming is to quickly locate new supplying peers whenever a VCR command is issued, in order to achieve smooth viewing experiences. For most existing commercial systems which resort to tracking servers for such neighbor discovery, the increasing scale of P2P VoD systems has brought heavy load onto the dedicated servers. To avoid overloading the servers and achieve instant neighbor discovery over the self-organizing P2P overlay, we design a novel method of organizing peers watching the same video, that constitutes a light-weighted indexing structure to support efficient streaming and fast neighbor discovery at the same time. InstantLeap achieves an O(1) neighbor discovery efficiency upon any playback "leaps" across the media stream in streaming overlays of any sizes, with a low messaging cost for the overlay maintenance. We support our design with rigorous analysis and extensive simulations.

Cognitive radio (CR) is an emerging technology in wireless access, aiming at vastly improving the way radio spectrum is utilized. Its basic idea is that a secondary user (unlicensed user) can be permitted to use licensed spectrum, provided that it does not interfere with any primary users (licensed users). CR technology enables the development of an intelligent and adaptive wireless communication system that is essentially aware of the radio frequency environment. In this paper, we have proposed a novel cognitive MAC protocol for cognitive radio networks under the property-rights model, in which, secondary users are divided into several non-overlapping groups, and each group uses the proposed auction algorithm to bid for leasing the required channels from the auctioneer appointed by primary users. To the best of our knowledge, this protocol is the first to maximize the utilization of spectrum resources while achieving revenue maximization for primary users. Simulations indicate that our proposed MAC protocol utilizes spectrum resources to the maximum, guarantees the fairness and dynamics of channels allocation among groups.

In current peer-to-peer systems, system performance is evaluated by the metrics that characterize the features of the whole system while how each node's character affects the system performance is rarely considered. In this paper, we first introduce a new metric of publishing efficiency to quantitatively measure the impact of node's character on the system performance, and also we demonstrate the significance of the proposed metric. Then we build an analytical model to study how nodes' online time, shared resources and the ranges that the indices and resources of the nodes serve queries affect their publishing efficiency. We validate the analytical results through simulation and discuss their significance to improving the average nodes' publishing efficiency in peer-to-peer systems.

Caching is an important technique to improve the performance of computer systems, especially for high performance computing systems. In traditional n-way set associative cache scheme, all sets have the same number of blocks. The blocks in a set cannot be used by other sets, resulting in inefficient cache utility for most applications with non-uniform cache access patterns. In this paper, we propose a novel cache sharing method, called the Way-Level Share Cache structure (WLSC), to enhance the caching performance by balancing the cache sharing. In addition to retaining the major properties of the traditional method, our method allows the blocks in some sets to be used by other sets and it can be done dynamically in the running processes. It can adapt to different applications. Simulation indicates that the proposed method can greatly increase the hit rate and thus improve the caching performance in the systems.

In current peer-to-peer (P2P) systems, system performance is evaluated by the metrics that characterize the features of the whole system while how each node in system affects the system performance is rarely considered. In this paper, we first introduce a new metric of publishing efficiency based on the impact of nodes' characters on the system performance. Then, we build an analytical model to study the relationship between nodes' characters and the ranges that resources of the nodes can serve queries when all nodes keep the same publishing efficiency. Based on the analytical results, we propose a new differentiated resource publishing (DRP) architecture to keep nodes' publishing efficiency high. To the best of our knowledge, DRP architecture is the first to improve P2P systems from the impact of nodes' characters on the system performance. Simulation shows that this architecture can keep nodes' publishing efficiency in a high level and also greatly reduce search cost with only modest system maintenance cost.

Twisted cubes are variants of hypercubes. In this paper, we study the optimal embeddings of paths of all possible lengths between two arbitrary distinct nodes in twisted cubes. We use TQnto denote the n-dimensional twisted cube and use dist(TQn, u, v) to denote the distance between two nodes u and v in TQn, where n ges l is an odd integer. The original contributions of this paper are as follows: 1) We prove that a path of length l can be embedded between u and v with dilation 1 for any two distinct nodes u and v and any integer l with dist(TQn, u, v) + 2 les l les 2n- 1 (n ges 3) and 2) we find that there exist two nodes u and v such that no path of length dist(TQn, u, v) + l can be embedded between u and v with dilation 1 (n ges 3). The special cases for the nonexistence and existence of embeddings of paths between nodes u and v and with length dist(TQn, u, v) + 1 are also discussed. The embeddings discussed in this paper are optimal in the sense that they have dilation 1

We present in this paper an efficient medium access control (MAC) protocol called iCSMA/CD for improving the efficiencies of optical wavelength division multiplexing (WDM) networks. The key idea behind the design of iCSMA/CD is similar to the well-known carrier sense multiple access with collision detection (CSMA/CD) MAC protocol for the Ethernet, in the sense that both use the CD technique to resolve contentions for the carrier. However, our proposed protocol is unique in that it exploits some look-ahead method for achieving better delay-throughput performance. Simulation experiments are conducted to evaluate the delay-throughput performance of a WDM ring network controlled by the proposed iCSMA/CD protocol and the results demonstrate the impressive advantages of iCSMA/CD

Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes.We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n \ge 3 and l with 1 \le l \le \left\lceil {\frac{{n + 1}}{2}} \right\rceil -1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia.

Processor fault diagnosis takes an important role in fault-tolerant computing on multiprocessor systems. There are two classical diagnosis strategies - the precise strategy and the pessimistic strategy, both of which are based on the well-known PMC diagnostic model. Nevertheless, the degree of diagnosability of the system is limited under these two strategies. A better method, called the t/k-diagnosis strategy, is proposed by Somani and Peleg, in which the identified fault-set is allowed to contain at most k fault-free processors. Using this diagnosis strategy, the degree of diagnosability of the hypercube increases greatly as the number of the fault-free processors in the fault-set increases. We study the t/k-diagnosability of so-called BC graphs that include hypercubes, crossed cubes, Mobius cubes, and twisted cubes, etc. We show that any n-dimensional BC graph is t(n, k)/k-diagnosable when n/spl ges/4 and 0/spl les/k/spl les/n, where t(n,k)=(k+1)n-1/2(k+1)(k+2)+1. Therefore, the crossed cube, the Mobius cube, and the twisted cube all have the same t/k-diagnosability as the hypercube. As a result, the algorithms developed for diagnosis on the hypercube may also be used to diagnose multiprocessor systems whose network topologies are based on BC graphs.

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between [(n+1)/2] and 2/sup n/-1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that [(n+1)/2]+1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube.

Link-state routing protocols, such as OSPF and IS-IS, are widely used in the Internet today. In link-state routing protocols, global network topology information is first collected at each node. A shortest path tree (SPT) is then constructed by applying Dijkstra's shortest path algorithm at each node. Link-state protocols usually require the flooding of new information to the entire (sub)network after changes in any link state (including link faults). Narvaez et al. proposed a fault-tolerant link-state routing protocol without flooding. The idea is to construct a shortest restoration path for each unidirectional link fault. Faulty link information is distributed only to the nodes in the restoration path and only one restoration path is constructed. It is shown that this approach is loop-free. However, the Narvaez et al. approach is inefficient when a link failure is bidirectional because a restoration path is unidirectional and routing tables of nodes in the path are partially updated. In addition, two restoration paths may be generated for each bidirectional link fault. In this paper, we extend the Narvaez et al. protocol to efficiently handle a bidirectional link fault by making the restoration path bidirectional. Several desirable properties of the proposed extended routing protocol are also explored. A simulation study is conducted to compare the traditional link-state protocol, the source-tree protocol, the Narvaez et al. unidirectional restoration path protocol, and the proposed bidirectional restoration path protocol.

The cluster server is widely used in different types of systems. However, different types of applications require different types of resources from the cluster. Multimedia services heavily depend on the available communication bandwidth between server and clients. On the other hand, some scientific applications rely on CPU computation power. If a cluster server can support both types of application, resource utilization can be enhanced substantially. Unfortunately, when both types of applications compete for the network bandwidth, the QoS of the multimedia services will be decreased since the data have a temporally dependency feature. The authors propose cooperative scheduling between these two types of application in a cluster server system such that when the applications compete for bandwidth for communication, the influence of QoS of multimedia video services can be minimized.

Link-state routing protocols, such as OSPF and IS-IS, are widely used on the Internet. In link-state routing protocols, global network topology is first collected at each node. A shortest path tree (SPT) is then constructed by applying Dijkstra's shortest path algorithm at each node. Link-state protocols normally require the flooding of new information to the entire (sub)network after changes in any link state (including link faults). Narvaez et al. (2000) proposed a fault-tolerant link-state routing protocol without flooding. The idea is to construct a shortest restoration path for each uni-directional link fault. Faulty link information is distributed only to the nodes in the restoration path and only one restoration path is constructed. It is shown that this approach is loop-free. However, the approach of Narvaez et al. is inefficient when a link failure is bi-directional, because a restoration path is uni-directional and routing tables of nodes in the path are partially updated. In addition, two restoration paths may be generated for each bi-directional link fault. We extend the Narvaez protocol to efficiently handle a bi-directional link fault by making the restoration path bi-directional. Several desirable properties of the proposed extended routing protocol are also explored.

Checkpointing is an effective fault-tolerant technique for improving system availability and reliability. However, a blind checkpointing placement can result in either performance degradation or expensive recovery cost. By means of the calculus of variations, we derive an explicit formula that links the optimal checkpointing frequency with a general failure rate, with the objective of globally minimizing the total expected cost of checkpointing and recovery. Theoretical result shows that the optimal checkpointing frequency is proportional to the square root of the failure rate and can be uniquely determined by the failure rate (time-varying or constant) if the recovery function is strictly increasing and the failure rate is /spl lambda/(/spl infin/)>0. J.L. Bruno and E.G. Coffman (1997) suggest that optimal checkpointing by its nature is a function of system failure rate, i.e., the time-varying failure rate demands time-varying checkpointing in order to meet the criteria of certain optimality. The results obtained in this paper agree with their viewpoint.

This paper presents the design and performance of a new parallel graphics renderer for 3D images. This renderer is based on an adaptive supersampling approach that works for time/space-efficient execution on two classes of parallel computers. Our rendering scheme takes subpixel supersamples only along polygon edges. This leads to a significant reduction in rendering time and in buffer memory requirements. Furthermore, we offer a balanced rasterization of all transformed polygons. Experimental results prove these advantages on both a shared-memory SGI multiprocessor server and a Unix cluster of Sun workstations. We reveal performance effects of the new rendering scheme on subpixel resolution, polygon number, scene complexity, and memory requirements. The balanced parallel renderer demonstrates scalable performance with respect to increase in graphic complexity and in machine size. Our parallel renderer outperforms Crow's scheme in benchmark experiments performed. The improvements are made in three fronts: (1) reduction in rendering time, (2) higher efficiency with balanced workload,: and (3) adaptive to available buffer memory size. The balanced renderer can be more cost-effectively embedded within many 3D graphics algorithms, such as those for edge smoothing and 3D visualization. Our parallel renderer is MPI-coded, offering high portability and cross-platform performance. These advantages can greatly improve the QoS in 3D imaging and in real-time interactive graphics.

In this paper, we propose an efficient barrier synchronization scheme on networks with arbitrary topologies. We first present a distributed method in building a barrier routing tree. The barrier messages can be delivered adaptively according to the hierarchy of the established barrier tree to void congestion and faulty nodes in the network. We then propose a new technique, called bandwidth-preempting technique, for a blocked barrier message to preempt a channel occupied by a data message so that the latency of a barrier message can be controlled without affecting much of the overall system performance. We also propose an analytical performance model and present simulation results for the performance evaluation of the proposed scheme. Performance evaluations show that the proposed scheme outperforms the existing algorithms for barrier synchronization.

In this paper, we introduce a family of scalable interconnection network topologies, named Recursive Cube of Rings (RCR), which are recursively constructed by adding ring edges to a cube. RCRs possess many desirable topological properties in building scalable parallel machines, such as fixed degree, small diameter, wide bisection width, symmetry, fault tolerance, etc. We first examine the topological properties of RCRs. We then present and analyze a general deadlock-free routing algorithm for RCRs. Using a complete binary tree embedded into an RCR with expansion-cost approximating to one, an efficient broadcast routing algorithm on RCRs is proposed. The upper bound of the number of message passing steps in one broadcast operation on a general RCR is also derived.

We describe a parallel rendering method based on the adaptive supersampling technique to produce anti-aliased images with minimal memory consumption. Unlike traditional supersampling methods, this one does not supersample every pixel, but only those edge pixels. We consider various strategies to reduce the memory consumption in order for the method to be applicable in situations where limited or fixed amount of pre-allocated memory is available. This is a very important issue, especially in parallel rendering. We have implemented our algorithm on a parallel machine based on the message passing model. Towards the end of the paper, we present some experimental results on the memory usage and the performance of the method.

With respect to scalability and arbitrary topologies of the underlying networks in multiprogramming and multithread environments, fault tolerance in acknowledged ATAB and concurrent communications become a challenge to reliable general wormhole routing multicomputers with arbitrary topologies. In this paper, the virtual ring tree (VRT) is proposed to deal with the challenge. A single startup is needed in the two proposed algorithms by a simple virtual node space, which also reduces the complexity of routing at intermediate steps of ATAB algorithms and re-beginning an ATAB, by cacheable virtual channels. The proposed algorithm can automatically handle static faults in networks.

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.>

This paper investigates the analysis of concurrent OO designs using a formal, executable specification technique called G-Net. After presenting an overview of the G-Net technique, we show how to use the G-Net notation to specify the concurrent OO systems. A formal transformation technique, which translates a G-Net specification to a semantically equivalent PrT-net, is presented. The resultant PrT-net can then be formally analyzed. The practical significance of this approach in fault-tolerant systems and distributed multimedia systems design is discussed.

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms.>

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to develop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed.>

Efficient routing of messages is the key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. Wormhole routing is the most promising switching technique used in new generation multicomputers. In this paper, we present multicast wormhole routing methods for multicomputers adopting 2D-mesh and hypercube topologies. The dual-path routing algorithm requires less system resource, while the multi-path routing algorithm creates less traffic. More importantly, both routing algorithms are deadlock-free, which is essential to wormhole networks. Keywords: Multicomputers, Heuristic Algorithms, Hypercube Topology, 2D Mesh Topology, Multicast Communication, Wormhole Routing, NP-completeness, Grid Graphs. This work was supported in part by the NSF grants ECS-8814027 and MIP-8811815 ii 1 Introduction The performance of multicomputers is highly dependent on the underlying communicat...