8348

Fast Parallel Implementation of Fractional Packing and Covering Linear Programs

Slobodan Jelic, Soren Laue, Domagoj Matijevic, Patrick Wijerama
Department of Mathematics, J. J. Strossmayer University of Osijek, Croatia
J. J. Strossmayer University of Osijek, 2012
@article{jelic2012fast,

   title={Fast Parallel Implementation of Fractional Packing and Covering Linear Programs},

   author={Jeli{‘c}, S. and Laue, S. and Matijevi{‘c}, D. and Wijerama, P.},

   year={2012}

}

Download Download (PDF)   View View   Source Source   

329

views

We present a parallel implementation of the randomized (1 + e)-approximation algorithm for packing and covering linear programs presented by Koufogiannakis and Young [4]. In order to make the algorithm more parallelizable we also implemented a deterministic version of the algorithm, i.e. instead of updating a single random entry at each iteration we updated deterministically many entries at once. This slowed down a single iteration of the algorithm but allowed for larger step sizes which lead to fewer iterations. We use NVIDIA’s parallel computing architecture CUDA for the parallel environment. We report a speedup over the times reported by Koufogiannakis and Young [4] between one and two orders of magnitude.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Like us on Facebook

HGPU group

167 people like HGPU on Facebook

Follow us on Twitter

HGPU group

1273 peoples are following HGPU @twitter

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 13.1
  • SDK: AMD APP SDK 2.9
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.2
  • SDK: nVidia CUDA Toolkit 6.0.1, AMD APP SDK 2.9

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2014 hgpu.org

All rights belong to the respective authors

Contact us: