CSC/ECE 506 Spring 2013/4a aj: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(100 intermediate revisions by 2 users not shown)
Line 3: Line 3:
This wiki article was directed by [https://docs.google.com/a/ncsu.edu/document/d/1cShv7MK21_EinS1UA_uXBzijjcpenmsSUMicP_kW8Wg/edit Wiki Topics for Chapters 3 and 4]
This wiki article was directed by [https://docs.google.com/a/ncsu.edu/document/d/1cShv7MK21_EinS1UA_uXBzijjcpenmsSUMicP_kW8Wg/edit Wiki Topics for Chapters 3 and 4]


==Identification <ref>http://www.bukisa.com/articles/13059_supercomputer-evolution</ref>==
==Identification==
A primary goal of the compiler is to identify opportunities for parallelization and to this end it may use feedback from the developer, high-level language constructs, low-level language constructs, and/or runtime data. Whereas processors focus on instruction-level parallelism and operating systems focus on program-level parallelization, compilers focus on loop-level and task-level parallelization to potentially improve performance. The data parallel style is based on the ability to have part of the data worked on by each processor. The functional style is based on the ability to simultaneously execute different statements or subroutines on different processors.
===Data/Loop-level Parallelism===
{| align="right"
| [[Image:grid.png|thumb|right|200px|8x8 Array of processing elements]]
|}


[[Image:kcomp1.jpg|thumb|right|400px|The K computer of Fujitsu leads the Top500 list as of November 2011]]
<pre style="overflow:auto;">
[[Image:kcomp2.jpg|thumb|right|250px|A 'K computer' rack. Each computer rack is equipped with about 100 CPUs]]
<code>
 
//Embarrassingly parallel or pleasingly parallel code
 
for (int i=0; i<N; i++)  
A supporting example of a data parallel code can be seen in Code 2.5 from [[#References | Solihin (2008)]]. Shown below, it has been annotated with comments identifying the region of the code which is data parallel.
 
//Data parallel code, easily parallelizable
for (int i=0; i<N; i++)  
     {
     {
     for (int j=0; j<N; j++)
     for (int j=0; j<N; j++)
Line 19: Line 20:
         }  
         }  
     }
     }
</code>
</pre>
In the code above, both loops can be parallelized. You can imagine an NxN grid of processors like the one shown at the right, with each processor working on one element of the array. However, this is often not done by compilers as the inner loop often incurs too much overhead. In this case you can imagine a single row of processors with each processor responsible for a single column. In both cases, each processor is executing the same instructions at roughly the same time using different data.


In the code above, the three 8 element arrays are each divided into two 4 element chunks. In the data parallel section, the code executed by the two threads is identical, but each thread operates on a different chunk of data.
<code>
//Not obviously parallelizable code
  for (int i=1; i<N; i++)
    {
    for (int j=1; j<N; j++)
        {
        A[i][j] = B[i-1][j] + C[i][j-1];  //dependencies on both previous iterations
        }
    }
</code>
However, the code above is parallelizable by sweeping the anti-diagonals. A problem with this approach however will be maintaining a reasonable load across all the processors as some processors will have little work.


===Algorithm/Task-level/Functional Parallelism===
{| align="right"
| [[Image:Two_procs.png|thumb|right|200px|Two separate subroutines executing on two separate processors]]
|}


==Paradigms<ref>http://www.cray.com/Assets/PDF/about/CrayTimeline.pdf</ref>==
<pre style="overflow:auto;">
 
<code>
[[Image:cray1.jpg|thumb|right|300px|Cray 1 supercomputer installed at Lawrence Livermore National Laboratory (LLNL), California, USA.]]
//Functionally parallel code
[[Image:cray-t3e.gif|thumb|right|300px|The Cray-T3E-1200E supercomputer]]
for (int i=0; i<N; i++)
 
    {
In 1993 Fujitsu sprung a surprise to the world by announcing a Vector Parallel Processor (VPP) series that was designed for reaching in the range of hundreds of Gflop/s. At the core of the system is a combined Ga-As/Bi-CMOS processor, based largely on the original design of the VP-200. The processor chips gate delay was made as low as 60 ps in the Ga-As chips by using the most advanced hardware technology available. The resulting cycle time was 9.5 ns. The processor has four independent pipelines each capable of executing two Multiply-Add instructions in parallel resulting in a peak speed of 1.7 Gflop/s per processor. Each processor board is equipped with 256 Megabytes of central memory.
    A[i][j] = B[i][j] + C[i][j];  //no dependencies on previous iterations
    D[i][j] = E[i][j] + C[i][j];  //no dependencies on previous iterations
    }
The above code can be split out as two for loops that execute simultaneously
for (int i=0; i<N; i++)
    {
    A[i][j] = B[i][j] + C[i][j];  //no dependencies on previous iterations
    }
for (int i=0; i<N; i++)
    {
    D[i][j] = E[i][j] + C[i][j];  //no dependencies on previous iterations
    }
</code>
</pre>
In the above case, parallelism was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel. A figure of two processing elements working on different routines is depicted to the right.


===Static<ref>http://www.versionone.com/Agile101/Methodologies.asp </ref>===
==Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref><ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>==
Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.


Static analysis is the most rudimentary form of automatic parallelism, simply relying on the input source code for information.
===Scalar and Array Analysis===
[[Image:Array_analysis.gif|thumb|right|300px|Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>]]


===Speculative <ref>http://www.netlib.org/benchmark/top500/reports/report94/Japan/node5.html</ref>===
Scalar and array analyses are usually performed in conjunction with each other in imperative, low-level languages like C or FORTRAN. "Scalar analysis breaks down a program to analyze scalar variable use and the dependencies that they have." The scalar analysis will find anything that it deems can be parallelized and any sections that it cannot find to be parallelizable, it is left to the array analysis.


In 1977 [http://en.wikipedia.org/wiki/Fujitsu Fujitsu] produced the first supercomputer prototype called the F230-75 APU which was a pipelined vector processor added to a scalar processor. This attached processor was installed in the Japanese Atomic Energy Commission (JAERI) and the National Aeronautic Lab (NAL).
One type of array analysis is called array data-flow analysis where the compiler will look for array data that can be privatizable. This privatization can allocate a local copy of an array so different threads in the program can work on different parts of the array. However, if there are any loop-carried dependencies, the analysis will deem that the array is not privatizable, thus not parallizable.


===Dynamic===
Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.


In 1993 Fujitsu sprung a surprise to the world by announcing a Vector Parallel Processor (VPP) series that was designed for reaching in the range of hundreds of Gflop/s. At the core of the system is a combined Ga-As/Bi-CMOS processor, based largely on the original design of the VP-200. The processor chips gate delay was made as low as 60 ps in the Ga-As chips by using the most advanced hardware technology available. The resulting cycle time was 9.5 ns. The processor has four independent pipelines each capable of executing two Multiply-Add instructions in parallel resulting in a peak speed of 1.7 Gflop/s per processor. Each processor board is equipped with 256 Megabytes of central memory.
===Commutativity Analysis===
Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the [http://en.wikipedia.org/wiki/Commutative_property commutativity property] in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:


===Interactive===
1. "The new value of each instance variable of the receiver objects of A and B must be the same after the execution of the object section of A followed by the object section of B as after the execution of the object section of B followed by the object section of A"


This paradigm has the ability to extract additional coarse-grained parallelism by seeking feedback from the developer.
2. "The multiset of operations directly invoked by either A or B under the execution order A followed by B must be the same as the multiset of operation directly invoked by either A or B under the execution order B followed by A"


===Polytope Model===
In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>


Deals with an abstraction to polygons, polyhedrons, or more generally polytopes. http://en.wikipedia.org/wiki/Polytope_model
===Polytope Method===
[[Image:Polytope.png|thumb|right|200px|Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>]]


== Pitfalls==
The [http://en.wikipedia.org/wiki/Polyhedral_model Polytope Model], or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.


[http://en.wikipedia.org/wiki/Hitachi Hitachi] has been producing supercomputers since 1983 but differs from other manufacturers by not exporting them. For this reason, their supercomputers are less well known in the West. After having gone through two generations of supercomputers, the S-810 series started in 1983 and the S-820 series in 1988, Hitachi leapfrogged NEC in 1992 by announcing the most powerful vector supercomputer ever.The top S-820 model consisted of one processor operating at 4 ns and contained 4 vector pipelines with four pipelines and two independent floating-point units. This corresponded to a peak performance of 2 Gflop/s. Hitachi put great emphasis on a fast memory although this meant limiting its size to a maximum of 512 MB. The memory bandwidth of 2 words per pipe per vector cycle, giving a peak rate of 16 GB/s was a respectable achievement, but it was not enough to keep all functional units busy.
===Profile Driven===
Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.


The S-3800 was announced two years ago and is comparable to NEC's SX- 3R in its features. It has up to four scalar processors with a vector processing unit each. These vector units have in turn up to four independent pipelines and two floating point units that can each perform a multiply/add operation per cycle. With a cycle time of 2.0 ns, the whole system achieves a peak performance level of 32 Gflop/s.
===Speculation===
 
Thread-level speculation refers to an environment where execution threads operate speculatively, performing potentially unsafe operations, and temporarily buffering the state they generate in a buffer or cache.<ref>http://iacoma.cs.uiuc.edu/iacoma-papers/encyclopedia_tls.pdf</ref> At some later point, it is determined whether the operations were correct or not, and if not then the thread is killed and may restart. Otherwise, the changes are committed and perhaps performance improvements that were non-obvious have taken place.
The S-3600 systems can be seen as the design of the S-820 recast in more modern technology. The system consists of a single scalar processor with an attached vector processor. The 4 models in the range correspond to a successive reduction of the number of pipelines and floating point units installed.
Link showing the list of the top 500 super computers
[http://www.top500.org/list/2009/11/100 top 500 super computers].
Link showing the statistics of top 500 supercomputer
[http://www.top500.org/static/lists/2009/11/top500_statistics.pdf statistics]


==Limitations==
==Limitations==
[[Image:ibm704.jpg|thumb|right|300px|IBM 704 at Lawrence Livermore National Laboratory (LLNL), California, USA (October 1956).]]
Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee.  Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization]
See http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization
===Limitations===
In the early 1950s, [http://en.wikipedia.org/wiki/IBM IBM] built their first scientific computer, the IBM 701. The IBM 704 and other high-end systems appeared in the 1950s and 1960s, but by today's standards, these early machines were little more than oversized calculators. After going through a rough patch, IBM re-emerged as a leader in supercomputing research and development in the mid-1990s, creating several systems for the U.S. Government's Accelerated Strategic Computing Initiative (ASCI). These computers boast approximately 100 times as much computational power as supercomputers of just ten years ago.  
* Tradeoff of program size and execution speed
===Fine-grained Parallelism===
* Inability to rewrite inefficient algorithms
blah blah blah
* Tradeoff between ensuring serialization and exploiting non-obvious parallelism
===Course-grained Parallelism===
* Lack of knowledge of loop sizes
blah blah blah
* Conditional statements that can only be analyzed at runtime
==Examples<ref>http://http://www.top500.org</ref>==
* Pointer-linked data structures pose challenges
==Examples==
===Power FORTRAN Analyzer===
===Power FORTRAN Analyzer===
blah blah blah
A powerful commercial product by Silicon Graphics International Corp. When used with Pro MPF it allows for visualization of the parallelization, input from the developer, describes why a loop was not parallelized, and can show the performance of each parallelized loop.<ref>http://www.sgi.com/products/software/irix/tools/prompf.html</ref>
An example of output of the analyzer is depicted below in which the compiler determined that the loop was able to be concurrentized/parallelized by scalar analysis.
{| align="right"
| [[Image:Sgi_logo.gif|thumb|right|300px|Founded by Stanford alumni in 1981 with an initial focus on 3D graphics<ref>http://en.wikipedia.org/wiki/Silicon_Graphics</ref>]]
|}
<pre style="overflow:auto;">
Footnotes Actions  Do Loops Line
    DIR                      1  # 1  "sample.f"
                                2      subroutine sample(a,b,c)
                                3      dimension  a(1000),b(1000),c(1000)
    SO C +--------  4      do 10 i = 1,1000
    SO        *_______  5  10  a (i) = b(i) + c(i)
                              6      end
Abbreviations Used
  SO    scalar optimization
  DIR    directive
  C      concurrentized
Loop Summary
      From  To    Loop    Loop    at
Loop#  line  line  label    index  nest  Status
1      4    5    Do 10    I      1      concurrentized
</pre>
<ref>http://techpubs.sgi.com/library/dynaweb_docs/0630/SGI_Developer/books/MproPF_PG/sgi_html/ch03.html</ref>


===Polaris===
===Polaris===
Line 84: Line 139:
===Intel  C and C++ Compilers===
===Intel  C and C++ Compilers===
A contemporary, advanced compiler that can incorporate multiple parallelization paradigms including: static analysis, interactive, and adaptive/profile-driven.
A contemporary, advanced compiler that can incorporate multiple parallelization paradigms including: static analysis, interactive, and adaptive/profile-driven.
==== Legend ====
Flags:
* '''Vendor''' – The manufacturer of the platform and hardware.
-O0, no optimization
* '''Rmax''' – The highest score measured using the [http://en.wikipedia.org/wiki/LINPACK LINPACK] benchmark suite. This is the number that is used to rank the computers. Measured in quadrillions of floating point operations per second, i.e. Petaflops(Pflops).
-O1, optimize without size increase
* '''Rpeak''' – This is the theoretical peak performance of the system. Measured in Pflops.
-O2, default optimization
* '''Processor cores''' – The number of active [http://en.wikipedia.org/wiki/Multi-core processor cores] used.
-O3, high-level loop optimization
 
  -ipo, multi-file inter-procedural optimization
===Top 10 supercomputers of today<ref>http://www.junauza.com/2011/07/top-10-fastest-linux-based.html</ref>===
-prof-gen, profile guided optimization
Below are the Top 10 supercomputers in the World(as of June 2011). An effort has been made to compare the architectural features of these supercomputers.
-prof-use, profile guided optimization
[[Image:K-computer-Fastest-Linux-Supercomputers 1.jpg|thumb|right|200px|World s fastest supercomputer: K-computer]]
-openmp, OpenMP 3.0 support
 
-paralell, automatic parallelization
'''1.K-computer:'''
[http://www.multicore-challenge.org/resources/FMCCII_Tutorial_Pabst.pdf]
 
===Gnu Compiler Collection (GCC)===
*K-computer is currently the world's fastest supercomputer. It is developed by Fujitsu at the RIKEN Advanced Institute for Computational Science campus in Kobe, Japan.
GCC supports instruction-level parallelism, vectorization, OpenMP, and a Message Passing Interface.
* As per the LINPACK benchmarking standards, K-computer managed to give a peak performance of a mind-blowing 8.16 petaflops toppling Tianhe-1A off its number one spot.
<ref>http://www.redhat.com/f/summitfiles/presentation/May31/Developer%20Tools/Novillo_ParallelProgGCC.pdf</ref>
*This supercomputer uses 68,544 2.0 GHZ 8-core SPARC 64 VIIIfx processors packed in 672 cabinets, for a total of 548,352 cores. In layman's term, K-computer's performance is almost equivalent to the performance of 1 million desktop computers.
*The file system used here is an optimized parallel file system based on Lustre, called Fujitsu Exabyte File System.
*One of the disadvantage with this high-performer is it consumes about 9.8 MW of power, that's the amount of power that would be enough to light 10,000 houses. When compared with its closest competitor, that is the Tianhe-1A, the K-computer is miles ahead and it is highly unlikely that it would lose its number 1 spot any time soon.
[[Image:Tianhe-IA-Fastest-Linux-Supercomputers 2.jpg|thumb|right|200px|Tianhe-IA]]
 
=== Supercomputer Programming Models<ref>http://books.google.com/books?id=tDxNyGSXg5IC&pg=PA4&lpg=PA4&dq=evolution+of+supercomputers&source=bl&ots=I1NZtZyCTD&sig=Ma2fHyp336BSp4Yv2ERmfrpeo4&hl=en&ei=IAReS4WbM8eUtgf2u8GnAg&sa=X&oi=book_result&ct=result&resnum=5&ved=0CB4Q6AEwBA#v=onepage&q=evolution%20of%20supercomputers&f=false</ref> ===
The parallel architectures of supercomputers often dictate the use of special programming techniques to exploit their speed. The base language of supercomputer code is, in general, Fortran or C, using special libraries to share data between nodes. Now environments such as PVM and MPI for loosely connected clusters and OpenMP for tightly coordinated shared memory machines are used. Significant effort is required to optimize a problem for the interconnect characteristics of the machine it is run on. The aim is to prevent any of the CPUs from wasting time waiting on data from other nodes.
 
Now we will discuss briefly regarding the programming languages mentioned above.
 
1) '''Fortran''' previously known as FORTRAN is a general-purpose, procedural, imperative programming language that is especially suited to computation like numeric and scientific computing. It was originally developed by IBM in the 1950s for scientific and engineering applications,then became very dominant in this area of programming early on and has been in use for over half a century in very much computationally intensive areas such as numerical weather prediction, finite element analysis, computational fluid dynamics (CFD), computational physics, and computational chemistry. It is one of the most popular and highly preferred language in the area of high-performance computing and is the language used for programs that benchmark and rank the world's fastest supercomputers.
 
Fortran a blend derived from The IBM Mathematical Formula Translating System encompasses a lineage of versions, each of which evolved to add extensions to the language while usually retaining compatibility with previous versions. Successive versions have added support for processing of character-based data (FORTRAN 77), array programming, modular programming and object-based programming (Fortran 90 / 95), and object-oriented and generic programming (Fortran 2003).
 
== External links ==
1.[http://expertiza.csc.ncsu.edu/wiki/index.php/1.1 Previous wiki]
 
2.[http://www.netlib.org/benchmark/top500/reports/report93/section2_12_3.html Japan History]
 
3.[http://www.top500.org Top500-The supercomputer website]
 
4.[http://www.bukisa.com/articles/13059_supercomputer-evolution Evolution of supercomputers]
 
5.[http://www.rit.edu/news/?v=47077 Supercomputers to "see" black holes]
 
6.[http://www.universetoday.com/2006/10/31/supercomputer-simulates-stellar-evolution/ Supercomputer simulates stellar evolution]
 
7.[http://www.encyclopedia.com/topic/supercomputer.aspx Encyclopedia on supercomputer]
 
8.[http://news.cnet.com/2300-1_3-5757343-2.html?tag=mncol Image source1]
 
9.[http://www.silicon.com/technology/hardware/2008/07/14/photos-inside-a-supercomputer-lab-39259269/3/ Image source2]
 
10.[http://www.scientificcomputing.com/news-hpc-Water-cooling-system-enables-supercomputers-to-heat-buildings-070609.aspx Water-cooling System Enables Supercomputers to Heat Buildings]
 
11.[http://nextbigfuture.com/2008/09/cray-has-supercomputer-cooling.html Cray's cooling technology]
 
12.[http://www.nas.nasa.gov/Resources/Systems/columbia.html Columbia system facts]
 
13.[http://chronicle.com/article/UC-Irvine-Supercomputer/29940/ UC-Irvine Supercomputer Project Aims to Predict Earth's Environmental Future]
 
14.[http://en.wikipedia.org/wiki/Supercomputer Wikipedia]
 
15.[http://books.google.com/books?id=tDxNyGSXg5IC&pg=PA4&lpg=PA4&dq=evolution+of+supercomputers&source=bl&ots=I1NZtZyCTD&sig=Ma2fHyp336BSp4Yv2ERmfrpeo4&hl=en&ei=IAReS4WbM8eUtgf2u8GnAg&sa=X&oi=book_result&ct=result&resnum=5&ved=0CB4Q6AEwBA#v=onepage&q=evolution%20of%20supercomputers&f=false Parallel programming in C with MPI and OpenMP ByMichael Jay Quinn]
 
16.[http://www.hpcwire.com/offthewire/Georgia-Tech-Uses-Supercomputing-for-Better-Insight-into-Genomic-Evolution-70290117.html Genomic Evolution]
 
17.[http://books.google.com/booksid=wx4kNh8ArH8C&pg=PA3&lpg=PA3&dq=evolution+of+supercomputers&source=bl&ots=7DVWaEYsZ4&sig=WKRWRuqtM-UfPoBWdka5ZWTgng&hl=en&ei=xAleSTmDpqutgfcj_2jAg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAoQ6AEwADgK#v=onepage&q=evolution%20of%20supercomputers&f=false The future of supercomputing: an interim report By National Research Council (U.S.). Committee on theFutureof Supercomputing]
 
18.[http://www.calit2.net/newsroom/article.php?id=572 Cosmic evolution]
 
19.[http://www.thefreelibrary.com/Firm+Builds+SuperComputers+for+One-Fifth+the+Price.%28Brief+Article%29-a076702427 SuperComputers for One-Fifth the Price]
 
20.[http://royal.pingdom.com/2009/06/11/10-of-the-coolest-and-most-powerful-supercomputers-of-all-time/ Top 10 supercomputers]
 
=='''References'''==
=='''References'''==
<references/>
<references/>

Latest revision as of 04:21, 15 February 2013

Introduction

Automatic parallelization, also auto parallelization, autoparallelization, or parallelization, the last one of which implies automation when used in context, refers to converting sequential code into multi-threaded or vectorized (or even both) code in order to utilize multiple processors simultaneously in a shared-memory multiprocessor (SMP) machine.<ref>http://en.wikipedia.org/wiki/Automatic_parallelization</ref> Developers desire parallelization as it can provide significant performance gains by reducing the amount of time a particular program or routine takes to complete by spreading the work across multiple processing elements. Ideally, the developer(s) would architect their applications to take advantage of parallel computers, but this may not occur for a few reasons: he/she inherited a sequentially written legacy program, lack of understanding how to program for parallel computers, or the simplicity of developing a sequential program is desired. In these cases, the developer needs to rely on another person to transform the code to support parallel execution or to rely on a compiler to identify and exploit parallelism in the source code. In the past decades the ability of compilers to extract parallelism was minimal or non-existant. Today, a majority of compilers are able to identify and extract parallelism from source code. This wiki article was directed by Wiki Topics for Chapters 3 and 4

Identification

A primary goal of the compiler is to identify opportunities for parallelization and to this end it may use feedback from the developer, high-level language constructs, low-level language constructs, and/or runtime data. Whereas processors focus on instruction-level parallelism and operating systems focus on program-level parallelization, compilers focus on loop-level and task-level parallelization to potentially improve performance. The data parallel style is based on the ability to have part of the data worked on by each processor. The functional style is based on the ability to simultaneously execute different statements or subroutines on different processors.

Data/Loop-level Parallelism

8x8 Array of processing elements
<code>
 //Embarrassingly parallel or pleasingly parallel code
 for (int i=0; i<N; i++) 
    {
    for (int j=0; j<N; j++)
        {
        A[i][j] = B[i][j] + C[i][j];   //no dependencies on previous iterations
        } 
    }
</code>

In the code above, both loops can be parallelized. You can imagine an NxN grid of processors like the one shown at the right, with each processor working on one element of the array. However, this is often not done by compilers as the inner loop often incurs too much overhead. In this case you can imagine a single row of processors with each processor responsible for a single column. In both cases, each processor is executing the same instructions at roughly the same time using different data. 

//Not obviously parallelizable code
for (int i=1; i<N; i++) 
   {
   for (int j=1; j<N; j++)
       {
       A[i][j] = B[i-1][j] + C[i][j-1];   //dependencies on both previous iterations
       } 
   }

However, the code above is parallelizable by sweeping the anti-diagonals. A problem with this approach however will be maintaining a reasonable load across all the processors as some processors will have little work.

Algorithm/Task-level/Functional Parallelism

Two separate subroutines executing on two separate processors
<code>
 //Functionally parallel code
 for (int i=0; i<N; i++) 
    {
    A[i][j] = B[i][j] + C[i][j];   //no dependencies on previous iterations
    D[i][j] = E[i][j] + C[i][j];  //no dependencies on previous iterations
    }
The above code can be split out as two for loops that execute simultaneously
 for (int i=0; i<N; i++) 
    {
    A[i][j] = B[i][j] + C[i][j];   //no dependencies on previous iterations
    }
 for (int i=0; i<N; i++) 
    {
    D[i][j] = E[i][j] + C[i][j];  //no dependencies on previous iterations
    }
</code>

In the above case, parallelism was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel. A figure of two processing elements working on different routines is depicted to the right.

Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref><ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>

Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.

Scalar and Array Analysis

Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>

Scalar and array analyses are usually performed in conjunction with each other in imperative, low-level languages like C or FORTRAN. "Scalar analysis breaks down a program to analyze scalar variable use and the dependencies that they have." The scalar analysis will find anything that it deems can be parallelized and any sections that it cannot find to be parallelizable, it is left to the array analysis.

One type of array analysis is called array data-flow analysis where the compiler will look for array data that can be privatizable. This privatization can allocate a local copy of an array so different threads in the program can work on different parts of the array. However, if there are any loop-carried dependencies, the analysis will deem that the array is not privatizable, thus not parallizable.

Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.

Commutativity Analysis

Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the commutativity property in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:

1. "The new value of each instance variable of the receiver objects of A and B must be the same after the execution of the object section of A followed by the object section of B as after the execution of the object section of B followed by the object section of A"

2. "The multiset of operations directly invoked by either A or B under the execution order A followed by B must be the same as the multiset of operation directly invoked by either A or B under the execution order B followed by A"

In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>

Polytope Method

Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>

The Polytope Model, or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.

Profile Driven

Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.

Speculation

Thread-level speculation refers to an environment where execution threads operate speculatively, performing potentially unsafe operations, and temporarily buffering the state they generate in a buffer or cache.<ref>http://iacoma.cs.uiuc.edu/iacoma-papers/encyclopedia_tls.pdf</ref> At some later point, it is determined whether the operations were correct or not, and if not then the thread is killed and may restart. Otherwise, the changes are committed and perhaps performance improvements that were non-obvious have taken place.

Limitations

Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee.  Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [1]

Limitations

  • Tradeoff of program size and execution speed
  • Inability to rewrite inefficient algorithms
  • Tradeoff between ensuring serialization and exploiting non-obvious parallelism
  • Lack of knowledge of loop sizes
  • Conditional statements that can only be analyzed at runtime
  • Pointer-linked data structures pose challenges

Examples

Power FORTRAN Analyzer

A powerful commercial product by Silicon Graphics International Corp. When used with Pro MPF it allows for visualization of the parallelization, input from the developer, describes why a loop was not parallelized, and can show the performance of each parallelized loop.<ref>http://www.sgi.com/products/software/irix/tools/prompf.html</ref> An example of output of the analyzer is depicted below in which the compiler determined that the loop was able to be concurrentized/parallelized by scalar analysis.

Founded by Stanford alumni in 1981 with an initial focus on 3D graphics<ref>http://en.wikipedia.org/wiki/Silicon_Graphics</ref>
 Footnotes Actions   Do Loops Line
    DIR                      1  # 1  "sample.f"
                                2       subroutine sample(a,b,c)
                                3       dimension  a(1000),b(1000),c(1000)
    SO C +--------  4       do 10 i = 1,1000
    SO        *_______   5  10   a (i) = b(i) + c(i)
                               6       end
 Abbreviations Used
   SO     scalar optimization
   DIR    directive
   C      concurrentized
 Loop Summary
       From  To    Loop     Loop    at
 Loop#  line  line  label    index   nest   Status
 1      4     5     Do 10    I       1      concurrentized

<ref>http://techpubs.sgi.com/library/dynaweb_docs/0630/SGI_Developer/books/MproPF_PG/sgi_html/ch03.html</ref>

Polaris

Designed in the early 1990s to take a sequential FORTRAN77 program and output an optimized version suitable for execution on a parallel computer. This compiler supported inter-procedural analysis, scalar and array privatization, and reduction recognition.<ref>http://polaris.cs.uiuc.edu/polaris/polaris-old.html</ref>

Stanford University Intermediate Format (SUIF 1,2)

Started out as an NSF-funded and DARPA-funded collaboration between a few universities in the late 1990s with a goal of creating a universal compiler. A major focus of SUIF was parallelization of C source code, and this started with taking an intermediate program representation of the code. At this stage, various automatic parallelization techniques were used including: interprocedure optimization, array privatization, and pointer analysis, reduction recognition.

Jade

A DARPA-funded project that focused on the interactive technique for automatic parallelization. Using this technique, the programmer is able to exploit coarse-grained concurrency.<ref>http://www-suif.stanford.edu/papers/ppopp01.pdf</ref>

Kuck and Associates, Inc. KAP

A commercial compiler that was later acquired by Intel. KAP was an early product which supported FORTRAN and C that featured advanced loop distribution and symbolic analysis.

Intel C and C++ Compilers

A contemporary, advanced compiler that can incorporate multiple parallelization paradigms including: static analysis, interactive, and adaptive/profile-driven. Flags: 

-O0, no optimization
-O1, optimize without size increase
-O2, default optimization
-O3, high-level loop optimization
-ipo, multi-file inter-procedural optimization
-prof-gen, profile guided optimization
-prof-use, profile guided optimization
-openmp, OpenMP 3.0 support
-paralell, automatic parallelization

[2]

Gnu Compiler Collection (GCC)

GCC supports instruction-level parallelism, vectorization, OpenMP, and a Message Passing Interface. <ref>http://www.redhat.com/f/summitfiles/presentation/May31/Developer%20Tools/Novillo_ParallelProgGCC.pdf</ref>

References

<references/>

Retrieved from "https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2013/4a_aj&oldid=73012"