# Optimal coverage of a $D$-dimensional grid with small blocks

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).

• 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. – D.W. Aug 1 '13 at 5:10
• 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. – 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.

• 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). – fjarri Aug 1 '13 at 6:05
• @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. – D.W. Aug 1 '13 at 6:15
• 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. – fjarri Aug 1 '13 at 6:23
• @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. – D.W. Aug 1 '13 at 15:59