Solving a 2D knapsack problem using a hybrid data-parallel/control style of computing

• Main Authors: Ulm, D.R., Baker, J.W., Scherger, M.C.
• Format: Conference Proceeding
• Language: English
• Subjects: Computer aided instruction; Computer science; Concurrent computing; Cost function; Dynamic programming; Hardware; Optimal control; Parallel algorithms; Parallel processing; Size control
• DOI: 10.1109/IPDPS.2004.1303328

Summary form only given. This paper describes a parallel solution of the sequential dynamic programming method for solving a NP class, 2D knapsack (or cutting-stock) problem which is the optimal packing of multiples of n rectangular objects into a knapsack of size L/spl times/W and are only obtainable with guillotine-type (side to side) cuts. Here, we describe and analyze this problem for the associative model. Since the introduction of associative SIMD computers over a quarter of a century ago, associative computing and the data-parallel paradigm remain popular. The MASC (multiple instruction stream associative computer) parallel model supports a generalized version of an associative style of computing. This model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to an equal number of partition sets of processors, and assignment of tasks to ISs using control parallelism. We solve this NP class problem with a parallel algorithm that runs in O(W(n+L+W)) time using L processors, where L>W for a 2D knapsack problem with a capacity of L/spl times/W. The new multiple IS version using LW processors and max{L,M} ISs runs in O(n+L+W) given practical hardware considerations. Both of these results are cost optimal with respect to the best sequential implementation. Moreover, an efficient MASC algorithm for this well-known problem should give insight to how the associative model compares to other parallel models such as PRAM.