Active replication is a common approach to building highly available and reliable distributed software applications. The redundant nested invocation (RNI) problem arises when servers in a replicated group issues nested invocations to other server groups in response to a client invocation. Automatic suppression of RNI is always a desirable solution, yet it is usually a difficult design issue. If the system has multithreading support, the difficulties of implementation increase dramatically. Intuitively, to design a deterministic thread execution control mechanism is a possible approach. Unfortunately, some modern operating systems implement thread on kernel level for execution fairness. For the kernel thread case, modification on thread control implies modifying the operating system kernel. This approach loses system portability which is one of the important requirements of CORBA or middleware. In this work, we propose a mechanism to perform the auto-suppression of redundant nested invocation in an active replication fault-tolerant (FT) CORBA system. Besides the mechanism design, we discuss the design correctness semantic and the correctness proof of our design.

In this article, it is shown that Unified Complex Hadamard Transform (UCHT) can be derived from Walsh functions and through direct matrix operation. Unique properties of UCHT are analyzed. Recursive relations through Kronecker product can be applied to the basic matrices to obtain higher dimensions. These relations are the basis for the flow diagram of a constant-geometry iterative VLSI hardware architecture. New Normalized Complex Hadamard Transform (NCHT) matrices are introduced which are another class of complex Hadamard matrices. Relations of UCHT and NCHT with other discrete transforms are discussed.

We propose a new algorithm for overdetermined blind source separation (BSS) based on multistage independent component analysis (MSICA). To improve the separation performance, we have proposed MSICA in which frequency-domain ICA and time-domain ICA are cascaded. In the original MSICA, the specific mixing model, where the number of microphones is equal to that of sources, was assumed. However, additional microphones are required to achieve an improved separation performance under reverberant environments. This leads to alternative problems, e.g., a complication of the permutation problem. In order to solve them, we propose a new extended MSICA using subarray processing, where the number of microphones and that of sources are set to be the same in every subarray. The experimental results obtained under the real environment reveal that the separation performance of the proposed MSICA is improved as the number of microphones is increased.

In this paper, we present a group communication protocol that achieves total ordering message delivery for mobile computing systems with multiple overlapping groups. Our mechanism is an efficient adaptation of the propagation-tree technique to the mobile computing environments. It takes advantages of the capability of stationary mobile support stations to overcome the deficiencies associated with mobile devices. We construct the propagation tree based on the stationary stations, rather than the mobile hosts. As a result, mobile hosts are relieved of the excessive load of forwarding messages and communications on wireless channels are confined to transmitting messages to destination processes. This is important considering that the bandwidth of the wireless channels is limited. Moreover, the proposed protocol employs a mechanism to synchronize transmissions within a wireless cell. This serves to avoid redundant transmissions of a message in a wireless network in an attempt to achieve better utilization of the network bandwidth. Our mechanism relies on a handoff operation to deal with mobility of mobile devices. The handoff procedure ensures a smooth integration of a mobile host into a new cell, while preserving reliability of communication and the total ordering property of message delivery.

Design points and the results seen in the development of a dynamically reconfigurable logic LSI, PCA-2, are described. PCA-2 enables the realization of flexible parallel processing based on the autonomous reconfiguration of logic circuits. To realize this feature, we introduce an asynchronous circuit design and a homogeneous cell array structure. PCA-2 represents an advance on the earlier LSI, PCA-1. Cutting edge CMOS technology is used to realize the structural merits of PCA hardware. Compared to PCA-1, PCA-2 offers 16 times greater integration level for programmable logic. Due to miniaturization and design refinement, PCA-2 provides a 6-fold increase in the circuit frequency of the configuration controller and a 3-fold increase in the operating frequency of the programmable logic. The results gained confirm the effects of refinement and the suitability of our architecture for device miniaturization.

This paper deals with a design problem of an adaptive robust control system for linear systems with structured uncertainties. The control law consists of a state feedback with a fixed gain designed by using the nominal system, a state feedback with an adaptive gain tuned by a parameter adjustment law and a compensation input. We show the parameter adjustment law and that sufficient conditions for the existence of the compensation input are given in terms of linear matrix inequalities (LMIs). Finally, a numerical example is included.

