Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Skyline algorithm for packing 2D rectangles

jvernay.fr

Post reply on HN
Print view View original

51–60 of 60 posts

Re: The Skyline algorithm for packing 2D rectangles

#51

Post by almostgotcaught »

romesmoke wrote: post #43
almostgotcaught wrote: post #33

Earlier quoted context omitted.

> Most of my PhD's effort has been devoted to beating the SOTA in this. Problem's importance nowadays is owed to deep learning's memory wall. lol i similarly spent 1 year of my phd trying to finagle this same thing for the same exact reason. got as far as proving that when it's parameterized (like in the case of DNNs with algebraically coupled layers) it's FPT (finite parameter tractable) which is like duh but also a…

Hm, you sound like you approached it from the theoretical ML side. My strategy was much less sophisticated: I implemented the Buchsbaum et al. paper you posted in another comment of yours.

I don't know what you mean. I studied the problem, implemented several papers, wasn't happy with the results, and then kept pushing on the actual complexity. When I figured out there was an existing bound I gave up because I wasn't a theory student so I didn't have time (or really desire) to try to improve on the bound.

Re: The Skyline algorithm for packing 2D rectangles

#52

Post by romesmoke »

almostgotcaught wrote: post #51
romesmoke wrote: post #43

Earlier quoted context omitted.

Hm, you sound like you approached it from the theoretical ML side. My strategy was much less sophisticated: I implemented the Buchsbaum et al. paper you posted in another comment of yours.

I don't know what you mean. I studied the problem, implemented several papers, wasn't happy with the results, and then kept pushing on the actual complexity. When I figured out there was an existing bound I gave up because I wasn't a theory student so I didn't have time (or really desire) to try to improve on the bound.

TBH I don't know what you mean either :D

I know that DSA is NP-complete, and none of the existing deep learning compilers implement the theoretical SOTA (you're probably referring to the 2+ε bound by Buchsbaum et al.)

I also know that scaling laws and the memory wall are soon gonna overpower the currently used heuristics (e.g., sort by size and do best-fit).

Anyways, I'm glad I "met" someone who has struggled against the same problem. Good luck with your research!

Re: The Skyline algorithm for packing 2D rectangles

#53

Post by zellyn »

imajoredinecon wrote: post #50
guessmyname wrote: post #34

Earlier quoted context omitted.

In theory, yes, but in practice... I’ve interviewed with several companies that asked me this specific question [1], including Facebook, ByteDance, LinkedIn, and a particular team at Apple (not my current team). The interviewers, perhaps somewhat optimistically [2], expected a fully working solution. They gave me about 40 minutes—more than the 15 minutes mentioned in the original comment—but I definitely needed the f…

“This exact problem” isn’t the packing problem discussed in the OP, right? It’s a different problem about taking the union of overlapping rectangles with their bottom edges at the same vertical position.

Reading just the headline, I thought that's what this post was referring to. I used to give the Skyline overlapping rectangle problem at Google for several years, until it got banned. I'd say that with appropriate nudges, most candidates were able to get through it in an hour. I don't know how things have changed since 2015, but this was all on a whiteboard, so at least there wasn't time wasted fighting a compiler.

Then again, my lifetime stats on interviewing at Google, measured by interview scores vs eventual offers extended was somewhere between noise and a slightly negative correlation, so I never did figure out why they let me interview at all! (I think I'm too nice in interviews, because I want everyone to succeed, and asking myself "if this person were on my team, would I be as happy to collaborate with them as I would be with Nick? Really?" only goes so far in counteracting that.)

Re: The Skyline algorithm for packing 2D rectangles

#54

Post by almostgotcaught »

romesmoke wrote: post #52
almostgotcaught wrote: post #51

Earlier quoted context omitted.

I don't know what you mean. I studied the problem, implemented several papers, wasn't happy with the results, and then kept pushing on the actual complexity. When I figured out there was an existing bound I gave up because I wasn't a theory student so I didn't have time (or really desire) to try to improve on the bound.

TBH I don't know what you mean either :D I know that DSA is NP-complete, and none of the existing deep learning compilers implement the theoretical SOTA (you're probably referring to the 2+ε bound by Buchsbaum et al.) I also know that scaling laws and the memory wall are soon gonna overpower the currently used heuristics (e.g., sort by size and do best-fit). Anyways, I'm glad I "met" someone who has struggled against…

> TBH I don't know what you mean either :D

Think about the ILP with disjunctions formulation of DSA. It's basically a set of linear equations right? In the case of DNNs, the equations are related: the sizes of the allocations in one layer (in say a CNN) are algebraically a function of the outputs of the previous layer. And so on all the way back to the inputs. So what looks like a set of linear equations in N variables is actually a much smaller set of nonlinear equations in K Okay non-linear equations are hard but that's not actually what I'm getting at - what I'm getting at is the instances of the DSA problem in a production ML pipeline are parametric. So I tried to solve this problem: given a DNN and its parameterized DSA instances, can you do some work offline (to solve "part" of the problem) so that at runtime there's not a lot of work left. And that question/problem/challenge falls into the bucket of FPT.

> Good luck with your research

I changed topics and graduated. No more research for me yay

Re: The Skyline algorithm for packing 2D rectangles

#55

Post by almostgotcaught »

romesmoke wrote: post #44
auvi wrote: post #11

Earlier quoted context omitted.

nice! you have your thesis or any related paper available online?

Hopefully I'll defend next summer. Papers-and-code-wise, I haven't published the "final" thing yet. Right now I'm looking into integrating it with IREE, to get some end-to-end figures.

> Right now I'm looking into integrating it with IREE

clever guy. IREE is just about the only serious/available runtime where you can do this because IREE codegens the runtime calls as well as the kernel code. But you're gonna have to either patch an existing HAL or write a new one to accomplish what you want to accomplish. If you want I can help you - if you go to the discord (https://discord.gg/J68usspH) and ask about this in #offtopic I'll DM you and can point you to the right places.

Re: The Skyline algorithm for packing 2D rectangles

#56

Post by romesmoke »

almostgotcaught wrote: post #54
romesmoke wrote: post #52

Earlier quoted context omitted.

TBH I don't know what you mean either :D I know that DSA is NP-complete, and none of the existing deep learning compilers implement the theoretical SOTA (you're probably referring to the 2+ε bound by Buchsbaum et al.) I also know that scaling laws and the memory wall are soon gonna overpower the currently used heuristics (e.g., sort by size and do best-fit). Anyways, I'm glad I "met" someone who has struggled against…

