The understanding of instruction set usage in typical DOS/Windows applications plays a very important role in designing high performance x86 compatible microprocessors. This paper presents the tools to such analysis, the analysis results, and their implications on the design of a RISC-based superscalar processor for efficient x86 instruction execution. The analyzed results are used to optimize the execution of frequently executed instructions and micro operations.

Semistructured data comprises irregular structure and has no a-priori database schema, therefore we encounter several problems such as inefficient data retrieval and wasteful data storage. To cope with such problems, some schema extraction algorithms over semistructured data have been proposed, in which data is modeled as an unordered tree. However, the order of elements is indispensable for document data, therefore we consider extracting an optimal database schema over an ordered tree. We consider an optimization problem to extract a smallest database schema such that the density of each class is no less than a given threshold, where the density of a class represents a similarity between the type of the class and those of the objects in the class. We first prove that the corresponding decision problem is strongly NP-complete, and show that another version of the problem is strongly NP-hard and belongs to Δ₂ P. Then we show that for any r < 3/2, there is no polynomial-time r-approximation algorithm that solves the optimization problem unless P = NP. Finally, we propose a kind of class called bounded class that can be constructed efficiently, then show a polynomial-time algorithm for constructing a database schema by using bounded classes.

We propose a new effective method of managing flash memory space for flash memory-specific file systems based on a log-structured file system. Flash memory has attractive features such as non-volatility and fast I/O speed, but it also suffers from inability to update in situ and from limited usage (erase) cycles. These drawbacks necessitate a number of changes to conventional storage (file) management techniques. Our focus is on lowering cleaning cost and evenly utilizing flash memory cells while maintaining a balance between these two often-conflicting goals. The proposed cleaning method performs well especially when storage utilization and the degree of locality are high. The cleaning efficiency is enhanced by dynamically separating cold data and non-cold data, which is called 'collection operation.' The second goal, that of cycle-leveling, is achieved to the degree that the maximum difference between erase cycles is below the error range of the hardware. Experimental results show that the proposed technique provides sufficient performance for reliable flash storage systems.

This paper presents a formal verification method based on logic simulation. In our method, some restricted class of circuits which include data paths can be verified without abstraction of data paths by using symbolic values. Our verifier extracts a transition relation from the state graph (given as a specification) which is expressed using symbolic values, and verifies based on simulation using those symbolic values if the circuit behaves correctly with respect to each transition of the specification. If the verifier terminates with "correct," then it can be guaranteed that for any applicable input vector sequence, the circuit and the specification behaves identically. We have implemented the proposed method on a Unix workstation and verified some FIFO and LIFO circuits by using it.

This paper introduces the concept of hierarchical testability of data paths for delay faults. A definition of hierarchically two-pattern testable (HTPT) data path is developed. Also, a design for testability (DFT) method is presented to augment a data path to become an HTPT one. The DFT method incorporates a graph-based analysis of an HTPT data path and makes use of some graph algorithms. The proposed method can provide similar advantages to the enhanced scan approach at a much lower hardware overhead cost.

This paper presents a child verb learning model mainly based on syntactic bootstrapping. The model automatically learns 4-5-year-old children's linguistic knowledge of verbs, including subcategorization frames and thematic roles, using a text in dialogue format. Subcategorization frame acquisition of verbs is guided by the assumption of the existence of nine verb prototypes. These verb prototypes are extracted based on syntactic bootstrapping and some psycholinguistic studies. Thematic roles are assigned by syntactic bootstrapping and other psycholinguistic hypotheses. The experiments are performed on the data from the CHILDES database. The results show that the learning model successfully acquires linguistic knowledge of verbs and also suggest that psycholinguistic studies of child verb learning may provide important hints for linguistic knowledge acquisition in natural language processing (NLP).

This paper describes a method for hands-free speech recognition, and particularly for the simultaneous recognition of multiple sound sources. The method is based on the 3-D Viterbi search, i.e., extended to the 3-D N-best search method enabling the recognition of multiple sound sources. The baseline system integrates two existing technologies--3-D Viterbi search and conventional N-best search--into a complete system. Previously, the first evaluation of the 3-D N-best search-based system showed that new ideas are necessary to develop a system for the simultaneous recognition of multiple sound sources. It found two factors that play important roles in the performance of the system, namely the different likelihood ranges of the sound sources and the direction-based separation of the hypotheses. In order to solve these problems, we implemented a likelihood normalization and a path distance-based clustering technique into the baseline 3-D N-best search-based system. The performance of our system was evaluated through experiments on simulated data for the case of two talkers. The experiments showed significant improvements by implementing the above two techniques. The best results were obtained by implementing the two techniques and using a microphone array composed of 32 channels. More specifically, the Word Accuracy for the two talkers was higher than 80% and the Simultaneous Word Accuracy (where both sources are correctly recognized simultaneously) was higher than 70%, which are very promising results.

