We present a general framework with which we can evaluate the flexibility and efficiency of various replay systems for parallel programs. In our approach, program monitoring is modeled by making a virtual dataflow program graph, referred to as a VDG, that includes all the instructions executed by the program. The behavior of the program replay is modeled on the parallel interpretation of a VDG based on two basic parallel execution models for dataflow program graphs: a data-driven model and a demand-driven model. Previous attempts to replay parallel programs, known as Instant Replay and P-Sequence, are also modeled as variations of the data-driven replay, i.e. the datadriven interpretation of a VDG. We show that the demand-driven replay, i.e. the demand-driven interpretation of a VDG, is more flexible in program replay than the data-driven replay since it allows better control of parallelism and a more selective replay. We also show that we can implement a demand-driven replay that requires almost the same amount of data to be saved during program monitoring as does the data-driven replay, and which eliminates any centralized bottleneck during program monitoring by optimizing the demand propagation and using an effective data structure.

A highly reliable network which can restore itself from network failures is one important concept for the future high capacity broadband network. In such self-healing network, flooding based failure-restoration algorithm is used to locate new routes and then to reroute failure traffic to that routes automatically when network failures such as link or node failures occur. Since the speed of this algorithm is degraded by the large amount of restoration messages produced by the process, such large volume messages should be reduced. In this paper, the scheme will be proposed, which reduces the large volume messages and efficiently selects alternative routes. In this scheme, the Message Wall will be used to filter useless restoration messages at the tandem nodes and Multi-Message Selecting method will be used to rapidly select a group of link-disjointed alternative routes from the feasible ones in each Flooding Wave sequence. The simulation results show that restoration messages are dramatically reduced and adequate alternative routes can be quickly found out.

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 finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

This paper describes the design and evaluation of fully scannable embedded memory arrays. A memory array, such as a register file, is made scannable by adding a small auxiliary circuit including a counter and multiplexers. Plural memory arrays can be chained into a single scan path along with ordinary flip-flops. Detailed configuration and implementation of the scannable CMOS and bipolar LCML register file macros are discussed. The overhead ratio of the CMOS register file macro with 16-word by 16-bit results in an 8.6% transistor count and a 6.4% die area. The access time overhaead is 7.8% and the set-up time increases by about 50ps. Bipolar LCML register file macros have been applied to gate array LSIs which have successfully achieved average stuck-at fault coverage of 99.2%.

The present paper clarifies that the variance of the maximum likelihood estimator (MLE) of a parameter does not reach the Cramer-Rao lower bound (CRLB) when fitting a straight-line to observed two-dimensional data. In addition, the variance of the MLE can be shown to be equal to the CRLB only if observed noise reduces to a one-dimensional Gaussian variable. For most practical applications, it can be assumed that noise is added only to the range direction. In this case, the MLE is clearly an asymptotically effective estimator. However, even if we assume such a noise model, ML line-fitting to the data from many points of view has a high computational cost. The present paper proposes an alternative fitting method in order to provide a cost-effective unbiased estimator. The reliability of this new method is analyzed statistically and by computer simulation.

In this paper, in order to achieve the low power consumption of programmable divider in a PLL frequency synthesizer, we propose a new prescaler method for low power consumption. A fixed prescaler is inserted in front of the (N +1/2) programmable divider which is designed based on the new principle. The divider ratio in the loop does not vary at all even if such a prescaler is utilized. Then the permissible delay periods of a programmable divider can be extended to two times as long as the conventional method, and the low power consumption and low cost in a PLL frequency synthesizer have been achieved.

This paper describes an analytic method, experimental results and simulation results for self-heating in a SOI (Silicon On Insulator) high voltage MOS transistor. The new analytic method enabled the temperature-rise caused by self-heating to be measured precisely. The temperature-rise in an operating transistor was evaluated by measuring the change of the source current against the source current without the self-heating. In advance, the relation between the temperature-rise and the current change had been prepared by measuring the current decrease when the hot-chuck temperature had been changed in iso-thermal condition. By using this method, the dependence of the temperature-rise or the current decrease on the operating condition or the thermal resistance were clarified. Furthermore, these measurement results and the thermal resistance which is calculated by a FEM analysis enabled a fully coupled electrothermal device simulation to be analyzed more precisely. The dependence of the current decrease on the buried oxide thickness were also calculated.

