Variable-sized object packing and its applications to instruction cache design

In this paper we study the problem of packing a sequence of objects into bins. The objects are all either divisible or indivisible and occur in accordance with a certain probability distribution. We would like to find the average number of entries wasted in a bin if objects are indivisible and the probability of splitting the last object in a bin if objects are divisible. We solve this problem under a unified formulation by modeling a packing process as a Markov chain whose state transition probabilities are derived from an application of the partitions of integers. An application of this study to instruction cache design shows that a line size of 16 bytes has minimized the probability of splitting the last ×86 instruction in a cache line. For micro-op cache design, a line size of four entries has minimized the number of entries wasted per line.