Deterministic execution testing has been considered a promising way for concurrent program testing because of its ability to replay a program's execution. Since, however, deterministic execution requires that a synchronization event sequence to be replayed be feasible and valid, it is not directly applicable to a situation in which synchronization sequences, being valid but infeasible, are taken into account. Resolving this problem is very important because a program may still meet its specification although the feasibility of all valid sequences is not satisfied. In this paper, we present a new approach to deterministic execution for testing concurrent systems. The proposed approach makes use of the notion of event independence and constructs an automation which accepts all the sequences semantically equivalent to a given event sequence to be replayed. Consequently, we can allow a program to be executed according to event sequences other than the given (possible infeasible) sequence if they can be accepted by the automation.

As LSIs are two-dimensional structures, the number of external pins increases at a lower rate than the corresponding increase in the number of gates on the LSI. Therefore, the number of flip-flops on a scan path increases as the density of gates on LSIs rises, resulting in longer test application times. In this paper, three novel DFT strategies aimed at reducing test application time are proposed. DFT strategy 1 is a full scan design method with test point insertion, DFT strategy 2 is a partial scan design method, and DFT strategy 3 is a partial scan design method with test point insertion. Experimental results show that these DFT strategies reduced the test application times by 45% to 82% compared with conventional full scan design methods.

An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.

The legal firing sequence problem of Petri nets (LFS) is one of fundamental problems in the analysis of Petri nets, because it appears as a subproblem of various basic problems. Since LFS is shown to be NP-hard, various heuristics has been proposed to solve the problem of practical size in a reasonable time. In this paper, we propose a new algorithm for this problem. It is based on the partial order verification technique, and reduces redundant branches in the search tree. Moreover, the proposed algorithm can be combined with various types of heuristics.

Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

We present a new technique for hierarchical intellectual property (IP) protection using partially-mergeable cores. The proposed core partitioning technique guarantees 100% protection of critical-IP, while simplifying test generation for the logic that is merged with the system. Since critical-IP is tested using BIST, the controllability and observability of internal lines in the core are enhanced, and test application time is reduced. Case studies using the ISIT-DLX and Picojava processor cores demonstrate the applicability of our technique.

There exist some results showing that quantum communications are more powerful than classical communications. Moreover, although quantum entangled states do not give extra information, by using prior entanglement the quantum communication complexity of some functions is less than the classical communication complexity. The communications with prior entanglement can be regarded as a type of public coin models. In this paper, we investigate quantum communications for multi-party with prior entanglement, and show that there exists a generalized inner product function for k-party such that the quantum communication complexity is at most k bits, but the classical communication complexity needs at least 3k/2 bits. Moreover, we also provide a generalized form of prior entanglements that is effective in order to compute some type of Boolean functions.

This letter proposes a hardware/software partitioning algorithm for digital signal processor cores with two register files. Given a compiled assembly code and a timing constraint of execution time, the proposed algorithm generates a processor core configuration with a new assembly code running on the generated processor core. The proposed algorithm considers two register files and determines the number of registers in each of register files. Moreover the algorithm considers two or more types of functional units for each arithmetic or logical operation and assigns functional units with small area to a processor core without causing performance penalty. A generated processor core will have small area compared with processor cores which have a single register file or those which consider only one type of functional units for each operation. The experimental results demonstrate the effectiveness and efficiency of the proposed algorithm.

In this paper we present two contributions for a set of local transformations (a selection set) to improve a performance of a very large circuit. The first contribution is an idea of "padding node" and "multi-separator-set. " We have proven that combination of padding node and multi-separator-set provides the optimum selection set. The second contribution is our heuristic method to find a semi-optimum multi-separator-set, which uses a network flow algorithm. Our method is robust for very large circuits, because its memory usage and calculation time are linear and polynomial order with the size of the circuit. We have compared our method with Singh's selection function method, which provides the optimum selection set and is the best method in literature to date. Our method has successfully optimized delays of all circuits, while Singh's selection function method has aborted with three large circuits because of memory overflow. The results also has shown our method has a comparable capability in delay optimization to Singh's method, although our method is heuristic.

A novel in vivo exposure setup has been developed for testing the possible promoting effects of 1.5 GHz digital cellular phones on mouse skin carcinogenesis. The exposure setup has two main features: one is the employment of an electrically short monopole antenna with capacitive-loading, which supplies the ability to realize a highly localized peak SAR above 2 W/kg without any thermal stress for a mouse; the other is the use of a transparent absorber to allow real-time observation of both the exposure process as well as mouse activities during the exposure. Dosimetric analyses for the exposure setup have been carried out both numerically and experimentally. Good agreement was confirmed between the numerical and experimental results, thereby demonstrating the validity of the novel exposure setup.

In this paper, we study nonblocking supervisory control of discrete event systems under partial observation. We introduce a weak normality condition defined in terms of a modified natural projection map. The weak normality condition is weaker than the original one and stronger than the observability condition. Moreover, it is preserved under union. Given a marked language specification, we present a procedure for computing the supremal sublanguage which satisfies Lm(G)-closure, controllability, and weak normality. There exists a nonblocking supervisor for this supremal sublanguage. Such a supervisor is more permissive than the one which achieves the supremal Lm(G)-closed, controllable, and normal sublanguage.

