Write a Blog >>
Wed 20 Jan 2016 16:55 - 17:20 at Grand Bay South - Track 2: Decidability and complexity Chair(s): C.-H. Luke Ong

A program can benefit from improved cache block utilization when contemporaneously accessed data elements are placed in the same memory block. This can reduce the program’s memory block working set and thereby, reduce the capacity miss rate. We formally define the problem of data packing for an arbitrary cache size and packing factor (the number of elements fitting in a cache block) and study how well the optimal solution can be approximated for two dual problems. On the one hand, we show that the cache hit maximization problem is approximable within a constant factor, for every fixed cache size. On the other hand, we show that unless P = NP, the cache miss minimization problem cannot be efficiently approximated.

Wed 20 Jan

POPL-2016-papers
16:30 - 17:45: Research Papers - Track 2: Decidability and complexity at Grand Bay South
Chair(s): C.-H. Luke Ong
POPL-2016-papers145330380000016:30 - 16:55
Talk
Media Attached
POPL-2016-papers145330530000016:55 - 17:20
Talk
Media Attached
POPL-2016-papers145330680000017:20 - 17:45
Talk
Media Attached