|
Frameworks Supporting The Polyhedral Model
Use of the polyhedral model (also called the polytope model) within a compiler requires software to represent the objects of this framework (sets of integer-valued points in regions of various spaces) and perform operations upon them (e.g., testing whether the set is empty). For more detail about the objects and operations in this model, and an example relating the model to the programs being compiled, see the polyhedral model page. There are many frameworks supporting the polyhedral model. Some of these frameworks use one or more libraries for performing polyhedral operations. Others, notably Omega, combine everything in a single package. Some commonly used libraries are the Omega Library (and a more recent fork), piplib,Paul Feautrier. ''Parametric Integer Programming.'' 1988 PolyLib, PPL, isl, the Cloog polyhedral code generator,Cedric Bastoul. ''Code Generation in the Polyhedral Model Is Easier Than You Think.'' PACT'13 IEEE International Conference on Parallel Architecture ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polytope Model
The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of operations -- too large to be explicitly enumerated -- thereby requiring a ''compact'' representation. Nested loop programs are the typical, but not the only example, and the most common use of the model is for loop nest optimization in program optimization. The polyhedral method treats each loop iteration within nested loops as lattice points inside mathematical objects called polyhedra, performs affine transformations or more general non-affine transformations such as tiling on the polytopes, and then converts the transformed polytopes into equivalent, but optimized (depending on targeted optimization goal), loop nests through polyhedra scanning. Simple example Consider the following example written in C: const int n = 100; int i, j, a n]; for (i = 1; i < n; i++) The essential problem with this code is that each iteration of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scalable Locality
Computer software is said to exhibit scalable localityDavid Wonnacott. ''Achieving Scalable Locality with Time Skewing.'' International Journal of Parallel Programming 30.3 (2002) if it can continue to make use of processors that out-pace their memory systems, to solve ever larger problems. This term is a high-performance uniprocessor analog of the use of scalable parallelism to refer to software for which increasing numbers of processors can be employed for larger problems. Overview Consider the memory usage patterns of the following loop nest (an iterative two-dimensional stencil computation): for t := 0 to T do for i := 1 to N-1 do for j := 1 to N-1 do new(i,j) := (A(i-1,j) + A(i,j-1) + A(i,j) + A(i,j+1) + A(i+1,j)) * .2 end end for i := 1 to N-1 do for j := 1 to N-1 do A(i,j) := new(i,j) end end end The entire loop nest touches about 2*N**2 array elements, and performs about 5*T*N**2 floating-point op ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Haverford College
Haverford College ( ) is a private liberal arts college in Haverford, Pennsylvania. It was founded as a men's college in 1833 by members of the Religious Society of Friends (Quakers), began accepting non-Quakers in 1849, and became coeducational in 1980. The college offers Bachelor of Arts and Bachelor of Science degrees in 31 majors across humanities, social sciences and natural sciences disciplines. It is a member of the Tri-College Consortium, which includes Bryn Mawr College, Bryn Mawr and Swarthmore College, Swarthmore colleges, as well as the Quaker Consortium, which includes those schools as well as the University of Pennsylvania. All the college's approximately 1300 students are undergraduates, and nearly all reside on campus. Social and academic life is governed by an academic honor code, honor code and influenced by Quaker philosophy. Its suburban campus has predominantly stone Quaker Colonial Revival architecture. The college's athletics teams compete as Haverford For ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Loop Nest Optimization
In computer science and particularly in compiler design, loop nest optimization (LNO) is an optimization technique that applies a set of loop transformations for the purpose of locality optimization or parallelization or another loop overhead reduction of the loop nests. (Nested loops occur when one loop is inside of another loop.) One classical usage is to reduce memory access latency or the cache bandwidth necessary due to cache reuse for some common linear algebra algorithms. The technique used to produce this optimization is called loop tiling, also known as loop blocking or strip mine and interchange. Overview Loop tiling partitions a loop's iteration space into smaller chunks or blocks, so as to help ensure data used in a loop stays in the cache until it is reused. The partitioning of loop iteration space leads to partitioning of a large array into smaller blocks, thus fitting accessed array elements into cache size, enhancing cache reuse and eliminating cache size requir ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Loop Dependence Analysis
In computer science, loop dependence analysis is a process which can be used to find dependencies within iterations of a loop with the goal of determining different relationships between statements. These dependent relationships are tied to the order in which different statements access memory locations. Using the analysis of these relationships, execution of the loop can be organized to allow multiple processors to work on different portions of the loop in parallel. This is known as parallel processing. In general, loops can consume a lot of processing time when executed as serial code. Through parallel processing, it is possible to reduce the total execution time of a program through sharing the processing load among multiple processors. The process of organizing statements to allow multiple processors to work on different portions of a loop is often referred to as parallelization. In order to see how we can exploit parallelization, we have to first analyze the dependencies with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex Enumeration
In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities: :Ax \leq b where ''A'' is an ''m''×''n'' matrix, ''x'' is an ''n''×1 column vector of variables, and ''b'' is an ''m''×1 column vector of constants. The inverse (dual) problem of finding the bounding inequalities given the vertices is called '' facet enumeration'' (see convex hull algorithms). Computational complexity The computational complexity of the problem is a subject of research in computer science. For unbounded polyhedra, the problem is known to be NP-hard, more precisely, there is no algorithm that runs in polynomial time in the combined input-output size, unless P=NP. A 1992 arti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Z-polyhedra
The study of integer points in convex polyhedra is motivated by questions such as "how many nonnegative integer-valued solutions does a system of linear equations with nonnegative coefficients have" or "how many solutions does an integer linear program have". Counting integer points in polyhedra or other questions about them arise in representation theory, commutative algebra, algebraic geometry, statistics, and computer science. The set of integer points, or, more generally, the set of points of an affine lattice, in a polyhedron is called Z-polyhedron, from the mathematical notation \mathbb or Z for the set of integer numbers."Computations on Iterated Spaces" in: The Compiler Design Handbook: Optimizations and Machine Code Generation, CRC Press 2007, 2nd edition, p.15-7/ref> Properties For a lattice Λ, Minkowski's theorem relates the number d(Λ) (the volume of a fundamental parallelepiped of the lattice) and the volume of a given symmetric convex set ''S'' to the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer Programming
An integer programming problem is a mathematical optimization or Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are Linear function (calculus), linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. If some decision variables are not discrete, the problem is known as a mixed-integer programming problem. Canonical and standard form for ILPs In integer linear programming, the ''canonical form'' is distinct from the ''standard form''. An integer linear program in canonical form is expressed thus (note that it is the \mathbf vector which is to be decided): : \begin & \text && \math ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alexander Barvinok
Alexander I. Barvinok (born March 27, 1963) is a professor of mathematics at the University of Michigan. Barvinok received his Ph.D. from St. Petersburg State University in 1988 under the supervision of Anatoly Moiseevich Vershik. In 1999 Barvinok received the Presidential Early Career Award for Scientists and Engineers (PECASE) from President Bill Clinton. Barvinok gave an invited talk at the 2006 International Congress of Mathematicians in Madrid. In 2012, Barvinok became a Fellow of the American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, .... References Living people Fellows of the American Mathematical Society 20th-century American mathematicians 21st-century American mathematicians Russian mathematicians University of Michigan faculty ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scalable Parallelism
Software is said to exhibit scalable parallelism if it can make use of additional processors to solve larger problems, i.e. this term refers to software for which Gustafson's law holds. Consider a program whose execution time is dominated by one or more loops, each of that updates every element of an array --- for example, the following finite difference heat equation stencil calculation: for t := 0 to T do for i := 1 to N-1 do new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // explicit forward-difference with R = 0.25 end for i := 1 to N-1 do A(i) := new(i) end end In the above code, we can execute all iterations of each "i" loop concurrently, i.e., turn each into a parallel loop. In such cases, it is often possible to make effective use of twice as many processors for a problem of array size 2N as for a problem of array size N. As in this example, scalable parallelism is typically a form of data parallelism. This form of paralleli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language (e.g. assembly language, object code, or machine code) to create an executable program. Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman - Second Edition, 2007 There are many different types of compilers which produce output in different useful forms. A ''cross-compiler'' produces code for a different CPU or operating system than the one on which the cross-compiler itself runs. A ''bootstrap compiler'' is often a temporary compiler, used for compiling a more permanent or better optimised compiler for a language. Related software include, a program that translates from a low-level language to a h ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
