JISE


  [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


On Message Sequences for Incremental Network Computing


Cho-Chin Lin
Department of Electronic Engineering 
National Ilan University 
Yilan, 260 Taiwan 
E-mail: cclin@niu.edu.tw


    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 inO((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 (JISE_200804_02.pdf)