Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
We consider the problem of interleaving sequences of positive and negative numbers in order to maximize the minimum, overall prefixes p of the interleaved sequence, of the sum of the numbers in p. A simple and efficient offline solution is given. We also consider an online version of the problem. Under a cost model suitable for the prefetching application that motivates the problem, a strongly competitive online algorithm is given. These problems abstract two practical problems of scheduling data prefetches in a multiprogrammed or multithreaded computing environment.
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University