Abstract:
Systems and methods perform affine partitioning on a code stream to produce code segments that may be parallelized. The code segments include copies of the original code stream with conditional inserted that aid in parallelizing code. The conditional is formed by determining the constraints on a processor variable determined by the affine partitioning and applying the constraints to the original code stream.

Description:
FIELD  
       [0001]     The embodiments of the invention relate generally to partitioning code and more particularly to affine partitioning code onto multiple processing units.  
       BACKGROUND  
       [0002]     From the very beginning of the computer industry, there has been a constant demand for improving the performance of systems in order to run application faster than before, or for running applications that can produce results in an acceptable time frame. One method for improving the performance of computer systems is to have the system run applications or portions of an application (e.g. a thread) in parallel with one another on a system having multiple processors. In order to run an application or thread in parallel, the application or thread must be independent, that is, it cannot depend on the results produced by another application or thread.  
         [0003]     The process of specifying which applications or threads can be run in parallel with one another may be referred to as partitioning. One particular type of partitioning used by current systems in referred to as affine partitioning. An affine partition may be used to uniformly represent many program transformations, such as loop interchange, loop reversal and loop skewing, loop fusing, and statement re-ordering. Further, space partitioning in an affine partitioning framework may be used to parallelize code below for multiprocessor systems.  
         [0004]     In general, an affine partition typically comprises a linear transformation and a translation of a vector or matrix operation within one or more loops, including transformation and translation of loop index variables. Various loop manipulations may be performed using affine partitioning. For example, loop interchange, loop reversal and loop skewing may be represented by linear transformations and translations performed in affine partitioning. The affine partition is an extension to unimodular transformation in use by current compilers. The affine partition extends the concept of unimodular transformation by: 
        i) Allowing each statement to have its own linear transformation. In comparison, for a unimodular transformation, all statements inside the loop body share one linear transformation.     ii) Allowing the partitioning to be applied to general loops structure. In comparison, a unimodular transform can only be applied to perfect nested loops.     iii) Allowing the degree of the linear transformation to be less than the nesting level of loops in the program. Namely, the transformation matrix could be non-square matrix. In contrast, a unimodular transformation requires the transformation matrix to be square matrix.        
 
         [0008]     While affine partitioning has provided benefits in producing code that can be run in parallel on multiprocessor systems, there remain significant issues. For example, many times successive iterations of a loop in a program will make continuous accesses to memory. Before partitioning, memory accesses of successive iterations of a loop may be near one another, resulting in a high likelihood that a memory reference will be available in faster cache memory. However, in affine partitioning, instances of instructions in a loop may be divided across multiple processors and code may be transformed such that memory access patterns are much different than prior to partitioning. As a result, it is more likely that memory accesses may no longer be contiguous or near one another, and in fact memory accesses may be quite far from one another. In this case, there is a higher likelihood of a cache miss, thereby increasing the time required to access memory. Thus some or all of the performance gains realized by executing instructions in parallel may be lost due to the increase in memory access times due to cache misses.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]      FIG. 1  is a block diagram showing hardware and software components of a system incorporating embodiments of the invention.  
         [0010]      FIG. 2A  is an exemplary source code fragment prior to affine partitioning and is used to illustrate the operation of various embodiments of the invention.  
         [0011]      FIG. 2B  is an exemplary code fragment after affine partitioning.  
         [0012]      FIG. 3  is a flowchart illustrating a method for affine partitioning program code according to embodiments of the invention.  
         [0013]      FIGS. 4A and 4B  are exemplary code fragments after affine partitioning and are used to illustrate the operation of exemplary embodiments of the invention.  
         [0014]      FIG. 5  is an exemplary code fragment illustrating the use of OpenMP in embodiments of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0015]     In the following detailed description of exemplary embodiments of the invention, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific exemplary embodiments in which the inventive subject matter may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the various embodiments of the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical, electrical and other changes may be made without departing from the scope of the inventive subject matter. The following detailed description is, therefore, not to be taken in a limiting sense.  
         [0016]     In the Figures, the same reference number is used throughout to refer to an identical component which appears in multiple Figures. Signals and connections may be referred to by the same reference number or label, and the actual meaning will be clear from its use in the context of the description.  
         [0017]      FIG. 1  is a block diagram showing hardware and software components of a system  100  incorporating embodiments of the invention. In some embodiments, system  100  includes a compiler  102  code stream  106  and processing units  110 . In some embodiments, processing units  110  may be processing engines that are part of a multiple core processor. These types of architectures  108  are referred to as multi-core architectures. Thus, a multi-core processing architecture is logically a single processor having multiple independent processing engines (cores). In alternative embodiments, processing units  110  may be individual processors on an arc hitecture  108  that comprises a circuit board with multiple processors present on the board. In further alternative embodiments, processing units  110  may each be on a board that is part of a multiple processor board system architecture  108 . In some embodiments, architecture  108  comprises an SMP (Symmetric Multiprocessing) architecture that makes multiple processing units available to complete individual processes simultaneously (multiprocessing). In SMP, any idle processor can be assigned any task, and additional processing units can be added to improve performance and handle increased loads. Further, applications can benefit from SMP or multi-core through multithreading. Multithreading provides the ability to execute different parts of a program, called threads, simultaneously.  
         [0018]     It should be noted that while four processing units  110  are illustrated in  FIG. 1 , no embodiment of the invention is limited to any particular number of processing units  110 . Various embodiments may have more or fewer processing units.  
         [0019]     Compiler  102  operates to read a source code stream  106  and to translate the source code stream  106  into object code that can run on one or more of processing units  110 . Source code stream  106  may be written any of a number of programming languages such as C, C++, C#, Fortran, ADA, Pascal, PL 1  etc. that are now available or may be developed in the future, with compiler  102  typically configured to operate on one type of programming language. The embodiments of the invention are not limited to any particular programming language.  
         [0020]     In some embodiments, compiler  102  includes a partitioning module  104  that analyzes portions of source code stream  106  to determine if portions of the source code can be partitioned into code segments that can be parallelized, that is, segments that can be run simultaneously on the multiple processing units  110 . Partitioning module  104  may be part of an optimizer component or a front-end component of compiler  102 . Partitioning module operates to perform affine partitioning of the portions of code stream  106 . In general, affine partitioning divides instances of an instruction across into partitions  116 . Code segments  106  (also referred to as threads) contain instances of the instructions and are assigned a partition  116 . The code segments of a partition are then assigned to run on one of the processors of the multi-core or multi-processor system. Partitioning across a set of processors may be referred to as space partitioning, while partitioning across a set of time stages may be referred to as time partitioning.  
         [0021]     Affine partitioning uses affine transformations to partition the instances. Generally speaking, an affine transformation comprises a linear transformation followed by a translation.  
         [0022]     It should be noted that although for partition are shown in  FIG. 1 , the actual number of partitions may vary and will depend on the structure of the code being partitioned. Further, there may be more of fewer partitions than the number of available processors. In this case, the code segments from multiple partitions may be assigned to run on a particular processor.  
         [0023]     In some embodiments, compiler  102  includes an OpenMP API (Application Program Interface)  114 . OpenMP is a specification for a set of compiler directives, library routines, and environment variables that can be used to specify shared memory parallelism in Fortran and C/C++ programs. Compiler  102  (or a front-end for compiler  102 ) may produce code including directives and/or function calls to the OpenMP API The OpenMP API supports multi-platform shared-memory parallel programming in C/C++ and Fortran on numerous hardware and software architectures, including Unix, Linux, and Microsoft Windows based platforms. Further details may be found in “OpenMP Application Program Interface” version 2.5 published May 2005 by the OpenMP Architecture Review Board.  
         [0024]     Further details on the operation of the system described above are provided below with reference to  FIG. 3 .  
         [0025]      FIG. 2A  is an exemplary code fragment prior to affine partitioning provided to illustrate the operation of various embodiments of the invention. As shown in  FIG. 2A , the exemplary code fragment includes two nested loops with inductions variables “i” and “j” respectively. Within the inner loop, two statements (labeled S 1  and S 2 ) are specified. The example code shown in  FIG. 2A  will be used to illustrate aspects of the operation of system and methods of the embodiments of the invention.  
         [0026]     The outermost loops of the code in  FIG. 2A  may be parallelized using affine partitioning.  FIG. 2B  is an example code fragment after affine partitioning performed by conventional systems. For the purposes of this specification, an instance of a statement during a particular iteration will be indicated by the values (ij) of the induction variables during the loop iteration. In the example shown in  FIG. 2B , the affine partition is:  
                       φ   1     ⁡     (     i   ,   j     )       =       ⁢     [         1             -   1     ]     ⁡     [         i           j         ]                               φ   2     ⁡     (     i   ,   j     )       =       ⁢     [           1             -   1     ]     ⁡     [         i           j         ]             +   1                     (   1   )             
 
 Where φ 1  is linear transformation for statement S 1  and φ 1  is linear transformation for statement S 2 . After the transformation, statement instances with same affine mapping results are grouped into same loop iteration of outermost loop P of the example code in  FIG. 2B . For example, in  FIG. 2A , because the instance (1,0), (2,1), of statement S 1  and instance (0,0),(1,1) of statement S 2  result in a mapping to partition 1, those instances of statements S 1  and S 2  are all executed in the iteration P=1 in the code after transformation. 
 
         [0027]     It should be noted that while the code shown in  FIG. 2B  can be parallelized, memory access by the code are much less likely to be continuous.  
         [0028]      FIG. 3  is a flowchart illustrating methods for affine partitioning program code according to embodiments of the invention. The methods may be performed within an operating environment such as that described above with reference to  FIG. 1  above. The methods to be performed by the operating environment constitute computer programs made up of computer-executable instructions. Describing the methods by reference to a flowchart enables one skilled in the art to develop such programs including such instructions to carry out the methods on suitable computers (the processor of the computer executing the instructions from machine-readable media such as RAM, ROM, CD-ROM, DVD-ROM, hard disk, flash memory etc.). The methods illustrated in  FIG. 3  are inclusive of the acts performed by an operating environment executing an exemplary embodiment of the invention.  
         [0029]     In some embodiments, the method begins by performing locality optimization for sequential code (block  302 ).  
         [0030]     Next, the system receives a code stream portion of the code being compiled (block  304 ). The code stream will typically comprise one or more nested loops, with one or more statements within the various body portions of the nested loops.  
         [0031]     The system determines an affine partitioning result set (block  306 ). The affine partitioning will typically be a space partitioning designed to parallelize the code stream across multiple processing units. The result set may comprise a 1-order affine partitioning result set in the case where all of the processing units form a 1-dimensional processor space (e.g., processing units shares a memory bus). Higher order affine partitioning result sets may be generated when different groups of processing units share different memory interconnects. It is desirable that the affine partitions P be in the form of: 
 
 P=A   i1   I   i1   +A   i2   I   i2   + . . . +A   ik   I   ik    (2) 
 
 where for the i-th statement, It is the induction variable and A is the affine transformation applied to the induction variable. In addition, P 0  will be used to refer to the minimal value of P and P L  will be used to refer to the maximal value for P. 
 
         [0032]     The system then divides the range of P (i.e. values from P 0  to P L ) into L portions that will be associated with L code segments:  
             {               ⁢       P   0     ≤   P   &lt;     P   1                       ⁢       P   1     ≤   P   &lt;     P   2                       ⁢       P   2     ≤   P   &lt;     P   3                       ⁢   ⋯                   ⁢       P     L   -   1       ≤   P   &lt;     P   L                       (   3   )             
 
 where L is the number of processing units in the target architecture (block  308 ). It is desirable that the portions be divided such that each code segment contains a similar amount of code. 
 
         [0033]     The system then processes the L code segments. For the t-th segment, a copy of original code stream is copied into the code segment (block  310 ). In addition, a conditional is determined for each statement (block  312 ). The conditional is determined by taking the condition P t ≦P&lt;P t+1  for each statement in the code and replacing P by correspondent linear formula of the induction variables. For example, the condition P t ≦P&lt;P t+1  becomes 
 
( P   t   −A   i1   I   i1   −A   i2   I   i2   − . . . −A   i,k   I   i,k−1 )/ A   ik   &lt;I   ik &lt;(P t+1   −A   i1   I   i1   −A   i2   I   i2   − . . . −A   i,k−1   I   i,k−1 )/ A   ik    (4) 
 
 In some embodiments, the conditional is then inserted into the code segment to provide for conditional execution of the affected statement or statements. 
 
         [0034]      FIG. 4A  is an exemplary code segment after affine partitioning provided to illustrate the operation of exemplary embodiments of the invention as described above. In the example, P may take values of 1−n to n. In an example configuration assuming a four processing unit target architecture, the range of values may be partitioned into four parts:  
             {               ⁢         1   -   n     &lt;   P   ≤       -   n     *     (     1   -     1   ⁢     /     ⁢     2         )         ,                     ⁢           -   n     *     (     1   -     1   ⁢     /     ⁢     2         )       &lt;   P   ≤   0     ,                     ⁢       0   &lt;   P   ≤     n   *     (     1   -     1   ⁢     /     ⁢     2         )         ,                     ⁢       n   *     (     1   -     1   ⁢     /     ⁢     2         )       &lt;   P   &lt;=   n                     (   5   )               
 It should be noted that is desirable to produce ranges that result in spreading the amount of code relatively evenly across the partitions while preserving memory access independence. In the example above, a diagonal partitioning of the space is assumed for the ranges in formula (5). Those of skill in the art will appreciate that other partitions are possible and within the scope of the embodiments of the invention. 
 
         [0035]     As illustrated, the code segment in  FIG. 4A  is for the first range in formula (5) and includes a copy of the original code stream illustrated in  FIG. 2A  with the conditional statements C 1  and C 2  added as determined according to formula (4) and block  312  above. In the four processing unit example, three other code segments would be produced, each corresponding to one of the ranges shown in example formula (5). It should be noted that unlike the code shown in  FIG. 2B , the code segment in  FIG. 4A  preserves the continuous memory access features of the original code stream, while still allowing parallelization.  
         [0036]     Returning to  FIG. 3 , in some embodiments, the conditional may be further simplified by merging a portion of the conditional statement into the loop boundary conditions for the k-th loop surrounding the i-th statement (block  314 ).  FIG. 4B  provides an example code segment after merging the conditional statement into the loop boundary for the code segment illustrated in  FIG. 4A .  
         [0037]     In some embodiments of the invention, the system may create OpenMP sections (block  316 ). An OpenMP section may be created for each processing unit in the target architecture. Then each code segment generated as described above is placed in the corresponding OpenMP section.  
         [0038]      FIG. 5  illustrates an example code fragment using OpenMP directives according to embodiments of the invention. Again, the example assumes a four processing unit configuration. Alternative embodiments may have more or fewer processing units. As illustrated in  FIG. 5 , a code segment is associated with each processor. In some cases, particularly when there may be a large number of processors and/or a large amount of code in the code segment, the size of the executable produced may be larger than desirable. Thus in alternative embodiments, a single code segment may be produced, with an additional conditional added to the code segment. The additional conditional statement is then used to control which processing unit processes a particular range of induction variables. This can result in a smaller executable at the expense of a small increase in execution time due to the added conditional.  
         [0039]     Thus as can be seen from the above, instead of merging iterations of the transformed code (as shown in  FIG. 2B ), the system and methods of the invention use affine partitioning to determine the constraints on processor variable P and apply the constraints to original code directly. Thus in some embodiments, memory may be accessed in a contiguous fashion after partitioning resulting in fewer cache misses.  
         [0040]     Systems and methods for affine partitioning code streams for parallelizing code in architectures having multiple processing units have been described. This application is intended to cover any adaptations or variations of the embodiments of the invention. It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. Therefore, it is manifestly intended that the inventive subject matter be limited only by the following claims and equivalents thereof.