Bounds on the Client-Server Incremental Computing

Cho-chin LIN; Da-wei WANG; Tsan-sheng HSU

doi:10.1093/ietfec/e89-a.5.1198

Bounds on the Client-Server Incremental Computing

Cho-chin LIN, Da-wei WANG, Tsan-sheng HSU

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1198-1206

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1198

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Cho-chin LIN, Da-wei WANG, Tsan-sheng HSU, "Bounds on the Client-Server Incremental Computing" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1198-1206, May 2006, doi: 10.1093/ietfec/e89-a.5.1198.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1198/_p

Copy

@ARTICLE{e89-a_5_1198,
author={Cho-chin LIN, Da-wei WANG, Tsan-sheng HSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Bounds on the Client-Server Incremental Computing},
year={2006},
volume={E89-A},
number={5},
pages={1198-1206},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1198},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Bounds on the Client-Server Incremental Computing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1198
EP - 1206
AU - Cho-chin LIN
AU - Da-wei WANG
AU - Tsan-sheng HSU
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1198
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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.
ER -