Monthly Archives: February 2014

Hybrid Hexagonal/Classical Tiling for GPUs

Hybrid Hexagonal/Classical Tiling for GPUs

  • Tobias Grosser, Albert Cohen, Justin Holewinski, P. Sadayappan, and Sven Verdoolaege. Hybrid Hexagonal/Classical Tiling for GPUs. In 12th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’14), page 66, Orlando, Florida, USA, 2014. doi:10.1145/2544137.2544160
    [BibTeX] [Abstract]

    Time-tiling is necessary for the efficient execution of iterative stencil computations. Classical hyper-rectangular tiles cannot be used due to the combination of backward and forward dependences along space dimensions. Existing techniques trade temporal data reuse for inefficiencies in other areas, such as load imbalance, redundant computations, or increased control flow overhead, therefore making it challenging for use with GPUs. We propose a time-tiling method for iterative stencil computations on GPUs. Our method does not involve redundant computations. It favors coalesced global-memory accesses, data reuse in local/shared-memory or cache, avoidance of thread divergence, and concurrency, combining hexagonal tile shapes along the time and one spatial dimension with classical tiling along the other spatial dimensions. Hexagonal tiles expose multi-level parallelism as well as data reuse. Experimental results demonstrate significant performance improvements over existing stencil compilers.

    @InProceedings{2014-02-GROSSER,
    author = {Tobias Grosser and Albert Cohen and Justin Holewinski and P. Sadayappan and Sven Verdoolaege},
    title = {{Hybrid Hexagonal/Classical Tiling for GPUs}},
    booktitle = {{12th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO '14)}},
    date = {2014-02-15/2014-02-19},
    address = {Orlando, Florida, USA},
    pages = {66},
    doi = {10.1145/2544137.2544160},
    abstract = {Time-tiling is necessary for the efficient execution of iterative stencil computations. Classical hyper-rectangular tiles cannot be used due to the combination of backward and forward dependences along space dimensions. Existing techniques trade temporal data reuse for inefficiencies in other areas, such as load imbalance, redundant computations, or increased control flow overhead, therefore making it challenging for use with GPUs. We propose a time-tiling method for iterative stencil computations on GPUs. Our method does not involve redundant computations. It favors coalesced global-memory accesses, data reuse in local/shared-memory or cache, avoidance of thread divergence, and concurrency, combining hexagonal tile shapes along the time and one spatial dimension with classical tiling along the other spatial dimensions. Hexagonal tiles expose multi-level parallelism as well as data reuse. Experimental results demonstrate significant performance improvements over existing stencil compilers.},
    year = {2014}
    }

Posted in Dissemination | Leave a comment
Multi-Player Game Theoretic MAC Strategies for Energy Efficient Data Dissemination

Multi-Player Game Theoretic MAC Strategies for Energy Efficient Data Dissemination

  • Angelos Antonopoulos and Christos Verikoukis. Multi-Player Game Theoretic MAC Strategies for Energy Efficient Data Dissemination. IEEE Transactions on Wireless Communications, 13(2):592-603, 2014. doi:10.1109/TWC.2013.120713.120790
    [BibTeX] [Abstract]

    The existence of multiple active sources in wireless data dissemination scenarios raises considerable channel access issues. Although the overall goal in the network is the successful accomplishment of the dissemination, the individual wireless nodes aim at maximizing their battery lifetime by minimizing their particular energy consumption. Considering thus the self-centered behavior of the nodes, we anticipate to design Medium Access Control (MAC) policies in order to provide the terminals with energy efficient solutions without compromising the dissemination completion time. In this paper, we propose non-cooperative game theoretic channel access strategies by estimating equilibrium points that achieve balance between conserving energy and completing the data dissemination. In particular, we present two different MAC strategies: i) a distributed approach for ad-hoc networks, and ii) a coordinated approach for infrastructure networks, where a central controller is sporadically used to accelerate the data dissemination. In addition, network-coded transmissions are considered to eliminate the need of control packets exchange. Both analytical and simulation results are provided to evaluate our proposed schemes, demonstrating the significant gains that game theoretic techniques can bring to the network performance compared to standardized solutions.

    @Article{2014-02-ANTONOPOULOS,
    author = {Angelos Antonopoulos and Christos Verikoukis},
    journal = {{IEEE Transactions on Wireless Communications}},
    title = {{Multi-Player Game Theoretic MAC Strategies for Energy Efficient Data Dissemination}},
    date = {2014-02-11},
    volume = {13},
    number = {2},
    pages = {592-603},
    doi = {10.1109/TWC.2013.120713.120790},
    abstract = {The existence of multiple active sources in wireless data dissemination scenarios raises considerable channel access issues. Although the overall goal in the network is the successful accomplishment of the dissemination, the individual wireless nodes aim at maximizing their battery lifetime by minimizing their particular energy consumption. Considering thus the self-centered behavior of the nodes, we anticipate to design Medium Access Control (MAC) policies in order to provide the terminals with energy efficient solutions without compromising the dissemination completion time. In this paper, we propose non-cooperative game theoretic channel access strategies by estimating equilibrium points that achieve balance between conserving energy and completing the data dissemination. In particular, we present two different MAC strategies: i) a distributed approach for ad-hoc networks, and ii) a coordinated approach for infrastructure networks, where a central controller is sporadically used to accelerate the data dissemination. In addition, network-coded transmissions are considered to eliminate the need of control packets exchange. Both analytical and simulation results are provided to evaluate our proposed schemes, demonstrating the significant gains that game theoretic techniques can bring to the network performance compared to standardized solutions.},
    year = {2014}
    }

Posted in Dissemination | Leave a comment