Key Message Algorithm: a communication optimization algorithm in cluster-based parallel computing

Parallel computing using Network of Workstations (NOWs) has become very popular recently. However, the execution of parallel applications on such systems has been hampered by the high communication overhead. To reduce the communication overhead and to speedup the execution of parallel applications on NOWs, the paper proposes a Key Message approach that minimizes the cost of message passing in a parallel application by prioritizing communications in the underlying shared communication network. We first describe the queueing network model on which our approach is based, then introduce the algorithm that identifies the messages to be prioritized in a parallel application, and finally discuss the results obtained. Our preliminary analysis of the algorithm on randomly generated task graphs shows improvement over the system without using the prioritization scheme