Previous 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


Journal of Information Science and Engineering, Vol. 24 No. 4, pp. 1023-1040 (July 2008)

On Message Sequences for Incremental Network Computing*

Cho-Chin Lin
Department of Electronic Engineering
National Ilan University
Yilan, 260 Taiwan

In a network computing platform, tasks compete with others for shared resources to communicate messages. Incremental computing masks communication latency by overlapping computation with communication. However, a sequence of messages with a large latency variance still makes computations proceed intermittently. In this paper, the impact of the message sequence on computation efficiency is studied and a framework which employs a well organized message sequence to maximize the efficiency of computations is introduced. Firstly, a network computing model for performing incremental computations is proposed. Based on the model, theorems are developed as the groundwork based on which algorithms for finding a well organized message sequence are derived. Finally, algorithms which find a well organized message sequence in O((r/k)k+1) and O(r!/(k!)r/k) comparison steps are given for sending r input data items using r/k messages of a given size k.

Keywords: network computing, high performance computing, incremental computing, parallel and distributed computing, message sequence

Full Text () Retrieve PDF document (200807_02.pdf)

Received June 30, 2006; revised November 13, 2006 & January 2, 2007; accepted January 23, 2007.
Communicated by Sy-Yen Kuo.
*This research was partially supported by the National Science Council of Taiwan, R.O.C. under grant No. 95-2221-E-197-013.