Monthly Archives: August 2015

Polyhedral AST Generation is More than Scanning Polyhedra

Polyhedral AST Generation is More than Scanning Polyhedra

  • Sven Verdoolaege, Tobias Grosser, and Albert Cohen. Polyhedral AST Generation is More than Scanning Polyhedra. Acm transactions on programming languages and systems, 37(4):12:1-12:50, 2015. doi:10.1145/2743016
    [BibTeX] [Abstract]

    Abstract mathematical representations such as integer polyhedra have been shown to be useful to precisely analyze computational kernels and to express complex loop transformations. Such transformations rely on abstract syntax tree (AST) generators to convert the mathematical representation back to an imperative program. Such generic AST generators avoid the need to resort to transformation-specific code generators, which may be very costly or technically difficult to develop as transformations become more complex. Existing AST generators have proven their effectiveness, but they hit limitations in more complex scenarios. Specifically, (1) they do not support or may fail to generate control flow for complex transformations using piecewise schedules or mappings involving modulo arithmetic; (2) they offer limited support for the specialization of the generated code exposing compact, straightline, vectorizable kernels with high arithmetic intensity necessary to exploit the peak performance of modern hardware; (3) they offer no support for memory layout transformations; and (4) they provide insufficient control over the AST generation strategy, preventing their application to complex domain-specific optimizations. We present a new AST generation approach that extends classical polyhedral scanning to the full generality of Presburger arithmetic, including existentially quantified variables and piecewise schedules, and introduce new optimizations for the detection of components and shifted strides. Not limiting ourselves to control flow generation, we expose functionality to generate AST expressions from arbitrary piecewise quasi-affine expressions, which enables the use of our AST generator for data-layout transformations. We complement this with support for specialization by polyhedral unrolling, user-directed versioning, and specialization of AST expressions according to the location at which they are generated, and we complete this work with fine-grained user control over the AST generation strategies used. Using this generalized idea of AST generation, we present how to implement complex domain-specific transformations without the need to write specialized code generators, but instead relying on a generic AST generator parametrized to a specific problem domain.

    @Article{2015-08-VERDOOLAEGE,
    author = {Sven Verdoolaege and Tobias Grosser and Albert Cohen},
    title = {{Polyhedral {AST} Generation is More than Scanning Polyhedra}},
    journal = {ACM Transactions on Programming Languages and Systems},
    date = {2015-08},
    volume = {37},
    number = {4},
    year = {2015},
    pages = {12:1-12:50},
    doi = {10.1145/2743016},
    publisher = {ACM},
    address = {New York, NY, USA},
    abstract = {Abstract mathematical representations such as integer polyhedra have been shown to be useful to precisely analyze computational kernels and to express complex loop transformations. Such transformations rely on abstract syntax tree (AST) generators to convert the mathematical representation back to an imperative program. Such generic AST generators avoid the need to resort to transformation-specific code generators, which may be very costly or technically difficult to develop as transformations become more complex. Existing AST generators have proven their effectiveness, but they hit limitations in more complex scenarios. Specifically, (1) they do not support or may fail to generate control flow for complex transformations using piecewise schedules or mappings involving modulo arithmetic; (2) they offer limited support for the specialization of the generated code exposing compact, straightline, vectorizable kernels with high arithmetic intensity necessary to exploit the peak performance of modern hardware; (3) they offer no support for memory layout transformations; and (4) they provide insufficient control over the AST generation strategy, preventing their application to complex domain-specific optimizations.
    We present a new AST generation approach that extends classical polyhedral scanning to the full generality of Presburger arithmetic, including existentially quantified variables and piecewise schedules, and introduce new optimizations for the detection of components and shifted strides. Not limiting ourselves to control flow generation, we expose functionality to generate AST expressions from arbitrary piecewise quasi-affine expressions, which enables the use of our AST generator for data-layout transformations. We complement this with support for specialization by polyhedral unrolling, user-directed versioning, and specialization of AST expressions according to the location at which they are generated, and we complete this work with fine-grained user control over the AST generation strategies used. Using this generalized idea of AST generation, we present how to implement complex domain-specific transformations without the need to write specialized code generators, but instead relying on a generic AST generator parametrized to a specific problem domain.}
    }

