Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

This paper formulates problems of fitting two corresponding sets of points by translation, rotation and scaling, and proposes efficient algorithms for the fitting. The algorithms are based on the theory of lower envelopes, or Davenport-Schinzel sequences, and linearization techniques in computational geometry, and are related to dynamic furthest Voronoi diagrams.

The fact that bounded interval band orthonormal scaling function shows oversampling property is demonstrated. The truncation error is estimated when scaling function with oversampling property is used to recover signals from their discrete samples.

In this paper, a new overload control strategy is proposed for a call control processor (CCP) in the base station controller (BSC) and processor utilization is measured. The proposed overload control strategy can regulate the call attempts by adopting measured processor utilization. A function, specifically a linear interpolation function based on Inverse Transform theory is used to convert controlled predictive average load rate in a call rejection rate. Then a call admission rate is obtained from the call rejection rate. Simulation shows that the proposed algorithm yields better performance than the conventional algorithm does under the heavy transient overload status in terms of call admission rate.

We propose and demonstrate a simple polarization-independent construction of a local node for optical WDM ring networks using a centralized multiwavelength light source (MWLS). The node is simply composed of a 4-port optical circulator, an add/drop multiplexing (ADM) filter, a reflective modulator, and a drop fiber Bragg grating (FBG). A Faraday rotator mirror (FRM) is used to enable an LiNbO3 intensity modulator to operate in the polarization-independent mode. We examine three ADM filters, an interference filter, a fiber Fabry-Perot (FP) filter, and a set of FBG's. An optical WDM system experiment is performed to demonstrate the feasibility of the proposed node construction.

A partial buffer sharing scheme is proposed as loss-priority control for a finite buffer with batch inputs. A partial batch acceptance strategy is used for a batch arriving at a finite buffer. Customer loss probabilities for high- and low-priority customers are derived under this batch acceptance strategy, using a supplementary variable method that is a standard tool for queueing analysis. A comparison of the partial buffer sharing scheme and a system without loss-priority control is made in terms of admissible offered load.

We apply evolutionary algorithms to neural network model of associative memory. In the model, some of the appropriate configurations of the synaptic weights allow the network to store a number of patterns as an associative memory. For example, the so-called Hebbian rule prescribes one such configuration. However, if the number of patterns to be stored exceeds a critical amount (over-loaded), the ability to store patterns collapses more or less. Or, synaptic weights chosen at random do not have such an ability. In this paper, we describe a genetic algorithm which successfully evolves both the random synapses and over-loaded Hebbian synapses to function as associative memory by adaptively pruning some of the synaptic connections. Although many authors have shown that the model is robust against pruning a fraction of synaptic connections, improvement of performance by pruning has not been explored, as far as we know.

Packet scheduling is one of the key mechanisms that will be employed in the network nodes (routers and switches) for supporting multiple quality of services. In this paper we propose a new packet scheduling algorithm called Urgency-based Round Robin (URR) which computes an index for flows in order to keep track of instantaneous bursts. Basically the index is employed as a measure of the time-dependent service necessity for each flow thus making it possible to detect those flows which might be in need of momentary service. Also, we propose a novel weight allocation scheme to be used together with the scheduler with the aim of preventing network underutilization. Our algorithm can be considered as a version of Weighted Round Robin (WRR) with improved delay characteristics. We show analytically that URR has the desired capability of upper-bounding unfairness. We also show, by simulation, that URR can improve delay performance even under extremely bursty traffic conditions without bandwidth overprovisioning. We also give simulation results for network traffic which exhibits long range dependency (self-similarity) and show that URR is again more effective than a plain round robin multiplexer.

Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of programs may degrade considerably. In this paper, we focus on automatic generation of communication routines for multi-dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some experimental results show the efficiency and flexibility of our techniques compared to the other redistribution works.

A unified theory for the characteristics of dual modes in a circular resonator is elucidated in simple analytical expressions. First, a circular resonator is considered as a ring transmission line which allows two oppositely traveling waves. The essential quantities that characterize a transmission line, i. e. , the propagation constant and characteristic impedance are obtained theoretically and/or experimentally. Secondly, any circular resonator is described by a ring resonator model which can be treated analytically, and the resonant frequencies are obtained when perturbations are added along the periphery of a circular resonator. A two stage BPF is created by adding I/O ports to the perturbed circular resonator. Its center frequency and bandwidth is calculated based on the ring resonator model. The circuit condition for obtaining two attenuation poles at both sides of the passband is given together with the method for their control.

Cursor RAMs have been composed of two memory planes. A cursor pattern is stored in these planes with 2-bit data depth. While the pixel port requires data from both planes at the same time, the MPU port accesses either one of the planes at a time. Since the address space is defined differently between the ports, conventional cursor RAMs could not have dealt with these different access ways at real time. This paper proposes a dual port cursor RAM with a dynamic data alignment architecture. The architecture processes the different access ways at real time, and reduces a large amount of control circuitry. Conventional cursor RAMs have been organized with a single port memory because dual port memory cells have been large. We have applied the port swap architecture which has reduced the cell size. The control block is further simplified because the controller no longer emulate a dual port memory. The cursor RAM with these architectures is fabricated with a double metal 0. 5 µm CMOS process technology. The active area is 1. 51. 6 mm2 including a couple of shift registers and a control block. It operates up to 263 MHz at the supply voltage of 3. 3 V.

