The problem of multi-user cooperation to achieve cooperative diversity for single-antenna terminals is considered. A cooperative strategy is proposed which divides multiple users into groups with each group having two users as partners. The two users alternately transmit their own information first, then simultaneously amplify and forward the partner's data in the same channel. Comparing to the conventional multi-user cooperation where the two users relay the partner's data in two orthogonal channels, the spectral efficiency of the proposed scheme is increased. However, as the two users relay the partner's data in the same channel, multi-user detection problem arises. An iterative detection making use of the new scheme's property is proposed in the presence of frequency offsets. The proposed scheme only requires time and frequency synchronization but no channel state information at the user terminals. To estimate the channel at the destination, a training scheme is proposed. The simulation results show that the proposed scheme can achieve the same cooperative diversity as the conventional scheme, while the spectral efficiency is lifted by 4/3.

As the size of large-scale computer systems increases, their mean-time-between-failures are becoming significantly shorter than the execution time of many current scientific applications. To complete the execution of scientific applications, they must tolerate hardware failures. Conventional rollback-recovery protocols redo the computation of the crashed process since the last checkpoint on a single processor. As a result, the recovery time of all protocols is no less than the time between the last checkpoint and the crash. In this paper, we propose a new application-level fault-tolerant approach for parallel applications called the fault-tolerant parallel algorithm (FTPA), which provides fast self-recovery. When fail-stop failures occur and are detected, all surviving processes recompute the workload of failed processes in parallel. FTPA, however, requires the user to be involved in fault tolerance. In order to ease the FTPA implementation, we developed get it fault-tolerant (GiFT), a source-to-source precompiler tool to automate the FTPA implementation. We evaluate the performance of FTPA with parallel matrix multiplication and five kernels of NAS Parallel Benchmarks on a cluster system with 1,024 CPUs. The experimental results show that the performance of FTPA is better than the performance of the traditional checkpointing approach.

Application-level checkpointing is a promising technology in the domain of large-scale scientific computing. The consistency of global checkpoint must be carefully guaranteed in order to correctly restore the computation. Usually, some complex coordinated protocols are employed to ensure the consistency of global checkpoint, which require logging orphan or in-transit messages during checkpointing. These protocols complicate the recovery of the computation and increase the checkpoint overhead due to logging message. In this paper, a new method which ensures the consistency of global checkpoint by static analysis is proposed. The method identifies the safe checkpointing regions in MPI programs, where the global checkpoint is always strongly consistent. All checkpoints are located in those safe checkpoint regions. During checkpointing, the method will not log any messages and introduce no extra overhead. The method was implemented and integrated into ALEC, which is a source-to-source precompiler for automating application-level checkpointing. The experimental results show that our method is effective.

Application-level checkpointing can decrease the overhead of fault tolerance by minimizing the amount of checkpoint data. However this technique requires the programmer to manually choose the critical data that should be saved. In this paper, we firstly propose a live-variable analysis method for MPI programs. Then, we provide an optimization method of data saving for application-level checkpointing based on the analysis method. Based on the theoretical foundation, we implement a source-to-source precompiler (ALEC) to automate application-level checkpointing. Finally, we evaluate the performance of five FORTRAN/MPI programs which are transformed and integrated checkpointing features by ALEC on a 512-CPU cluster system. The experimental results show that i) the application-level checkpointing based on live-variable analysis for MPI programs can efficiently reduce the amount of checkpoint data, thereby decrease the overhead of checkpoint and restart; ii) ALEC is capable of automating application-level checkpointing correctly and effectively.

Fault tolerance is a critical issue in the arena of large-scale computing. The fault-tolerant parallel algorithm (FTPA) is an application-level technique for tolerating hardware failures. FTPA achieves fast failure recovery making use of parallel recomputing. However, it complicates the coding of the application program. This paper uses compiler technology to automate the design of FTPA, and introduces the implementation of a tool called GiFT (Get it Fault-Tolerant). GiFT utilizes the extended data-flow analysis to choose the state needed by failure recovery, exploits the parallel recomputing time model to compute the optimal number of recomputing processes, and uses parallelization technologies to generate parallel recomputing codes. The experimental results show that original MPI programs can be transformed into the FTPA counterparts by GiFT correctly, and the performance of GiFT-generated FTPA programs is comparable to the performance of hand-modified FTPA programs.