Posted in Dissemination | Leave a comment
Acoustic Direction Finding In Highly Reverberant Environment With Single Acoustic Vector Sensor

Acoustic Direction Finding In Highly Reverberant Environment With Single Acoustic Vector Sensor

  • Metin Aktas, Toygar Akgün, and Hüseyin Özkan. Acoustic Direction Finding In Highly Reverberant Environment With Single Acoustic Vector Sensor. In Proceedings of the 23rd European Signal Processing Conference (EUSIPCO 2015), pages 2301-2305, Nice, France, 2015. doi:10.1109/EUSIPCO.2015.7362795
    [BibTeX] [Abstract]

    We propose a novel wideband acoustic direction finding method for highly reverberant environments using measurements from a single Acoustic Vector Sensor (AVS). Since an AVS is small in size and can be effectively used within the full acoustic frequency bands, the proposed solution is suitable for wideband acoustic source localization. In particular, we introduce a novel approach to extract the signal portions that are not distorted with multipath signals and noise. We do not make any stochastic and sparseness assumptions regarding the underlying signal source. Hence, our approach can be applied to a wide range of wideband acoustic signals. We present experiments with acoustic signals that are specially exposed to long reverberations, where the Signal-to-Noise Ratio is as low as 0 dB. In these experiments, the proposed method reliably estimates the source direction with less than 5 degrees of error even under the introduced significantly high reverberation conditions.

    @InProceedings{2015-08-AKTAS,
    author = {Metin Aktas and Toygar Akg\"{u}n and H\"{u}seyin \"{O}zkan},
    title = {{Acoustic Direction Finding In Highly Reverberant Environment With Single Acoustic Vector Sensor}},
    booktitle = {{Proceedings of the 23rd European Signal Processing Conference (EUSIPCO 2015)}},
    date = {2015-08-31/2015-09-04},
    pages = {2301-2305},
    doi = {10.1109/EUSIPCO.2015.7362795},
    address = {Nice, France},
    abstract = {We propose a novel wideband acoustic direction finding method for highly reverberant environments using measurements from a single Acoustic Vector Sensor (AVS). Since an AVS is small in size and can be effectively used within the full acoustic frequency bands, the proposed solution is suitable for wideband acoustic source localization. In particular, we introduce a novel approach to extract the signal portions that are not distorted with multipath signals and noise. We do not make any stochastic and sparseness assumptions regarding the underlying signal source. Hence, our approach can be applied to a wide range of wideband acoustic signals. We present experiments with acoustic signals that are specially exposed to long reverberations, where the Signal-to-Noise Ratio is as low as 0 dB. In these experiments, the proposed method reliably estimates the source direction with less than 5 degrees of error even under the introduced significantly high reverberation conditions.},
    year = {2015}
    }

Posted in Dissemination | Leave a comment
Metodo y sistema de localizacion espacial mediante marcadores luminosos para cualquier ambiente

Metodo y sistema de localizacion espacial mediante marcadores luminosos para cualquier ambiente

  • Eugenio Villar Bonet, Patricia Maria Martínez Mediavilla, Francisco José Alcalà Galàn, Pablo Pedro Sànchez Espeso, and Víctor Fernàndez Solorzano. Método y sistema de localización espacial mediante marcadores luminosos para cualquier ambiente. Patent (ES-2543038-B2), Universidad de Cantabria, Spain, 2015.
    [BibTeX]
    @Misc{2015-08-VILLAR,
    author = {Eugenio {Villar Bonet} and Patricia Maria {Mart\'{i}nez Mediavilla} and Francisco Jos\'{e} {Alcal\`{a} Gal\`{a}n} and Pablo Pedro {S\`{a}nchez Espeso} and V\'{i}ctor {Fern\`{a}ndez Solorzano}},
    title = {{M\'{e}todo y sistema de localizaci\'{o}n espacial mediante marcadores luminosos para cualquier ambiente}},
    date = {2015-08-13},
    year = {2015},
    howpublished = {Patent (ES-2543038-B2), Universidad de Cantabria, Spain}
    }

Posted in Dissemination | Leave a comment