Shared memory multiprocessors are frequently used as compute servers with multiple parallel programs executing at the same time. In such environments, an operating system switches the contexts of multiple processes. When the operating system switches contexts, in addition to the cost of saving the context of the process being swapped out and that of bringing in the context of the new process to be run, the cache performance of processors also can be affected. The blocked algorithm improves cache performance by increasing the locality of memory references. In a blocked program using this algorithm, program performance can be significantly affected by the reuse of a block loaded into a cache memory. If frequent context switching replaces the block before it is completely reused, the cache locality in a blocked program cannot be successfully exploited. To address this problem, we propose a preemption-safe policy to utilize the cache locality of blocked programs in a multiprogrammed system. The proposed policy delays context switching until a block is fully reused within a program, but also compensates for the monopolized processor time on processor scheduling mechanisms. Our simulation results show that in a situation where blocked programs are run on multiprogrammed shared-memory multiprocessors, the proposed policy improves the performance of these programs due to a decrease in cache misses. In such situations, it also has a beneficial impact on the overall system performance due to the enhanced processor utilization.

In high-speed data networks, it is important to execute high-speed address resolution for packets at a router. To accomplish high-speed address resolution, address cache is effective. For HTTP accesses, it has been discussed that the Dual Zipfian Model can describe the distribution of the destination IP addresses, and it enabled us to derive the cache miss ratio in the steady state, i. e. , the cache miss ratio when the cache has full entries. However, at the time that systems are initialized or network topology is changed, the address cache has no address information or invalid address information. This paper shows the compulsory miss ratio which is the cache miss ratio when the cache has no address entry. In addition, we discuss the replacement policies of cache entries, for fast recovery of packet reachability, when the cache has information of unreachable address.

In industrial assembly lines, seam sealing is a painting process used for making watertight seals or for preventing rusting. In the process, sealant is painted on seams located at the joints of pressed metal parts. We developed a sealing robot system that adjusts the sealing gun motion adaptively to the seam position sensed by a range sensor (a scanning laser rangefinder which senses profile range data). In this paper, we propose a high-speed and highly reliable algorithm for seam position computation from the sensed profile range data around the seam. It is proved experimentally that the sealing robot system used with the developed algorithm is very effective, especially for reducing wasted sealant.

We have developed a map-based approach that enables us to efficiently extract information about man-made objects, such as buildings, from aerial images. An image is matched with a corresponding map in order to estimate the object information in the image (i. e. , presence, location, shape, size, kind, and surroundings). This approach is characterized by using a figure contained in a map as an object model for a top-down (model-driven) analysis of an object in the aerial image. We determined the principal steps of the map-based approach needed to extract object information and update a map. These steps were then applied to obtain the locations of missing buildings and the heights of existing buildings. The extraction results of experiments using aerial images of Kobe City (taken after the 1995 earthquake) show that the approach is effective for automatically extracting building information from aerial images and for rapidly updating map data.

A rigorous modal approach based on the transmission-line description has developed to explore effectively the filtering characteristics of planar optical DFB guiding structures. Using the modal transmission-line theory, the leakage and filtering characteristics of metal-strip gratings and dielectric gratings with gain or loss are first evaluated in details at the first- and third-order Bragg regimes. It can thus serve as a powerful template for computational algorithms to determine systematically and rigorously the optical effects of multilayered periodic guiding structures, which are not readily obtained by other methods.

Principle of a single shot demultiplextion by means of time-to-space conversion was investigated using femtosecond nonlinear optical response of absorption bleaching of squarylium dye (SQ) J-aggregates. Spincoated films of squarylium dye J-aggregates on glass substrates exhibit efficient and ultrafast transmittance change, which recovers 73% of its initial level (0 fs) within 1 ps. A simple method for time-to-space conversion was applied for this film. We took our attention to one of the characteristics of femtosecond pulse, which is the spatial thinness in its propagation direction. Femtosecond pulses of a single pump pulse and train of four probe pulses were illuminated to the same area (diameter of 10 mm) of the surface of the SQ J-aggregates film. Direction of the probe beam was normal to the surface of the film and that of the pump beam was oblique angle in horizontal plane. Caused by spatial delay of a pump pulse due to the illumination in oblique angle to the film, four probe pulses with interval time of 1 ps (1 THz) meet separate places on the film. Because of the fast response of the SQ J-aggregates, the film picked out part of each probe pulse, which has narrower shapes in horizontal direction compared to the initial circular one by transmittance change of the film. The spatially separated four lines were observed by a CCD camera for an image of the transmitted probe pulse train. These results suggest that the response time of SQ J-aggregate film, which determines the horizontal width of each line, to be enough for demultiplexing of 1 THz optical signals.

