Heui-Seok SEO In Sang CHUNG Yong Rae KWON
This paper presents an approach to specification-based testing of concurrent programs with representative test sequences generated from Statecharts. Representative test sequences are a subset of all possible interleavings of concurrent events that define the behaviors of a concurrent program. Because a program's correctness may be determined by checking whether a program implemented all behaviors in its specification or not, the program can be regarded as being correct if it can supply an alternative execution that has the same effects as the program's behavior with each representative test sequence. Based on this observation, we employ each representative test sequence as a seed to generate an automaton that accepts its equivalent sequences to reveal the same behavior. In order to effectively test a concurrent program, the automaton such generated accepts all sequences equivalent to the representative test sequence and it is used to control test execution. This paper describes an automated process of generating automata from a Statecharts specification and shows how the proposed approach works on Statecharts specifications through some examples.
Atsuo TACHIBANA Shigehiro ANO Toru HASEGAWA Masato TSURU Yuji OIE
Since congestion is very likely to happen in the Internet, locating congested areas (path segments) along a congested path is vital to appropriate actions by Internet Service Providers to mitigate or prevent network performance degradation. We propose a practical method to locate congested segments by actively measuring one-way end-to-end packet losses on appropriate paths from multiple origins to multiple destinations, using a network tomographic approach. Then we conduct a long-term experiment measuring packet losses on multiple paths over the Japanese commercial Internet. The experimental results indicate that the proposed method is able to precisely locate congested segments. Some findings on congestion over the Japan Internet are also given based on the experiment.
The changes in fiber strain and fiber loss with temperature are quantitatively evaluated for 0.5 mm UV-coated fiber and three kind of fiber-optic access cables, for dropping and indoor wiring, employing 0.5 mm UV-coated fiber. Measurements of the fiber strain and loss increase are conducted using a quasi-heterodyne interferometer method and a photon-counting optical-time-domain-reflectmeter, respectively, at 1.3 and 1.55 µ m. From the strain characteristics, the following observations are made: (a) In the temperature range from -40 to 20 the fiber strain followed the cable strain quite closely, thus maintaining a tight cable structure and (b) from 20 to 80, the fiber exhibited a lower strain than the cable strain. Furthermore, no loss increase due to temperature change was observed for the 0.5-mm diameter coated fiber and the three type of optical cables.
Yasuo SATO Shuji HAMADA Toshiyuki MAEDA Atsuo TAKATORI Seiji KAJIHARA
In this paper we introduce a statistical quality model for delay testing that reflects fabrication process quality, design delay margin, and test timing accuracy. The model provides a measure that predicts the chip defect level that cause delay failure, including marginal small delay. We can therefore use the model to make test vectors that are effective in terms of both testing cost and chip quality. The results of experiments using ISCAS89 benchmark data and some large industrial design data reflect various characteristics of our statistical delay quality model.
A novel concurrent core test approach is proposed to reduce the test cost of SOC. Prior to test, the test sets corresponding to cores under test (CUT) are merged by using the proposed merging algorithm to obtain a minimum merged test set. During test, the proposed scan tree architecture is employed to support the concurrent core test using the merged test set. The approach achieves concurrent core test with one scan input and low hardware overhead. Moreover, the approach does not need any additional test generation, and it can be used in conjunction with general compression/decompression techniques to further reduce test cost. Experimental results for ISCAS 89 benchmarks have proven the efficiency of the proposed approach.
Landscapes have been the main theme in Chinese painting for over one thousand years. Chinese ink painting is a form of non-photorealistic rendering. Terrain is the major subject in Chinese landscape painting, and surface wrinkles are important in conveying the orientation of mountains and contributing to the atmosphere. Over the centuries, masters of Chinese landscape painting have developed various kinds of wrinkles. This work develops a set of novel methods for rendering wrinkles in Chinese landscape painting. A three-dimensional terrain is drawn as an outline and wrinkles, using information on the shape, shade and orientation of the terrain's polygonal surface. The major contribution of this work lies in the modeling and implementation of six major types of wrinkles on the surface of terrain, using traditional Chinese brush techniques. Users can select a style of wrinkle and input parameters to control the desired effect. The proposed method then completes the painting process automatically.
This letter studies the effect of node mobility on application-level QoS of audio-video multipath streams in wireless ad hoc networks. The audio-video streams are transmitted with the MultiPath streaming scheme with Media Synchronization control (MPMS), which was previously proposed by the authors. We perform computer simulation with a grid topology network of IEEE 802.11b including two mobile nodes. The simulation results show that MPMS is effective in achieving high application-level QoS in mobile networks as well.
We present a training algorithm to create a neural network (NN) ensemble that performs classification tasks. It employs a competitive decay of hidden nodes in the component NNs as well as a selective deletion of NNs in ensemble, thus named a pruning algorithm for NN ensembles (PNNE). A node cooperation function of hidden nodes in each NN is introduced in order to support the decaying process. The training is based on the negative correlation learning that ensures diversity among the component NNs in ensemble. The less important networks are deleted by a criterion that indicates over-fitting. The PNNE has been tested extensively on a number of standard benchmark problems in machine learning, including the Australian credit card assessment, breast cancer, circle-in-the-square, diabetes, glass identification, ionosphere, iris identification, and soybean identification problems. The results show that classification performances of NN ensemble produced by the PNNE are better than or competitive to those by the conventional constructive and fixed architecture algorithms. Furthermore, in comparison to the constructive algorithm, NN ensemble produced by the PNNE consists of a smaller number of component NNs, and they are more diverse owing to the uniform training for all component NNs.
Canh Quang TRAN Hiroshi KAWAGUCHI Takayasu SAKURAI
A low-power FPGA design approach is proposed based on a fine-grain VDD control scheme called micro-VDD-hopping. Four configurable logic blocks (CLBs) are grouped into one block where VDD is shared. In the micro-VDD-hopping scheme, VDD in each block is changed between VDDH (high VDD) and VDDL (low VDD) spatially and temporally in order to achieve lower power without performance degraded. A low-power level shifter that has less contention is also proposed for low-swing inter-block signals. The FPGA incorporates the Zigzag power-gating scheme, in which special care has been taken to cope with a sneak leakage-path problem. A test chip was fabricated using a 0.35-µm CMOS technology, together with the conventional fixed-VDD FPGA for comparison. Measurement results show that dynamic power in the proposed scheme can be reduced by 86% when a frequency is half of the maximum one. Simulation using a 90-nm CMOS technology shows that leakage power can be reduced by 97%, when the proposed method is used. The area overhead of the proposed FPGA is 2%.
Scaling of CMOS Integrated Circuit is becoming difficult, due mainly to rapid increase in power dissipation. How will the semiconductor technology and industry develop? This paper discusses challenges and opportunities in system LSI from three levels of perspectives: transistor level (physics), IC level (electronics), and business level (economics).
Since their inception almost fifty years ago, hidden Markov models (HMMs) have have become the predominant methodology for automatic speech recognition (ASR) systems--today, most state-of-the-art speech systems are HMM-based. There have been a number of ways to explain HMMs and to list their capabilities, each of these ways having both advantages and disadvantages. In an effort to better understand what HMMs can do, this tutorial article analyzes HMMs by exploring a definition of HMMs in terms of random variables and conditional independence assumptions. We prefer this definition as it allows us to reason more throughly about the capabilities of HMMs. In particular, it is possible to deduce that there are, in theory at least, no limitations to the class of probability distributions representable by HMMs. This paper concludes that, in search of a model to supersede the HMM (say for ASR), rather than trying to correct for HMM limitations in the general case, new models should be found based on their potential for better parsimony, computational requirements, and noise insensitivity.
Kouichi YAMAGUCHI Muneo FUKAISHI
This paper describes a BIST circuit for testing SoC integrated multi-channel serializer/deserializer (SerDes) macros. A newly developed packet-based PRBS generator enables the BIST to perform at-speed testing of asynchronous data transfers. In addition, a new technique for chained alignment checks between adjacent channels helps achieve a channel-count-independent architecture for verification of multi-channel alignment between SerDes macros. Fabricated in a 0.13-µm CMOS process and operating at > 500 MHz, the BIST has successfully verified all SerDes functions in at-speed testing of 5-Gbps20-ch SerDes macros.
The spatial distribution of the electric field in the low to high frequency bands radiated from printed circuit board (PCB) should be estimated continuously from near to far field. The characteristic of the electric field distribution is analyzed by the FDTD-multiple analysis space (FDTD-MAS) method, which can analyze from near to far field continuously, and compared with measured results. Since the analyzed electric field distribution is good agreement with measured results, it is suggested that the continuous distribution for electric field from near to far field can be calculated by the FDTD-MAS method. The electric field at low frequency is larger than that at high frequency within 1 m.
Son-Hong NGO Xiaohong JIANG Susumu HORIGUCHI
We propose an ant-based algorithm to improve the alternate routing scheme for dynamic Routing and Wavelength Assignment (RWA) in all-optical wavelength-division- multiplexing (WDM) networks. In our algorithm, we adopt a novel twin routing table structure that comprises both a P-route table for connection setup and a pheromone table for ants' foraging. The P-route table contains P alternate routes between a source-destination pair, which are dynamically updated by ant-based mobile agents based on current network congestion information. Extensive simulation results upon the ns-2 network simulator indicate that by keeping a suitable number of ants in a network to proactively and continually update the twin routing tables in the network, our new ant-based alternate routing algorithm can result in a small setup time and achieve a significantly lower blocking probability than the promising alternate shortest-path (ASP) algorithm and the fixed-paths least congestion (FPLC) algorithm for dynamic RWA even with a small value of P.
The concept of grid computing emerged with the appearance of high-speed network. Effective grid worker (i.e., computing resource) selection mechanism is important to achieve reliable grid computing system since each worker participate in grid computing is heterogeneous. In this paper, we suggest a credible worker selection mechanism that maximizes grid computing performance by allocating appropriate tasks to each grid worker. Diverse workers can be used efficiently by grid applications through the ranking process of worker's credibility. Initially, the rank of each grid worker's credibility is decided considering static information only such as CPU speed, RAM size, storage capacity and network bandwidth. And then, the rank is refined by using dynamic information such as failure rate, turn around time provided after the task is completed, and correctness of the return value. In the experiments, we find that the proposed mechanism provides improved grid computing performance with high credibility.
Mobile applications require software reconfiguration to improve resource usage and availability. We propose a power-aware reconfiguration scheme that (1) moves energy-demanding applications to proxy servers, and (2) adjusts the fidelity of mobile applications as resources diminish. We formulate a cooperative reconfiguration plan which determines when, where, and which components should be deployed and have their fidelity controlled, so as to minimize the power consumption of mobile devices and to utilize the system resources of servers efficiently. We then construct a graph-theoretic model of the cost of migrating components to one proxy server or to a cluster of servers. In this model, changes to the residual energy of mobile devices, available server resources, and the wireless network bandwidth can all accelerate or decelerate the migration and fidelity control of applications. We suggest an approximation algorithm that achieves a near-optimal solution in terms of energy consumption. Our proposal will support mobile applications which require large amount of computation and need to maintain their services for an extended time such as video conferencing, multimedia e-mail, and real-time navigation. Simulation-based experiments verify that our scheme is an efficient way to extend the battery life of mobile devices and to improve the response time of mobile applications.
Jyh Perng FANG Yang-Shan TONG Sao Jie CHEN
In the floorplan design of System-on-Chip (SOC), Buffer Site Approach (BSA) has been used to relax the buffer congestion problem. However, for a floorplan with dominant wide bus, BSA may instead worsen the congestion. Our proposed Enhanced Buffer Site Approach (EBSA) extends existing BSA in a way that buffers of dominant wide bus can be distributed more evenly while reserving the same fast operation speed as BSA does. Experiments have been performed to integrate our model into an iterative floorplanning algorithm, and the results reveal that buffer congestion in a floorplan with dominant wide bus can be much abated.
Hiroshi YAMAMOTO Kenji KAWAHARA Tetsuya TAKINE Yuji OIE
Recent improvements in the performance of end-computers and networks have made it feasible to construct a grid system over the Internet. A grid environment consists of many computers, each having a set of components and a distinct performance. These computers are shared among many users and managed in a distributed manner. Thus, it is important to focus on a situation in which the computers are used unevenly due to decentralized management by different task schedulers. In this study, which is a preliminary investigation of the performance of task allocation schemes employed in a decentralized environment, the average execution time of a long-lived task is analytically derived using the M/G/1-PS queue. Furthermore, assuming a more realistic condition, we evaluate the performance of some task allocation schemes adopted in the analysis, and clarify which scheme is applicable to a realistic grid environment.
Takaaki MANABE Jun Hyun AHN Iwao YAMAGUCHI Mitsugu SOHMA Wakichi KONDO Ken-ichi TSUKADA Kunio KAMIYA Susumu MIZUTA Toshiya KUMAGAI
The 5-cm-diameter double-sided YBa2Cu3O7 (YBCO) films were prepared by metal organic deposition (MOD) using a commercially available metal-naphthenate coating solution. Firstly, YBCO film was prepared by MOD on one side of a double-side-polished 5-cm-diameter LaAlO3 substrate. Secondly, another side was similarly coated with YBCO by MOD. After the latter processing, degradation of average Jc value in the first side was not observed; but the fluctuation of critical current density Jc slightly increased. The double-sided YBCO films showed average Jc values of 0.8-1.0 MA/cm2 at 77 K and microwave surface resistances Rs(12 GHz) of 0.86-1.07 mΩ at 70 K.
Che-Wun CHIOU Chiou-Yng LEE An-Wen DENG Jim-Min LIN
Because fault-based attacks on cryptosystems have been proven effective, fault diagnosis and tolerance in cryptography have started a new surge of research and development activity in the field of applied cryptography. Without magnitude comparisons, the Montgomery multiplication algorithm is very attractive and popular for Elliptic Curve Cryptosystems. This paper will design a Montgomery multiplier array with a bit-parallel architecture in GF(2m) with concurrent error detection capability to protect it against fault-based attacks. The robust Montgomery multiplier array with concurrent error detection requires only about 0.2% extra space overhead (if m=512 is as an example) and requires four extra clock cycles compared to the original Montgomery multiplier array without concurrent error detection.