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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s