Bounds on the Client-Server Incremental Computing(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
We discuss the problem of finding a dominant sequence for sending input data items from a low-end client to a server for computational intensive tasks under the realistic assumption of unpredictable communication behavior. Under this assumption, the client has to send the input data items using a specified sequence to maximize the number of computations performed by the server at any time. The sequence-finding problem is NP-hard for the general case. In this paper, we address three fundamental and useful applications: the product of two polynomials, matrices multiplication and Fast Fourier Transform. We show that the sequence-finding problems of the three applications can be solved optimally in linear time. However, we also show counter examples to rule out any possibility of finding a dominant sequence for sparse cases of the three applications. Finally, a simulation is conducted to show the usefulness of our method.
社団法人電子情報通信学会の論文
2006-05-01