One of the difficulties in high-level synthesis and compiler optimization is obtaining a good schedule without knowing the exact computation time of the tasks involved. The uncertain computation times of these tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship between these tasks can be represented as a data-flow graph where each node models the task associated with a probabilistic computation time. A set of edges represents the dependencies between tasks. In this research, we study scheduling and optimization algorithms taking into account the probabilistic execution times. Two novel algorithms, called probabilistic retiming and probabilistic rotation scheduling, are developed for solving the underlying nonresource and resource constrained scheduling problems, respectively. Experimental results show that probabilistic retiming consistently produces a graph with a smaller longest path computation time for a given confidence level, as compared with the traditional retiming algorithm that assumes a fixed worst-case and average-case computation times. Furthermore, when considering the resource constraints and probabilistic environments, probabilistic rotation scheduling gives a schedule whose length is guaranteed to satisfy a given probability requirement. This schedule is better than schedules produced by other algorithms that consider worst-case and average-case scenarios.

This paper presents a novel approach to reducing the communication costs incurred when performing multiple multicasts on wormhole routed two-dimensional mesh multiprocessor systems. Both unicast and path-based implementations of multicasting incur communication costs due to the inherent message passing and contention for network resources. The start-up time dominates the transmission time when the data volume is small. However, in the presence of multiple multicasts when the data volume is very large, the communication delays due to message blocking and resource contention become very significant. Because of this, we present a hybrid static-dynamic technique to reduce the communication costs incurred when performing multiple multicasts on wormhole routed direct networks. This technique requires a focus on ordering and routing information for the individual message transmissions. At compile time, each message is assigned a priority using the recently developed collision graph model. Then at runtime these priorities are used to arbitrate the message transmissions. As a base, dimension-ordered routing is used. However, to further reduce the communication costs, some messages will be rerouted. This technique is useful either as a stand-alone algorithm or as an embedded procedure into existing algorithms. Furthermore, the techniques can be applied to higher dimension direct networks. For a single multicast, our work performs as well as conventional methods. For multiple multicasts, results show that our approach provides significant improvement over baseline techniques.

In applications requiring very high throughput or which have real-time deadlines, the use of parallel processing techniques has become widespread. Although there exists potential for vast performance gains, the communication overhead inherent in such systems can significantly lessen these gains. In this paper, with tightly-coupled architectures as the platform, the static communication scheduling of messages in the network is addressed. The compile time determination of when nodes should send their messages to other nodes is what is termed static communication scheduling. In parallel systems the static scheduling of computational tasks has been studied for some time, however an in depth analysis of our problem is very new. This paper builds a framework based on the newly developed collision graph model. Using this model, the determination of an optimal schedule is proven to be NP-Complete. Several efficient algorithms are designed to deal with a general case model of message traffic, and experiments show a significant improvement over baseline approaches.

While research on the static scheduling of computational tasks for parallel systems has been ongoing for years, most work does not consider the communication costs nor does it consider the network congestion. A new static scheduling technique is presented which focuses on the communication overhead inherent in parallel processing systems. This paper builds a framework based on a newly developed graph model called a collision graph to study this problem. Using this model, algorithms are developed which can be embedded into existing static scheduling methods to improve their performance. The scheduling of cyclic data flow graphs was shown to be improved significantly as this technique was applied to the cyclo-compaction scheduling algorithm.