This paper presents an efficient method to derive the first passage time of an extended stochastic Petri net by simple algebraic operations. The reachability graph is derived from an extended stochastic Petri net, and then converted to a timed stochastic state machine which is a semi-Markov process. The mean and the variance of the first passage time are derived by algebraic manipulations with the mean and the variance of the transition time, and the transition probability for each transition in the state machine model. For the derivation, three reduction rules are introduced on the transition trajectories in a well-formed regular expression. An efficient algorithm is provided to automate the suggested method.

In this paper, a new approach is proposed for solving a real scheduling problem in a metal mold assembly process. This process is of a job-shop type, and the problem is large-scale and has complicated constraints. In this problem precedence relations exist not only among operations but also among jobs. The system has several types of single function machines and a type of multi-function machine. Furthermore, the number of machines belonging to each type is not single but plural. Therefore the selection of machine is necessary for executing each operation. An autonomous decentralized scheduling method is applied to this problem. In this method, a number of decision makers called modules cooperate with one another in order to attain the goal of the overall system. They determine the scheduling plan on the basis of their cooperation and the satisfaction of their own objective function levels. Particularly, the practicability of this method is considered through numerical results.

Hash routing is an algorithm for a distributed WWW caching system that achieves a high hit rate by preventing overlaps of objects between caches. However, one of the drawbacks of hash routing is its lack of robustness against failure. Because WWW becomes a vital service on the Internet, the capabilities of fault tolerance of systems that provide the WWW service come to be important. In this paper, we propose a duplicated hash routing algorithm, an extension of hash routing. Our algorithm introduces minimum redundancy to keep system performance when some caching nodes are crashed. In addition, we optionally allow each node to cache objects requested by its local clients (local caching), which may waste cache capacity of the system but it can cut down the network traffic between caching nodes. We evaluate various aspects of the system performance such as hit rates, error rates and network traffic by simulations and compare them with those of other algorithms. The results show that our algorithm achieves both high fault tolerance and high performance with low system overhead.

This paper proposes a model checking method for microcomputer programs. To deal with the state explosion problem, we adopt a compositional verification approach. Based on the proposed method, a microcomputer program for a real-life air-conditioner is verified. The program is large enough to cause state explosion. Among fourteen typical properties of the program, five properties are successfully verified by our method.

This paper proposes a novel cache architecture suitable for merged DRAM/logic LSIs, which is called "dynamically variable line-size cache (D-VLS cache). " The D-VLS cache can optimize its line-size according to the characteristic of programs, and attempts to improve the performance by exploiting the high on-chip memory bandwidth on merged DRAM/logic LSIs appropriately. In our evaluation, it is observed that an average memory-access time improvement achieved by a direct-mapped D-VLS cache is about 20% compared to a conventional direct-mapped cache with fixed 32-byte lines. This performance improvement is better than that of a doubled-size conventional direct-mapped cache.

In this paper, a program generator for communication protocol software will be presented. Our program generator takes an extended finite state machine as a domain model and generates a group of C++ classes needed for an implementation. For each state of the FSM, a C++ class is generated, where the interface events are implemented as member functions of the corresponding state object. Protocol data units (PDUs) are embedded as Message objects and specified in the same way as packet filter and is interpreted to generate necessary PDU definition statements and PDU manipulation statements. Also, protocol objects from different layers can be linked together by using an organization model, where a protocol entity is invoked by its upper layer entity or lower layer entity by member function calls.

We present an architecture of a VOD system employing proxy servers. The proposed VOD system provides efficient and reliable VOD services and solves the problems caused by traditional VOD systems of centralized, hierarchical or distributed architecture. The proxy servers are placed between video servers and user systems. The proxy server is a small size video server that has not only caching function but also intelligence such as VCR-like video stream control or navigation of other proxy/video servers to search for a selected video program. Using a VOD system of the proposed architecture, the VOD services can be provided to more users because it reduces the workload of video servers and network traffic. We provide the performance model of the system. Service availability is also analyzed. The proposed architecture shows better performance and availability than the traditional VOD architectures.

