Long Short-Term Memory (LSTM) has been proven an efficient way to model sequential data, because of its ability to overcome the gradient diminishing problem during training. However, due to the limited memory capacity in LSTM cells, LSTM is weak in capturing long-time dependency in sequential data. To address this challenge, we propose an Attention-aware Bidirectional Multi-residual Recurrent Neural Network (ABMRNN) to overcome the deficiency. Our model considers both past and future information at every time step with omniscient attention based on LSTM. In addition to that, the multi-residual mechanism has been leveraged in our model which aims to model the relationship between current time step with further distant time steps instead of a just previous time step. The results of experiments show that our model achieves state-of-the-art performance in classification tasks.

Unlike previous unknown nouns tagging task, this is the first attempt to focus on out-of-vocabulary (OOV) lexical evaluation tasks that does not require any prior knowledge. The OOV words are words that only appear in test samples. The goal of tasks is to provide solutions for OOV lexical classification and predication. The tasks require annotators to conclude the attributes of the OOV words based on their related contexts. Then, we utilize unsupervised word embedding methods such as Word2Vec and Word2GM to perform the baseline experiments on the categorical classification task and OOV words attribute prediction tasks.

Several applications have been proposed for mobile wireless sensor networks. Some of these applications require the transfer of a large amount of data in a short period of time. This is challenging, since mobility can lead to a deterioration in the quality of an established link. Frequent link disconnection may in turn require a mobile node to repeatedly establish new links with the surrounding relay nodes to proceed with the data transfer. The new link establishment may cause extra data communication latency and make most of the applications delay sensitive. To evaluate the effect of mobility on latency, this paper first sets up a mathematical model based on a hybrid medium access control (MAC) protocol in mobile scenarios. It then uses NS2 simulation to further analyze the latency associated with mobility. Both results show that the latency increases with an increment in the network density and the duty cycle.

In this paper, a novel scheme is introduced for human facial feature extraction. Unlike previous methods that fit a 3D morphable model to 2D intensity images, our scheme utilizes 3D range images to extract features without requiring manually-defined initial landmark points. A linear transformation is used to achieve the mapping between the 3D model and a 3D range image, which makes the computation simple and fast. Moreover, our scheme is robust to the illumination and pose variations. In addition to features from range images, extra features can be obtained by examining optional 2D texture images. Using our scheme, we can also perform automatic eye/mouth corner localization. Experimental results show the high accuracy and robustness of our scheme.

In this paper, we describe a novel 3-D face recognition scheme for 3-D face recognition that can automatically identify faces from range images, and is insensitive to holes, facial expression, and hair. In our scheme, a number of carefully selected range images constitute a set of example faces, and another range image is chosen as a ldquogeneric face.rdquo The generic face is then warped to match each of the example faces in the least mean square sense. Each such warp is specified by a vector of displacement values. In feature extraction operation, when a target face image comes in, the generic face is warped to match it. The geometric transformation used in the warping is a linear combination of the example face warping vectors. The coefficients in the linear combination are adjusted to minimize the root mean square error. After the matching process is complete, the coefficients of the composite warp are used as features and passed to a Mahalanobis-distance-based classifier for face recognition. Our technique is tested on a data set containing more than 600 range images. Experimental results in the access-control scenario show the effectiveness of the extracted features.

Finite difference (FD) methods are the most prevalent numerical modelling algorithms for evaluating initial or boundary value problems in scientific and engineering applications. Unfortunately, simulating time evolutions for transient physical phenomenon is computationally demanding and data-intensive. This paper introduces an efficient implementation of FD computing engine on FPGA-based reconfigurable computing (RC) platform. Instead of following the formal high-order FD expressions with standard IEEE-754 compliant floating point arithmetic units, a new class of optimized finite-accurate FD schemes was proposed, whose FD coefficients are optimized to be represented with only a few binary bits without deteriorating numerical accuracy criterions. Furthermore, in order to simplify the implementation of floating-point summations, the conventional costly floating-point adder tree was replaced by a floating-point/fixed-point hybrid accumulator using group-alignment technology. The resulting fully-pipelined FD computing engine with finite accurate coefficients can provide us similar or even better worst case relative and absolute rounding errors than standard floating-point arithmetic, but consumes only a fraction of hardware resources. This new design can be easily applied to our previous work (He et al., 2005) and result in a more efficient and compact implementation with higher computational performance

