Advice from Bumble-Bees on Scheduling Parallel Functional Tasks

It has been suggested that time-complexity information can be derived at compile-time and used to guide task scheduling decisions for functional programs executing on parallel processors [San90, Mah90]. However, in [Par93] we highlight several problems with this idea. The most serious problem is that estimates of mean time-complexity can be misleading predictors of the absolute time required to evaluate tasks. This is a problem because the success or failure of scheduling decisions is heavily influenced by absolute timings. The problem is particularly acute when, at run-time, the program receives input about which the compiler has no (or at best, limited) knowledge. Accurate time-complexity information is extremely difficult to calculate for higher-order, lazy functional programs [San90]. An alternative solution proposed in [Mah90] is that time-complexity information can be estimated by recording sample execution profiles of the program under analysis. We adopt the latter approach and ..