A heterogeneous parallel computing environment consisting of different types of workstations and communication links plays an important role in parallel computing. In many applications on the system, collective communication operations are commonly used as communication primitives. Thus, design of the efficient collective communication operations is the key to achieve high-performance parallel computing. But the heterogeneity of the system complicates the design. In this paper, we consider design of an efficient gather operation, one of the most important collective operations. We show that an optimal gather schedule is found in O(n2k-1) time for the heterogeneous parallel computing environment with n processors of k distinct types, and that a nearly-optimal schedule is found in O(n) time if k=2.

GPS receivers are susceptible to jamming by interference. This paper proposes a recurrent neural network (RNN) predictor for new application in GPS anti-jamming systems. Five types of narrowband jammers, i. e. AR process, continuous wave interference (CWI), multi-tone CWI, swept CWI, and pulsed CWI, are considered in order to emulate realistic conditions. As the observation noise of received signals is highly non-Gaussian, an RNN estimator with a nonlinear structure is employed to accurately predict the narrowband signals based on a real-time learning method. The node decoupled extended Kalman filter (NDEKF) algorithm is adopted to achieve better performance in terms of convergence rate and quality of solution while requiring less computation time and memory. We analyze the computational complexity and memory requirements of the NDEKF approach and compare them to the global extended Kalman filter (GEKF) training paradigm. Simulation results show that our proposed scheme achieves a superior performance to conventional linear/nonlinear predictors in terms of SNR improvement and mean squared prediction error (MSPE) while providing inherent protection against a broad class of interference environments.

A parity check matrix for a binary linear code defines a bipartite graph (Tanner graph) which is isomorphic to a subgraph of a factor graph which explains a mechanism of the iterative decoding based on the sum-product algorithm. It is known that this decoding algorithm well approximates MAP decoding, but degradation of the approximation becomes serious when there exist cycles of short length, especially length 4, in Tanner graph. In this paper, based on the generating idempotents, we propose some methods to design parity check matrices for cyclic codes which define Tanner graphs with no cycles of length 4. We also show numerically error performance of cyclic codes by the iterative decoding implemented on factor graphs derived from the proposed parity check matrices.

The 2-vertex-connectivity augmentation problem for specified vertices (2VCA-SV) is defined as follows: Given an undirected graph G=(V,E), a subgraph G0=(V,E') of G, a specified set of vertices S V and a weight function w:E R^+ (nonnegative real numbers), find a set E" E-E' with the minimum total weight, such that G0+E"=(V,E' E") has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(|V||E|+ |V|2 log |V|) time algorithm 2-ABIS, whose performance ratio is 2 (3, respectively), for 2VCA-SV if G0 has a connected component containing S (otherwise).

The alternative c-means algorithm has recently been presented by Wu and Yang for robust clustering of data. In this letter, we analyze the convergence of this algorithm by transforming it into an equivalent form with the Legendre transform. It is shown that this algorithm converges to a local optimal solution from any starting point.

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n3) time per triangulation without duplications.

Based on a Quantum-inspired Evolutionary Algorithm (QEA), a new disk allocation method is proposed for distributing buckets of a binary cartesian product file among unrestricted number of disks to maximize concurrent disk I/O. It manages the probability distribution matrix to represent the qualities of the genes. Determining the excellent genes quickly makes the proposed method have faster convergence than DAGA. It gives better solutions and 3.2 - 11.3 times faster convergence than DAGA.

The wavelet transform (WT) has recently emerged as a powerful tool for image compression. In this paper, a new image compression technique combining the genetic algorithm (GA) and grey-based competitive learning network (GCLN) in the wavelet transform domain is proposed. In the GCLN, the grey theory is applied to a two-layer modified competitive learning network in order to generate optimal solution for VQ. In accordance with the degree of similarity measure between training vectors and codevectors, the grey relational analysis is used to measure the relationship degree among them. The GA is used in an attempt to optimize a specified objective function related to vector quantizer design. The physical processes of competition, selection and reproduction operating in populations are adopted in combination with GCLN to produce a superior genetic grey-based competitive learning network (GGCLN) for codebook design in image compression. The experimental results show that a promising codebook can be obtained using the proposed GGCLN and GGCLN with wavelet decomposition.

This paper proposes a new multistage technique of algebraic codebook in CELP coders called Trellis Search inspired from the Trellis Coded Quantization (TCQ). This search technique is implemented into the fixed codebook of the standard G.729 for objective evaluation on a large corpus of a testing speech database. Simulations results show that in terms of computer execution time the proposed search scheme reduces the codebook search by approximately 23% compared to the time of focused search used in the standard G.729. This yields to a reduction of about 8% in the computer execution time of the coder at the cost of a slight degradation of speech quality but perceptually not noticeable. Moreover, this new technique shows better speech quality than the G.729A at the expense of a higher complexity.

A novel fast calculation algorithm (FCA) for calculating the decision metric of the multiple-symbol differential detection (MSDD) considering the autocorrelation of a received sequence is proposed. In correspondence to the star quadrature amplitude modulation (QAM), the M algorithm is adopted to MSDD over Rayleigh fading channels, in order to reduce the number of search paths. The computational complexity of the decision metric can be greatly reduced by the proposed FCA and the M algorithm. Through computer simulations, it is confirmed that the symbol error rate (SER) performance of the MSDD considering autocorrelation is closer to that of the ideal coherent detection as the length of an observed sequence becomes larger over Rayleigh fading channels.

