Research On Parallel Solution For Cutting & Packing Problem Based On GPU High-Performance Computing

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.