1 Search Results for "Ghandeharizadeh, Shahram"

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.35

The Subset Assignment Problem for Data Placement in Caches

Authors: Shahram Ghandeharizadeh, Sandy Irani, and Jenny Lam

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

We introduce the subset assignment problem in which items of varying sizes are placed in a set of bins with limited capacity. Items can be replicated and placed in any subset of the bins. Each (item, subset) pair has an associated cost. Not assigning an item to any of the bins is not free in general and can potentially be the most expensive option. The goal is to minimize the total cost of assigning items to subsets without exceeding the bin capacities. This problem is motivated by the design of caching systems composed of banks of memory with varying cost/performance specifications. The ability to replicate a data item in more than one memory bank can benefit the overall performance of the system with a faster recovery time in the event of a memory failure. For this setting, the number n of data objects (items) is very large and the number d of memory banks (bins) is a small constant (on the order of 3 or 4). Therefore, the goal is to determine an optimal assignment in time that minimizes dependence on n. The integral version of this problem is NP-hard since it is a generalization of the knapsack problem. We focus on an efficient solution to the LP relaxation as the number of fractionally assigned items will be at most d. If the data objects are small with respect to the size of the memory banks, the effect of excluding the fractionally assigned data items from the cache will be small. We give an algorithm that solves the LP relaxation and runs in time O(binom{3^d}{d+1} poly(d) n log(n) log(nC) log(Z)), where Z is the maximum item size and C the maximum storage cost.

Cite as

Shahram Ghandeharizadeh, Sandy Irani, and Jenny Lam. The Subset Assignment Problem for Data Placement in Caches. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 35:1-35:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ghandeharizadeh_et_al:LIPIcs.ISAAC.2016.35,
  author =	{Ghandeharizadeh, Shahram and Irani, Sandy and Lam, Jenny},
  title =	{{The Subset Assignment Problem for Data Placement in Caches}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{35:1--35:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.35},
  URN =		{urn:nbn:de:0030-drops-68058},
  doi =		{10.4230/LIPIcs.ISAAC.2016.35},
  annote =	{Keywords: Memory management, caching, simplex method, linear programming, min-cost flow}
}

Refine by Author
1 Ghandeharizadeh, Shahram
1 Irani, Sandy
1 Lam, Jenny

Refine by Classification

Refine by Keyword
1 Memory management
1 caching
1 linear programming
1 min-cost flow
1 simplex method

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Ghandeharizadeh, Shahram"

The Subset Assignment Problem for Data Placement in Caches

Abstract

Cite as

Thanks for your feedback!

Could not send message