This paper describes the architecture of ReVolver/C40 a scalable parallel machine for volume rendering and its prototype implementation. The most important feature of ReVolver/C40 is view-independent real time rendering of translucent 3D object by using perspective projection. In order to realize this feature, the authors propose a parallel volume memory architecture based on the principal axis oriented sampling method and parallel treble volume memory. This paper also discusses the implementation issues of ReVolver/C40 where various kinds of parallelism extracted to achieve high-perfromance rendering are explained. The prototype systems had been developed and their performance evaluation results are explained. As the results of the evaluation of the prototype systems, ReVolver/C40 with 32 parallel volume memory is estimated to achieve more than 10 frame per second for 2563 volume data on 2562 screen by using perspective projection. The authors also review the development of ReVolver/C40 from several view points.

Given the importance of the traffic on modern communication networks, advanced error correction methods are needed to overcome the changes expected in channel quality. Conventional countermeasures that use high dimensionality parity codes often fail to provide sufficient error correction capability. We propose a parity code with high dimensionality that is iteratively decoded. It provides better error correcting capability than conventional decoding methods. The proposal uses the steepest descent method to increase code bit reliability and the coherency between parities and code bits gradually. Furthermore, the quantization of the decoding algorithm is discussed. It is found that decoding with quantization can keep the error correcting capability high.

In an optical time domain reflectometer type strain measurement system, we theoretically derive the shape of the Brillouin gain spectrum produced in an optical fiber under a parabolic strain distribution which is formed in a uniformly loaded beam. Based on the derived result, we investigate the effects of the parabolic strain distribution parameters and the measurement conditions such as the launched pulse width and the measurement position on the beam on the deformation of the Brillouin backscattered-light power spectrum shape. In addition, we investigate the strain measurement error resulting from the deformation of the power spectrum shape by analyzing the peak-power frequency at which the power spectrum is maximized.

This paper assesses the media synchronization quality of recovery control schemes from asynchrony, which are referred to as reactive control schemes here, in terms of objective and subjective measures. We deal with four reactive control techniques: skipping, discarding, shortening and extension of output duration, and virtual-time contraction and expansion. We have carried out subjective and objective assessment of the media synchronization quality of nine schemes which consist of combinations of the four techniques. The paper makes a comparison of media synchronization quality among the schemes. It also clarifies the relations between the two kinds of quality measures.

As a lot of programs and contents such as movie files are being delivered via the Internet, and copies are often stored in distributed servers in order to reduce the load on the original servers, to ease network congestion, and to decrease response time. To retrieve an object file, existing methods simply select one or more servers. Such methods divide a file into equal pieces whose size is determined a priori. This approach is not practical for networks that offer variable bandwidth. In order to more utilize variable bandwidth, we propose an adaptive downloading method. We evaluate it by experiments conducted on the Internet. The results show that the new method is effective and that it will become an important network control technology for assurance.

The center problem of a graph is motivated by a number of facility location problems. In this paper, we propose parallel algorithms for finding the center of interval graphs and circular-arc graphs. Our algorithms run in O(log n) time algorithm using O(n/log n) processors while the intervals and arcs are given in sorted order. Our algorithms are on the EREW PRAM model.

Space-time transmit diversity (STTD) and space-time block coding (STBC) are attractive techniques for high bit-rate and high capacity transmission. The concatenation scheme of turbo codes and STBC (Turbo-STBC) was proposed and it has been shown that the Turbo-STBC can achieve the good error rate performance. Recently, low-density parity-check (LDPC) codes have attracted much attention as the good error correcting codes achieving the near Shannon limit performance like turbo codes. The decoding algorithm of LDPC codes has less complexity than that of turbo codes. Furthermore, when the block length is large, the error rate performance of the LDPC codes is better than that of the turbo codes with almost identical code rate and block length. In this letter, we propose a concatenation scheme of LDPC codes and STBC. We refer to it as the LDPC-STBC. We evaluate the error rate performance of the LDPC-STBC by the computer simulation and show that the error rate performance of the LDPC-STBC is almost identical to or better than that of the Turbo-STBC in a flat Rayleigh fading channel.

Software rejuvenation is a proactive fault management technique that has been extensively studied in the recent literature. In this paper, we focus on an example for a telecommunication billing application considered in Huang et al. (1995) and develop the discrete-time stochastic models to estimate the optimal software rejuvenation schedule. More precisely, two software availability models with rejuvenation are formulated via the discrete semi-Markov processes, and the optimal software rejuvenation schedules which maximize the steady-state availabilities are derived analytically. Further, we develop statistically non-parametric algorithms to estimate the optimal software rejuvenation schedules, provided that the complete sample data of failure times are given. Then, a new statistical device, called the discrete total time on test statistics, is introduced. Finally, we examine asymptotic properties for the statistical estimation algorithms proposed in this paper through a simulation experiment.

Richardson and Urbanke developed a powerful method density evolution which determines, for various channels, the capacity of irregular low-density parity-check code ensembles. We develop generalized density evolution for minutely represented ensembles and show it includes conventional representation as a special case. Furthermore, we present an example of code ensembles used over binary erasure channel and binary input additive white Gaussian noise channel which have better thresholds than highly optimized ensembles with conventional representation.

