Cache memories are one of the main factors that affect software performance, and their use is becoming increasingly common even in embedded systems. Efficient analysis of the effects of parameter variations (cache size, degree of associativity, replacement policy, line size, . . . ) is at the same time an essential and very time-consuming aspect of embedded system design, whose complexity increases when multi-tasking and real-time aspects must be considered. We propose a new simulation-based methodology, focused on an approximate model of the cache and of the multi-tasking reactive software, that allows one to trade off smoothly between accuracy and simulation speed. In particular, we propose to accurately consider intra-task conflicts, but approximate inter-task conflicts by considering only a finite number of previous task executions. The rationale for this choice can be found in a common pattern in embedded systems, where a "normal" data flow results in a regular intra-task common flow, interrupted from time to time by some urgent event, that pessimistically can be considered as disrupting the cache behavior. The approach is conservative because re-execution of a task after a large amount of time will always be considered as not in cache, and the simulation speed-up is considerable.

A recursive maximum likelihood decoding (RMLD) algorithm is more efficient than the Viterbi algorithm. The decoding complexity of the RMLD algorithm depends on the recursive sectionalization. The recursive sectionalization which minimizes the decoding complexity is called the optimum sectionalization. In this paper, for a class of non-linear codes, called rectangular codes, it is shown that a near optimum sectionalization can be obtained with a dynamic programming approach. Furthermore, for a subclass of rectangular codes, called C-rectangular codes, it is shown that the exactly optimum sectionalization can be obtained with the same approach. Following these results, an efficient algorithm to obtain the optimum sectionalization is proposed. The optimum sectionalizations for the minimum weight subcode of some Reed-Muller codes and of a BCH code are obtained with the proposed algorithm.

In this paper, an instruction-cache scheme called Multi-Path Tracing is proposed to enhance the trace cache. Paths are classified to improve the trace cache hit ratio by reducing the path conflict and basic blocks are joined to reduce the hardware cost needed to implement the trace cache. Simulation results for various SPEC integer benchmarks show that the proposed scheme increases the hit ratio by more than 25% and the effective fetch size by 10%.

This paper demonstrates the necessity of special handling mechanisms for type (or sort) information when learning logic programs on the basis of background knowledge that includes type hierarchy. We have developed a novel relational learner RHB, which incorporates special operations to handle the computing of the least general generalization (lgg) of examples and the code length of logic programs with types. It is possible for previous learners, such as FOIL, GOLEM and Progol, to generate logic programs that include type information represented as is_a relations. However, this expedient has two problems: one in the computation of the code length and the other in the performance. We will illustrate that simply adding is_a relations to background knowledge as ordinary literals causes a problem in computing the code length of logic programs with is_a literals. Experimental results on artificial data show that the learning speed of FOIL exponentially slows as the number of types in the background knowledge increases. The hypotheses generated by GOLEM are about 30% less accurate than those of RHB. Furthermore, Progol is two times slower than RHB. Compared to the three learners, RHB can efficiently handle about 3000 is_a relations while still achieving a high accuracy. This indicates that type information should be specially handled when learning logic programs with types.

This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.

We have developed an InP-based monolithic optical frequency discriminator consisting of a temperature-insensitive optical filter and dual photodiodes. This integrated device detects the optical frequency deviation of the input light as differential photocurrent from the dual photodiodes, and the photocurrent is fedback to the light source for frequency stabilization through a differential amplifier. The FSR and extinction ratio of the filter are 50 GHz and 20 dB. The total opto-electronic conversion efficiency is 40%. In a frequency stabilization experiment using the developed discriminator, the frequency fluctuation of a DFB laser was reduced to less than 10 MHz.

Classification of the new and used bills using the spectral patterns of raw time-series acoustic data (observation data) poses some difficulty. This is the fact that the observation data include not only a bill sound, but also some motor sound and noise by a transaction machine. We have already reported the method using adaptive digital filters (ADFs) to eliminate the motor sound and noise. In this paper, we propose an advanced technique to eliminate it by the neural networks (NNs). Only a bill sound is extracted from observation data using prediction ability of the NNs. Classification processing of the new and used bills is performed by using the spectral data obtained from the result of the ADFs and the NNs. Effectiveness of the proposed method using the NNs is illustrated in comparison with former results using ADFs.

We have developed an InP-based monolithic optical frequency discriminator consisting of a temperature-insensitive optical filter and dual photodiodes. This integrated device detects the optical frequency deviation of the input light as differential photocurrent from the dual photodiodes, and the photocurrent is fedback to the light source for frequency stabilization through a differential amplifier. The FSR and extinction ratio of the filter are 50 GHz and 20 dB. The total opto-electronic conversion efficiency is 40%. In a frequency stabilization experiment using the developed discriminator, the frequency fluctuation of a DFB laser was reduced to less than 10 MHz.

A microprocessor integrated with DRAM on the same die has the potential to improve system performance by reducing memory latency and improving memory bandwidth. In this paper we evaluate the performance of a single chip multiprocessor integrated with DRAM when the DRAM is organized as on-chip main memory and as on-chip cache. We compare the performance of this architecture with that of a more conventional chip which only has SRAM-based on-chip cache. The DRAM-based architecture with four processors outperforms the SRAM-based architecture on floating point applications which are effectively parallelized and have large working sets. This performance difference is significantly better than that possible in a uniprocessor DRAM-based architecture, which performs only slightly faster than an SRAM-based architecture on the same applications. In addition, on multiprogrammed workloads, in which independent processes are assigned to every processor in a single chip multiprocessor, the large bandwidth of on-chip DRAM can handle the inter-access contention better. These results demonstrate that a multiprocessor takes better advantage of the large bandwidth provided by the on-chip DRAM than a uniprocessor.

