I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)$ such that:

  1. $\prod_{i=1}^D m_i = M$,

  2. $R = \prod_{i=1}^D f(N_i, m_i) m_i - \prod_{i=1}^D N_i$ is as low as possible. Here $f(N,m)$ is the minimal number of blocks of length $m$ necessary to cover a 1D grid with size $N$ (or, formally, $f(N, m) = N / m$ if $N$ is a multiple of $m$, and $f(N,m) = N\,\mathrm{div}\,m + 1$ otherwise).

  3. The number of $m_i$ equal to 1 is as high as possible (but this is low priority, the condition 2 is more important).

How should I approach this? Is there some standard algorithm this can be reduced to?

In my case $M$ is not very big (of the order of 1000). Also, an absolute minimum in all cases is not strictly required; if there is an approximate algorithm, it will do to.

(In case anyone is interested in the application, I want to use it to find work group dimensions for an OpenCL kernel with a known global size and total number of work items).

  • $\begingroup$ Is $M$ effectively random? What does its prime factorization look like? e.g., how many unique prime factors does it have? How large is $D$? This will affect how many possible decompositions there are. $\endgroup$ – D.W. Aug 1 '13 at 5:10
  • $\begingroup$ In the application, $M$ is usually 16 or 32 times some random number from 1 to 32. $D$ is usually 1 to 3, but I would like to support cases with $D$ up to 6 or 7. $\endgroup$ – fjarri Aug 1 '13 at 5:35

One unsophisticated approach is to factor $M$, then exhaustively explore all possible decompositions of $M$ into a product of $D$ integers, and see which is best according to your criteria. I suspect this will prove to be an entirely reasonable solution for your example parameter ranges.

The number of possible decompositions is exponentially large, in general. If $M=\prod_i p_i^{e_i}$, then there are $\prod_i {D+e_i-1 \choose e_i}$ possible decompositions, which (depending upon $M$) could be rather a lot.

However, for your particular parameter values, the number of possible decompositions will probably still be manageable, so the unsophisticated algorithm should work fine. If $D=3$ and $M$ is 32 times a random number from 1 to 32, then the number of possible decompositions will range from a minimum of 21 possibilities (for $M=32\times 1$) to a maximum of 252 possibilities (for $M=32\times 30$). That's small enough that you can easily enumerate all possibilities and see which is best.

If you increase $D$ to $D=7$, then the number of possible decompositions will vary from a minimum of 462 (for $M=32\times 1$) to a maximum of 45276 possibilties (for $M=32\times 30$). That's still small enough that you can enumerate all possibilities and use the unsophisticated algorithm I mention above.

If you run into some other parameter choices where there are too many decompositions, a simple variant would be to randomly pick a bunch of different decompositions and see which of those is the best. It's not the fanciest algorithm around, but it's a reasonable thing to try.

Anyway, this should solve your problem for the parameter sizes you mention.

| cite | improve this answer | |
  • $\begingroup$ I was hoping that some kind of greedy algorithm exists, which gives a "good enough" solution, so that I could avoid unnecessary brute force. While 250 possibilities may not be that many, the enumeration time can be noticeable (but I need to check that). $\endgroup$ – fjarri Aug 1 '13 at 6:05
  • $\begingroup$ @Bogdan, I suggest that you program it and measure how long it takes. Enumerating 250 possibilities (or 45276 possibilities) is something that a program should be able to do extremely quickly (certainly way less than a second). If this is a one-time computation, I can't imagine this would be a problem. I wonder if you might be over-estimating how long this will take. $\endgroup$ – D.W. Aug 1 '13 at 6:15
  • $\begingroup$ That's exactly what I'm doing now :) The problem is: 1) I'm using a dynamic language, 2) less than a second is still too slow (I may need to calculate several dozen of such decompositions at the start of the program). I would prefer not to spend so much time on a minor low-level operation like that, so I may have to fall back to the randomized approach you proposed. $\endgroup$ – fjarri Aug 1 '13 at 6:23
  • $\begingroup$ @Bogdan, the way you describe it, there are only $2\times 32$ possibilities for $M$. Why don't you precompute the optimal decomposition for each (once), and then hardcode those decompositions into your program? You can hardcode into your program a table that shows the optimal decomposition for each such $M$, and then when you run your program, it just looks up the optimal decomposition in the table rather than enumerating all possibilities at runtime. $\endgroup$ – D.W. Aug 1 '13 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.