Multi-layer ceramic modules (MLCs) are modern, miniaturized versions of printed circuit boards. They are small sandwiches of metal wiring layers alternating with ceramic insulating layers; a microchip is mounted to one face while the other mounts to a system board. A simple memory MLC may have a dozen layers while those for high-end processors can have over a hundred. Electrical connections between the metal layers pass through holes that are mechanically punched in the ceramic layers before they are metallized and laminated together; each layer has a different hole pattern. The modules are relatively small, so typically each layer is punched out in 9 or 16 copies on each ceramic sheet, about 200mm on a side.
Wiring and metallized holes for one layer (detail)
The holes are punched by a special-purpose "die set". Roughly the same size as the ceramic sheet, a die might have 256 punch pins in a 16x16 array. Unlike the punches in a ring-binder notebook three-hole punch, each pin on the die is individually actuated to punch a hole only if it is aligned over a point where a hole is desired --- as if the notebook punch could be told to punch the top and middle holes but skip the bottom one. The ceramic sheet is repositioned under the punch hundreds or thousands of times until all the holes have been punched.
Not only are the mechanical dies expensive, but the punching step was a manufacturing bottleneck, so to lower production costs and increase volumes it was important to speed up the process. Since each die has the pins in a particular fixed pattern, the problem has two parts: using existing dies as efficiently as possible, and designing more efficient new dies.
Operating an existing die more efficiently can itself be broken into two problems. First, what is the smallest set of positions of a ceramic sheet from which the die can punch all the holes? With any possible position we associate the holes that can be punched at that position: 0 of them at worst, 256 at best. Finding a minimum set of positions from which all the holes can be punched is then a "Set Cover" problem, a standard problem in theoretical computer science. Although it is NP-hard, excellent heuristics are available and (for good reasons) the instances in question are particularly easy. In fact, one cannot consider all possible positions (there are infinitely many), and just determining the set of "reasonable" possible offsets is a bit tricky. In particular, there is a small amount of error tolerance, so it may be possible to punch two holes from one position, even though both align only inexactly with their respective pins.
Chip-mounting face of an MLC, with its complicated pattern of wires and contact points. The dense center region is where the processor chip will go
Second, given a set of positions, in what sequence should they be visited to minimize the time spent traveling between them? This is the classic Traveling Salesman Problem, with an unusual metric. To move from one position to another, the table carrying the ceramic sheet accelerates as fast as possible to the halfway position, then decelerates at the same rate to arrive at the destination. The X and Y axes operate independently, so the time taken is the square root of the X or Y distance, whichever is larger. One interesting thing about this metric is that a shortest TSP tour can cross over itself; this cannot happen in the usual Euclidean metric. Like Set Cover, the TSP is NP-hard, but again good heuristics are available. In this case, IBM Tokyo Reseearch's Hiroyuki Okano customized their solver to the unusual metric.
Solving these two problems allowed existing dies to operate around 5% faster. Unlike these two problems, the problem of designing more efficient new dies does not fit a neat existing mathematical model. The key insight was that dies with pins arranged in a grid, rather than some more complex pattern, tend to be best, for reasons simple enough but too involved to explain here. In principle then, we can consider all possible X and Y spacings (both are multiples of some underlying unit), and use the methods above to see how long each of the10,000 or so possible dies would take to produce each of the 100 layers for an MLC. While the software is fast, though, it is not feasible to run it a million times. Fortunately, the same insight that motivates use of simple grid-based dies also suggests a couple of simple estimates for how many positions a given die will need, and thus how much time. These estimates are used to winnow the full set of dice down to a smaller number, which are then evaluated exactly. The die-design task was previously done manually by engineers, but to optimize the pin positions in light of tens of thousands of holes to be punched is a task beyond human comprehension. Our algorithmic approach produced dies with throughputs a staggering 20-50% above those of existing or planned dies, again at no extra cost.
Innovator's corner
Gregory Sorkin Researcher
What is the most exciting potential future use for the work you're doing?
Applying mathematical optimization to the real world to me means doing more with less: less energy, less time, less machinery, less money. That has some worrying aspects, but letting people have more while taking less from the planet is basically good.
What is the most interesting part of your research?
Many problems we would like to solve are profoundly intractable, in a concrete mathematical sense. Computer scientists work around this with alternative approaches like approximation algorithms and average-case anaylsis, and there is a lot of active research in both, as well as in exciting new directions like stochastic programming (optimizing in the face of uncertainty) and algorithmic auction theory (offering better economic models). There is beautiful mathematics here too, and important connections with physics.
What inspired you to go into this field?
My musician father encouraged me in mathematics, but in college I found calculus on manifolds too hard: I preferred nice easy questions like "how many different ways are there to arrange n matchsticks end to end" (how many graphs are there with n edges)? Professors warned me that these easy to state combinatorial problems are actually painfully hard, and they were right. Luckily, they are also fun.
What is your favorite invention of all time?
I'm enamoured of the web, laptops, mp3 players, and digital cameras. But let's not forget the vital basics: plumbing.
Research team
Related Research
Disciplines: Computer Science
, Electrical Engineering
, Mathematical Sciences
Research Areas: Algorithms & Theory