> TBH I don't know what you mean either :D Think about the ILP with disjunctions formulation of DSA. It's basically a set of linear equations right? In the case of DNNs, the equations are related: the sizes of the allocations in one layer (in say a CNN) are algebraically a function of the outputs of the previous layer. And so on all the way back to the inputs. So what looks like a set of linear equations in N variabl…

Wait a minute:

1. Formulating DSA as ILP doesn't scale. TelaMalloc starts from this fact as motivation.

2. There's no 1-1 mapping between tensors and allocations. Buffer re-use is important.

3. There's room for offline DSA instances as well. IREE's Stream dialect has a related transform (LayoutSlices.cpp).

Anyways, I'm no ML expert. DSA is much more generic than deep learning compilers. I can't wait to graduate myself and never hear the involved keywords again.

Re: The Skyline algorithm for packing 2D rectangles

#57

Post by p0ckets »

almostgotcaught wrote: post #37
p0ckets wrote: post #36

Earlier quoted context omitted.

An even more recent one from Google: https://github.com/google/minimalloc

i gave up on the problem about 18 months ago so i didn't keep up with the research area. is this yours? the runtimes are of course very good but i don't see a comparison on how good the approximation is vs telamalloc (or just ILP). i'll say this though: it's miraculuos that the impl is so small.

Not mine. I just happened to hear about it from a colleague recently.

Re: The Skyline algorithm for packing 2D rectangles

#58

Post by RaftPeople »

mzl wrote: post #47

The standard heuristic any 2D packing algorithm starts with is left-bottom or bottom-left (the choice is symmetrical). Place a piece as much to the left as possible, and among equal choicse as low as possible (or vice versa, as the choice was in the linked article). From this base heuristic, further meta-heuristics can be developed with choices for the order to pack parts, how to choose among "almost equal" positions…

I created a 3D bin packing at work with similar basic heuristic you described, plus some additional flavor for testing some number of different combinations during each iteration (and choosing the path that had best results up to that point).

The interesting thing I found is that the simple heuristics work pretty well. I actually had to dial back the level of optimization because it took too long for the human packers to duplicate the packing correctly to be able to close the carton.

I had to set it to a level that retained enough wasted space that allowed them quickly find their own solution, but knowing that for sure all of this stuff will fit into carton size X, because saving an extra few dollars in shipping didn't offset the labor dollars to pack it that way.

Re: The Skyline algorithm for packing 2D rectangles

#59

Post by almostgotcaught »

romesmoke wrote: post #56
almostgotcaught wrote: post #54

Earlier quoted context omitted.

> TBH I don't know what you mean either :D Think about the ILP with disjunctions formulation of DSA. It's basically a set of linear equations right? In the case of DNNs, the equations are related: the sizes of the allocations in one layer (in say a CNN) are algebraically a function of the outputs of the previous layer. And so on all the way back to the inputs. So what looks like a set of linear equations in N variabl…

Wait a minute: 1. Formulating DSA as ILP doesn't scale. TelaMalloc starts from this fact as motivation. 2. There's no 1-1 mapping between tensors and allocations. Buffer re-use is important. 3. There's room for offline DSA instances as well. IREE's Stream dialect has a related transform (LayoutSlices.cpp). Anyways, I'm no ML expert. DSA is much more generic than deep learning compilers. I can't wait to graduate mysel…

> Formulating DSA as ILP doesn't scale.

it doesn't scale to what? 405B LLMs? no probably not. but i have plots that show not unreasonable solve times for CNNs with ~30k tensors (~10 minutes) using gurobi.

> There's no 1-1 mapping between tensors and allocations. Buffer re-use is important.

yes i'm aware... that's why I made the comment above that you can't pull this trick in e.g., PyTorch.

> 3. There's room for offline DSA instances as well. IREE's Stream dialect has a related transform (LayoutSlices.cpp).

yes again, i'm aware - that's why I made the comment above that IREE is the only place you could pull this trick. LayoutSlices is one place but hooking the allocator in the HAL is simpler if you don't want to fight IREE's various transformations that happen after that.

> DSA is much more generic than deep learning compilers.

yes that's I posted the OR literature first...

> I can't wait to graduate myself and never hear the involved keywords again.

amen

Post reply on HN