This paper describes a new architecture-based microprocessor, a dynamically programmable parallel processor (DPPP), that consists of large numbers of simplified ALUs (sALU) as processing blocks. All sALUs are interconnected via a code division multiple-access bus interface that provides complete routing flexibility by establishing connections virtually through code-matching instead of physical wires. This feature is utilized further to achieve high parallelism and fault tolerance. High fault tolerance is realized without the limitations of conventional fabrication-based techniques nor providing spare elements. Another feature of the DPPP is its simple programmability, as it can be configured by compiling numerical formula input using the provided user auto-program interface. A prototype chip based on the proposed architecture has been implemented on a 4.5 mm 4.5 mm chip using 0.6 µm CMOS process.

Reliability-based decoding algorithm in multistage decoding of multilevel codes is discussed. Through theoretical analyses, effects of soft reliability information are examined for different types of partitionings.

This paper proposes a vector quantization scheme which makes it possible to consider the dynamics of input vectors. In the proposed scheme, a linear transformation is applied to the consecutive input vectors and the resulting vector is quantized with a distortion measure defined by the statistics. At the decoder side, the output vector sequence is determined using the statistics associated with the transmitted indices in such a way that a likelihood is maximized. To solve the maximization problem, a computationally efficient algorithm is derived. The performance of the proposed method is evaluated in LSP parameter quantization. It is found that the LSP trajectories and the corresponding spectra change quite smoothly in the proposed method. It is also shown that the use of the proposed method results in a significant improvement of subjective quality.

This paper describes an electromagnetically coupled microstrip divider that provides high output port isolation and DC cutting. The device consists of a parasitic resonator placed above microstrip patch resonators, achieving tight coupling for both input and output ports. FDTD simulation and measurements reveal that the device has a high isolation between output ports. Equal and unequal 2-way and 3-way power dividers are presented in this paper.

Simulation based education and training, especially wargame simulations, are being used widely in the field of defense modeling and in simulation communities. In order to efficiently train students and trainees, the wargame simulations must have both high performance and high fidelity. In this paper, we discuss design and implementation issues for a prototype of a parallel and distributed wargame simulation system. This wargame simulation system is based on High Level Architecture (HLA) and employs some optimization to achieve both high performance and high fidelity in the simulation system. The results show that the proposed optimization method is effective when optimization is applied to 93.5% or less of the moving objects (PFs) within the range of detection (RofD) of both the red and blue teams. Specifically, when each team has 1000 PFs we found that if the percentage of PFs within RofD is less than 50% for both teams, our method is over two times better than for the situation where there is no optimization.

We present a scalable parallel rasterizer based on our interleaved scanline rasterization. The sorting overhead of a conventional scanline-based parallel rendering approach has been studied and removed by implementing a scanline assignment hardware. All advantages of the scanline-based parallel rendering are kept such that a good scalability and a small memory usage are achieved. Our architecture is evaluated precisely by a discrete event-based simulation, and the rendering performance and utilization are shown for a various number of rasterizers. The simulation results show more than 8 Mtriangles/s of performance with 64 rasterization engines running at 10 MHz.

This paper presents a novel image coding scheme based on separate coding of region and residue sources. In a subband image coding scheme, quantization errors in each subimage spread over the reconstructed image and result in a blurring or a boundary artifact. To obtain high compression ratio without considerable degradation, an input image, in our scheme, is separated into region and residue sources which are coded using different coding schemes. The region source is coded by adaptive arithmetic coder. The residue source is coded using multiresolution subimages generated by applying a subband filter. Each block in the subimages is predicted by an affine transformation of blocks in lower resolution subimages. Experimental results show that a high coding efficiency is achieved using the proposed scheme, especially in terms of the subjective visual quality and PSNR at low bit-rate compression.

The effect of Unbalanced-Magnetic-Pull (UMP) on vibration and run-outs has become stringent in the design for high performance HDD spindle motors. In this paper, reducing the UMP and also minimizing its variability for an 8-pole 9-slot spindle motor to achieve robustness in the performance is described and illustrated using novel robust design methods. A screening experiment identifies the key design parameters. Using Design of experiment (DOE) and Analysis of Variance (ANOVA), the parameter design reduces the amplitude of UMP and minimizes its variability by product parameter optimization. The tolerance design improves the quality by tightening tolerances on product or process parameters to reduce the performance variation. The optimal design process includes considerations of manufacturing and process noises, such as manufacturing tolerances for the slot opening and variation of the rotor magnet magnetization distribution due to the magnetization fixture and process. The optimal design procedure is briefly introduced and the results are presented.

This paper presents a fast inversion method for electromagnetic imaging of cylindrical dielectric objects with the optimal regularization parameter used in the Levenberg-Marquardt method. A novel procedure for choosing the optimal regularization parameter is proposed. The method of moments with pulse-basis functions and point matching is applied to discretize the equations for the scattered electric field and the total electric field inside the object. Then the inverse scattering problem is reduced to solving the matrix equation for the unknown expansion coefficients of a contrast function, which is represented as a function of the relative permittivity of the object. The matrix equation may be solved in the least-squares sense with the Levenberg-Marquardt method. Thus the contrast function can be reconstructed by the minimization of a functional, which is expressed as the sum of a standard error term on the scattered electric field and an additional regularization term. While a regularization parameter is usually chosen according to the generalized cross-validation (GCV) method, the optimal one is now determined by minimizing the absolute value of the radius of curvature of the GCV function. This scheme is quite different from the GCV method. Numerical results are presented for a circular cylinder and a stratified circular cylinder consisting of two concentric homogeneous layers. The convergence behaviors of the proposed method and the GCV method are compared with each other. It is confirmed from the numerical results that the proposed method provides successful reconstructions with the property of much faster convergence than the conventional GCV method.