locked
Efficient parallelisation when two indices are in the same loop RRS feed

  • Question

  • In another post (https://social.microsoft.com/Forums/en-US/197b5d37-6650-46b9-ac47-3b082672e4cb/implementing-an-efficient-trueskill-through-time-model?forum=infer.net) Tom Minka stated:

    "In the expression "skill[year][player]", if "year" and "player" change according to two separate loop counters, as in the original model, then the generated code will be efficient.  If "year" and "player" change according to a single loop counter, as in the model of August 11 6PM, then the generated code is not efficient and you want the larger range to come first."

    In general if, in a loop, one has a Jagged array which needs to be indexed twice with variables on the same loop counter, is there a way to structure the model to generate efficient code as though they were on different loop counters?

    Thursday, November 6, 2014 5:25 PM

Answers

  • You can put all of the jagged array elements into a single flat array and use computed indices to access the right element.  It will be ugly, but fast.
    • Marked as answer by MarkG87 Thursday, November 6, 2014 6:33 PM
    Thursday, November 6, 2014 6:00 PM
    Owner

All replies

  • You can put all of the jagged array elements into a single flat array and use computed indices to access the right element.  It will be ugly, but fast.
    • Marked as answer by MarkG87 Thursday, November 6, 2014 6:33 PM
    Thursday, November 6, 2014 6:00 PM
    Owner
  • Tom,

    Please could you give some sample code to explain how you'd do this in principle? I'm not sure how to generate the computed indices and use them as you suggest.
    Friday, November 7, 2014 12:04 PM
  • Instead of skill[year][player] you use skill[firstPlayerOfYear[year]+player] where firstPlayerOfYear specifies when a given year starts in the flat array.  Since we are assuming both year and player come from a single underlying loop counter i, this turns into skill[index[i]] where index[i] is precomputed to equal firstPlayerOfYear[year[i]]+player[i].
    Tuesday, November 11, 2014 6:09 PM
    Owner