1-15hit |
Yi GUO Heming SUN Ping LEI Shinji KIMURA
Approximate computing has emerged as a promising approach for error-tolerant applications to improve hardware performance at the cost of some loss of accuracy. Multiplication is a key arithmetic operation in these applications. In this paper, we propose a low-cost approximate multiplier design by employing new probability-driven inexact compressors. This compressor design is introduced to reduce the height of partial product matrix into two rows, based on the probability distribution of the sum result of partial products. To compensate the accuracy loss of the multiplier, a grouped error recovery scheme is proposed and achieves different levels of accuracy. In terms of mean relative error distance (MRED), the accuracy losses of the proposed multipliers are from 1.07% to 7.86%. Compared with the Wallace multiplier using 40nm process, the most accurate variant of the proposed multipliers can reduce power by 59.75% and area by 42.47%. The critical path delay reduction is larger than 12.78%. The proposed multiplier design has a better accuracy-performance trade-off than other designs with comparable accuracy. In addition, the efficiency of the proposed multiplier design is assessed in an image processing application.
Yukihiro SASAGAWA Jun YAO Yasuhiko NAKASHIMA
Razor Flip-Flop (FF) is a good combination for the dynamic voltage scaling (DVS) technique to achieve high energy efficiency. We previously proposed a RazorProtector scheme, which uses, under a very high IR-drop zone, a redundant data-path to provide a very fast recovery for a Razor-FF based processor. In this paper, we propose a dynamic method to adjust the redundancy level to fine-grained fit both the program behaviors and processor manufacturing variations so as to achieve an optimal power saving. We design an online turning method to adjust the redundancy level according to the most related parameters, ILP (Instruction Level Parallelism) and DCF (Delay Criticality Factor). Our simulation results show that under a workload suite with different behaviors, the adaptive redundancy can achieve better Energy Delay Product (EDP) reduction than any static controls. Compared to the traditional application of Razor-FF and DVS, our proposed dynamic control achieves an EDP reduction of 56% in average for the workloads we studied.
Xiuyan JIANG Dejian YE Yiming CHEN Xuejun TIAN
Smart TVs are expected to play a leading role in the future networked intelligent screen market. Currently, many operators are planning to deploy it in large scale in a few years. Therefore, it is necessary for smart TVs to provide high quality services for users. Packet loss is one critical reason that decreases the QoS in smart TVs. Even a very small amount of packet loss (1-2%) can decrease the QoS and affect users' experience seriously. This paper applies stochastic differential equations to analyzing the queue in the buffer of access points in smart TV multicast systems, demonstrates the reason for packet loss, and then proposes an end-to-end error recovery scheme (short as OPRSFEC) whose core algorithm is based on Reed-Solomon theory, and optimizes four aspects in finite fields: 1) Using Cauchy matrix instead of Vandermonde matrix to code and decode; 2) generating inverse matrix by table look-up; 3) changing the matrix multiplication into the table look-up; 4) originally dividing the matrix multiplication. This paper implements the scheme on the application layer, which screens the heterogeneity of terminals and servers, corrects 100% packet loss (loss rate is 1%-2%) in multicast systems, and brings very little effect on real-time users experience. Simulations demonstrate that the proposed scheme has good performances, successfully runs on Sigma and Mstar Moca TV terminals, and increases the QoS of smart TVs. Recently, OPRSFEC middleware has become a part of IPTV2.0 standard in Shanghai Telecom and has been running on the Mstar boards of Haier Moca TVs properly.
Yukihiro SASAGAWA Jun YAO Takashi NAKADA Yasuhiko NAKASHIMA
Recently, the DVS (Dynamic Voltage Scaling) method has been aggressively applied to processors with Razor Flip-Flops. With Razor FF detecting setup errors, the supply voltage in these processors is down-scaled to a near critical setup timing level for a maximum power consumption reduction. However, the conventional Razor and DVS combinations cannot tolerate well error rate variations caused by IR-drops and environment changes. At the near critical setup timing point, even a small error rate change will result in sharp performance degradation. In this paper, we propose RazorProtector, a DVS application method based on a redundant data-path which uses a multi-cycle redundant calculation to shorten the recovery penalty after a setup error occurrence. A dynamic redundancy-adapting scheme is also given to use effectively the designed redundant data-path based on a study of the program, device and error rate characteristics. Our results show that RazorProtector with the adaptive redundancy architecture can, compared to the traditional DVS method with Razor FF, under a large setup rate caused by a 10% unwanted voltage drop, reduce EDP up to 78% at 100 µs/V, 88% at 200 µs/V voltage scaling slope.
Young H. JUNG Hong-Sik KIM Yoonsik CHOE
This paper describes a channel-adaptive packet scheduler for improved error control performance in a peer-cooperative distributed media streaming system. The proposed packet-scheduling algorithm was designed for the case in which streaming server peers rely on an error-recovery strategy using retransmission and application-layer automatic repeat request rather than error protection using forward error correction. The proposed scheduler can maximize retransmission opportunities and reduce the frame loss rate by using the observed channel status from each server peer. Simulation results show that the proposed algorithm enhances error-recovery performance in distributed multimedia streaming better than other schedulers.
Masato KITAKAMI Teruki KAWASAKI
Since the compressed data, which are frequently used in computer systems and communication systems, are very sensitive to errors, several error recovery methods for data compression have been proposed. Error recovery method for LZ77 coding, one of the most popular universal data compression methods, has been proposed. This cannot be applied to LZSS coding, a variation of LZ77 coding, because its compressed data consist of variable-length codewords. This paper proposes a burst error recovery method for LZSS coding. The error sensitive part of the compressed data are encoded by unary coding and moved to the beginning of the compressed data. After these data, a synchronization sequence is inserted. By searching the synchronization sequence, errors in the error sensitive part are detected. The errors are recovered by using a copy of the part. Computer simulation says that the compression ratio of the proposed method is almost equal to that of LZ77 coding and that it has very high error recovery capability.
Depeng JIN Shijun LIN Li SU Lieguang ZENG
Motivated by different error characteristics of each path, we propose a study-based error recovery scheme for Networks-on-Chip (NoC). In this scheme, two study processes are executed respectively to obtain the characteristics of the errors in every link first; and then, according to the study results and the selection rule inferred by us, this scheme selects a better error recovery scheme for every path. Simulation results show that compared with traditional simple retransmission scheme and hybrid single-error-correction, multi-error-retransmission scheme, this scheme greatly improves the throughput and cuts down the energy consumption with little area increase.
Masato KITAKAMI Satoshi NAKAMURA
Although data compression is popularly used, compressed data have a problem that they are very sensitive to errors. This paper proposes a single burst error recovery method for Huffman coding by using the bidirectionally decodable Huffman coding. Computer simulation shows that the proposed method can recover 2.5lburst bits burst error with high probability, where lburst is the maximum length of burst errors which the proposed method is expected to be able to recover.
Hongyuan CHEN Masato KITAKAMI Eiji FUJIWARA
One of the disadvantages of compressed data is their vulnerability, that is, even a single corrupted bit in compressed data may destroy the decompressed data completely. Therefore, Variable-to-Fixed length Arithmetic Coding, or VFAC, with error detecting capability is discussed. However, implementable error recovery method for compressed data has never been proposed. This paper proposes Burst Error Recovery Variable-to-Fixed length Arithmetic Coding, or BERVFAC, as well as Error Detecting Variable-to-Fixed length Arithmetic Coding, or EDVFAC. Both VFAC schemes achieve VF coding by inserting the internal states of the decompressor into compressed data. The internal states consist of width and offset of the sub-interval corresponding to the decompressed symbol and are also used for error detection. Convolutional operations are applied to encoding and decoding in order to propagate errors and improve error control capability. The proposed EDVFAC and BERVFAC are evaluated by theoretical analysis and computer simulations. The simulation results show that more than 99.99% of errors can be detected by EDVFAC. For BERVFAC, over 99.95% of l-burst errors can be corrected for l 32 and greater than 99.99% of other errors can be detected. The simulation results also show that the time-overhead necessary to decode the BERVFAC is about 12% when 10% of the received words are erroneous.
Masami SHISHIBORI Kazuaki ANDO Yuuichirou KASHIWAGI Jun-ichi AOE
Natural language interface systems can accept more unrestricted queries from users than other systems, however it is impossible to understand erroneous sentences which include the syntax errors, unknown words and misspelling. In order to realize the superior natural language interface, the automatic error correction for erroneous sentences is one of problems to be solved. The method to apply the LR parsing strategies is one of the famous approaches as the robust error recovery scheme. This method is able to obtain a high correction accuracy, however it takes a great deal of time to parse the sentence, such that it becomes a very important task to improve the time-cost. In this paper, we propose the method to improve the time efficiency, keeping the correction accuracy of the traditional method. This method makes use of a new parsing table that denotes the states to be transited after accepting each symbol. By using this table, the symbol which is allocated just after the error position can be utilized for selecting correction symbols, as a result, the number of candidates produced on the correction process is reduced, and fast system can be realized. The experiment results, using 1,050 sentences including error characters, show that this method can correct error points 69 times faster than the traditional method, also keep the same correction accuracy as the traditional method.
In a decentralised system the problems of fault tolerance, and in particular error recovery, vary greatly depending on the design assumptions. For example, in a distributed database system, if one disregards the possibility of undetected invalid inputs or outputs, the errors that have to be recovered from will just affect the database, and backward error recovery will be feasible and should suffice. Such a system is typically supporting a set of activities that are competing for access to a shared database, but which are otherwise essentially independent of each other--in such circumstances conventional database transaction processing and distributed protocols enable backward recovery to be provided very effectively. But in more general systems the multiple activities will often not simply be competing against each other, but rather will at times be attempting to co-operate with each other, in pursuit of some common goal. Moreover, the activities in decentralised systems typically involve not just computers, but also external entities that are not capable of backward error recovery. Such additional complications make the task of error recovery more challenging, and indeed more interesting. This paper provides a brief analysis of the consequences of various such complications, and outlines some recent work on advanced error recovery techniques that they have motivated.
Yeali S. SUN Fu-Ming TSOU Meng Chang CHEN
As the current Internet becomes popular in information access, demands for real-time display and playback of continuous media are ever increasing. The applications include real-time audio/video clips embedded in WWW, electronic commerce, and video-on-demand. In this paper, we present a new control protocol R3CP for real-time applications that transmit stored MPEG video stream over a lossy and best-effort based network environment like the Internet. Several control mechanisms are used: a) packet framing based on the meta data; b) adaptive queue-length based rate control scheme; c) data preloading; and d) look-ahead pre-retransmission for lost packet recovery. Different from many adaptive rate control schemes proposed in the past, the proposed flow control is to ensure continuous, periodic playback of video frames by keeping the receiver buffer queue length at a target value to minimize the probability that player finds an empty buffer. Contrary to the widespread belief that "Retransmission of lost packets is unnecessary for real-time applications," we show the effective use of combining look-ahead pre-retransmission control with proper data preloading and adaptive rate control scheme to improve the real-time playback performance. The performance of the proposed protocol is studied via simulation using actual video traces and actual delay traces collected from the Internet. The simulation results show that R3CP can significantly improve frame playback performance especially for transmission paths with poor packet delivery condition.
Kazuyuki SHIMA Ken-ichi MATSUMOTO Koji TORII
We present a comparison of correlated failures for multiversion software using community error recovery (CER) and software breeding (SB). In CER, errors are detected and recovered at checkpoints which are inserted in all the versions of the software. SB is analogous to the breeding of plants and animals. In SB, versions consist of loadable modules, and a driver exchanges the modules between versions to detect and eliminate faulty modules. We formulate reliability models to estimate the probability of failure for software using either CER or SB. Our reliability models assume failures in the checkpoints in CER and the driver in SB. We use beta-binomial distribution for modeling correlated failures of versions, because much of the evidence suggests that the assumption that failures in versions occur independently is not always true. Our comparison indicates that multiversion software using SB is more reliable than that using CER when the probability of failure in the checkpoints in CER or the driver in SB is 10-7.
This paper focuses on recovering from processor transient faults in pipelined multiprocessor systems. A pipelined machine may employ out of order execution and branch prediction techniques to increase performance, thus a precise computation state would not be available. We propose an efficient scheme to maintain the precise computation state in a pipelined machine. The goal of this paper is to implement checkpointing and rollback recovery utilizing the technique of precise interrupt in a pipelined system. Detailed analysis is included to demonstrate the effectiveness of this method.
Ingrid KIRSCHNING Jun-Ichi AOE
The Time-Slicing paradigm is a newly developed method for the training of neural networks for speech recognition. The neural net is trained to spot the syllables in a continuous stream of speech. It generates a transcription of the utterance, be it a word, a phrase, etc. Combined with a simple error recovery method the desired units (words or phrases) can be retrieved. This paradigm uses a recurrent neural network trained in a modular fashion with natural connectionist glue. It processes the input signal sequentially regardless of the input's length and immediately extracts the syllables spotted in the speech stream. As an example, this character string is then compared to a set of possible words, picking out the five closest candidates. In this paper we describe the time-slicing paradigm and the training of the recurrent neural network together with details about the training samples. It also introduces the concept of natural connectionist glue and the recurrent neural network's architecture used for this purpose. Additionally we explain the errors found in the output and the process to reduce them and recover the correct words. The recognition rates of the network and the recovery rates for the words are also shown. The presented examples and recognition rates demonstrate the potential of the time-slicing method for continuous speech recognition.