Time domain or frequency domain Finite Difference (FD) methods are one of the most popular numerical modelling techniques in the solution of scientific and engineering problems. However, these simulations are still time-consuming and cannot be used routinely except in institutes that can afford the high cost of running and maintaining supercomputers or large PC-cluster systems. In this paper, we present an efficient implementation of FPGA-based FD computing engine using acoustic wave modeling problems as an example. Instead of following the formal high-order FD expressions with standard IEEE-754 compliant floating-point multipliers and adders, we propose a new class of optimized FD schemes, whose FD coefficients are optimized to be only a few binary bits so that much fewer Logic Cell (LC) resources or on-chip multipliers are needed without deteriorating numerical accuracy criterions. Furthermore, we simplify the implementation of following floatingpoint summations by group-alignment technology. A floating-point/fixed-point hybrid accumulator with similar relative and absolute rounding errors now replaces the conventional costly floating-point adder tree.

A successful application-oriented reconfigurable coprocessor design requires not only a powerful FPGA-based computing engine along with suitable hardware architecture, but also an efficient algorithm tailored for this special application. In this paper, we present our hardware architecture and numerical algorithms designed to speedup the time-domain finite-difference simulation of linear wave propagation problems in 2D and 3D space on FPGA-based reconfigurable platforms. Application fields of this work include seismic modeling and migration, computational electromagnetics, aeroacoustics, marine acoustics, to name a few. By writing first-order linear wave equations into second-order form, we halve the number of unknowns and simplify the treatment of parameters. We also adopt higher-order finite-difference (FD) schemes to further reduce the number of unknowns at the cost of increasing floating-point computations per discrete grid point. By doing so, we relief the bandwidth requirements between the FPGA and onboard memories but put more burden on the computing engine to take full advantage of FPGA's computational potentials. The speed of our design implemented on a Xilinx ML401 Virtex-4 evaluation platform is about 1.5/spl sim/4 times faster than a pure software implementation of the same algorithm running on a 3.0 GHz DELL workstation. This impressive result is mainly attributed to the memory architecture design, which is well-tuned for our numerical higher-order FD algorithms and can utilize onboard memory bandwidth more wisely. Furthermore, the good scalability of our design makes it compatible with most commercial reconfigurable coprocessor platforms and correspondingly, the performance would be proportional to their onboard memory bandwidth.

The designs of application specific integrated circuits and/or multiprocessor systems are usually required in order to improve the performance of multidimensional applications such as digital-image processing and computer vision. Wavelet-based algorithms have been found promising among these applications due to the features of hierarchical signal analysis and multiresolution analysis. Because of the large size of multidimensional input data, off-chip random access memory (RAM) based systems have ever been necessary for calculating algorithms in these applications, where either memory address pointers or data preprocessing and rearrangements in off-chip memories are employed. This paper establishes and follows novel concepts in data dependence analysis for generalized and arbitrarily multidimensional wavelet-based algorithms, i.e., the wavelet-adjacent field and the super wavelet-dependence vector. Based on them, a series of novel nonlinear I/O data space transformations for variable localization and dependence graph regularization for wavelet algorithms is proposed. It leads to general designs of non-RAM-based architectures for wavelet-based algorithms where off-chip communications for intermediate calculation results are eliminated without preprocessing or rearranging input data.