In this paper, we propose a simplified transform-based and variable-rate vocoder, which is evolved from the code-excited linear prediction (CELP) coding structure. With pre-emphasis and de-emphasis filters, the transformed-based CELP vocoder incorporates a long-term predictor, a discrete cosine transform (DCT), and pre-filters and postfilters for achieving perceptually weighted quantization. The proposed transform-based vocoder requires less computational complexity with slightly worse quality than the CELP coders. Furthermore, the proposed DCT-based coding structure easily figured with additional DCT coefficients could simultaneously offer low, middle, and high bit rates to adapt the variation of bandwidth for modern Internet or wireless communications.

An efficient algorithm is proposed for the adaptive sizing of a tracking window in correlation-based video tracking. Since a tracking window specifies a support region when estimating a target displacement, the ability to adapt the window size relative to a moving target significantly influences the performance of video tracking. The basic strategy of the proposed algorithm is to maintain the occupancy rate of the target in the tracking window within a specified range. As such, the proposed algorithm measures the occupancy rate using the ratio of the power of the spatial gradients in the edge subwindows, which edge the tracking window, to that in the tracking window. In addition, the level of any complex background and additive white noise is also evaluated to reduce their effect on the gradients. Experimental results using various artificial and real sequences confirm that the proposed algorithm can effectively adjust a tracking window to a moving target and is robust to a complex background and noise.

Double Cross Cylinder (DCC) is an object created by intersecting the cylinder of Y-axis and the cylinder of the Z-axis. DCC mapping is a new method for effectively mapping the environment. This method eliminates the singularity effect caused in the environment maps and shows an almost even amount of area for the environment occupied by a single texel. The surrounding environment can also be stored more effectively through more accurate sampling. Improvement is also achieved in the rendering time of the DCC mapping method and octahedral mapping method based on DCC mapping. Therefore, the DCC mapping method is suitable to be applied on environment navigation systems due to its effective storage of the environment and faster sampling time.

To estimate inner multi-layer tissue conductivity distribution in a cross section of the local tissue by using bioresistance data measured noninvasively on the surface of the tissue, a measurement method using divided electrodes is proposed, where a current electrode is divided into several parts. The method is evaluated by computer simulations using a three-dimension (3D) model and two two-dimension (2D) models. In this paper, conductivity distributions of the simplified (2D) model are analyzed based on a combination of a finite difference method (FDM) and a steepest descent method (SDM). Simulation results show that conductivity values for skin, fat and muscle layers can be estimated with an error less than 0.1%. Even though different strength random noise is added to measured resistance values, the conductivities are estimated with reasonable precise, e.g., the average error is about 4.25% for 10% noise. The configuration of the divided electrodes are examined in terms of dividing pattern and the size of surrounding guard electrodes to confine and control the input currents from the divided electrodes within a cross sectional area in the tissue.

In this letter, we consider one-to-all broadcast on distributed memory parallel computers based on message-passing, such as cluster of WSs or PCs. We present an efficient broadcast algorithm, called overlapped-two-phase broadcast (O2PB), that is an enhanced version of two-phase broadcast (2PB). The O2PB algorithm is compared with other algorithms, such as linear broadcast, tree broadcast and 2PB algorithms. According to our theoretical and experimental results, when the size of message to be broadcasted is large, the O2PB algorithm is fastest among all the algorithms. The O2PB algorithm is approximately 20% faster than the 2PB algorithm.

This paper discusses a new type of semi-supervised document clustering that uses partial supervision to partition a large set of documents. Most clustering methods organizes documents into groups based only on similarity measures. In this paper, we attempt to isolate more semantically coherent clusters by employing the domain-specific knowledge provided by a document analyst. By using external human knowledge to guide the clustering mechanism with some flexibility when creating the clusters, clustering efficiency can be considerably enhanced. Experimental results show that the use of only a little external knowledge can considerably enhance the quality of clustering results that satisfy users' constraint.

Timed token protocols inadequately provide periodic communication service, although this is crucial for hard real time systems. We propose an algorithm to guaranteeing periodic communication service on a timed token protocol network. In this approach, we allocate bandwidth to each node so that the summation of bandwidth allocations is Target Token Rotation Time (TTRT). If a node cannot consume the allocated time, the residual time is made concession to other nodes for non-periodic service using a timer which contains the unused time value and is appended to the token. This algorithm can always guarantee transmission of real-time messages before their deadlines when the network utilization is less than 50%.

A new algorithm is presented for recovering the blocks lost with the cell loss in the ATM transmission of the images coded by Jacquin's fractal coding. The key technique of the proposed BLRA (block loss recovery algorithm) is a fractal extrapolation that estimates the pixels in a lost block by using the contractive mapping parameters of a range block homogeneous to the lost block. The proposed BLRA is applied to the lost blocks in the iteration of decoding.

Compared with much research in the spatial-domain and transform-domain watermarking techniques, VQ-based watermarking technique has not been fully treated. A digital image watermarking scheme based on vector quantisation (VQ) is proposed to improve the degree of spreading watermark information. By partitioning the codebook into 3 groups, the scheme tries to embed one binary information for each block. The scheme spreads the watermark information almost evenly over the image with little extra distortion. The experimental results prove the efficiency and effectiveness of the scheme.