Ranking fuzzy numbers is one of very important research topics in fuzzy set theory because it is a base of decision-making in applications. However, fuzzy numbers may not be easily ordered into one sequence according to their magnitudes because they represent uncertain values. When two fuzzy numbers overlap with each other, a fuzzy number may not be considered absolutely larger than the other. That is, even when a fuzzy number may be considered larger than the other, it may also be considered smaller than the other. It means that for a given set of fuzzy numbers, several ranking sequences possibly exist. However, most of the existing ranking methods produce only one ranking sequence. They ignore other possible sequences due to the overlap between fuzzy numbers. We propose a ranking method which generates possible ranking sequences of given fuzzy numbers. Our method takes a viewpoint from users, and uses it for evaluation of fuzzy numbers. Fuzzy numbers will be ranked based on the evaluations and a fuzzy set of sequences of fuzzy numbers will be produced as a ranking results. Numeric examples and comparisons with other methods are also presented.

This paper presents a novel data placement and retrieval scheme for video-on-demand systems. In particular, a zone-based data placement scheme is employed to reduce the average seek time of the disk array storage system and thus increase the disk access bandwidth to allow the video server provide more services of video programs concurrently. Furthermore, due to the inherent nature of video access, a popular program always requires more accesses and therefore occupies more disk I/O bandwidth as request for serving such program increases. A new retrieval strategy is proposed to maintain a single copy of each video program disregarding the popularity of the video programs, and to achieve maximum I/O throughput of the video server.

The Earth Simulator (ES), developed by the Japanese government's initiative "Earth Simulator project," is a highly parallel vector supercomputer system. In May 2002, the ES was proven to be the most powerful computer in the world by achieving 35.86 teraflops on the LINPACK benchmark and 26.58 teraflops for a global atmospheric circulation model with the spectral method. Three architectural features enabled these great achievements; vector processor, shared-memory and high-bandwidth non-blocking interconnection crossbar network. In this paper, an overview of the ES, the three architectural features and the result of performance evaluation are described particularly with its hardware realization of the interconnection among 640 processor nodes.

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

A low complexity multi-user receiver with blind channel estimation and multiple access interference (MAI) suppression is proposed for a CDMA system under multipath fading and frequency offset. The design of the receiver involves the following procedure. First, a method of joint MAI suppression and channel estimation is developed based on the generalized sidelobe canceller (GSC) technique. In particular, channel estimates are obtained blindly in the form of the effective composite signature vectors (CSV) of the users. Second, a low-complexity partially adaptive (PA) realization of the receiver is proposed which incorporates reduced-rank processing based on the information of multi-user CSV's. By a judiciously designed decorrelating procedure, a new PA receiver is obtained with a much lower complexity. Finally, pilot symbols assisted frequency offset estimation and channel gain compensation give the estimate of users' symbols. Further performance enhancement is achieved by a decision aided scheme in which the signal is reconstructed and subtracted from the receiver input data, leading to significantly faster convergence. The proposed receiver is shown to be robust to multipath fading and frequency offset, and achieves nearly the same performance of the optimal maximum SINR and MMSE receivers with a much lower overhead for pilot symbols.

The objective of this study was to explore suitable spatial filters for inverse estimation of cortical potentials from the scalp electroencephalogram. The effect of incorporating noise covariance into inverse procedures was examined by computer simulations. The parametric projection filter, which allows inverse estimation with the presence of information on the noise covariance, was applied to an inhomogeneous three-concentric-sphere model under various noise conditions in order to estimate the cortical potentials from the scalp potentials. The present simulation results suggest that incorporation of information on the noise covariance allows better estimation of cortical potentials, than inverse solutions without knowledge about the noise covariance, when the correlation between the signal and noise is low. The method for determining the optimum regularization parameter, which can be applied for parametric inverse techniques, is also discussed.

This letter investigates the peak-to-average power ratio (PAR) reduction scheme employing a simple symbol transform in OFDM-CDMA systems. This approach is very simple because of no additional complexity and works with arbitrary numbers of subcarriers and without restriction on the allocation of spreading code, maintaining an original transmission efficiency. Simulation results show that the investigated scheme gives the PAR reduction gain of 2-3 dB compared to the original OFDM and OFDM-CDMA signals, and can provide the further PAR reduction by combing the partial transmit sequence (PTS) scheme, which is less complex compared to the ordinary PTS approach.

Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.

Within a few years it will be possible to integrate a billion transistors on a single chip operating at frequency more than 10 GHz. At this integration level, we propose using a multi-level ISA to express fine-grain data parallelism to hardware instead of using a huge transistor budget to dynamically extract it. Since the fundamental data structures for a wide variety of data parallel applications are scalar, vector, and matrix, our proposed Trident processor extends a scalar ISA with vector and matrix instruction sets to effectively process matrix formulated applications. Like vector architectures, the Trident processor consists of a set of parallel lanes (each lane contains a set of vector pipelines and a slice of register file) combined with a fast scalar core. However, Trident processor can effectively process on the parallel lanes not only vector but also matrix data. One key point of our architecture is the local communication within and across lanes to overcome the limitations of the future VLSI technology. Another key point is the effective execution of a mixture of scalar, vector, and matrix operations. This paper describes the architecture of the Trident processor and evaluates its performance on BLAS and on the standard matrix bidiagonalization algorithm. The last one is evaluated as an example of an entire application based on a mixture of scalar, vector, and matrix operations. Our results show that many data parallel applications, such as scientific, engineering, multimedia, etc., can be speeded up on the Trident processor. Besides, the scalability of the Trident processor does not require more fetch, decode, or issue bandwidth, but requires only replication of parallel lanes.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.

In this paper, we propose an answer seeking algorithm for question answering that integrates structural matching and paraphrasing, and report the results of our empirical evaluation conducted with the aim of examining effects of incorporating those two components. According to the results, the contribution of structural matching and paraphrasing was not so large as expected. Based on error analysis, we conclude that structural matching-based approaches to answer seeking require technologies for (a) coreference resolution, (b) processing of parse forests instead of parse trees, and (c) large-scale acquisition of paraphrase patterns.