Micro-Threading: Effective Management of Tasks in Parallel Applications

Emiliano Silvestri

Abstract:
Modern parallel applications, to be run on top of multi-core systems, are ever more characterized by the presence of many differentiated activities, which can be (re-)dispatched on different elaboration units—at disparate wall-clock-times—in order to make parallelism effective. Consequently, several programming models (or environments) for multi-core shared-memory architectures give to developers the capability to indicate what portions of the application must be treated as tasks, which can then be run in parallel. However, once these tasks have been CPU- dispatched they are executed in a non-preemptible manner until they spontaneously re-interact with the specific runtime layer hosting the application, a possibility for which there is no guarantee on when it will occur again at run-time. In the meantime, sudden program state changes can always arise as a consequence of the effects that each of these tasks can have on the program evolution throughout its execution. Operating System classical preemption does not fully cope with this problem—given that the timeline for this preemption procedure is general purpose and not necessarily suited for a given application context—and may be attempted to be exploited limited to scenarios where multiple tasks are assigned for being processed to different threads, which is not the optimal case for most application domains. Also, in some application fields we also have the exploitation of speculation (giving rise to potential causality inconsistencies), which is something not dealt with by the Operating System. As a result, whenever one of such (speculative) changes in the application state occurs, the application’s current execution dynamics may already be far from the optimal ones, which is a condition that can affect its performance in a significant manner. This must be addressed through timely re-assessments of the work assigned to the underlying computing resources regardless of whether the application tasks were intended to release the CPU at that time. To cope with this problem, we propose a new execution model for tasks, called Micro-Threading model, which provides for application-transparent task interruptions at arbitrary points of their executions. These interruptions are aimed at re-evaluating the current task-to-CPU assignments, in a manner fully alternative with respect to the thread-to-CPU assignment established by the Operating System. Also, we provide an implementation of this model to support task-preemptive execution in a wide range of applications contexts deployed on top of x86 machines with Unix-like Operating Systems. These include Transactional Memory, OpenMP and speculative Parallel Discrete Event Simulation. Clearly, the exploitation of micro-threads in these contexts has also led us to introduce new algorithms and solutions suited for optimizing the linkage of the micro-thread based execution to application level specific features. These proposals form a kind of reference to be considered for the exploitation of micro-threads in application scenarios related to the specific ones considered in this thesis. The results obtained by the experiments we carried out confirm the capability of our proposal to provide better run-time dynamics thanks to higher reactivity to program state changes, which is reflected in promptly renewing the overall scheduling of tasks to CPU-cores and/or in re-assessing the execution trajectory of each single task whenever is deemed counterproductive for the performance of the application as a whole.

BibTeX Entry: