Edson Pedro Ferlin · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 1997
Este trabalho aborda alguns conceitos e definições de processamento paralelo, que são aplicados a paralelização automática, e também às análises e condições para as dependências dos dados, de modo a aplicarmos os métodos de paralelização: Hiperplano, Transformação Unimodular, Alocação de Dados Sem Comunicação e Particionamento & Rotulação. Desta forma, transformamos um programa seqüencial em seu equivalente paralelo. Utilizando-os em um sistema de memória distribuída com comunicação através da passagem de mensagem MPI (Message-Passing Interface), e obtemos algumas métricas para efetuarmos as avaliações/comparações entre os métodos.
Cited by 0
Revol, Nathalie, Yahya Ould Mohammed El Hadj, Institut National de Recherche en Informatique et en Automatique (INRIA), 38 - Montbonnot-Saint-Martin (France). Unite de Recherche Rhone-Alpes · OpenGrey (Institut de l'Information Scientifique et Technique) · 2001
Cited by 0Open access
Dierstein, Anne, Hayer, Roman, Rauber, Thomas · ERef Bayreuth (University of Bayreuth) · 1993
Cited by 1
Manish Gupta Sayak, Manish Gupta, Sayak Mukhopadhyay et al. · 1999
Parallelizing compilers have traditionally focussed mainly on parallelizing loops. This paper presents a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis to detect the independence of multiple recursive calls in a procedure. This allows exploitation of a scalable form of nested parallelism, where each parallel task can further spawn off parallel work in subsequent recursive calls. We describe a run-time system which efficiently supports this kind of nested parallelism without unnecessarily blocking tasks. We have implemented this framework in a parallelizing compiler, which is able to automatically parallelize programs like quicksort and mergesort, written in C. For cases where even the advanced symbolic analysis and array section analysis we describe are not able to prove the independence of procedure calls, we propose novel techniques for speculative run-time parallelization, which are more efficient and powerful in this context than analogous techniques proposed previously for speculatively parallelizing loops. Our experimental results on an IBM G30 SMP machine show good speedups obtained by following our approach. 1
Cited by 0
yann Orlarey, Stéphane Letz, Dominique Fober · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
International audience
Cited by 1Open access
Manish Gupta, S. Mikhopadhyay, N. Sinha · 2003
Parallelizing compilers have traditionally focused mainly on parallelizing loops. We present a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis to detect the independence of multiple recursive calls in a procedure. This allows exploitation of a scalable form of nested parallelism, where each parallel task can further spawn off parallel work in subsequent recursive calls. We describe a run-time system which efficiently supports this kind of nested parallelism without unnecessarily blocking tasks. We have implemented this framework in a parallelizing compiler, which is able to automatically parallelize programs like quicksort and mergesort, written in C. For cases where even the advanced symbolic analysis and array section analysis we describe are not able to prove the independence of procedure calls, we propose novel techniques for speculative run-time parallelization, which are more efficient and powerful in this context than analogous techniques proposed previously for speculatively parallelizing loops. Our experimental results on an IBM G30 SMP machine show good speedups obtained by following our approach.
Cited by 8
Michel Cosnard, Emmanuel Jeannot · 1997
Cited by 2
Nadya Bliss · 2008
Cited by 0
Peter Kraft, Amos Waterland, Daniel Y. Fu et al. · arXiv (Cornell University) · 2018
Prior work on Automatically Scalable Computation (ASC) suggests that it is possible to parallelize sequential computation by building a model of whole-program execution, using that model to predict future computations, and then speculatively executing those future computations. Although that prior work demonstrated scaling, it did not demonstrate speedup, because it ran entirely in emulation. We took this as a challenge to construct a hardware prototype that embodies the ideas of ASC, but works on a broader range of programs and runs natively on hardware. The resulting system is similar in spirit to the original work, but differs in practically every respect. We present an implementation of the ASC architecture that runs natively on x86 hardware and achieves near-linear speedup up to 44-cores (the size of our test platform) for several classes of programs, such as computational kernels, map-style programs, and matrix operations. We observe that programs are either completely predictable, achieving near-perfect predictive accuracy, or totally unpredictable, and therefore not amenable to scaling via ASC-like techniques. We also find that in most cases, speedup is limited only by implementation details: the overhead of our dependency tracking infrastructure and the manipulation of large state spaces. We are able to automatically parallelize programs with linked data structures that are not amenable to other forms of automatic parallelization.
Cited by 2Open access
Mohammad Raza, Cristiano Calcagno, Philippa Gardner · Lecture notes in computer science · 2009
Cited by 41
Shigeyuki Sato, Hideya Iwasaki · ACM SIGPLAN Notices · 2011
Existing work that deals with parallelization of complicated reductions and scans focuses only on formalism and hardly dealt with implementation. To bridge the gap between formalism and implementation, we have integrated parallelization via matrix multiplication into compiler construction. Our framework can deal with complicated loops that existing techniques in compilers cannot parallelize. Moreover, we have sophisticated our framework by developing two sets of techniques. One enhances its capability for parallelization by extracting max-operators automatically, and the other improves the performance of parallelized programs by eliminating redundancy. We have also implemented our framework and techniques as a parallelizer in a compiler. Experiments on examples that existing compilers cannot parallelize have demonstrated the scalability of programs parallelized by our implementation.
Cited by 30
Neha Singh · 2016
Nowdays we can see change in technology from single core to multicore. Even though the Systems are Nowdays we can see change in technology from single core to multicore. Even though the Systems are provided with multicore processors only one of the core is utilized for the execution of C program. In computers, parallel processing is the processing of program instructions by dividing them among multiple processors or multiple cores with the objective of running a program in less time. Here in our paper we try to parallelize any complex C program automatically by inserting OpenMP pragmas before loops present in C program thereby reducing the time required for execution moreover leading to proper utilization of CPU.
Cited by 2
Hal Id Inria, Clément Hurlin · 2009
HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. appor t t e ch n i qu e
Cited by 0
Manish Gupta, Sayak Mukhopadhyay, N. Sinha · International Journal of Parallel Programming · 2000
Cited by 44
Sepideh Maleki, Martin Burtscher · 2018
Linear recurrences encompass many fundamental computations including prefix sums and digital filters. Later result values depend on earlier result values in recurrences, making it a challenge to compute them in parallel. We present a new work- and space-efficient algorithm to compute linear recurrences that is amenable to automatic parallelization and suitable for hierarchical massively-parallel architectures such as GPUs. We implemented our approach in a domain-specific code generator that emits optimized CUDA code. Our evaluation shows that, for standard prefix sums and single-stage IIR filters, the generated code reaches the throughput of memory copy for large inputs, which cannot be surpassed. On higher-order prefix sums, it performs nearly as well as the fastest handwritten code from the literature. On tuple-based prefix sums and digital filters, our automatically parallelized code outperforms the fastest prior implementations.
Cited by 6
Deokhwan Kim, Saša Misailovíc, Martin Rinard · DSpace@MIT (Massachusetts Institute of Technology) · 2010
Traditional parallelizing compilers are designed to generate parallel programs that produce identical outputs as the original sequential program. The difficulty of performing the program analysis required to satisfy this goal and the restricted space of possible target parallel programs have both posed significant obstacles to the development of effective parallelizing compilers. The QuickStep compiler is instead designed to generate parallel programs that satisfy statistical accuracy guarantees. The freedom to generate parallel programs whose output may differ (within statistical accuracy bounds) from the output of the sequential program enables a dramatic simplification of the compiler and a significant expansion in the range of parallel programs that it can legally generate. QuickStep exploits this flexibility to take a fundamentally different approach from traditional parallelizing compilers. It applies a collection of transformations (loop parallelization, loop scheduling, synchronization introduction, and replication introduction) to generate a search space of parallel versions of the original sequential program. It then searches this space (prioritizing the parallelization of the most time-consuming loops in the application) to find a final parallelization that exhibits good parallel performance and satisfies the statistical accuracy guarantee. At each step in the search it performs a sequence of trial runs on representative inputs to examine the performance, accuracy, and memory accessing characteristics of the current generated parallel program. An analysis of these characteristics guides the steps the compiler takes as it explores the search space of parallel programs. Results from our benchmark set of applications show that QuickStep can automatically generate parallel programs with good performance and statistically accurate outputs. For two of the applications, the parallelization introduces noise into the output, but the noise remains within acceptable statistical bounds. The simplicity of the compilation strategy and the performance and statistical acceptability of the generated parallel programs demonstrate the advantages of the QuickStep approach.
Cited by 7Open access
Hans Vandierendonck, Koen De Bosschere · 2011
The efficient development of multi-threaded software has, for many years, been an unsolved problem in computer science. Finding a solution to this problem has become urgent with the advent of multi-core processors. Furthermore, the problem has become more complicated because multi-cores are everywhere (desktop, laptop, embedded system). As such, they execute generic programs which exhibit very different characteristics than the scientific applications that have been the focus of parallel computing in the past. Implicitly parallel programming is an approach to parallel pro-gramming that promises high productivity and efficiency and rules out synchronization errors and race conditions by design. There are two main ingredients to implicitly parallel programming: (i) a con-ventional sequential programming language that is extended with annotations that describe the semantics of the program and (ii) an automatic parallelizing compiler that uses the annotations to in-crease the degree of parallelization. It is extremely important that the annotations and the automatic parallelizing compiler are designed with the target application do-main in mind. In this paper, we discuss the Paralax approach to im-plicitly parallel programming and we review how the annotations and the compiler design help to successfully parallelize generic programs. We evaluate Paralax on SPECint benchmarks, which are a model for such programs, and demonstrate scalable speedups, up to a factor of 6 on 8 cores.
Cited by 0
Diego Novillo · 2006
This paper describes the design and implementation of the OpenMP specification v2.5 in GCC. The implementation supports all the languages specified in the standard (C, C++ and Fortran), and it is generally available on any platform that supports POSIX threads. Emphasis is placed on the internal architecture and, in particular, the intermediate representation, which could be used in the implementation of automatic parallelization techniques. The paper also presents performance results on the SPEC OMP2001 benchmark. 1
Cited by 0
Cristianno Martins Vieira · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2010
Orientador: Sandro Rigo
Cited by 0Open access
Jaekyu Cho · 2002
In parallelizing huge legacy codes such as NCARIPenn State MMS, a proper software environment is critical for reducing the time and effort. This thesis presents an empirical study of automatic parallelization based on the NCAR/Penn State MMS model, the Pacific Northwest National Laboratory (PNNL) version of MMS and a FDM benchmark program. ParAgent, a tool for automatic parallelization, VisS-D a visualization tool, a web-based monitor, and Rabbit, a performance analysis tool were used in this study. In addition, ahigh-level communication library was developed to complement the use of ParAgent.
Cited by 0Open access