Model-based Dynamic Control of Speculative Forays in Parallel Computation

• Published in: Electronic notes in theoretical computer science 2016-10, Vol.327, p.93-107
• Main Authors: Perumalla, Kalyan S., Olama, Mohammed M., Yoginath, Srikanth B.
• Format: Article
• Language: English
• Subjects: Model-based Execution; Parallel Computing; Reversible execution; Speculative Execution
• ISSN: 1571-0661; 1571-0661
• DOI: 10.1016/j.entcs.2016.09.025

In simulations running in parallel, the processors would have to synchronize with other processors to maintain correct global order of computations. This can be done either by blocking computation until correct order is guaranteed, or by speculatively proceeding with the best guess (based on local information) and later correcting errors if/as necessary. Since the gainful lengths of speculative forays depend on the dynamics of the application software and hardware at runtime, an online control system is necessary to dynamically choose and/or switch between the blocking and speculative strategies. In this paper, we formulate the reversible speculative computing in large-scale parallel computing as a dynamic linear feedback control (optimization) system model and evaluate its performance in terms of time and cost savings as compared to the traditional (forward) computing. We illustrate with an exact analogy in the form of vehicular travel under dynamic, delayed route information. The objective is to assist in making the optimal decision on what computational approach is to be chosen, by predicting the amount of time and cost savings (or losing) under different environments represented by different parameters and probability distribution functions. We consider the cases of Gaussian, exponential and log-normal distribution functions. The control system is intended for incorporating into speculative parallel applications such as optimistic parallel discrete event simulations to decide at runtime when and to what extent speculative execution can be performed gainfully.