Abstract

When converting matrices to lists of XOR operations, there are CPU savings that can result from strategically scheduling the XOR operations and leveraging intermediate results so that fewer XOR's are performed. It is an open problem to derive a schedule from a bit-matrix that minimizes the number of XOR operations.

We attack this open problem, deriving two new heuristics called Uber-CHRS and X-Sets to schedule encoding and decoding bit-matrices with reduced XOR operations. We evaluate these heuristics in a variety of realistic erasure coding settings and demonstrate that they are a significant improvement over previously published heuristics. In particular, a hybrid of the two heuristics, which we call Uber-XSet, provides consistently good schedules across all of our tests. We provide an open-source implementation of these heuristics so that practitioners may leverage our work.

Citation Information

• Plain Text:

  .techreport     psr:10:heu
  author          J. S. Plank and C. D. Schuman and B. D. Robison
  title           Heuristics for Optimizing Matrix-Based Erasure Codes for Fault-Tolerant Storage Systems
  institution     University of Tennessee
  month           December
  year            2010
  number          CS-10-664
  where           http://web.eecs.utk.edu/~jplank/plank/papers/CS-10-664.html
  

• Bibtex:

  @TECHREPORT{psr:10:heu,
          author = "J. S. Plank and C. D. Schuman and B. D. Robison",
          title = "Heuristics for Optimizing Matrix-Based Erasure Codes for Fault-Tolerant Storage Systems",
          institution = "University of Tennessee",
          month = "December",
          year = "2010",
          number = "CS-10-664",
          where = "http://web.eecs.utk.edu/~jplank/plank/papers/CS-10-664.html"
  }