In this letter we propose a new fast matching algorithm that has no degradation of predicted images such as found in the conventional full search (FS) algorithm, so as to reduce the amount of computation of the FS algorithm for motion estimation in real-time video coding applications. That is, our proposing algorithm reduces only unnecessary computations in the process of motion estimation without decreasing the prediction quality compared to the conventional FS algorithm. The computational reduction comes from rapid elimination of impossible motion vectors. In comparison to the FS algorithm, we obtained faster elimination of inappropriate candidate motion vectors using efficient matching units based on image complexity. Experimentally, we demonstrated that the unnecessary computations were removed by about 30% as compared to the other fast FS algorithms.

This paper presents a new hierarchical scheduling method for a large-scale manufacturing system based on the hybrid Petri-net model, which consists of CPN (Continuous Petri Net) and TPN (Timed Petri Net). The study focuses on an automobile production system, a typical large-scale manufacturing system. At a high level, CPN is used to represent continuous flow in the production process of an entire system, and LP (Linear Programming) is applied to find the optimal flow. At a low level, TPN is used to represent the manufacturing environment of each sub-production line in a decentralized manner, and the MCT algorithm is applied to find feasible semi-optimal process sequences for each sub-production line. Our proposed scheduling method can schedule macroscopically the flow of an entire system while considering microscopically any physical constraints that arise on an actual shop floor.

A software module for the three-dimensional simulation of etching processes has been developed. It works on multilayer structures given as triangulated surface meshes. The mesh is moved nodewise according to rates which, in this work, have been determined from isotropic and anisotropic components. An important feature of the algorithm is the automatic detection of triple lines along mask edges and the refinement of triangles at these triple lines. This allows for the simulation of underetching. The capabilities of the algorithm are demonstrated by several examples such as the simulation of glass etching for the fabrication of a phase shift mask for optical lithography and the etching of an STI trench structure. Moreover, etch profiles of a silicon substrate covered by an oxide mask are shown for different parameters of the etch components. Spacer etching has also been performed. Furthermore, a specific algorithm for the simulation of purely isotropic etching is described and demonstrated.

In this letter, base station placement is automatically determined from pre-defined candidate sites using a genetic approach, and the transmit power is obtained taking the interference situation into account in cases of interference-dominant systems. In order to apply a genetic algorithm to the base station placement problem, a real-valued representation scheme is proposed. Corresponding operators such as crossover and mutation are also introduced. The proposed algorithm is applied to an inhomogeneous traffic density environment, where a base station's coverage may be limited by offered traffic loads. An objective function is designed for performing the cell planning in a coverage- and cost-effective manner.

An adaptive array antenna for the suppression of high-power interference in direct-sequence code-division multiple access (DS-CDMA) systems is presented. Although DS-CDMA has sufficient flexibility to support a variety of services, from voice to moving-pictures, with high levels of quality, multiple access interference (MAI) is a problem. This is particularly so of the high-power interference which accompanies high-speed transmission in DS-CDMA. While the application of adaptive array antennas is an effective way of improving signal-to-interference-plus-noise ratio (SINR), problems with this approach include large levels of power consumption and the high costs of hardware and of implementing the antennas. Therefore, our main purpose is to realize a simple configuration for an adaptive array system. In order to reduce the required amounts of processing, a common beam provides suppression of high-power interference for the low-bit-rate users; this makes per-user preparation of weights unnecessary. This approach also reduces the consumption of power by the system. Interference is cancelled by minimization of the array output power (i.e., the application of a power inversion algorithm) before despreading. The approach also allows us to improve the implementation of the antenna elements by using small auxiliary antennas. The basic performance of the system is confirmed through numerical calculation and computer simulation. Furthermore, a real-time processing unit has been developed and the effectiveness of the approach is confirmed by an experiment in a radio-anechoic chamber.

The ATM-ABR service category provides minimum cell rate (MCR) guarantees and robust connections even with insufficient network resources. Recently proposed rate-management algorithms for supporting multimedia applications over ABR mainly aim at minimizing the cell loss and delay. However, jitter is also an important element of QoS for multimedia applications. In this paper, we focus our attention on the arrival point of the critical cell corresponding to the end of data packet and propose a simple cell scheduling scheme for source node to reduce the jitter on application level over the ATM-ABR service class. In our proposed method, critical cells are delayed intentionally and the packet stream at application level becomes smooth. We verify the effectiveness of our proposed algorithm by an analytical model and simulation. From those results, we find that our proposed scheduling algorithm is effective in reducing the application level jitter even when the tagged cell stream is transmitted along the path with multiple nodes.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

We consider the routing for a multicast in a WDM all-optical network. We prove a min-max theorem on the number of wavelengths necessary for routing a multicast. Based on the min-max theorem, we propose an efficient on-line algorithm for routing a multicast.

An automated synthesis for analog computational circuits in transistor-level configuration is presented. A cell-based structure is introduced to place moderate constraints on the MOSFET circuit topology. Even though each cell has a simple structure that consists of one current path with four transistors, common analog building blocks can be implemented using combinations of the cells. A genetic algorithm is applied to search circuit topologies and transistor sizes that satisfy given specifications. Synthesis capabilities are demonstrated through examples of three types of computational circuits; absolute value, squaring, and cubing functions by using computer simulations and real hardware.

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.