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
Times are displayed in time zone: (GMT-05:00) Guadalajara, Mexico City, Monterrey change

16:30 - 17:45: Research Papers - Track 2: Decidability and complexity at Grand Bay South
Chair(s): C.-H. Luke OngUniversity of Oxford, UK
POPL-2016-papers16:30 - 16:55
Oded PadonTel Aviv University, Neil ImmermanUniversity of Massachusetts, Amherst, Sharon Shoham, Aleksandr KarbyshevTel Aviv University, Mooly SagivTel Aviv University
Media Attached
POPL-2016-papers16:55 - 17:20
Rahman Lavaee, Chen DingUniversity of Rochester
Media Attached
POPL-2016-papers17:20 - 17:45
Stéphane GimenezUniversity of Innsbruck, Georg MoserUniversity of Innsbruck
Media Attached