Message routing algorithms for static task scheduling

Two heuristic-based routing algorithms are presented. They take into account the need for precise information about intertask data communication which in aa message-passing, single-stage, n-dimensional network environment includes the communication delay for sending certain amounts of data at a certain moment through certain links. They also attempt to provide the best routes for communication, as well as the communication delay information on the routes. The difficulty is that for a given set of links, the communication delay can be different if the message is sent through at a different moment. The communication delay is influenced by current traffic on the links. The algorithms not only accurately compute the times that are needed to send messages from multiple-source processing elements (PEs) to a destination PE, but also indicate the paths that are used to transfer the messages. Each of the algorithms can be used in the static scheduling algorithms to computer the time needed to transfer messages in a multiprocessor system. The author also indicates that the optimal routing problem is NP-complete