Predicting and bounding the speedup of multithreaded Solaris programs

In Solaris, threads are frequently relocated. The data associated with a re located thread have to be moved from the cache of the old processor to the new processor. In order to avoid poor memory performance due to thread relo cation, threads can be bound to processors-static scheduling. Finding a sta tic schedule which results in maximum speedup is NP-hard. It is even diffic ult to determine if a static schedule is close to the optimal case or not. Here, a technique for predicting the speedup of multithreaded Solaris progr ams is presented. Based on an existing theoretical result, a lower bound on the maximal speedup is also obtained. The predicted speedup and the bound are based on recordings from a single-processor execution. When comparing t he predictions with the real speedup using a multiprocessor with eight proc essors, we see that the predictions are very good. By comparing the speedup of a static schedule with the bound, we see that it is worthwhile to look for other schedules. (C) 1999 Academic Press.