The AMR wideband speech codec was recently developed for high-quality wideband speech communications. Although it has an excellent performance due to expanded bandwidth of speech signal, it requires a huge amount of computation especially in codebook search. To solve this problem, this paper proposes an efficient codebook search method for AMR wideband codec. Starting from a poorly performing initial codevector, the proposed method enhances the performance of the codevector iteratively by exchanging the worst pulse in the codevector with a better one after evaluating the role of each pulse. Simulations show that the AMR wideband codec adopting the proposed codebook search method provides better performance with much less computational load than that using the standard method.

This paper describes a real-time blind source separation (BSS) method for moving speech signals in a room. Our method employs frequency domain independent component analysis (ICA) using a blockwise batch algorithm in the first stage, and the separated signals are refined by postprocessing using crosstalk component estimation and non-stationary spectral subtraction in the second stage. The blockwise batch algorithm achieves better performance than an online algorithm when sources are fixed, and the postprocessing compensates for performance degradation caused by source movement. Experimental results using speech signals recorded in a real room show that the proposed method realizes robust real-time separation for moving sources. Our method is implemented on a standard PC and works in realtime.

We newly propose a novel blind separation framework for Single-Input Multiple-Output (SIMO)-model-based acoustic signals using an extended ICA algorithm, SIMO-ICA. The SIMO-ICA consists of multiple ICAs and a fidelity controller, and each ICA runs in parallel under the fidelity control of the entire separation system. The SIMO-ICA can separate the mixed signals, not into monaural source signals but into SIMO-model-based signals from independent sources as they are at the microphones. Thus, the separated signals of SIMO-ICA can maintain the spatial qualities of each sound source. In order to evaluate its effectiveness, separation experiments are carried out under both nonreverberant and reverberant conditions. The experimental results reveal that the signal separation performance of the proposed SIMO-ICA is the same as that of the conventional ICA-based method, and that the spatial quality of the separated sound in SIMO-ICA is remarkably superior to that of the conventional method, particularly for the fidelity of the sound reproduction.

Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.

Motion estimation is the key issue in video compressing. Several methods for motion estimation based on the center biased strategy and minimum mean square error trend searching have been proposed, such as TSS, FSS, UCBDS and MIBAS, but these methods yield poor estimates or find local minima. Many other methods predict the starting point for the estimation; such methods include PMEA, PSA and GPS: these can be fast but are inaccurate. This study addresses the causes of wrong estimates, local minima and incorrect predictions in the prior estimation methods. The Multiple Searching Trend (MST) is proposed to overcome the problems of ineffective searches and local minima, and the Adaptive Dilated Searching Field (ADSF) is described to prevent prediction from wrong location. Applying MST and ADSF to the listed estimating methods, such as UCBDS, a fast and accurate can be reached. For this this reason, the method is called CockTail Searching (CTS).

Fault-tolerance is an essential feature of the distributed systems where the possibility of a failure increases with the growth of the system. In spite of extensive researches over two decades, fault-tolerance systems have not succeeded in practical use. It is due to the high overhead and the unhandiness of the previous fault-tolerance systems. In this paper, we propose MPICH-GF, a user-transparent checkpointing system for grid-enabled MPICH. Our objectives are to fill the gap between the theory and the practice of fault-tolerance systems, and to provide a checkpointing-recovery system for grids. To build a fault-tolerant MPICH version, we have designed task migration, dynamic process management, and atomic message transfer. MPICH-GF requires no modification of application source codes, and it affects the MPICH communication characteristics as less as possible. The features of MPICH-GF are that it supports the direct message transfer mode and that all of the implementation has been done at the lower layer, that is, the abstract device level. We have evaluated MPICH-GF using NPB applications on Globus middleware.

We have developed a novel basic technology for terahertz (THz) imaging, which allows detection and identification of chemicals by introducing the component spatial pattern analysis. The spatial distributions of the chemicals were obtained from terahertz multispectral transillumination images, using absorption spectra previously measured with a widely tunable THz-wave parametric oscillator. We have also separated the component spatial patterns of frequency-dependent absorptions in chemicals and frequency-independent components such as plastic, paper and measurement noise in THz spectroscopic images. Further we have applied this technique to the detection and identification of illicit drugs concealed in envelopes.