When wireless multi-media information such as voice, video, data and so on are transmitted, the difference required quality of Service (QoS) including required Bit Error Rate (BER), required information bit rate, message's delay constraints as well as traffic performance should be taken into account. A wireless multi-media system should achieve a flexible balance of these differences. In this letter, an Adaptive Chip/Bit Control Method is proposed for Wireless Multi-media CDMA System. The proposed method controls both chip and bit rate of each medium according to the offered traffic condition and the quality measurement of each medium. In the proposed method, measurement are carried out in the base station. Simulation results show that the proposed method not only maintain the required BER of each medium, but achieve a higher total throughput even in high traffic condition. Thus we see that the proposed method possesses higher flexible ability than conventional methods.

This paper describes a new Artificial Neural Network (ANN), UNItary Decomposition ANN (UNIDANN), which can perform the unitary eigendecomposition of the synaptic weight matrix. It is shown both analytically and quantitatively that if the synaptic weight matrix is Hermitian positive definite, the neural output, based on the proposed dynamic equation, will converge to the principal eigenvectors of the synaptic weight matrix. Compared with previous works, the UNIDANN possesses several advantageous features such as low computation time and no synchronization problem due to the underlying analog circuit structure, faster convergence speed, accurate final results, and numerical stability. Some simulations with a particular emphasis on the applications to high resolution bearing estimation problems are also furnished to justify the proposed ANN.

This paper describes IDDQ testability for bridging faults in a variety of flip-flops. The flip-flop is a basic element of the sequential circuit and there are various structures even for the same type. In this paper, we use five kinds of master-slave D-type flip-flops as the circuit under test. Target faults are two-line resistive bridging faults extracted from a circuit layout. A flip-flop with a deliberately introduced bridging fault is simulated by the SPICE simulator. Simulation results show that IDDQ testing cannot detect faults existing at specific points in some flip-flops, and this problem depends on the flip-flop structure. However, IDDQ testing has high fault coverage ( 98%) compared with traditional logic testing. We also examine performances of fully IDDQ testable flip-flops.

Unequal error protection (UEP) is a very promising coding technique for satellite broadcasting, as it gradually reduces the transmission rate. From the viewpoint of bandwidth efficiency, UEP should be achieved in the context of multilevel coded modulation. However, the conventional mapping between encoded bits and modulation signals, usually realized for multilevel block modulation codes and multistage decoding, is not very compatible with UEP coding because of the large number of resulting nearest neighbor codewords. In this paper, new coded modulation schemes for UEP based on unconventional partitioning are proposed. A linear operation referred to as interlevel combination is introduced. This operation generalizes previous partitioning proposed for UEP applications and provides additional flexibility with respect to UEP capabilities. The error performance of the proposed codes are evaluated both by computer simulations and a theoretical analysis. The obtained results show that the proposed codes achieve good tradeoff between the proportion and the error performance of each error protection level.

In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It is proved that the Block Sorting algorithm is asymptotically optimal for stationary ergodic finite order Markov sources. Our proof is based on the facts that symbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burrows-Wheeler transform, and the codeword length of each group can be bounded by a function described with the frequencies of symbols included in the group.

Recently, Garcia and Stichtenoth proposed sequences of algebraic function fields with finite constant fields such that their sequences attain the Drinfeld-Vl bound. In the sequences, the third algebraic function fields are Artin-Schreier extensions of Hermitian function fields. On the other hand, Miura presented powerful tools to construct one-point algebraic geometric (AG) codes from algebraic function fields. In this paper, we clarify rational functions of the third algebraic function fields which correspond to generators of semigroup of nongaps at a specific place of degree one. Consequently, we show generator matrices of the one-point AG codes with respect to the third algebraic function fields for any dimension by using rational functions of monomial type and rational points.

In this paper, we study unequal error protection (UEP) capabilities of punctured convolutional codes. For constructing the good UEP convolutional codes, the conditional weight distributions of UEP convolutional codes are defined and evaluated. The conditional weight distributions are computed by using the transfer functions of time-varying trellis structures of punctured convolutional codes. The best UEP convolutional codes from the viewpoint of the weight distributions are listed.

This paper proposes and investigates a coding and decoding scheme to achieve adaptive unequal error protection (UEP) using several convolutional codes which have different error-correcting capabilities. An appropriate encoder is selected to unequally protect each frame of information sequence according to the importance of the frame. Since the supplemental information of selected encoder is not sent for the sake of reducing redundancy, we assume that the decoder does not know which encoder was used, and the decoder has to estimate the used encoder. In order to estimate which encoder was used, the method using biased metric in Viterbi decoding is proposed. In decoding, however, there is a problem of Decoder-Selection-Error (DSE), which is an error that the decoder selected in a receiver does not correspond to the encoder used in a transmitter. An upper bound of DSE rate in decoding is derived. The proposed decoding scheme using the biased metric in a trellis can improve DSE rate and BER performance, because transition probability of encoders is taken into account in calculating likelihood by means of making branch or path metric biased. Computer simulation is employed to evaluate the BER performance and DSE rate of the proposed scheme. The performance is compared with a conventional equal error protection scheme and a UEP with the supplemental information on the used encoder. It is found that the proposed scheme can achieve better performance than them in case N=2.

In this paper, we give lower bounds for the generalize Hamming weights of linear codes constructed on affine algebraic varieties. By introducing a number g*, which is determined by a given affine variety, we show that when the order t of generalized Hamming weights is greater than g*, the proposed lower bound agrees with their true generalize Hamming weights. Moreover, if we use the notion of well-behaving, we can obtain a more precise bound. Finally, we compare the proposed bound and the conventional one for algebraic geometric code on the curve Cab.