8209

Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm

Imen Chakroun, Mohand Mezmaz, Nouredine Melab, Ahcene Bendjoudi
INRIA – CNRS : UMR8022 – Universite Lille 1 – Sciences et Technologies
hal-00731859, 2012
@article{chakroun:hal-00731859,

   hal_id={hal-00731859},

   url={http://hal.inria.fr/hal-00731859},

   title={Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm},

   author={Chakroun, Imen and Mezmaz, Mohand and Melab, Nouredine and Bendjoudi, Ahc{‘e}ne},

   language={Anglais},

   affiliation={DOLPHIN – INRIA Lille – Nord Europe , Institut de Math{‘e}matiques [Mons] , Laboratoire d’Informatique Fondamentale de Lille – LIFL , Centre de recherche sur l’Information Scientifique et Technique – CERIST},

   publisher={John Wiley & Sons},

   journal={Concurrency and Computation: Practice and Experience},

   audience={internationale },

   year={2012},

   pdf={http://hal.inria.fr/hal-00731859/PDF/cpedoc.pdf}

}

Download Download (PDF)   View View   Source Source   

1366

views

In this paper, we address the design and implementation of GPU-accelerated Branch-and-Bound algorithms (B&B) for solving Flow-shop scheduling optimization problems (FSP). Such applications are CPU-time consuming and highly irregular. On the other hand, GPUs are massively multi-threaded accelerators using the SIMD model at execution. A major issue which arises when executing on GPU a B&B applied to FSP is thread or branch divergence. Such divergence is caused by the lower bound function of FSP which contains many irregular loops and conditional instructions. Our challenge is therefore to revisit the design and implementation of B&B applied to FSP dealing with thread divergence. Extensive experiments of the proposed approach have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based execution, accelerations up to x77.46 are achieved for large problem instances.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

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] => 1480813427
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1480813427
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => l8rXE54cCwHUYXHauG7kvffXnmY=
        )

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

HGPU group

2079 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: