On the assessment of input streams for incremental network computing

Network latency is an adverse factor for computations performed across the network. Overlapping computation with communication is an important technique for hiding latency. It has been shown that network latency cannot be effectively hidden without considering the order of sending data [C.-C. Lin, Strategies for achieving high performance incremental computing on a network environment, in: Proc.18th Int’l Conf. on Advanced Information Networking and Applications 1, 2004, pp. 113–118]. However, finding a data-sending order for the input to a task which minimizes the remote execution time for any network traffic pattern is NP-hard [C.-C. Lin, D.-W. Wang, T.-S. Hsu, Bounds on the client-server incremental computing, IEICE Trans. Fundamentals E89-A (5) (2006) 1198–1206]. Thus, heuristic algorithms are often employed to search an optimal input stream. The performance of algorithms relies on an effective mechanism for guiding the search toward a promising direction. In this paper, the computation-progress graph is proposed for transforming an input stream of a task to its corresponding pattern of progressive computations. Then, the assessing function is defined for assigning scores to the found input streams based on the computation-progress graph. Based on the scores, the promising search directions can be determined. Finally, the effectiveness of our assessing function is also demonstrated by the search of the optimal orders for computing the product of two polynomials, matrix multiplication and FFT.