The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning peg solitaire is the feasibility issue. An early tool used to show the infeasibility of various peg games is the rule-of-three [Suremain de Missery 1841]. In the 1960s the description of the solitaire cone [Boardman and Conway] provides necessary conditions: valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper, we recall these necessary conditions and present new developments: the lattice criterion, which generalizes the rule-of-three; and results on the strongest pagoda functions, the facets of the solitaire cone.

This paper proposes and evaluates a character or symbol code system called EPICS for multilingual information processing. EPICS integrates a variable-length coding system using 16-bit units and a smart virtual machine. EPICS enhances the interchangeability of data. The variable-length coding system provides a huge code space. This huge space can include not only standardized code sets but also non-standardized codes of ancient symbols and user-specific symbols. The smart virtual machine executes inputs as instructions and is dynamically customizable. It allows us to define and modify instructions during runtime and provides us with customization facilities. Customization facilities can be used to specify a sorting order and normalization. Customization also makes it possible for an information producer (sender) to express his intentions or annotations in data and for an information consumer (receiver) to process the data depending on his needs. Moreover, customization enables one to send compressed data and decompression program fragments incrementally and efficiently without predefined decompression algorithms.

This paper reports the performance of an AC-voltage sensor with a LiNbO3 integrated retroreflective structure based on the Y-junction Mach-Zehnder interferometer. This structure is capable of realizing a low-cost sensor chip because of the small chip size and single optical-fiber connection. In the sensitivity and frequency response evaluation, detection sensitivities of 6.3 µ V / Hz have been measured with a frequency response from 6 Hz to 2 GHz. These measurement limitations were also analyzed theoretically and compared with the experimental results. This unique sensor enables precise voltage measurement in an EMI environment, even inside a computer.

In a Cache Coherent Non-Uniform Memory Access (CC-NUMA) system, memory transactions can be classified into two types: inter-node transactions and intra-node transactions. Because the latency of inter-node transactions is usually hundreds times larger than that of intra-node transactions, it is important to reduce the latency of inter-node transactions. Even though the remote cache in the CC-NUMA systems improves the latency of inter-node transactions through caching the remote memory lines, the remote and processor caches of snoop-based CC-NUMA systems have to retain the multi-level cache inclusion property for the simplification of snooping. The inclusion property degrades the cache performance by following factors. First, all the remote memory lines in a processor cache should be preserved in the remote cache of the same node. Second, a line replacement at the remote cache replaces the same address line in the processor caches, which does not comply with the replacement policy of the processor caches. In this paper, we propose Access-list which renders the inclusion property unnecessary, and evaluate the performance of the proposed system by program-driven simulation. From the simulation results, it is shown that the miss rates of caches are reduced and the efficiency of the snoop filtering is similar to the system with the inclusion property. It turns out that the performance of the proposed system is improved up to 1.28 times.

This paper proposes a new approach to achieving high performance and low energy consumption for set-associative caches. The cache, called way-predicting set-associative cache, speculatively selects a single way, which is likely to contain the data desired by the processor, from the set designated by a memory address, before it starts a normal cache access. By accessing only the single way predicted, instead of accessing all the ways in a set, energy consumption can be reduced. In order for the way-predicting cache to perform well, accuracy of way prediction is important. This paper shows that the accuracy of an MRU (most recently used)-based way prediction is higher than 90% for most of the benchmark programs. The proposed way-predicting cache improves the ED (energy-delay) product by 60-70% compared to the conventional set-associative cache.

We fabricated a 16-kB cache macro using 0.35-µm quadruple-metal CMOS technology. This is a 285-MHz, two-port 16-kB (512256 b) cache macro that has a 2-ns access time. This high-speed performance is enabled by a hierarchical bit-line architecture that uses double global bit-line pairs (WGBs), and a high-speed timing-insensitive sense amplifier (ISA) that shortens the access time.

Inductive Logic Programming (ILP) is a study of machine learning systems that use clausal theories in first-order logic as a representation language. In this paper, we survey theoretical foundations of ILP from the viewpoints of Logic of Discovery and Machine Learning, and try to unify these two views with the support of the modern theory of Logic Programming. Firstly, we define several hypothesis construction methods in ILP and give their proof-theoretic foundations by treating them as a procedure which complets incomplete proofs. Next, we discuss the design of individual learning algorithms using these hypothesis construction methods. We review known results on learning logic programs in computational learning theory, and show that these algorithms are instances of a generic learning strategy with proof completion methods.