loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)
Bounds on the Client-Server Incremental Computing
Hong Kong, SAR, China
May 10-May 12
ISBN: 0-7695-2135-5
Cho-chin Lin, National Ilan University, Taiwan
Tsan-sheng Hsu, Academia Sinica, Nankang, Taiwan
Da-wei Wang, Academia Sinica, Nankang, Taiwan
We discuss the problem of finding a dominating sequence for sending the input data items from a low-end client to a server for computational intensive tasks under the realistic assumption of unpredictable communication behaviors. Under the assumption, the client sends the input data items using a specified sequence to maximum the number of computations performed at the server at any moment. The sequence-finding problem is NP-hard for the general case. In this paper, we address two fundamental and useful applications: matrix multiplication and Fast Fourier Transform. We have shown that the sequence-finding problems of the applications can be solved optimally in linear time. However, we have also shown counter examples to rule out any possibility of finding a dominating sequence for the sparse cases. Finally, a simulation is conducted to show the correctness and usefulness of our results.
Citation:
Cho-chin Lin, Tsan-sheng Hsu, Da-wei Wang, "Bounds on the Client-Server Incremental Computing," ispan, pp.86, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.