We show that given a priori knowledge of the messages to be routed for a specific parallel application, efficient algorithms can be designed to generate low message traffic congestion and deadlock free routings at compile-time. The problem can be formulated as a graph theoretic problem. Since the problem of finding a deadlock free routing with minimal maximum message traffic congestion is shown to be NP-hard, an efficient heuristic is proposed. Performance of the heuristic for both random message distribution and for several specific applications on hypercube and torus topologies is evaluated by simulations. We show that, compared with the E-cube and XY fixed routings, the heuristic has significant improvement with respect to maximum congestion for the specific applications as well as for the nonuniform message distribution case which models communication locality. For the uniform message distribution case, the heuristic has moderate improvement.