Franke, Bjoern

Castaneda Lozano, Roberto

Jackson, Paul

O'Boyle, Michael

Vasiladiotis, Christos

2023-01-17T16:56:04Z

2023-01-17T16:56:04Z

2023-01-17

Parallel computer architectures have dominated the computing landscape for the past two decades; a trend that is only expected to continue and intensify, with increasing specialization and heterogeneity. This creates huge pressure across the software stack to produce programming languages, libraries, frameworks and tools which will efficiently exploit the capabilities of parallel computers, not only for new software, but also revitalizing existing sequential code. Automatic parallelization, despite decades of research, has had limited success in transforming sequential software to take advantage of efficient parallel execution. This thesis investigates three approaches that use commutativity analysis as the enabler for parallelization. This has the potential to overcome limitations of traditional techniques. We introduce the concept of liveness-based commutativity for sequential loops. We examine the use of a practical analysis utilizing liveness-based commutativity in a symbolic execution framework. Symbolic execution represents input values as groups of constraints, consequently deriving the output as a function of the input and enabling the identification of further program properties. We employ this feature to develop an analysis and discern commutativity properties between loop iterations. We study the application of this approach on loops taken from real-world programs in the OLDEN and NAS Parallel Benchmark (NPB) suites, and identify its limitations and related overheads. Informed by these findings, we develop Dynamic Commutativity Analysis (DCA), a new technique that leverages profiling information from program execution with specific input sets. Using profiling information, we track liveness information and detect loop commutativity by examining the code’s live-out values. We evaluate DCA against almost 1400 loops of the NPB suite, discovering 86% of them as parallelizable. Comparing our results against dependence-based methods, we match the detection efficacy of two dynamic and outperform three static approaches, respectively. Additionally, DCA is able to automatically detect parallelism in loops which iterate over Pointer-Linked Data Structures (PLDSs), taken from wide range of benchmarks used in the literature, where all other techniques we considered failed. Parallelizing the discovered loops, our methodology achieves an average speedup of 3.6× across NPB (and up to 55×) and up to 36.9× for the PLDS-based loops on a 72-core host. We also demonstrate that our methodology, despite relying on specific input values for profiling each program, is able to correctly identify parallelism that is valid for all potential input sets. Lastly, we develop a methodology to utilize liveness-based commutativity, as implemented in DCA, to detect latent loop parallelism in the shape of patterns. Our approach applies a series of transformations which subsequently enable multiple applications of DCA over the generated multi-loop code section and match its loop commutativity outcomes against the expected criteria for each pattern. Applying our methodology on sets of sequential loops, we are able to identify well-known parallel patterns (i.e., maps, reduction and scans). This extends the scope of parallelism detection to loops, such as those performing scan operations, which cannot be determined as parallelizable by simply evaluating liveness-based commutativity conditions on their original form.

https://hdl.handle.net/1842/39718

http://dx.doi.org/10.7488/era/2967

en

The University of Edinburgh

Stanislav Manilov, Christos Vasiladiotis, and Björn Franke. “Generalized Profile Guided Iterator Recognition”. In: Proceedings of the 27th International Confer ence on Compiler Construction - CC 2018. Vienna, Austria: ACM Press, 2018, pp. 185–195. ISBN: 978-1-4503-5644-2. DOI: 10.1145/3178372.3179511.

C. Vasiladiotis et al. “Loop Parallelization Using Dynamic Commutativity Analysis”. In: 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). Feb. 2021, pp. 150–161. DOI: 10.1109/CGO51591. 2021.9370319.

Chris Vasiladiotis. Iterator Recognition Code Repository. https://github.com/ compor/IteratorRecognition. July 2019.

Tobias J. K. E. von Koch, Stanislav Manilov, Christos Vasiladiotis, Murray Cole, and Björn Franke “Towards a Compiler Analysis for Parallel Algorithmic Skeletons” in Proceedings of the 27th International Conference on Compiler Construction (CC 2018), Vienna, Austria, 2018

Aleksandr Maramzin, Christos Vasiladiotis, Roberto Castañeda Lozano, Murray Cole, and Björn Franke ““It Looks Like You’re Writing a Parallel Loop”: A Machine Learning Based Parallelization Assistant” in Proceedings of the 6th ACM SIGPLAN International Workshop on AI-Inspired and Empirical Methods for Software Engineering on Parallel Computing Systems (AI-SEPS 2019), Athens, Greece, 2019

Nishil Talati, Kyle May, Armand Behroozi, Yichen Yang, Kuba Kaszyk, Christos Vasiladiotis, Tarunesh Verma, Lu Li, Brandon Nguyen, Jiawen Sun, John Magnus Morton, Agreen Ahmadi, Todd Austin, Michael O’Boyle, Scott Mahlke, Trevor Mudge, Ronald Dreslinski “Prodigy: Improving the Memory Latency of Data-Indirect Irregular Workloads Using Hardware-Software Co-Design’ in Proceedings of the 27th IEEE International Symposium on High-Performance Computer Architecture, (HPCA 2021), Virtual, Republic of Korea, 2021

parallelism

parallelization

compiler

commutativity models

liveness-based commutativity

NPB suites

Dynamic Commutativity Analysis

Structured parallelism discovery with hybrid static-dynamic analysis and evaluation techniques

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy