Search

Abstract: The recent video coding standard H.264/AVC show extremely higher coding efficiency compare to any other previous standards. H.264/AVC can achieve over 50% of bit rate saving with same quality using the rate–distortion process, but it brings high computational complexity. In this paper, we propose an algorithm that can reduce the complexity of the codec by reducing the block mode decision process adaptively. Block mode decision process in H.264/AVC consists of inter mode decision process and intra mode decision process. We deal with reduction method for inter and intra mode decision. In this paper an efficient method is proposed to reduce the inter mode decision complexity using the direct prediction methods based on block correlation and adaptive rate distortion cost threshold for early stopping. The fast intra mode reduction algorithm based on inter mode information is also proposed to reduce the computational complexity. The experimental results show that the proposed algorithm can achieve up to 63.34–77.39% speed up ratio with a little PSNR loss. Increment in bit requirement is also not much noticeable. [Copyright &y& Elsevier]

Abstract: In this paper, we consider how to optimize I/O server placement in order to improve parallel I/O performance in switch-based clusters. The significant advances in cluster networks in recent years have made it practical to connect tens of thousands of hosts via networks that have enormous and scalable total capacity, and in which communications between a host and any other host incur the same cost. The same cost property frees users from consideration of network contention and allows them to concentrate on load-balancing issues. We formulate the server placement problem on a cluster that has the same cost property as a weighted bipartite matching with the goal of balancing the workload on the I/O nodes. To find an optimal solution to this problem, we propose an algorithm, called Load Balance Matching (LBM), where is the number of compute nodes and is the number of I/O servers. We also investigate server placement for general clusters in which multiple same-cost subclusters are interconnected to form a large cluster. This class of clusters typically adopt irregular topologies that allow the construction of scalable systems with an incremental expansion capability. Also, due to the limited bandwidth on network links between subclusters, network link contention is a major concern when distributing servers over the entire network. We show that finding an optimal placement strategy for general clusters with the goal of minimizing link contention is computationally intractable. To resolve this problem, we propose a hierarchical strategy that places servers in two steps. First, to minimize link contention, we decide which subcluster each server should be assigned to. We propose a tree-based heuristic algorithm, called Load Balance Traversing (LBT), to solve this problem. In the second step, the LBM algorithm decides the location of each server within a subcluster. Our simulation results demonstrate that LBT achieves a significant improvement in parallel I/O performance over four other algorithms, and is near-optimal in some cases. [Copyright &y& Elsevier]

Abstract: This paper presents two new randomized distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Both algorithms, called Alg-Neighbors and Alg-Edges, make use of biased and unbiased dice having faces, and are analyzed in terms of correctness, expected time complexity and rate of convergence. First, the Alg-Neighbors algorithm is presented as a generalization of the Calabrese/França algorithm for dice (or coins) with 2 faces. It is proved that a convenient biasing function applied to all dice changes the expected time complexity from sub-exponential, i.e., (for unbiased dice with faces), to , where is the number of the system’s nodes. Next, it is shown that the Alg-Edges algorithm is able to produce acyclic orientations in steps with high probability, where denotes the total number of edges. Finally, a speed of convergence versus quality of acyclic orientation generation (associated number of colors) tradeoff is identified between Alg-Neighbors and Alg-Edges algorithms. Computational experiments were carried out in order to provide a more accurate description of the behavior of both algorithms. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to study multidimensional continued fraction algorithm over the field of formal power series. In the case of the Brun algorithm by using its homogenous version, we prove that it converges. [Copyright &y& Elsevier]

Abstract: This paper investigates both the precision and the model checking efficiency of abstract models designed to preserve branching time logics w.r.t. a 3-valued semantics. Current abstract models use ordinary transitions to over approximate the concrete transitions, while they use hyper transitions to under approximate the concrete transitions. In this work, we refer to precision measured w.r.t. the choice of abstract states, independently of the formalism used to describe abstract models. We show that current abstract models do not allow maximal precision. We suggest a new class of models and a construction of an abstract model which is most precise w.r.t. any choice of abstract states. As before, the construction of such models might involve an exponential blowup, which is inherent by the use of hyper transitions. We therefore suggest an efficient algorithm in which the abstract model is constructed during model checking, by need. Our algorithm achieves maximal precision w.r.t. the given property while remaining quadratic in the number of abstract states. To complete the picture, we incorporate it into an abstraction-refinement framework. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity , and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of , which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. [Copyright &y& Elsevier]

Abstract: The Singular Value Decomposition (SVD) is a vital problem that finds a place in numerous application domains in science and engineering. As an example, SVDs are used in processing voluminous datasets. Many sequential and parallel algorithms have been proposed to compute SVDs. The best known sequential algorithms take cubic time. This amount of time may not be acceptable especially when the data size is large. Thus parallel algorithms are desirable. In this paper, we present a novel technique for the parallel computation of SVDs. This technique yields impressive speedups. We discuss implementation of our technique on parallel models of computing such as the mesh and the PRAM. We also present an experimental evaluation of our technique. [Copyright &y& Elsevier]