Physical models for fully depleted (FD) and non-fully depleted (NFD) SOI MOSFETs are overviewed, and recent applications of them (in SOISPICE) are described, stressing the need for good physics-based accounting for the inherently coupled bipolar and MOS device features in reliable circuit design. The applications suggest that asymmetrical double-gate FD/SOI CMOS technology can be scaled below 0.1 µm, whereas the single-gate counterpart seemingly cannot be, and that the floating-body charge dynamics and the associated transient leakage current in NFD/SOI (and FD/SOI) pass transistors in memory (DRAM and SRAM) circuits can be effectively controlled by optimal device design.

A hierarchical fault tracing method for VLSIs with bi-directional busses from CAD layout data in the CAD-linked electron beam test system is described. When fault tracing reaches at a cell connected to a bi-directional bus, our method is able to judge the direction of the signal flow, input or output, by using waveforms acquired by an EB tester, in a consistent manner independently of circuit functions as with a previously proposed tracing method for circuits without bi-directional busses.

The currying of term rewriting systems (TRSs) is a transformation of TRSs from a functional form to an applicative form. We have already introduced an order-sorted version of currying and proved that the compatibility and confluence of order-sorted TRSs were preserved by currying. In this paper, we focus on a key property of TRSs, completeness. We first show some proofs omitted in Ref. [3]. Then, we prove that the SN (strongly normalizing) property, which corresponds to termination of a program, is preserved by currying. Finally, we prove that the completeness of compatible order-sorted TRSs is preserved by currying.

