Augustus K. Uht · ACM SIGARCH Computer Architecture News · 1993
Our goal is to dramatically increase the performance of uniprocessors through the exploitation of instruction level parallelism, i.e. that parallelism which exists amongst the machine instructions of a program. Speculative execution may help a lot, but, it is argued, both branch prediction and eager execution are insufficient to achieve performances in speedup factors in the tens (with respect to sequential execution), with reasonable hardware costs.A new form of code execution, Disjoint Eager Execution (DEE) , is proposed which uses less hardware than pure eager execution, and has more performance than pure branch prediction; DEE is a continuum between branch prediction and eager execution. DEE is shown to be optimal, when processing resources are constrained.Branches are predicted in DEE, but the predictions should be made in parallel in order to obtain high performance. This is not allowed, however, by the use of the standard insrtruction stream model, the dynamic model (the order is as indicated by the contents of the Program Counter).The use of the static insruction stream is proposed instead. The static instruction stream oreder is the same as the order of the code in memory, and is independent of the execution of branches. It allows reduced branch dependencies, as well.It is argued that a new version, Levo, of an old machine model, CONDEL-2, will be able to attain massive Instruction Level Parallelsim.
Cited by 4
David I. August, Jialu Huang, Thomas B. Jablin et al. · 2011
Previous chapters have discussedmany of the tools available to a programmer looking to parallelize code by hand. While valuable, each requires considerable effort by the programmer beyond that which is required for a typical single-threaded program. As more power is placed in the hands of the programmer, programmers must concern themselves with additional issues only posed by parallel programs-race conditions, deadlock, livelock, and more [1-3]. Furthermore, sequential legacy code presents its own problem. Not designed with parallelism in mind, the programmer may encounter great trouble in transforming the code to a parallel form. Automatic parallelization offers another option to programmers interested in par-allelizing their code. Automatic parallelism extraction techniques do not suffer the same limitations as manual parallelization. Indeed, through analysis, a compiler can often find parallelism in sequential code that is not obvious even to a skilled programmer. However, automatically parallelizing code poses a significant challenge of its own: finding means to extract and exploit parallelism in the code. The compiler must determine first what transformations can be done, and throughout this chapter, we will see a number of the possible techniques in the compiler’s transformation toolbox. Simply put, this means the compiler must both find an exploitable region of code through analysis and transform the code into a parallel form. Analyses and transformations must work together to find and then exploit parallelization opportunities.
Cited by 1
Neal Crago · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2011
We present Outrider, an architecture for throughput-oriented processors that exploits intra-thread memory-level parallelism (MLP) to improve performance efficiency on highly threaded workloads. Outrider enables a single thread of execution to be presented to the \narchitecture as multiple decoupled instruction streams, consisting of either memory accessing or memory consuming instructions. The key insight is that by decoupling the instruction streams, the processor pipeline can expose MLP in a \nway similar to out-of-order designs while relying on a low-complexity in-order micro-architecture. Instead of adding more threads as is done in modern GPUs, Outrider can expose the same MLP with fewer threads and reduced contention for resources shared among threads. \n \nWe demonstrate that Outrider can outperform single-threaded cores by 23-131% and a 4-way simultaneous multi-threaded core by up to 87% in data parallel applications in a 1024-core system. Outrider achieves these performance gains without incurring the overhead of additional hardware thread contexts, which results in improved efficiency compared to a \nmulti-threaded core.
Cited by 0
Milind Girkar, Constantine D. Polychronopoulos · IEEE Transactions on Parallel and Distributed Systems · 1992
Presents the hierarchical task graph (HTG) as an intermediate parallel program representation which encapsulates minimal data and control dependences, and which can be used for the extraction and exploitation of functional, or task-level parallelism. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability to a variety of parallel architectures. The construction of the HTG at a given hierarchy level, the derivation of the execution conditions of tasks which maximizes task-level parallelism, and the optimization of these conditions which results in reducing synchronization overhead imposed by data and control dependences are emphasized. Algorithms for the formation of tasks and their execution conditions based on data and control dependence constraints are presented. The issue of optimization of such conditions is discussed, and optimization algorithms are proposed. The HTG is used as the intermediate representation of parallel Fortran and C programs for generating parallel source as well as parallel machine code.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 187
Ajita John, James C. Browne · 1995
This paper reports on experimental research on extraction of coarse grain parallelism from constraint systems. Constraint specifications are compiled into task level procedural parallel programs in C. Three issues found to be important are: (i) inclusion of operations over structured types as primitives in the representation, (ii) inclusion of modularity in the constraint systems, and (iii) use of functions in the constraint representation. The role of these issues is described. The compilation process focuses on determining the parallel structure defined by the constraints and creates a parallel program in the format of the CODE 2.0 parallel programming environment. The compilation algorithm is described. An example compilation of a constraint system defining a simple numerical algorithm to a parallel C program is given and performance results are reported. Directions for future enhancement of the compilation process are suggested. 1 Introduction and Background Interest in parallel...
Cited by 0
Andreas Konietzko · Zenodo (CERN European Organization for Nuclear Research) · 2009
Konietzko, A. (2009). Parallelism and information structure: ATB-extraction from coordinate ellipsis. In S. Featherston & S. Winkler (eds.), The Fruits of Empirical Linguistics. Volume 2: Product, 179-195. Berlin: de Gruyter.
Cited by 0Open access
Sergei Gorlatch · Lecture notes in computer science · 1996
Cited by 33
Amin, Alaaeldin A.M., Elleithy, Khaled M. · University of Bridgeport ScholarWorks (University of Bridgeport) · 2014
In this paper a new approach for parallelism analysis and extraction of Digital Signal Processing algorithms is introduced. The high level description of the input is given in CIRCAL. A dependency graph of the problem is constructed to check existence of cycles. Loops in the dependency graph are parallelized The approach is illustrated by an example.
Cited by 0
Laboratoire de l'informatique du parallélisme, Boulet, Pierre, Darte, Alain et al. · LARA - Libre Acces aux Rapports scientifiques et techniques · 2006
(eng) In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and their ability to incorporate various optimizing criteria such as maximal parallelism detection, detection of permutable loops , minimization of synchronizations, easiness of code generation, etc. We complete the discussion by presenting new results related to code generation and loop fusion for a particular class of multi-dimensional schedules, called shifted linear schedules. We demonstrate that algorithms based on such schedules, while generally considered as too complex, can indeed lead to simple codes.
Cited by 0
I D E Titesis, George Allen Sawyer, I D~?~t&apos;wnsaimment A et al. · 1990
Cited by 0
Beverly Lynn Vellandi · 1991
Two topics currently of interest to the computer aided design (CAD) for the very large scale integrated circuit (VLSI) community are using the VHSIC Hardware Description Language (VHDL) effectively and decreasing simulation times of VLSI designs through parallel execution of the simulator. The goal of our research is to increase the degree of parallelism obtainable in VHDL simulation, and consequently to decrease simulation times. Our research targets simulation on massively parallel architectures. Experimentation and instrumentation were done on the SIMD Connection Machine. In this thesis we discuss our method used to extract parallelism and restructure a VHDL program, experimental results using this method, and requirements for a parallel architecture for fast simulation.
Cited by 4
Andreas Konietzko · 2009
Cited by 1
Daniel Cordes, Peter Marwedel · 2012
A large amount of research work has been done in the area of automatic parallelization for decades, resulting in a huge amount of tools, which should relieve the designer from the burden of manually parallelizing an application. Unfortunately, most of these tools are only optimizing the execution time by splitting up applications into concurrently executed tasks. In the domain of embedded devices, however, it is not sufficient to look only at this criterion. Since most of these devices are constraint-driven regarding execution time, energy consumption, heat dissipation and other objectives, a good trade-off has to be found to efficiently map applications to multiprocessor system on chip (MPSoC) devices. Therefore, we developed a fully automated multi-objective aware parallelization framework, which optimizes different objectives at the same time. The tool returns a Pareto-optimal front of solutions of the parallelized application to the designer, so that the solution with the best trade-off can be chosen.
Cited by 8
Daniel Cordes, Michael S. Engel, Peter Marwedel et al. · 2012
The development of automatic parallelization techniques has been fascinating researchers for decades. This has resulted in a significant amount of tools, which should relieve the designer from the burden of manually parallelizing an application. However, most of these tools only focus on minimizing execution time which drastically reduces their applicability to embedded devices. It is essential to find good trade-offs between different objectives like, e.g., execution time, energy consumption, or communication overhead, if applications should be parallelized for embedded multiprocessor system-on-chip (MPSoC) devices. Another important aspect which has to be taken into account is the streaming-based structure found in many embedded applications such as multimedia and network services. The best way to parallelize these applications is to extract pipeline parallelism. Therefore, this paper presents the first multi-objective aware approach exploiting pipeline parallelism automatically to make it most suitable for resource-restricted embedded devices. We have compared the new pipeline parallelization approach to an existing task-level extraction technique. The evaluation has shown that the new approach extracts very efficient multi-objective aware parallelism. In addition, the two approaches have been combined and it could be shown that both approaches perfectly complement each other.
Cited by 5
Guyue Wang, Shinichi Yamagiwa, Koichi Wada · 2014
Manycore architecture promotes a massively parallel computing on the accelerators. Especially GPU is one of the main series of the high performance computing, which is also employed by top supercomputers in the world. The programming method on such accelerators includes development of a control program. The accelerator executes it to schedule the invocation timing of the accelerator's kernel program. The kernel program needs to be written based on the stream computing paradigm. Connecting I/Os of the kernel programs, we can develop a large application. When we consider the processing flow as a directed graph, we can implement a GUI-based programming tool for the accelerators. It visualizes a pipeline-based processing flow. However, it is very hard to find the starting point of a complex processing flow. Moreover, although the processing pipeline should include the potential parallelism, it is hard for the programmer to exploit it intuitively. This paper proposes an algorithm applying the spanning tree that mechanically exploits the parallelism and determines an execution order.
Cited by 2
Kelly Chiqueto, Guilherme Janson, Carina Thaís de Almeida et al. · American Journal of Orthodontics and Dentofacial Orthopedics · 2011
Cited by 25Open access
S.F. Mendes, Pedro Sampaio · 2002
This work deals with query optimization far parallel object-oriented databases using rule-based optimizers. The solution enacted departs from an existing non-parallel database query optimizer and extends it with a parallelism extraction module that modifies the original query optimizer to generate query plans for a parallel OODBMS architecture. The ideas are applied in the design of a parallel optimizer for OQL. The implementation approach shows that the parallelism extraction technique combined with a rule-based optimizer generator tool can help to produce a parallel optimizer from a non-parallel one with minimum effort.
Cited by 1
Tesis Doctorals en Xarxa (Consorci de Serveis Universitaris de Catalunya)
Cited by 0
Georgios Tournavitis, Björn Franke · 2010
In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
Cited by 46
Laboratoire de l'informatique du parallélisme, Darte, Alain, Vivien, Frédéric · LARA - Libre Acces aux Rapports scientifiques et techniques · 2006
(eng) We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.
Cited by 0