On The Thread Scheduling Problem

Abstract: This paper considers the thread scheduling problem. The thread scheduling problem abstracts the problem of minimizing memory latency, using a directed data dependency graph generated form a compiler, to improve run time eÆciency. Two thread scheduling problems are formulated and shown to be strongly NP-complete. New methods and algorithms for analyzing a data dependency graph in order to com-pute the theoretical best runtime (lower bound of the nishing time) and to estimate the required minimum number of PEs needed to achieve certain nishing time are pre-sented. The new methods and algorithms improve upon some of the existing analysis and transformation techniques