1,721,078 research outputs found
New Area-Time Lower Bounds for the Multidimensional DFT
Get PDFArea-time lower bounds are derived for the VLSI computation of the (n1 x n2 x ... nd)-point multidimensional DFT (MDDFT) over different types of rings and different types of input/output protocols. First, an AT^2 = Ω((N log|R|)^2) bound is obtained for any finite ring R, where N = n1 x n2 x ... x nd, for any word-local protocol. The bound was previously known for the special case when R = Z_M, the ring of integers modulo M.
Second, an AT^2 = Ω((Nb)^2) word-local bound is derived when R is the complex field, the components of the input are fixed-point numbers of b bits, and the precision of the output components guarantees that the resulting approximate transform is injective. No area-time lower bound was previously known for the DFT over the complex field.
Third, an AT^2 = Ω((N log|R|)^2) bound is derived when R = GF(p^m) is a finite field of polynomials of degree m with coefficients in Z_p, for certain classes of non word-local protocols. This is the first area-time lower bound derived for the DFT with I/O protocols that are not word-local
A General PRAM Simulation for Clustered Machines
No full textWe present a general deterministic scheme to implement a shared memory abstraction on any distributed-memory machine which exhibits a clustered structure. More specifically, we develop a memory distribution strategy and an access protocol for the Decomposable BSP (D-BSP), a generic machine model whose bandwidth/latency parameters can be instantiated to closely reflect the characteristics of machines that admit a hierarchical decomposition into independent clusters. Our scheme achieves provably optimal slowdown for those machines where delays due to latency dominate over those due to bandwidth limitations. For machines where this is not the case, the slowdown is a mere logarithmic factor away from the natural bandwidth-based lower bound
Translating Submachine Locality into Locality of Reference
No full textThe design of algorithms exhibiting a high degree of temporal and spatial locality of reference is crucial to attain good performance on current and foreseeable computing systems featuring ever deeper memory hierarchies. Previous work has demonstrated that task parallelism can be efficiently transformed into locality of reference in two-level hierarchies. Recently, we moved a step forward and showed how the more structured type of parallelism exposed by submachine locality can be efficiently turned into temporal locality on arbitrarily deep hierarchies. In this work, we complete and extend the above result by encompassing also spatial locality. Specifically, we present a scheme to simulate parallel algorithms designed for the Decomposable BSP (a BSP variant which captures submachine locality) on the Hierarchical Memory Model with Block Transfer. The simulation yields good hierarchy-conscious sequential algorithms from parallel ones, and provides evidence of the strict relation between submachine locality in parallel computation and locality of reference (both temporal and spatial) in the hierarchical memory setting
Translating submachine locality into locality of reference
No full textIn this work, we show that the submachine locality exposed by hierarchical bulk-synchronous computations can be efficiently turned into locality of reference on arbitrarily deep hierarchies. Specifically, we develop efficient schemes to simulate parallel programs written for the Decomposable BSP (a BSP variant which features a hierarchical decomposition into submachines) on the sequential Hierarchical Memory Model (HMM), which rewards the exploitation of temporal locality, and on its extension with block transfer, the BT model, which also rewards the exploitation of spatial locality. The simulations yield good hierarchy-conscious sequential algorithms from parallel ones, and provide evidence of the strict relation between submachine locality in parallel computation and locality of reference in the hierarchical memory setting. We also devise a generalization of the HMM result to the self-simulation of D-BSP augmented with hierarchical memory modules, which yields an interesting analog of Brent's lemma, thus proving that the enhanced model features a seamless integration of memory and network hierarchies
Accessing Tape Music Documents on Mobile Devices
No full textThe aim of this article is to present and discuss an innovative methodology aimed at accessing digitized copies of historical tape music audio documents; the methodology leverages on the multimedia and multisensory capabilities of mobile devices to provide an unprecedented level of fruition. In addition to the methodology, and stemming from it, we present an actual software application for Android tablet devices. This novel piece of software was designed and developed in a multidisciplinary team involving engineers as well as musicians, composers, and archivists. The strongest element in our work is the fact that it follows a rigorous process and it is based on the principles of philological awareness; thus, it also takes into consideration the critical points in the musicologist's domain such as (i) the definition of preservation (i.e., master) copy, (ii) the importance of secondary information, (iii) the history of production and transmission of audio documents
Implementing Shared Memory on Clustered Machines (Extended Abstract)
No full textWe present a general deterministic scheme to implement a shared memory abstraction on any distributed-memory machine which exhibits a clustered structure. More specifically, we develop a memory distribution strategy and an access protocol for the Decomposable BSP (D-BSP), a generic machine model whose bandwidth/latency parameters can be instantiated to closely reflect the characteristics of machines that admit a hierarchical decomposition into independent clusters. Our scheme achieves provably optimal slowdown for those machines where delays due to latency dominate over those due to bandwidth limitations. For machines where this is not the case, the slowdown is a mere logarithmic factor away from the natural bandwidth-based lower bound. An important feature of the scheme is that it can be made fully constructive for small memory sizes, while for larger sizes it relies solely on nonconstructive graphs of weak expansion
Heterogeneous Ensembles for the Missing Feature Problem
Get PDFMissing values are ubiquitous in real-world datasets. In this work, we show how to handle them with heterogeneous ensembles of classifiers that outperform state-of-the-art solutions. Several approaches are compared using several different datasets. Some state-of-the-art classifiers, e.g., SVM and RotBoost, are tested first and coupled with the Expectation-Maximization (EM) imputation method. The classifiers are then combined to build ensembles. Using the Wilcoxon signed-rank test (reject the null hypothesis, level of significance 0.05), we show that our best heterogeneous ensembles, obtained by combining a forest of decision trees (a method that does not require any dataset-specific tuning) with a cluster-based imputation method, outperforms two dataset-tuned solutions: a stand-alone SVM classifier and a random subspace of SVMs, both based on LibSVM, the most widely used SVM toolbox in the world. Our heterogeneous ensembles also exhibit better performance than a recent cluster-based imputation method for handling missing values (a method which has been shown to outperform several other state-of-the-art imputation approaches) when both the training set and the testing set contain 10% missing values
Factorized Sparse Approximate Inverses on GPUs
No full textGPUs exhibit significantly higher peak performance than conventional CPUs. However, due to their programming model and microarchitecture, only highly parallel algorithms can exploit their full potential. In this context, the FSAI preconditioner may represent – with its inherent parallelism – an optimal candidate for the conjugate gradient-like solution of sparse linear systems. While its application to a vector involves only matrix-vector products, a GPU-based implementation requires a nontrivial recasting of multiple computational steps
A GPU implementation of the Factored Sparse Approximate Inverse preconditioner for the iterative solution of SPD linear systems
No full text- …
