Storage system in a multimedia server must satisfy two contradicting requirements: real-timeliness and large number of parallel user requests. Efficient algorithms for data placement, disk head scheduling, and request admission control schemes are needed to support the requirements. In this paper, we propose efficient schemes to maximize system resource utilization and service availability: cyclic placement scheme, subgroup retrieval scheme, and measurement-based request admission control scheme. Performance analysis through simulation revealed that the amount of system buffers required can be reduced by 70% approximately.
Chikayoshi SUMI Akifumi SUZUKI Kiyoshi NAKAYAMA
In order to estimate elasticity distribution of living soft tissue by ultrasonic pulse-echo method, we developed an algorithm by which we estimate 2-D displacement vector field from two successive rf echo data frames. The algorithm estimates a displacement vector iteratively by matching the phase characteristics of the local regions of two data frames. The estimation process is composed of coarse one and the fine one. In the coarse estimation process, the displacement is estimated by detecting the peak of the 2-D cross-correlation function. In the fine process, the displacement is estimated iteratively by shifting the 2nd frame data so that the phase characteristics matches with that of the 1st frame data. In each iterative step of both processes, the estimated displacement vector field is spatially smoothed. This proposed algorithm exhibits excellent performance in obtaining accurate and smooth distribution of displacement vector which is required to obtain strain distribution and finally shear modulus distribution. We conducted an experiment on an agar phantom which has inhomogeneous shear modulus distribution. Using the proposed method, we obtained 2-D displacement field with reasonable accuracy. We reconstructed a relative shear modulus map using axial strain assuming 1-D stress condition. The reconstructed map using the calculated axial strain through 2-D displacement estimation algorithm was satisfactory, and was clearly superior to the one through 1-D displacement estimation algorithm. The proposed 2-D displacement field estimation algorithm seems to be a versatile and powerful tool to measure strain distribution for the purpose of tissue elasticity estimation under various deformation conditions.
In VLSI or PCB layout, one often encounters a region that is either of rectilinear shape or can be approximated by a rectilinear region. Although many placement methods have been proposed, most of them are applicable only to rectangular regions. For these algorithms to be applied to a rectilinear region, two processing steps, region partitioning and rectangular region cell placement are necessary. Hence, the placement results are so far dependent on the locations of the regions partitioned and frequently become trapped in local minima. Recently, neural networks have been suggested as a new way to resolve the cell placement problem. This paper proposed a unified modeling method that uses a neural net model with additional calibration nodes to model rectilinear region cell placement. In this method, the ideal distance between cells is preserved to simultaneously minimize both the total wire length and the module overlap. Unlike traditional approaches, the proposed algorithm requires only a single processing step. Experiments have been conducted to verify the performance of the proposed algorithm. The total wire length obtained by our method is shorter than those generated by previous methods.
Various authors have proposed probabilistic extensions of Valiant's PAC (Probably Approximately Correct) learning model in which the target to be learned is a (conditional) probability distribution. In this paper, we improve upon the best known upper bounds on the sample complexity of the parameter estimation part of the learning problem for distributions and stochastic rules over a finite domain with respect to the Kullback-Leibler divergence (KL-devergence). In particular, we improve the upper bound of order O(1/ε2) due to Abe, Takeuchi, and Warmuth to a bound of order O(1/ε). In obtaining our results, we made use of the properties of a specific estimator (slightly modified maximum likelihood estimator) with respect to the KL-divergence, while previously known upper bounds were obtained using the uniform convergence technique.
Hisao KOIZUMI Katsuhiko SEO Fumio SUZUKI Yoshisuke OHTSURU Hiroto YASUURA
In this paper we propose a co-design method for control systems using combination of models. By co-design," we mean a cooperative design method in which the behavior of the entire system is simulated as a single model while parameters of the system are being optimized. Our co-design method enables the various subsystems in the system, which have been designed independently as tasks assigned to different designers in the traditional design method, to be designed simultaneously in a unified cooperative way from the system-wide perspective of a system designer. Our proposed method combines models of controlling and controlled subsystems into a single model for the behavior of the entire control system. After the optimum control conditions are determined through simulation of the combined models, based on the corresponding algorithms and parameters, ASIC design proceeds quickly with accurate verification using iterative replacements of the behavior model by the electronic circuit model. To evaluate the proposed method, we implemented a design environment. We then applied our method to the design of ASICs in three test cases (in a control system and in audio-visual systems) to investigate its effectiveness. This paper introduces the concepts of the proposed co-design method, the design environment and the experimental results, and points out the new issues for system design.
Wooi Voon CHANG Toshimitsu USHIO Shigemasa TAKAI Sadatoshi KUMAGAI Shinzo KODAMA
Many typical control problems such as deadlock avoidance problems and mutual exclusion problems can be formulated as forbidden marking problems. This paper studies a forbidden marking problem in controlled complementary-places Petri nets, which are suitable model for sequential control systems. We show a necessary and sufficient condition for the existence of a control law for this problem. We also obtain a maximally permissive control law which allows a maximal number of transitions to fire subject to a condition that forbidden markings will never be reached.
The potential attenuation process of charged human body (HB) is analyzed. A two-dimensional circuit model is presented for predicting the potential attenuation characteristics of the HB charged on the floor. The theoretical equation for the HB potential is derived in the closed form in the Laplacian transformation domain, and the numerical inverse Laplace transform is used to compute it. The half-life or relaxation time of the HB potential for decay is numerically examined with respect to the electrical parameters of shoes. The experiment is also conducted for verifying the validity of the computed result.
Masahiko TOYONAGA Shih-Tsung YANG Isao SHIRAKAWA Toshiro AKINO
This paper describes a new clustering approach for VLSI placement, which is based on a fractal dimension analysis for the topological structure of modules in a logic diagram. A distinctive feature of this approach is that a measure of the 'fractal dimension' has been introduced into a logic diagram in such a way that the clustering of modules is iterated while the fractal dimension among clustered modules is retained in a prescribed range. A part of experimental results is also shown, which demonstrates that our clustering approach raises the placement performance much higher than the conventional clustering methods.
Nozomu TOGAWA Masao SATO Tatsuo OHTSUKI
Technology mapping algorithms for LUT (Look Up Table) based FPGAs have been proposed to transfer a Boolean network into logic-blocks. However, since those algorithms take no layout information into account, they do not always lead to excellent results. In this paper, a simultaneous technology mapping, placement and global routing algorithm for FPGAs, Maple, is presented. Maple is an extended version of a simultaneous placement and global routing algorithm for FPGAs, which is based on recursive partition of layout regions and block sets. Maple inherits its basic process and executes the technology mapping simultaneously in each recursive process. Therefore, the mapping can be done with the placement and global routing information. Experimental results for some benchmark circuits demonstrate its efficiency and effectiveness.
Tetsushi KOIDE Yoshinori KATSURA Katsumi YAMATANI Shin'ichi WAKABAYASHI Noriyoshi YOSHIDA
This paper presents a heuristic floorplanning method that improves the method proposed by Vijayan and Tsay. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method can reduce the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results for MCNC benchmarks showed that the quality of solutions of the proposed method is better than [7],[8] by about 15% on average, and even for the large number of blocks, the proposed method keeps the high quality of solutions.
The methodology for latchup-free design in bipolar and PMOS merged gates, so-called BiPMOS gates, is considered. Although BiPMOS gates can provide higher switching characteristics than conventional, individually drawn, BiCMOS gates even when the supply voltage is reduced, the general methodology to prevent latchup has been lacking. This paper presents an approximate, but sufficiently correct, mathematical technique to solve the Laplace equation, which gives the distribution of latchup trigger current for the given BiPMOS drawings. It is shown that the resistances of the collector plug and the spreading resistance under the base-collector junction greatly influence latchup, and that the well-emitter overlapping space becomes a problem in the case of a single collector. The distribution of latchup triggering current for the double-emitter double collector NPN transistor indicates the optimum position of the source diffusion area.
This paper uses both network analysis and experiments to confirm that the neural network learning algorithm that minimizes output variation (BPV) provides much more robustness than back-propagation (BP) or BP with noise-modified training samples (BPN). Network analysis clarifies the relationship between sample displacement and what and how the network learns. Sample displacement generates variation in the output of the output units in the output layer. The output variation model introduces two types of deformation error, both of which modify the mean square error. We propose a new error which combines the two types of deformation error. The network analysis using this new error considers that BPV learns two types of training samples where the modification is either towards or away from the category mean, which is defined as the center of sample distribution. The magnitude of modification depends on the position of the training sample in the sample distribution and the degree of leaning completion. The conclusions is that BPV learns samples modified towards to the category mean more stronger than those modified away from the category mean, namely it achieves nonuniform learning. Another conclusion is that BPN learns from uniformly modified samples. The conjecture that BPV is much more robust than the other two algorithms is made. Experiments that evaluate robustness are performed from two kinds of viewpoints: overall robustness and specific robustness. Benchmark studies using distorted handprinted Kanji character patterns examine overall robustness and two specifically modified samples (noise-modified samples and directionally-modified samples) examine specific robustness. Both sets of studies confirm the superiority of BPV and the accuracy of the conjecture.
Shoichiro YAMADA Masahiro KASAI
This paper deals with the wire length expressions using differentiable nonlinear functions, as a result they can be used in analytical placement methods. These expressions can be applicable to clique, bipartite-graph, and half-perimeter net models, and quadratic and Manhattan metrics to estimate the wire lengths.
Michio HORIGOME Yoshito KAWASAKI Qin Qin CHEN
This letter deals with the reliability function in the case of periodic preventive replacement of items in order to increase MTBF, that is, two replacement policies; strictly periodic replacement (SPR) and randomly periodic replacement (RPR). We stress on simple introduction of the reliability theory under preventive replacement policies using the Laplace transform and obtain the theoretical results of SPR and RPR. Then these results are applied to the Weibull distribution and finally in order to show useful information of preventive replacement, the numerical results of SPR are provided.
Tadashi MATSUMOTO Kohkichi TSUJI
The structural necessary and sufficient condition for "the transition-liveness means the place-liveness and vice-versa" of a subclass NII of general Petri nets is given as "the place and transition live Petri net, or PTL net, ÑII". Furthermore, "the one-token-condition Petri net, or OTC net,
This letter presents a new method for adaptive control of nonminimum phase discrete-time systems with disturbances based on the technique of pole-zero placement. The long division method is used to decompose apolynomial into a stable polynomial and an unstable one. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.
Shinichiro OHNUKI Tsuneki YAMASAKI Takashi HINATA
The transient scattering of a half sine pulse wave by a conducting rectangular cylinder with an open sidewall is rigorously analyzed by using the point matching method (taking into account the edge condition exactly) combined with the fast inversion of Laplace transform. Numerical results are presented for back scattered and forward scattered responses of the far fields when a half sine pulse is incident on the open side and the closed side of the cylinder. The physical meaning of the transient responses is discussed in detail. The comparison of the responses with those by a perfect conducting rectangular cylinder is presented.
Ikuo ARAI Kazuma MOTOMURA Tsutomu SUZUKI
A method to measure the displacement from the phase rotation of the Doppler signal including the displacement information of the moving body is proposed, where the displacement resolution can be improved 4 times by making the phase rotation faster. Furthermore, this test system is applied in clinical use. The test system is built up by using a two-phase microwave Doppler sensor covering a 10GHz band, where the Doppler frequency is multiplied 4 times by signal processing. Thus, the resolution is improved from a conventional 12.6mm (in case of 11.9GHz) to 3.15mm, and practical utilization has been attained. The microwave Doppler radar system described in this paper is adequate for the displacement measurement for a relatively fast moving body. As a medical sensor for clinical use, measurement examples of head movement in a vestibule examination (vestibule oculomotor reflexive inspection) and finger movement in a cerebellum function test are given. Furthermore by using two sets of this Doppler radar system, a 2-dimensional measurement of head movement is possible.
The physical system is considered more suitable for measurement purposes the greater is its linearity. However, in nature and engineering there are no purely linear physical transducing systems for convertion a primary onformation. The use of the linear features of the system in the measurement process finally causes the drawbacks: systematic error due to nonlinear distortions, low ratio informative signal/ noise, the necessity to evaluate a great number of the a priori parameters of the transducer in order to receive an absolute result, low thermostability because every a priori parameter itself has a temperature dependence. To exclude these drawbacks a method has been developed using nonlinear physical systems in the base of the displacements measurement. In this work is presented the realization of the method using electretic and electrostatic transducer as a converting physical system. A contactless transducer is placed parallelly to the surface of the object which displacements are measured. The transducer is driven to harmonic oscillations. Typical time intervals between even and odd extremums of the transducer output signal are measured. The object displacements are determined according to the changes of the typical time intervals. The method itself has no errors because approximations were not made while deriving the relations. The source of the errors is inaccurate registration of the start and the end of the typical time intervals. In the work are analysed the errors related to the concrete realization devices: analogue differentiator, peak detector and analog digital transducer. It is shown that the measurement is possible only if the physical system is nonlinear. The method is generalized to that case if the function of transformation of ths system has the form f(x) and monotonous character. The results of experimental investigations confirm the theoretical conclusions.
Junichi NAKAYAMA Kenichi NAKAMURA Yasuo YOSHIDA
A systematic method is proposed to generate a random image with a known correlation function and the modified Laplace distribution; the modified Laplace distribution includes the one-side exponential distribution and the Laplace distribution as a special case. Several random images with an isotropic correlation and the modified Laplace distribution are generated and displayed in figures.