Online dispatching and parallel processing algorithms for saving money in systems with heterogeneous, single-buffered, speed-scalable processors

We propose three online dispatching and parallel processing algorithms to optimally assign arriving heterogeneous tasks to heterogeneous speed-scalable processors under the single-buffered computing architecture. The goal of our algorithms is to minimize the total financial cost (in dollars) of response time and energy consumption (TCRTEC) of tasks using dynamic speed-scaling, where each processor's speed can change dynamically within hardware and software processing constraints. Processors are heterogeneous in that they may differ in their hardware specifications with respect to maximum processing rate and power function parameters. Tasks are heterogeneous in terms of computation volume, memory and minimum processing requirements. We consider that the unit price of response time for each task is heterogeneous since the user may want to pay higher/lower unit prices for certain tasks. We assume that the unit price of energy for all tasks may be determined by the actual price of energy in a given geographical region and time of day. We model the overhead loading time incurred when a task is loaded by a given processor prior to its execution and assume it to be heterogeneous as well. We synthesize the Single Buffer Decision and Parallel Processing (SBDPP) algorithm and its two other versions. The first two versions allow the user to specify the unit price of energy and response time for executing each arriving task. The algorithm's second version extends the functionality of the first by allowing the user or the Operating Software (OS) of the computing device to further modify a task's unit price of time or energy in order to achieve a linearly controlled operation point that lies somewhere in the economy-performance mode continuum of the task's execution. The algorithm's third version operates exclusively on the latter. We briefly extend the SBDPP algorithm and its versions to consider migration, where an unfinished task is paused and resumed on another processor. The SBDPP algorithm is qualitatively compared against its two other versions. The SBDPP dispatcher is analytically shown to outperform the well-known Round Robin dispatcher in terms of the TCRTEC performance metric. Furthermore, numerical simulations suggest that the SBDPP dispatcher outperforms the Round Robin dispatcher with average cost savings exceeding 300% in both stochastic and deterministic traffic conditions even when processors are mildly heterogeneous (processor hardware parameters conservatively chosen not to differ from mean by more than 10%). Simulations also suggest that even when processors are mildly heterogeneous, the SBDPP dispatcher robustly tolerates a higher arrival rate that is over five times that of the Round Robin dispatcher (without rejecting any task in the long run). We deduce a relationship among the number of processors, response time of tasks and the ideal deterministic arrival rate of tasks.