Abstract: The spatiotemporal dynamics of cortical oscillations across human brain regions remain poorly understood because of a lack of adequately validated methods for reconstructing such activity from noninvasive electrophysiological data. In this paper, we present a novel adaptive spatial filtering algorithm optimized for robust source time–frequency reconstruction from magnetoencephalography (MEG) and electroencephalography (EEG) data. The efficacy of the method is demonstrated with simulated sources and is also applied to real MEG data from a self-paced finger movement task. The algorithm reliably reveals modulations both in the beta band (12–30 Hz) and high gamma band (65–90 Hz) in sensorimotor cortex. The performance is validated by both across-subjects statistical comparisons and by intracranial electrocorticography (ECoG) data from two epilepsy patients. Interestingly, we also reliably observed high frequency activity (30–300 Hz) in the cerebellum, although with variable locations and frequencies across subjects. The proposed algorithm is highly parallelizable and runs efficiently on modern high-performance computing clusters. This method enables the ultimate promise of MEG and EEG for five-dimensional imaging of space, time, and frequency activity in the brain and renders it applicable for widespread studies of human cortical dynamics during cognition. [Copyright &y& Elsevier]

Abstract: This paper introduces a new implementation of wavelet packet decomposition which is combined with SPIHT (Set Partitioning in Hierarchical Trees) compression scheme. We provide the analysis of the problems arising from the application of zerotree quantisation based algorithms (such as SPIHT) to wavelet packet transform coefficients. We established the generalized parent–child relationships for wavelet packets, providing complete tree structures for SPIHT. The proposed algorithm can be used for both wavelet dyadic and Wavelet Packet decomposition (WP-SPIHT). An extensive evaluation of the algorithm was performed and it has been shown that WP-SPIHT significantly outperforms base-line SPIHT coder for texture images. For these images the suboptimal WP cost-function enables good enough energy compaction that is efficiently exploited by the WP-SPIHT. [Copyright &y& Elsevier]

Abstract: Boosting algorithms are procedures that “boost” low-accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. In this paper we study boosting in the presence of random classification noise, giving both positive and negative results. We show that a modified version of a boosting algorithm due to Mansour and McAllester (J. Comput. System Sci. 64(1) (2002) 103) can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the “weak learner” satisfies a slightly stronger condition than the usual weak learning guarantee. We give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise. [Copyright &y& Elsevier]

Abstract: Given a simple connected graph and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph remains simple and has at least two internally disjoint paths between u and v for each pair . The problem is known to be NP-hard, and a -approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an time -approximation algorithm to the problem. [Copyright &y& Elsevier]

Abstract: The reductive decision procedure for unavoidable strings was recently shown to have an exponential lower bound. Hence, as a special case of generalized pattern matching, the existence of an efficient algorithm deciding string unavoidability remains an interesting open question. It has been hypothesized that some combination of the four necessary conditions implied by the known decidability results would be sufficient. Three of these criteria are determined in polynomial time, and the fourth provides the needed recursion. In this paper, however, we demonstrate the existence of arbitrarily many avoidable strings meeting any extended conjunction of the four necessary conditions. These insufficiency results are achieved by analyzing the appropriate graphical interpretations of the given algorithms. We provide a new combinatorial operation on the corresponding strings and generate arbitrary counterexamples from an empirically located minimal set. Thus, string unavoidability cannot be efficiently decided by the known reductive method or its immediate implications. [Copyright &y& Elsevier]

Abstract: The cutwidth of a graph G is the smallest integer k such that the vertices of G can be arranged in a linear layout in such a way that, for every , there are at most k edges with one endpoint in and the other in . In this paper we provide, for any constant k, a linear time algorithm that for any input graph G, answers whether G has cutwidth at most k and, in the case of a positive answer, outputs the corresponding linear layout. [Copyright &y& Elsevier]

Abstract: In this paper we present a generic algorithm for factoring polynomials over global fields . As efficient implementations of that algorithm for number fields and function fields differ substantially, these cases will be treated separately. Complexity issues and implementations will be discussed in part II which also contains illustrative examples. [Copyright &y& Elsevier]

Abstract: This paper presents a real-time implementation of Motion-JPEG2000 encoder using a fixed-point DSP chip. Among several modules in JPEG2000 encoder, the lifting algorithm for discrete wavelet transform (DWT) and the embedded block coding with optimized truncation (EBCOT) comprise more than 85% of the encoding complexity. Thus, it is very important to design and optimize these two modules in order to increase the performance of the hardware implementation. First we propose an overlapped block transferring (OBT) method that can significantly improve the performance of the lifting algorithm for DWT by increasing the cache hit rate. We show that the execution time of the lifting scheme can be further reduced by programming the DSP software using the single instruction multiple data (SIMD) instructions and the super scalar pipeline structure. Moreover, we introduce a parallel-pass method for fast implementation of EBCOT. This method reduces the processing time of EBCOT by processing the three coding passes of the same bit-plane in parallel. Experimental results show that our developed Motion-JPEG2000 DSP system meets the common requirement of the real-time video coding [30 frames/s (fps)] and is proven to be a practical and efficient DSP solution. [Copyright &y& Elsevier]