We present algorithms for high performance communication between message-passing parallel programs, and evaluate the algorithms as implemented in InterComm. InterComm is a framework to couple parallel programs in the presence of complex data distributions within a coupled application. Multiple parallel libraries and languages may be used in the different programs of a single coupled application. The ability to couple such programs is required in many emerging application areas, such as complex simulations that model physical phenomena at multiple scales and resolutions, and image data analysis applications. We describe the new algorithms we have developed for computing inter-program communication patterns. We present experimental results showing the performance of various algorithmic tradeoffs, and also compare performance against an earlier system.