This paper proposes an optimization method of data saving for application-level checkpointing based on the live-variable analysis method for MPI programs. We presents the implementation of a source-to-source precompiler (CAC) for automating applicationlevel checkpointing based on the optimization method. The experiment shows that CAC is capable of automating application-level checkpointing correctly and reducing checkpoint data effectively.

The problem of carrier and clock synchronization without a training sequence for a robust receiver working at low signal-to-noise (SNR) ratios is considered. Both short packet and long burst transmission scenarios are taken into account. A low-complexity iterative symbol timing and carrier synchronization algorithm making use of the extrinsic information from the soft- input soft-output (SISO) decoder is proposed. The non-data-aided (NDA) algorithms are used for initial synchronization. In order to solve the phase ambiguity problem inherent in the NDA phase synchronization algorithm, two SISO decoders denoted by I and Q decoders, respectively, along with a differential decoder are proposed. The simulation results show that the proposed iterative synchronizer and decoder can reach the ideal performance at very low SNR with an increased allowed residual frequency offset and [-pi,pi] phase uncertainty region.

We consider the problem of carrier frequency and phase synchronization at low SNR without a training sequence for short packet transmission. A low-complexity iterative joint symbol timing and carrier synchronization algorithm making use of the extrinsic information from the soft-input soft-output (SISO) decoder is proposed. The non-data-aided (NDA) algorithms are used for initial synchronization. The simulation results show that the frequency offset estimation is the most critical problem in low SNR region. The proposed low-complexity algorithm can reach the ideal performance with perfect synchronization in the absence of frequency offset at very low SNR. When the frequency offset exists, the proposed algorithm can work effectively and improve the performance significantly.

In this paper we propose a non-data aided estimator for joint time delay, carrier frequency offset (CFO) and channel estimation for uplink asynchronous CDMA system. The cost function for CFO estimation is a determinant of a matrix, which is a function of the CFO. The CFO estimator does the estimation by performing a linear search and the search point which minimizes the determinant is the estimated CFO. The matrix corresponding to the estimated CFO is used for channel estimation, where the channel impulse response (CIR) is obtained as the eigenvector corresponding to the minimum eigenvalue of that matrix. Time synchronization is inherently done along with the channel estimation, assuming the maximum channel order for all user channels is known. We also modify the existing estimator based on generalized eigenvalue problem (GEVP) and show the performance improvement through computer simulations. The performance of the proposed method is compared with the modified generalized eigenvalue problem method (MGEVPM). Computer simulations show that the proposed estimator performs better than MGEVPM and has wider CFO acquisition range than MGEVPM. Using Taylor's series approximation, we reformulate the proposed estimator in order to reduce the computational complexity. Through computer simulations we show that the performance of the reformulated estimator improves with increase in the order of Taylor's series and performs better than MGEVPM.

This paper addresses the problem of blindly estimating the carrier offset and channel response in the uplink of multi-user CDMA systems having large variation in carrier offset. Two blind subspace-based estimation methods, namely Exact Determinant Minimization Method (EDMM) and Approximate Determinant Minimization Method (ADMM) are proposed, which exploit the orthogonality between the signal and noise subspaces. The performance of the proposed methods is compared with the available solution using Generalized Eigenvalue Problem Method (GEVPM). Simulation results are given to show that the proposed methods give better performance than the GEVPM and have a wider acquisition range for the carrier offset.

In this paper, we introduce a novel sampling offset estimation scheme based on iterative two-dimensional estimation principle for Multi-band Orthogonal Frequency Division Multiplexing (MB-OFDM) system. The proposed scheme estimates the sampling frequency offset through the phase distortion of pilot sub-carriers in each OFDM symbol and improves the accuracy by averaging the estimate from each pilot sub-carrier across both the sub-carrier dimension and the symbol dimension. Through analysis and simulation, we show that the proposed scheme is superior to existing schemes in minimizing the performance degradation due to sampling frequency offset in MB-OFDM system effectively, especially in long packet transmission.

