Deadlock-free Asynchronous Communication Strategies for Unstructured Computations on iPSC/860

In this paper, we describe efficient, scalable, and deadlock-free asynchronous communication strategies suitable for unstructured computations on iPSC/860. Using these deadlock-free strategies, which incur small overhead, we have optimized the communication in parallel sparse Cholesky factorization. We present experimental results to show that such optimizations can lead to more than 50% saving in communication costs.