Although the notion of the parallelism in multidimensional applications has existed for a long time, it is so far unknown what the bound (if any) of inter-iteration parallelism in multirate multidimensional digital signal processing (DSP) algorithms is, and whether the maximum inter-iteration parallelism can be achieved for arbitrary multirate data flow algorithms. This paper explores the bound of inter-iteration parallelism within rate-balanced multirate multidimensional DSP algorithms and proves that this parallelism can always be achieved in hardware system given the availability of a large number of processors and the interconnections between them.

Migration is the most important seismic data processing method that recovers subsurface images of the Earth's interior using surface-recorded data volumes obtained from seismic reflection surveys. A reconfigurable coprocessor platform called SPACE (seismic data processing accelerator with reconfigurable engine) using field programmable gate array (FPGA) technology is proposed in this paper to speed up these computationally demanding and data-intensive seismic migration applications. The proposed SPACE platform is characterized by its simple architecture and abundant on-board memory resources along with ultra-wide memory bandwidth, which also makes the platform suitable for other seismic data processing methods or some large-scale scientific computing applications. The time-consuming kernel part of the pre-stack Kirchhoff time migration (PSTM) algorithm is programmed into the FPGA-based coprocessor platform, which acts as a hardware accelerator attached to an Intel-based workstation through the local peripheral controller interface (PCI) bus. Improved performance can be achieved by integrating a number of parallel running fully pipelined arithmetic modules into a single FPGA chip. Our simulation results show that the proposed coprocessor platform operating at a conservative speed of 50 MHz can calculate the Kirchhoff summations for 50 million points per second, which is about 15.6 times faster than a referential 2.4 GHz Pentium 4 workstation. The impressive performance of the proposed platform implies its broad applications in seismic data processing industry.

The dead-end problem is an importance issue of location-based routing in sensor networks, which occurs when a message falls into a local minimum using greedy forwarding. Current methods for this problem are insufficient either in eliminating traffic/path memorization or finding satisfied short paths. We propose a novel algorithm, named partial-partition avoiding geographic routing (PAGER), to solve the problem. The basic idea of PAGER is to divide a sensor network graph into functional sub-graphs, and provide each sensor node with message forwarding directions based on these sub-graphs. That results in loop-free short paths without memorization of traffics/paths in sensor nodes. We implement our algorithm in a protocol and evaluate it in sensor networks with different parameters. Results show that PAGER generates considerably shorter paths, higher delivery ratio and lower energy consumption than the greedy perimeter stateless routing protocol. At the same time, PAGER achieves better performance in handling large-scale networks than the ad-hoc on-demand distance vector protocol.

An ad hoc network is a self-organized and distributed entity consisting of a number of mobile stations (MS) without the coordination of any centralized access point. Clustering is one of the fundamental problems in ad hoc networks. In this context, we describe a distributed clustering algorithm for multihop ad hoc networks. We first propose a randomized control channel broadcast access method to maximize the worst-case control channel efficiency, based on which a distributed clustering algorithm is proposed. Both theoretical analysis and simulations indicate that the proposed clustering algorithm takes much less time and overhead to cluster a given network with more stable cluster structure, while incurring very small maintenance overhead in a dynamic network resulting from the mobility of the MS.

An ad hoc network is a self-organized and distributed entity, consisting of n mobile stations (MSs) without the coordination of any centralized access point. Initialization is one of the fundamental tasks to set up an ad hoc network, which involves assigning each of the n MSs a distinct ID number from 1 to n, distributedly. In Nakano et al. (2000), randomized initialization protocols are developed for single-hop ad hoc networks under different conditions. However, carrier sensing has not been utilized and suitable acknowledgment schemes for the algorithms are not developed. Moreover, the assumption taken by Nakano et al. about MSs being able to listen while transmitting is not valid for ad hoc networks. In this context, we describe two algorithms for initializing an ad hoc network with carrier sensing capability. First, a novel acknowledgment scheme is proposed for notifying a transmitting MS whether its transmission is successful during the initialization. Then, two distributed and randomized initialization algorithms are developed and analyzed, under the assumptions of a known and unknown number of users in the network, respectively. Both algorithms are obtained based on optimizing some key parameters to minimize the total time required to complete the initialization. Both theoretical analysis and simulations indicate that the proposed initialization algorithms outperform the existing methods, in the sense that they take much less time to complete the initialization and the average number of transmission attempts before success is much smaller.