A semiblind method for channel estimation in multiple-input multiple-output (MlMO) orthogonal frequency-division multiplexing (OFDM) systems is proposed. The MIMO-OFDM channel matrix is first estimated blindly up to an ambiguity matrix using the subspace identification algorithm based on the second-order statistics of the channel outputs. The ambiguity matrix is then estimated using a few training symbols. It shows that the number of training symbols required by the proposed semiblind method is significantly less than that used in the training sequence based channel estimation algorithm. The simulation results demonstrate the effectiveness of the proposed algorithm.

An asynchronous multicode multicarrier code-division multiple-access (CDMA) scheme for the uplink of wireless communication systems is considered in order to support multimedia services. The uncoded bit error rate of the system is analyzed after taking account of the intercarrier interference due to time-varying fading channels, inter-code interference due to the multicode assignment, and multiple access interference. Numerical results indicate that the system performance is improved with increasing the number of parallel data substreams and the processing gain. The two parameters have to be sufficiently large for supporting multimedia services.

A simplified iterative detector and decoder (IDD) through pre-hard-decision (preHD) is proposed in the serial-concatenated coded and pre-transformed single-carrier system over flat Rayleigh fading channel. For the first iteration, the preHD is done by linear least squares (LS) or minimum mean-squared error (MMSE) detection, and a Chase-like symbol reliability calculation method is designed to select the preHD symbols. For the following iterations, the symbol soft information from SISO decoder is used for preHD. It is shown that the complexity of combined preHD and detection declines exponentially with the number of preHD symbols. Moreover, the performance degradation of simplified IDD is marginal when the pre-transformation size is large and the number of preHD symbols is small.

We investigate the problem of CDMA multiuser detection in the presence of a small residual carrier offset. We propose, in particular, a method based on the generalized eigenvalue problem for efficiently estimating the channel response and the carrier offset. A closed-form solution is obtained without any knowledge of the transmitted symbols. Simulation results are given to verify the validity of the proposed method. It is shown that the proposed method can achieve a similar or better performance but with a reduced computational complexity as compared to a previous algorithm which uses a polynomial matrix projection property.

The problem of CDMA multiuser detection in the presence of a small residual carrier is considered in this paper. Subspace-based approaches are employed for channel estimation and signal demodulation. The channel response and carrier offset are estimated separately in order to avoid the computational complexity of joint estimation of two parameters. The simulation results show that the separate estimation approach results in lower BER than a previous subspace-based joint estimation algorithm does for a large range of carrier offsets which are generally considered in practical applications. Adaptive channel estimation in a time-variant channel is also considered. A novel adaptive algorithm for subspace estimation, namely the normalized orthogonal Oja (NOOja) algorithm, is used to track the channel variations with time. The NOOja algorithm is applicable for both signal and noise subspace tracking and offers advantages of better orthogonality and numerical stability than previous tracking algorithms without any significant increase in computational complexity. It is shown that the NOOja algorithm exhibits good tracking performance in a time-variant channel.

The system capacity determined by the outage probability of a multi-beam LEO system with CDMA and FDMA/TDMA is analyzed. In the case of CDMA, all possible multiple access interference is taken into account by a comprehensive interference analysis model including the effects of channel fading and shadowing, power control, practical spot beam antenna gains and imperfect equalization of the antenna pattern across a cell region. The results indicate that in LEO systems the CDMA capacity is significantly reduced because of the power control imperfections and the fact that multiple access interference is much more severe than that in terrestrial systems. A comparison with FDMA/TDMA shows that the capacity of an FDMA/TDMA system is comparable to a CDMA one for the LEO satellite systems.

Bit error probability of a CDMA-based multispot beam LEO system with imperfect power control over Rice-lognormal channels is calculated in this paper. The power control error is assumed to be a lognormal random variable. In the model, the multiple access interference due to all users seen by the serving satellite of the user-of-interest is taken into account, which is more realistic and differs from other reported work (Monk and Milstein 1995; Vojcic et al., 1994) in which only part of all possible interference was considered. The numerical results show that the power control error has a significant effect on the system performance.