16521

A Non-linear GPU Thread Map for Triangular Domains

Cristobal A. Navarro, Benjamin Bustos, Nancy Hitschfeld
Instituto de Informatica, Universidad Austral de Chile
arXiv:1609.01490 [cs.DC], (6 Sep 2016)
@article{navarro2016nonlinear,

   title={A Non-linear GPU Thread Map for Triangular Domains},

   author={Navarro, Cristobal A. and Bustos, Benjamin and Hitschfeld, Nancy},

   year={2016},

   month={sep},

   archivePrefix={"arXiv"},

   primaryClass={cs.DC}

}

Download Download (PDF)   View View   Source Source   

138

views

There is a stage in the GPU computing pipeline where a grid of thread-blocks, in parallel space, is mapped onto the problem domain, in data space. Since the parallel space is restricted to a box type geometry, the mapping approach is typically a k-dimensional bounding box (BB) that covers a p-dimensional data space. Threads that fall inside the domain perform computations while threads that fall outside are discarded at runtime. In this work we study the case of mapping threads efficiently onto triangular domain problems and propose a block-space linear map $lambda(omega)$, based on the properties of the lower triangular matrix, that reduces the number of unnnecessary threads from $mathcal{O}(n^2)$ to $mathcal{O}(n)$. Performance results for global memory accesses show an improvement of up to 18% with respect to the bounding-box approach, placing $lambda(omega)$ on second place below the rectangular-box approach and above the recursive-partition and upper-triangular approaches. For shared memory scenarios $lambda(omega)$ was the fastest approach achieving 7% of performance improvement while preserving thread locality. The results obtained in this work make $lambda(omega)$ an interesting map for efficient GPU computing on parallel problems that define a triangular domain with or without neighborhood interactions. The extension to tetrahedral domains is analyzed, with applications to triplet-interaction n-body applications.
VN:F [1.9.22_1171]
Rating: 3.4/5 (5 votes cast)
A Non-linear GPU Thread Map for Triangular Domains, 3.4 out of 5 based on 5 ratings

* * *

* * *

TwitterAPIExchange Object
(
    [oauth_access_token:TwitterAPIExchange:private] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
    [oauth_access_token_secret:TwitterAPIExchange:private] => o29ji3VLVmB6jASMqY8G7QZDCrdFmoTvCDNNUlb7s
    [consumer_key:TwitterAPIExchange:private] => TdQb63pho0ak9VevwMWpEgXAE
    [consumer_secret:TwitterAPIExchange:private] => Uq4rWz7nUnH1y6ab6uQ9xMk0KLcDrmckneEMdlq6G5E0jlQCFx
    [postfields:TwitterAPIExchange:private] => 
    [getfield:TwitterAPIExchange:private] => ?cursor=-1&screen_name=hgpu&skip_status=true&include_user_entities=false
    [oauth:protected] => Array
        (
            [oauth_consumer_key] => TdQb63pho0ak9VevwMWpEgXAE
            [oauth_nonce] => 1474867437
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1474867437
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => nvwCT22Na9EVMwmIME5JMNxdIuQ=
        )

    [url] => https://api.twitter.com/1.1/users/show.json
)
Follow us on Facebook
Follow us on Twitter

HGPU group

1996 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: