Dissertation > Excellent graduate degree dissertation topics show

Research on Parallel Solution for Cutting & Packing Problem Based on GPU High-Performance Computing

Author: XuHui
Tutor: LuYiPing
School: Beijing Jiaotong University
Course: Mechanical Design and Theory
Keywords: Packing GPU parallel computing CUDA Exact algorithm Simulated annealing algorithm
CLC: O224
Type: Master's thesis
Year: 2010
Downloads: 216
Quote: 3
Read: Download Dissertation

Abstract


ABSTRACT:Packing problem is a classical combinatorial optimization problem. It brings huge challenge for its practical utility and its own NP completeness, which has attracted extensive and in-depth study from many scholars in mathematics, computer science and other fields. Currently, the serial algorithms are commonly used to solve packing problem, parallel computing especially on low-cost is underdeveloped, which affects the efficiency of algorithm and solution quality more seriously. Therefore, in order to improve solving efficiency of packing problem fundamentally, we design parallel algorithm with the structure of CUDA based on GPU.CUDA has good performance, compatibility and integrates of CPU and GPU productivity. It can already run on any level of system from large-scale computing devices to individual products. It has lower cost of development. Thus, this paper opens up research on these two types of problems:two-dimensional unconstrained packing problem and two-dimensional stripe packing problem. We get satisfactory solution.In this paper, the work is summarized as follows:First of all, sum up the current research of layout problem, analyze the current parallel research results, do summarization on CUDA-parallel and parallel principles of packing problem based on CUDA.Then, design CUDA parallel improving on precise algorithm of unconstrained two-dimensional packing problem, the solving speed raises nearly ten times mostly. Analyze solving steps of two-dimensional unconstrained exact algorithm based on dynamic programming, propose and design CUDA parallel strategy according to the characteristics of dynamic programming, improve it through CUDA programming. By comparing serial and parallel test data, the speed of improved algorithm raises about ten times mostly, and between five to six times for small-scale examples.Finally, design CUDA parallel improving on the meta-heuristic algorithm of two-dimensional strip packing problem, the solving speed raises graeter than seven times. Design a new disturbance criterion, summarize the conventional parallel strategy, propose and design CUDA parallel strategy according to the characteristics of algorithm, improve it through CUDA programming. By comparing serial and parallel test data, the speed of improved algorithm raises about seven point three times for the same example, which shows the improved algorithm is feasible.These work show that, we can effectively improve algorithm efficiency and increase value by using CUDA parallel technique in cutting and packing problem solving. In CUDA parallel solution, we need to pay attention to the division of block and thread, data transmission and memory allocation. The following work can start the application in other complex algorithms, or we can induce some improved thoughts into the algorithm in CUDA parallel improvement.

Related Dissertations

  1. Design and Study on Movable Packing Machine in Acrylic Fiber Production Lines,TH248
  2. Experiment Study of the Biogas Purification Process by Zeolite Filling Washing,TQ221.11
  3. Effects of Nano-Packing on Preservation Quality of Flammulina Velutipes and Agaricus Bisporus,TS219
  4. Study on Chitosan-Based Composiate Nano-Coating Dope and Its Effect of Fresh-Keeping for Coated Egg,TS253.2
  5. A Hyper-heuristic Using GRASP with Path-Relinking,TP301.6
  6. Research on Image Digital Watermarking Technology Based on CUDA,TP309.7
  7. The Research of Orthophoto Generation Based on GPU Parallel Acceleration,TP391.41
  8. The Comparation and Research between Chinese and Japanses Tourist Food Packing Design,TB472
  9. Experimental Study on Dense Packing of Monosized and Binary Spherical Particles Subjected to Vibrations,O347.7
  10. A Study of the Designing of Preserved Fruit Package at the Beginning of the Reform and Opening,J524.2
  11. Research on GPU-based Parallel Computing on BLAST Program,TP338.6
  12. Research and Realization of GPU Based Medical Image Volume Rendering Algorithm,TP391.41
  13. The Optimal Design of Plate-fin Heat Exchanger by Simulated Annealing Algorithm,TK172
  14. Application of CUDA in the Very Short Term Load Forecasting of Multi-node,TM715
  15. Application Research of GPU in Vehicle Detection and Tracking System,TP391.41
  16. Acceleration of X-ray Computed Tomography Reconstruction for Rice Tiller,TP391.41
  17. Study on Dense Stereo Image Matching Based on Parallel Computing,TP391.41
  18. Research of Rapid Intelligent Intrusion Detection Technology,TP393.08
  19. Research of Finite Element Method on GPU,O241.82
  20. 3D Virtual Endoscopy of Cardiovascular System,TP391.41
  21. Energy Minimization Based Segmentation and 3-D Visualization for Abdominal CT Image,TP391.41

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Optimization of the mathematical theory
© 2012 www.DissertationTopic.Net  Mobile