This paper presents two man-machine reliability models. A system consists of one machine unit, one operator, and one event detecting monitor. The machine unit has three states, normal, abnormal, and failed. The event detecting monitor may fail in two ways. If a machine unit becomes abnormal, the event detecting monitor sends a signal, and the operator takes necessary actions. If the operator fails in the action in the cause of human error, the machine unit goes down. The condition of the operator is classified into two types, good and bad. The time to repair, and the human error rate both depend on the condition of the operator. The MTTF is obtained by using a Markov model and numerical computation. Furthermore, the optimal operating period which minimizes the overall cost is decided by using computer methods. Some numerical examples are shown.

This paper describes a new system for extracting and classifying bibliography regions from the color image of a book cover. The same as all the color image processing, the segmentation of color space is an essential and important step in our system; and here HSI color space is adopted rather than RGB color space. The color space is segmented into achromatic and chromatic regions first; and the segmentation is completed after thresholding the intensity histogram of the achromatic region and the hue histogram of the chromatic region. Then text region extraction and classification follows. After detecting fundamental features (stroke width and local label width) text regions are determined by comparing smeared blocks to the original candidate image. Based on the general cover design model, text regions are classified into author region, title region, and publisher region furthermore, and a bibliography image is obtained as a result, without applying OCR. The appearance of the book is 3D reconstructed as well. In this paper, two examples are presented.

This paper presents a new approach to computer image generation via three proposed methods for translating the evolution of a Petri net into fractal image synthesis. The idea is derived from the concept of fractal iteration principles in the escape-time algorithm and chaos game. The approach uses a Petri net as a powerful abstract modeling tool for fractal image synthesis via its duality, deadlock, inhibitor arc, firing sequence and marking reachability. The objective of this approach is to enhance the analysis technique of a Petri net and use it as a novel technique for fractal image synthesis. Generating fractal images via the dynamics of a Petri net allows an easy and direct proof for the similarity and correspondence between the dynamics of complex quadratic fractals by the recursive procedure of the escape-time algorithm and the state of a Petri net via a reachability problem. The reachability problem will be manipulated in terms of the dynamics of the fractal in order to generate images via three proposed methods. Validation of our approach is given by discussion and an illustration of some experimental results.

In this paper, by making good use of the parallel-transit-evaluation algorithm and sparsity of the connection between neurons, a pipeline structure is successfully introduced to the sequential Boltzmann machine processor. The novel structure speeds up nine times faster than the previous one, with only the 12% rise in hardware resources under 10,000 neurons. The performance is confirmed by designing it using 1.2 µm CMOS process standard cells and analyzing the probability of state-change.

This paper proposes an analysis method of the roundoff error due to finite-wordlength decoding in fractal image coding. The proposed method can be applied to large images such as 256 256 or 512 512 images because it needs no complex matrix computation. The simplified model used here ignores the effect of decimation ratio on the roundoff error because it is negligible. As an analysis result, the proposed method gives the output error variance which consists of grey-tone scaling coefficients and an iteration number. This method is tested on various types of 12 standard images which have 256 256 size or 512 512 size with 256 grey levels. Comparisons of simulation results with analysis results are given. The results show that our analysis method is valid for the fractal image coding.

Distributed Web caching allows multiple clients to quickly access a pool of popular Web pages. Conventional distributed Web caching schemes, e. g. , the Internet cache protocol and hash routing, require the sending of many query messages among cache servers and/or impose a large load on the cache servers when they are widely dispersed. To overcome these problems, we propose a hash-based query caching method using both a hash function and a query caching method. This method can find cached objects among several cache servers by using only one query message, enabling the construction of an efficient large-scale distributed Web cache server. Compared to conventional methods, this method reduces cache server overhead and object retrieval latency.

In a multisystem data sharing environment (MDSE), the computing nodes are locally coupled via a high-speed network and share a common database at the disk level. To reduce the amount of expensive and slow disk I/O, each node caches database pages in its main memory buffer. This paper focuses on the MDSE that uses record-level locking as a concurrency control. While the record-level locking can guarantee higher concurrency than page-level locking, it may result in heavy message traffic. In this paper, we first propose a cache coherency scheme that can reduce the message traffic in the standard locking. Then the scheme is extended to the context where lock caching and lock de-escalation are adopted. Using a distributed database simulation model, we evaluate the performance of the proposed schemes under a wide variety of database workloads.

This paper introduces an alternating rebound Turing machine and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any o(log n) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any o(logn) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log n. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by o(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene .

This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.

This paper proposes an algorithm for analyzing the reachability property of Petri nets by the use of unfoldings. It is known that analyzing the reachability by using unfoldings requires exponential time and space to the size of unfolding. The algorithm is based on the branch and bound technique, and experimental results show efficiency of the algorithm.

In order to reduce state explosion problem, techniques such as symbolic state space traversal and partial order reduction have been proposed. Combining these two techniques, however, seems difficult, and only a few research projects related to this topic have been reported. In this paper, we propose handling single place zero reachability problem of Petri nets by using both partial order reduction and symbolic state space traversal based on ZBDDs. We also show experimental results of several examples.