The problem of broadcast channel access in single-hop and multihop ad hoc networks is considered. Two novel randomized and distributed channel access algorithms are developed and analyzed for single-hop and multihop networks, respectively. These algorithms are designed based on maximizing the worst-case channel efficiency, by optimizing some key parameters, including the backoff probability distribution and slot length. The proposed algorithm for single-hop networks offers significantly higher throughput than the CSMA methods when the traffic load is heavy, while still achieving good performance when the load is light or medium. The proposed algorithm for multihop networks can flexibly adapt to the traffic load, and offers much better throughput performance than the existing broadcast scheduling algorithms in light or medium load.

The data compression based on dictionary techniques works by replacing phrases in the input string with indexes into some dictionary. The dictionary can be static or dynamic. In static dictionary compression, the dictionary contains a predetermined fixed set of entries. In dynamic dictionary compression, the dictionary changes its entries during compression. We present parallel algorithms for two parsing strategies for static dictionary compression. One is the optimal parsing strategy with dictionaries that have the prefix properly, for which our algorithm requires O(L+log n) time and O(n) processors, where n is the number of symbols in the input string, and L is the maximum length of the dictionary entries, while previous results run in O(L+log n) time using O(n/sup 2/) processors or in O(L+log/sup 2/ n) time using O(n) processors. The other is the longest fragment first (LFF) parsing strategy, for which our algorithm requires O(L+log n,) time and O(n log L) processors, while a previous result obtained an O(L log n) time performance on O(n/log n) processors. For both strategies, we derive our parallel algorithms by modifying the on-line algorithms using a pointer doubling technique.

Studies parallel algorithms for two static dictionary compression strategies. One is the optimal dictionary compression with dictionaries that have the prefix property, for which our algorithm requires O(L+log n) time and O(n) processors, where L is the maximum allowable length of the dictionary entries, while previous results run in O(L+log n) time using O(n/sup 2/) processors, or in O(L+log/sup 2/n) time using O(n) processors. The other algorithm is the longest-fragment-first (LFF) dictionary compression, for which our algorithm requires O(L+log n) time and O(nL) processors, while the previous result has O(L log n) time performance on O(n/log n) processors. We also show that the sequential LFF dictionary compression can be computed online with a lookahead of length O(L/sup 2/).

Traditional approach for generating loop transformation matrix, which is based upon the computation of distance vectors or direction vectors, does not work for those nested loops whose distance vectors are uncomputable and direction vectors contain no useful information. In this paper, we present a new technique for generating transformation matrix that is based upon identifying certain types of linear equations or inequalities of distance vectors. Two issues related to this technique are discussed in this paper: 1) Given a nested loop how to identify these linear equations or inequalities; 2) Given such a linear equation or inequality how to generate a legal and unimodular transformation matrix for the purpose of loop parallelization.

This contribution is focused on self-routing permutation networks capable of routing all n! permutations of its n inputs to its n outputs without internal conflict. First, a self-routing permutation network named BNB SRPN is described. The network realizes the self-routing capability on the structure of the generalized baseline network, a modified model of the original baseline network. The network reduced both the hardware and the delay time compared with other comparable networks by a simple algorithm using 1-bit information for the routing decision. The network also has a good hardware regularity. In addition, a cost-effective self-routing network is presented, which is derived from the BNB SRPN. The network's hardware complexity, O(N log N), is the same as that of the Benes network which is not self-routing. The principle realizing a modular structure is also presented. The modular structure is derived from the principle to localize the routing decision. It is shown that the modular structure results in the reduction of the total delay through the network.>

