Modeling optimistic concurrency using quantitative dependence analysis
Modeling optimistic concurrency using quantitative dependence analysis
复制标题
使用定量依赖分析对乐观并发进行建模
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Călin Caşcaval
中科院分区：
文献类型：
--
作者：
C. V. Praun;R. Bordawekar;Călin Caşcaval
这项工作提出了一种定量的方法来分析程序中的并行化机会与不规则的内存访问潜在的数据依赖屏蔽可用的并行性。该模型捕获关键部分之间的数据和因果依赖关系作为算法属性，并将其量化为在执行指令的数量上计算的密度。该模型从运行时方面进行抽象，例如调度、线程数量和在特定并行化中使用的并发控制。我们说明了几个应用程序的模型，需要有序和无序执行的关键部分。我们描述了一个运行时的工具，计算从一个确定性的单线程程序执行的依赖密度。这种密度度量提供了对乐观并行化的潜力、算法调度的机会以及由于同步瓶颈而导致的性能缺陷的深入了解。根据我们的分析结果，我们将应用程序分为三类，低，中，高的依赖密度。具有低依赖性密度的应用程序自然是乐观并发的良好候选者，具有中等密度的应用程序可能需要知道乐观并发的算法依赖性的调度器才能有效，而具有高依赖性密度的应用程序可能不适合并行化。
This work presents a quantitative approach to analyze parallelization opportunities in programs with irregular memory access where potential data dependencies mask available parallelism. The model captures data and causal dependencies among critical sections as algorithmic properties and quantifies them as a density computed over the number of executed instructions. The model abstracts from runtime aspects such as scheduling, the number of threads, and concurrency control used in a particular parallelization. We illustrate the model on several applications requiring ordered and unordered execution of critical sections. We describe a run-time tool that computes the dependence densities from a deterministic single-threaded program execution. This density metric provides insights into the potential for optimistic parallelization, opportunities for algorithmic scheduling, and performance defects due to synchronization bottlenecks. Based on the results of our analysis, we classify applications into three categories with low, medium, and high dependence densities. Applications with low dependence density are naturally good candidates for optimistic concurrency, applications with medium density may require a scheduler that is aware of the algorithmic dependencies for optimistic concurrency to be effective, and applications with high dependence density may not be suitable for parallelization.