Traditional Web cache servers based on HTTP and ICP infrastructure tend to have higher hardware and management cost, have difficulty in availability, automatic and dynamic reconfiguration, and may have slow links to some users. We find that peer-to-peer technology can help solve these problems. The peer cache service (PCS) we proposed here leverages each peer's local cache, similar access patterns, fully distributed coordination, and fast communication channels to enhance response time, scale of cacheable objects, and availability. Moreover, incorporating goals and strategies such as making the protocol lightweight and mutually compatible with existing cache infrastructure, supporting mobile devices, undertaking dynamic three-level caching, and exchanging cache meta-information further improve the effectiveness and differentiate our work from other similar-at-first-glance P2P Web cache systems.

Cluster computation has been used in the applications that demand performance, reliability, and availability, such as cluster server groups, large-scale scientific computations, distributed databases, distributed media-on-demand servers and search engines etc. In those applications, multicast can play the vital roles for the information dissemination among groups of servers and users. This paper proposes a set of novel efficient fault-tolerant multicast routing algorithms on hypercube interconnection of cluster computers using multicast shared tree approach. We present some new algorithms for selecting an optimal core (root) and constructing the shared tree so as to minimize the average delay for multicast messages. Simulation results indicate that our algorithms are efficient in the senses of short end-to-end average delay, load balance and less resource utilizations over hypercube cluster interconnection networks.

In a Distributed Computing Systems (DCS) tasks submitted to it, are usually partitioned into different modules and these modules may be allocated to different processing nodes so as to achieve minimum turn around time of the tasks utilizing the maximum resources of the existing system such as CPU speed, memory capacities etc. The problem lies on how to obtain the optimal allocation of these multiple tasks by keeping in mind that no processing node is overloaded due to this allocation. This paper proposes an algorithm A*RS, using well-known A*, which aims to reduce the search space and time for task allocation. It aims at minimization of turn around time of tasks in the way so that processing nodes do not become overloaded due to this allocation. Our experimental results justify the claims with necessary supports by comparing it with the earlier algorithm for multiple tasks allocation.

Graph data in large scientific/engineering applications are often too massive to fit inside the computer's main memory. The resulting input/output (I/O) costs could be a major performance bottleneck. This paper proposes an extension to extant multilevel graph partitioning algorithms with improved I/O-efficiency. The input graph is envisioned as the union of disjoint blocks (subgraphs) of almost the same size. Each block is coarsened in turn. Recursive matching and contraction are the operations in this phase. All the coarsened blocks are then merged in an iterative manner in order to ensure that the resulting graph fits in the main memory. This graph is then treated with an in-core multilevel graph partitioning algorithm in the usual way. Our experimental results show that the larger graph size is, the more dependent on the I/O-efficiency the performance is. And our modification can easily partition very large graphs. It also exhibits considerable improvement in I/O-complexity.

This paper shows how to use sticker to construct solution space of DNA for the library sequences in the set-packing problem and the clique problem. Then, with biological operations, we propose DNA-based algorithms to remove illegal solutions and to find legal solutions for the set-packing and clique problems from the solution space of sticker. Any NP-complete problem in Cook's Theorem can be reduced and solved by the proposed DNA-based computing approach if its size is equal to or less than that of the set-packing problem. Otherwise, Cook's Theorem is incorrect on DNA-based computing and a new DNA algorithm should be developed from the characteristics of the NP-complete problem. Finally, the result to DNA simulation is given.

Techniques for automatic program recognition, at the algorithmic level, could be of high interest for the area of Software Maintenance, in particular for knowledge based reengineering, because the selection of suitable restructuring strategies is mainly driven by algorithmic features of the code. In this paper an automated hierarchical concept parsing recognition technique, and a formalism for the specification of algorithmic concepts, is presented. Based on this technique, the design and development of ALCOR, a production rule based system for automatic recognition of algorithmic concepts within programs, aimed at support of knowledge based reengineering for high performance, is presented.

The sizes of recent Java-based server-side applications, like J2EE containers, have been increasing continuously. Past techniques for improving the performance of Java applications have targeted relatively small applications. Moreover, when the methods of these small target applications are invoked, they are not usually distributed over the entire memory space. As a result, these techniques cannot be applied efficiently to improve the performance of current large applications. We propose a dynamic code repositioning approach to improve the hit rates of instruction caches and translation look-aside buffers. Profiles of method invocations are collected when the application performs with its heaviest processor load, and the code is repositioned based on these profiles. We also discuss a method-splitting technique to significantly reduce the sizes of methods. Our evaluation of a prototype implementing these techniques indicated 5% improvement in the throughput of the application.