Author: eliasndcoding

May 29, 2020

Erratum in Timescale Functions for Parallel Memory Allocation [Li et. al., 2019]

Elias Neuman-Donihue, University of Rochester, May 2020

A small correction to Li et. al.’s paper: in section 3.2, the length of a time window is defined as “its end time minus its start time plus one.” However, in section 3.2.1, there is a reference to “windows of length k from 0 \leq k \leq n,” the lower bound of which refers to windows with their end index before their start. This also leads to some mathematical inconsistencies in sections 3.2.1 and 3.2.2.

One such error is the calculation of reuse(1): by the stated definition, an interval of length k=1 has only one allocation, so the reuse should be one if the window also contains a matching free operation and 0 otherwise. Therefore, since there are a total of n windows of length 1, the average reuse of all such windows should be:

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}

However, by the formulae stated in 3.2.2:

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=1)s_i - \sum_{i=1}^{m}I(e_i-s_i=1)(s_i + 1) + 2\sum_{i=1}^{m}I(e_i-s_i=1)}{n}

reuse(1) =\frac{\sum_{i=1}^{m}I(e_i-s_i=1)}{n} \neq \frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}

In order to standardize the equations with the provided definition of window length, a few changes must be made:

In Eq. 1 and Eq. 2, every instance of e_i - s_i \le k should instead read e_i - s_i < k

Then in Eq. 2,
Z(k)= \frac{\sum_{i=1}^{m}I(e_i - s_i < k) \cdot k}{n-k+1}

The recursive equations should then read

X(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)s_i

X(k) = X(k-1) + \sum_{i=1}^{m}I(s_i\ge n-(k-1)) + \sum_{i=1}^{m}I(e_i-s_i+1=k)min(n-k, s_i)

Y(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)e_i

Y(k) = Y(k-1) + \sum_{i=1}^{m}I(e_i\le k-1) + \sum_{i=1}^{m}I(e_i-s_i+1=k)max(k, e_i)

Z(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)

Z(k) = Z(k-1) + \sum_{i=1}^{m}I(e_i-s_i < k) + \sum_{i=1}^{m}I(e_i-s_i+1=k) \cdot k