¡@

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

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.