loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008)
A Distributed Parallel Algorithm to Solve the 2D Cutting Stock Problem
February 13-February 15
ISBN: 978-0-7695-3089-5
ASCII Text
x 
 
Coromoto Leon, Gara Miranda, Casiano Rodriguez, Carlos Segura, "A Distributed Parallel Algorithm to Solve the 2D Cutting Stock Problem," Parallel, Distributed, and Network-Based Processing, Euromicro Conference on, pp. 429-434, 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), 2008.
 
 
BibTex
x
 
@article{ 10.1109/PDP.2008.31,
author = {Coromoto Leon and Gara Miranda and Casiano Rodriguez and Carlos Segura},
title = {A Distributed Parallel Algorithm to Solve the 2D Cutting Stock Problem},
journal ={Parallel, Distributed, and Network-Based Processing, Euromicro Conference on},
volume = {0},
year = {2008},
issn = {1066-6192},
pages = {429-434},
doi = {http://doi.ieeecomputersociety.org/10.1109/PDP.2008.31},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel, Distributed, and Network-Based Processing, Euromicro Conference on
TI - A Distributed Parallel Algorithm to Solve the 2D Cutting Stock Problem
SN - 1066-6192
SP429
EP434
A1 - Coromoto Leon,
A1 - Gara Miranda,
A1 - Casiano Rodriguez,
A1 - Carlos Segura,
PY - 2008
KW - cutting stock problem
KW - load balancing
KW - synchronization scheme
VL - 0
JA - Parallel, Distributed, and Network-Based Processing, Euromicro Conference on
ER -
 
This work analyses the difficulties of parallelizing the best known sequential algorithm for the 2D Cutting Stock Problem. All the approaches to parallelize the algorithm strive against its highly irregular computation structure and its sequential nature. A distributed-memory parallel algorithm has been designed through a time-driven task intercommunication service. The service allows to introduce a load balancing scheme that tries to hide the non-homogeneous work load nature of the involved single tasks. Experimental results obtained for MVAPICH Infiniband and MPICH Gigabit Ethernet implementations prove the efficiency of the communication and balancing schemes and show the almost linear speedup achieved by the parallel algorithm.
Index Terms:
cutting stock problem, load balancing, synchronization scheme
Citation:
Coromoto Leon, Gara Miranda, Casiano Rodriguez, Carlos Segura, "A Distributed Parallel Algorithm to Solve the 2D Cutting Stock Problem," pdp, pp.429-434, 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.