A fast rip-up and reroute algorithm for very large scale gate arrays is proposed. The automatic routing program for gate arrays usually consists of an initial routing process and rip-up and rerouting process. The rip-up and rerouting process eliminates the unconnects introduced by the initial routing process. There are two main reasons for leaving some unconnects: routing order dependency and local wire congestion. The existing rip-up and reroute algorithms can efficiently resolve unconnects caused by the routing order dependency. However, they cannot do unconnects caused by the local wire congestion. On the other hand, the proposed algorithm combines a `global' and `local' rip-up and reroute process and efficiently resolve unconnects caused by both of them. The `global' process reduces the local wire congestion by ripping up and rerouting global paths. The `local' process eliminates the unconnects, mainly caused by routing order dependency, by ripping up and rerouting local paths. The effectiveness of our method is demonstrated by our experimental results on industrial sea-of-gates (SOG) circuits and a well-known benchmark circuit.

The purpose of this study is to present results of forecast of ranges for yen to US dollar exchange rate fluctuation in order to evaluate the performance of two algorithms: the original backpropagation (OBP), which is the most widely used algorithm, and the second algorithm (NBP), which is a proposed modification to the first one by the authors. The set of data consisted of economic and financial values that have already been calculated by the Bank of Japan and the Japanese Ministry of Planning and Finance. This data was available though the Nikkei Data Service and stretched from January, 1986, to the end of December, 1992. The results obtained show not only that NBP performs better than OBP since the former speeds up convergence time to a given error value, but also NBP shows a good generalization performance.

An ink-jet head using a buckling diaphragm microactuator is described. The microactuator is composed of a silicon substrate, silicon dioxide insulator, nickel heater layer and electro-plated nickel diaphragm. All the edges of the diaphragm are fixed on the substrate and a narrow gap is formed between the diaphragm and the substrate. A nozzle plate is connected to the actuator by an adhesive spacer to get the ink-jet head. An ink chamber is formed by the surfaces of the diaphragm, the nozzle plate, and the side wall of the spacer. When the diaphragm is heated, thermally induced compressive stress causes the diaphragm to buckle rapidly and the diaphragm simultaneously deflects toward the nozzle plate. The deflection raises the pressure in the ink chamber and an ink droplet is then ejected through the nozzle. The head design was carried out using mechanical analysis of a buckling model, and heat transfer simulation. The diaphragm made from nickel is 300 µm diameter and 2 µm-thick. The narrow gap is 0.4 µm. The cathode current density in nickel sulphamate solution used for nickel electro-plating of the diaphragm was 20 mA/cm2. An ink droplet has been ejected with a velocity of 8 m/s while the ink-jet head is operated by heating the diaphragm with a current of 510 mA at 16.6 V for 10 µs at 1.8 kHz.

In accordance with the diffusion of applications, such as the Desk Top Publishing system, the Document Formatting system and the Document Editing system, it is easy to make a document by using a computer. However, as for allocating the diagrams (figures and tables), there are few document processing systems able to allocate diagrams on the appropriate places automatically. In a document processing system it is a very important issue to allocate diagrams on the most suitable places. This paper defines the criteria for allocating diagrams on the suitable positions by investigating published papers. These criteria concern 1) the order of diagrams to be allocated, 2) the stability of the diagram allocations, 3) the distance between the diagram and the location of the corresponding first reference in the text, 4) the allocation balance of diagrams in a text, 5) the restricted areas where diagrams shouldn't be allocated, 6) the allocation priorities between diagrams of different width. Moreover, this paper proposes a method for deciding the diagram allocations satisfying the above criteria automatically and fast on document formatting systems. In this case we have limited its application to one type of ducuments, which is papers. Especially, this method can skillfully allocate diagrams of different width on the page by reallocating the diagrams and texts within it, and can allocate diagrams over the document uniformly.

Competition in some telecommunication services has emerged in Japan since deregulation of telecommunication markets in 1985. Demand forecasting methods which take into account competition and investment plan based on it should be studied. There are many forecasting and network planning methods, but most of them do not take into account competition. Thus, in this paper, the competitive Bass model, attraction model, regression model and entropy model are discussed as forecasting methods which can be used under competitive environment. Most of the existing planning methods have treated costs and interest rates as deterministic values, but in fact they are not deterministic. Thus, we show a method which represents undefined factors by fuzzy numbers with triangular membership functions.

This paper investigates the problem of constructing a logical multicasting tree which dispatches data to multiple destinations according to their bandwidth requirements. An optimization problem is formulated to minimize the maximum delay between a sender and multiple receivers. An algorithm of finding the optimum branching locations is presented. Performance analysis from the closed queueing network theory is given to evaluate a multicasting tree network based on this proposed algorithm.

A thermally controlled magnetization actuator (TCMA) is proposed for micro-mechanical relays. It is actuated by changing the local magnetization of the structure by remote heating using a laser beam. It is fabricated by nickel surface micromachining (a fabrication technique using nickel electroplating). The optical power of the laser diode used to drive the TCMA is about 30 mW. The switching time of the microrelay was experimentally measured to be 10 ms, the same as that of a conventional mechanical relay. The contact force was calculated to be 20 µN, which can be improved by increasing the size of the TCMA.

We developed the computer calligraphy, that is, a computer formation of brush-written Kanji characters using calligraphic knowledge. The style of brush handwriting depends mainly on the way of using a writing brush. Brush writing skills include the direction of brush at the beginning, curvature and turning the brush, the brush-up at the termination point in a stroke. We make up the calligraphic knowledge base according to the above mentioned brush writing skills. For simulating real brush movement, we represent the brush contact form that is the brush shape on the writing plane as a brush-touch. The system can control the size and direction of this brush-touch during the brush simulation. The system simulates the real brush writing to move the brush-touch along the skeleton letter shape in the standard database. We get the brush written Kanji from the locus of the brush-touch movement. We can extend this system to the new on line training system for brush writing using the simulation of brushtouch movement modified by the pressure, speed and rotation of the writing brush, and the skeleton letters written by a learner from the tablet. This system is also useful for students learning how to write Japanese letters beautifully with brush.

The purpose of our study is to develop an intelligent adaptive instruction system that manages intelligently the learner's estimated knowledge structure and optimizes the selection of problems according to his/her knowledge structures. The system adopts the dynamic problems of high school physics as a material of study, and is intended to operate on a UNIX Work Station. For these purposes, the system is composed of three parts, 1) interface part, 2) problem solving expert part, and 3) optimization expert system part for problem selection. The main feature of our system is that both knowledge structures of learner and teacher are represented by structural graph, and the problem selection process is controlled by the relationship between the learner's knowledge structure and the teacher's knowledge structure. In our system the relationship between these two knowledge structures is handled in the optimization expert system part for problem selection. In this paper the theory of the optimization expert system part for problem selection is described, and the effectiveness of this part is clarified through a simulation experiment of the originally defined matching coefficient.

This study proposes an amplitude limiting type spread spectrum communication to be applied to extremely low power radio wave communicaion and evaluates capability of the code division multiplex. First, changes in output from the correlation device, maximum power, and in allowable noise power are compared by computer simulation for the case where the number of multiplex channels is increased. Second, possible relationship between noise intensity and error rate is measured by actual loading experiments using a device developed for trial purpose. Third, majority decision logic is proposed for the said device to realize amplitude limiting type code division multiplex easily. When the amplitude is limited, the maximum power can be controlled at about 2 dB, and channels with more than half of the number of spread sign can be used. It is revealed that, in the spread spectrum, alteration of the number of multiplex channels is made easy by application of this method.