A subsequence of a given string is any string obtained by deleting none or some symbols from the given string. A longest common subsequence (LCS) of two strings is a common subsequence of both that is as long as any other common subsequences. The problem is to find the LCS of two given strings. The bound on the complexity of this problem under the decision tree model is known to be mn if the number of distinct symbols that can appear in strings is infinite, where m and n are the lengths of the two strings, respectively, and m/spl les/n. In this paper, we propose two parallel algorithms far this problem on the CREW-PRAM model. One takes O(log/sup 2/ m + log n) time with mn/log m processors, which is faster than all the existing algorithms on the same model. The other takes O(log/sup 2/ m log log m) time with mn/(log/sup 2/ m log log m) processors when log/sup 2/ m log log m > log n, or otherwise O(log n) time with mn/log n processors, which is optimal in the sense that the time/spl times/processors bound matches the complexity bound of the problem. Both algorithms exploit nice properties of the LCS problem that are discovered in this paper.>

Parallel processing systems with cache or local memory in the memory hierarchies are considered. These systems have a local cache memory in each processor and usually employ a write-invalidate protocol for the cache coherence. In such systems, a problem called 'cache or local memory thrashing' can arise in executions of parallel programs, when the data unnecessarily moves back and forth between the caches or local memories in different processors. An approach to eliminate, or at least to reduce, such movement for nested parallel loops is presented. It is based on relations between array element accesses and enclosed loop indexes in the loops. The relations can be used to assign processors to execute the appropriate iterations for parallel loops in the loop nests with respect to the data in their caches or local memories. An algorithm for calculating the correct iteration of the parallel loop in terms of loop indexes of the previous iterations executed in the processor is presented. This method benefits parallel code with nested loop structures in a wide range of applications. The experimental results show that the technique can achieve speedups up to 2.>

The reconfiguration of multipipeline arrays in the presence of both faulty processing elements (PEs) and switching elements (SEs) is addressed. Different fault models are used for the PEs and SEs: a PE can be either fault free or faulty; a SE is modeled using a novel functional approach which relates its switching capabilities to its status. This permits a PE to retain a partial functionality in the presence of a fault. An appropriate transformation of the multipipeline array reconfiguration problem to a maximum flow problem is then presented. The conditions under which this transformation is possible, are fully analyzed. A reconfiguration algorithm based on the maximum flow algorithm is presented; the proposed algorithm is optimal as the number of reconfigured pipelines is maximized.>

A novel general algorithm for signed number division in the residue number system (RNS) is presented. The parity checking technique used for sign and overflow detection in this algorithm is more efficient and practical than conventional methods. Sign magnitude arithmetic division is implemented using binary search. There is no restriction to the dividend and the divisor (except zero divisor), and no quotient estimation is necessary before the division is executed. Only simple operations are needed to accomplish this RBS division. All these characteristics have made the algorithm simple, efficient, and practical for implementation on a real RNS divider.>

A general algorithm for signed number division in residue number systems (RNSs) is presented. A parity checking technique is used to accomplish the sign and overflow detection in this algorithm. Compared with conventional methods of sign and overflow detection, the parity checking method is more efficient and practical. Sign magnitude arithmetic division is implemented using binary search. There is no restriction on the dividend and the divisor (except zero divisor), and no quotient estimation is necessary before the division is started. In hardware implementations, the storage of one table is required for parity checking, and all the other arithmetic operations are completed by calculations. Only simple operations are needed to accomplish this RNS division.>

A self-routing permutation network capable of routing all n factorial permutations of its n inputs to its n outputs is presented. The network implements the binary radix sorting on the structure of the generalized baseline network, a modified model of the original baseline network. The network has O(N log/sup 3/ N) hardware complexity and O(log/sup 3/ N) delay time for N-inputs. The network makes use of the localized bit information instead of the global information in routing procedure. This strategy leads to the reduction of both the hardware and the delay time compared with other comparable networks. The resulting hardware is simple, and has a good regularity.>