Method for automatic parallelization of software

[0002] This application claims the benefit of U.S. Provisional Application No. 60/201,444 filed May 3, 2000 entitled Automatic Parallelization: An Incremental, Optimistic Practical Approach,” which is incorporated herein by reference.

[0003] The present invention relates generally to parallel programs, and specifically, to a method for automatic parallelization of certain programs.

[0004] Parallel programming is a difficult and expensive process. While tools have been developed to assist with parallelization, these tools still require that the user have a deep knowledge of parallelization—a topic not within the grasp of most users who could benefit from parallelizing, especially when the programs at issue are inherently parallel. Furthermore, the target platforms for these programs is often a specialty multiprocessing computer.

[0005] A program which is inherently parallel implements algorithms that lend themselves to straightforward parallel implementation. This type of program does not require use of a specialty multiprocessing computer, and can be effectively implemented on a network of workstations (NOW) instead. In parallelizing programs for a NOW, a number of difficulties arise: communication is not cheap, faults and slowdowns are common, and machines may join and leave the computation at any time.

[0006] The most straightforward way to provide for communication in a parallel program is through the use of a shared memory. This is easy to implement on a multiprocessor, because every memory location has a unique id in the global address space. On a NOW, a software layer called a Distributed Shared Memory (DSM) can create an illusion of a physical global address space.

[0007] Further, a method known as Two-Phase Idempotent Eager Scheduling (TIES) was created to address the problem of slowdowns and failures, as well as machines joining and leaving computation, when parallelizing on a NOW. The traditional method of parallelization called for division of a sequential application into alternating serial and parallel steps. Each parallel step was composed of a number of independent threads of control that could be executed simultaneously. While serial steps would be executed locally, individual threads of parallel steps were scheduled on available processors. When the last thread terminates, the parallel step is finished. The TIES system instead simultaneously assigns several copies of individual threads to several machines to guarantee termination as long as at least one continues to progress. When the first has successfully reported the results, the other machines are freed for other tasks. In order to guarantee correctness, the starting memory state must be identical for each copy, and thus, this original memory state is preserved until the parallel step has successfully concluded. Not only does this address the issues of failure and slowdown and machines joining and leaving the computation, but also the TIES scheme minimizes communications during the parallel step because the complete memory image for each thread is available at the start of the parallel step.

[0008] An embarrassingly parallel program is a program whose execution time is dominated by a small number of coarse-grained parallel loops. The lack of internode communication requirements within the main loops of the programs is ideal for use with the TIES methodology, where no inter-iteration communication is permitted.

[0009] Another problem that arises in parallelization is the issue of data dependence, which occurs particularly if two iterations access the same memory location and at least one access is a write. Some dependencies can be satisfied through a technique called privatization, which allocates individual copies of a variable to each loop iteration. However, if an earlier iteration writes a value which is to be read by a later iteration, a flow dependence is indicated, and a loop containing this type of dependence may not be parallelizable. A dependence may also be categorized as either loop-independent, if it exists independently of any loop inside which it is nested, or loop-carried, if not. While a loop-independent dependence does not inhibit parallelization, a loop-carried dependence may inhibit parallelization.

[0010] Detecting dependencies has traditionally been done by comparing each possibly overlapping array reference with every other. Array summarization techniques, representing aggregate activity for a set of accesses have been proposed. However, in real world applications, flow dependence has been shown to be undecidable. In part, this is because static analysis cannot completely address analysis issues which arise in complex real-world applications.

[0011] The following program illustrates this problem.

[0012] The main loop of this program has different dependencies depending on the runtime value of argv[1]. If argv[1] is between −5 and −1, there is a loop-carried flow dependence. If argv[1] is between 1 and 5, there is a loop-carried anti-dependence, which means an earlier iteration reads a value which is written by a later iteration. If argv[1] is 0, there is a loop-independent flow dependence. Other values of argv[1] show no dependence. Clearly static analysis may not be able to provide sufficient information to permit parallelization.

[0013] Because static analysis is not adequate, various approaches of runtime analysis have been suggested. In the previous example, a runtime test on the value of argv[1] Would determine whether a serial or parallel version of the loop was selected. One strategy is to use “inspector loops”, or side-effect-free skeletons of the original loop in which address calculations are performed. The inspector loop executes quickly, and then the pattern of memory accesses can be used to allow or disallow parallelization of the original loop. The drawback to this strategy is that the inspector loop may be difficult or impractical to extract. Another strategy is speculative parallelization, in which the loops are parallelized with possible dependencies, the actual existence of which is checked at run-time. A shadow array is allocated for every array that might contain a flow dependence. As the elements in the original array are accessed, the shadow array records the access type. When the parallel step is over, the access patterns of all iterations can be compared to determine if there is an actual flow dependence. If it turns out to be illegal, a backup copy of the shared memory is used to re-execute the loop sequentially. Drawbacks to this method include mangling of code and high overhead for parallelization of coarse grained loops.

[0014] Thus, a method that will automatically parallelize code for implementation on a NOW, while avoiding the problems and drawbacks detailed above is desirable.

[0015] The present invention provides a scalable, automated, network friendly method for building parallel applications from embarrassingly parallel serial programs. The steps of an exemplary method follow: First, the application loops with significant potential parallelism are identified. Second, from the set of loops identified, those loops which can statically be shown to not be parallelizable are disqualified. Next, the program is transformed into a parallel form in which the remaining identified loops are optimistically parallelized and packaged into per-iteration functions. Variables that need to be shared are segregated into a particular section of memory via simple source code transformation. The previous steps are performed by the compiler, which further inserts calls to the runtime system for scheduling and shared memory allocation and set-up.

[0016] The server application, then, contains all code outside of any parallel loop as well as calls to the scheduling subsystem that replace the parallelized loop. The client applications contain the loop bodies of the parallelized loops (per-iteration functions) Each client application is constructed to accept a consecutive range of iteration space as well as the iteration step as input parameters.

[0017] At run-time, many copies of the per-iteration functions are spawned on different machines to simultaneously perform different iteration ranges. The shared memory segment is available to all the machines through DSM. During execution, the memory access statistics on the granularity of individual data types are collected as the loop iterations are performed. As the ranges of iterations are concluded, shared memory updates and access statistics are returned to the memory server. The server then dynamically checks that no memory dependencies were in fact violated. If a violation is detected, the program can either abort in ordinary applications or can gracefully continue serially in sensitive applications. In subsequent runs, the program is re-parallelized, but the parallelization of the offending loop is disabled. Information obtained through the program failures is entered into a program database which guides future re-parallelizations.

[0018] These, as well as other features and advantages of the present invention, will become apparent to those of ordinary skill in the art by reading the following detailed description, with appropriate reference to the accompanying drawings.

[0019] The invention will now be described by way of example only with reference to the accompanying drawings, in which:

[0020] FIG. 1 is an example of an interprocedural loop level graph;

[0021] FIG. 2 is a diagram illustrating shared variable transformation;

[0022] FIG. 3 illustrates scalar initializations;

[0023] FIG. 4 illustrates aggregate initializations;

[0024] FIG. 5 shows aggregate access types; and

[0025] FIG. 6 depicts transforming structure aggregates.

[0026] The first step is to determine what to parallelize—in this case, coarse-grained loops. Coarse-grained loops are preferred because they ensure a high ratio of work to overhead, because the overhead is greatly pronounced when implementing on a NOW. The loop tree of a procedure is a root node plus one node for each loop, with edges connecting each node to all loops which it directly contains. The program loop graph is the graph obtained by adding a connecting edge from each loop tree node to the root of the loop tree for each function called from that node. Global Recursion Level Analysis (GRLA) is an interprocedural analysis technique that uses the Program Call Graph and the Control Flow Graph of each procedure to assign staging levels indicating relative frequency of execution to each block of code.

[0027] In one example of this method, GRLA is started by assigning staging levels at the leaves of the program loop graph, which are each assigned level 0. The stage level of each inner loop is one more than the meet of each of its constituent loops. In the case of a root loop tree node, it is precisely the meet of the staging levels of all inner loops. When the staging levels have been assigned, the coarsest grained loops will be the ones with the highest lattice values. In the event that unused functions are present within a program, this analysis will discover a number of “main” functions, and it takes the highest-labeled function as the main function.

[0028] Within this main function, there are likely to be statements, function calls, and loops. Individual statements and low-numbered function calls and loops are ignored. Loops with high level are considered for parallelization and functions with high level are recursively examined. The main function is thus divided up into a sequence of alternating sequential code and parallelizable loops.

[0029] The Program Loop Level Graph is one manner to graphically represent the preceding dataflow analysis, by extending the Program Call Graph to make loop nesting explicit. For the exemplary program shown above, the resulting Loop Level Graph is shown in FIG. 1. The nodes srand48, drand48, and print 200 are undefined library functions and are not considered in the analysis. For all other nodes, the number in parenthesis represents the loop level. The nodes main, mmult, print, and randomFill 210 represent the nominal outer loops of their respective functions. Each of the functions mmult, print, and randomFill are assigned the same level as the single loop they contain, whereas main is assigned the maximum level of all loop levels it encloses.

[0030] Traversing the graph allows efficient assignment of a loop-nesting level to each loop of each function, the highest are the coarsest grain loops. The most expensive program loops are determined using two major steps: assigning loop levels to each loop and finding the maximum of these over the entire program.

[0031] The nesting level algorithm is as follows:

[0032] Every function contains an outer loop with a nesting level of 0, which is merely a container for the function body. The algorithm begins by taking the maximum loop nesting level of all functions called within the loop, and then calls itself recursively for each inner loop to find the maximum loop nesting level over all inner loops. Finally it assigns the loop nesting level as the maximum of the function nesting level and the inner loop nesting level, with one added if this is a recursive call (an actual inner loop). The SetNests function is applied to each function separately, in reverse topological order based on the call graph.

[0033] Finding the costliest loops proceeds using the following algorithm:

[0034] The algorithm checks for recursive cycles in the call graph and does not follow them. For every other loop call, it calls itself recursively on the function's outer loop. At the bottom level of the recursion, all 0-level outer function loops have been explored, and the algorithm simply checks every inner loop of every function loop and returns the ones that exceed some nesting threshold. One good heuristic seems to be to consider all outer loops with a nesting level within 2 units of the maximum level found at the outer loop of the main function.

[0035] Once coarse-grained loops are identified, these loops are then analyzed for parallelizability. This involves minimal testing for a non-exhaustive list of disqualifying conditions including: input operations or other system calls; termination conditions where are inherently sequential; premature loop exit conditions; non-local transfers of control; obvious loop-carried flow-dependence; and obvious allocation of memory without corresponding deallocation. At this point, user can be notified of which loop was a desirable parallelism candidate and the grounds for its disqualification, allowing the user to remove or modify the offending code. The final result of the preceding is a maximal set of parallelizable coarse-grained loops present in the input program.

[0036] Once parallelizable loops have been identified, the interprocedural shared variables must be identified. Variables which occur within a parallel loop body and elsewhere are clearly shared. It is not so clear whether addressed variables and heap memory are shared, but a conservative approach is to label all of these instances as shared. To determine what variables are referenced within a parallel loop, the following algorithm is called on each parallel loop candidate:

[0037] For each candidate loop, the algorithm adds locally referenced variables, plus the results of calling itself recursively on each of its inner loops and the nominal outer loop of each of the functions it calls. Further, all variables addressed anywhere in the program can be added, unless it is proven that the address never crosses a parallel loop boundary. From this list of possibly shared variables, only those live outside the loop body are selected.

[0038] It is difficult to keep a DSM system simple and efficient if it must manage an unlimited number of tiny shared memory segments, so it is customary to aggregate all shared data into a single place. Unless the program was designed with this notion, the shared memory segment will be composed of variables which are arbitrarily scattered across the application. To comply with DSM semantics, these variables must be collected into a single contiguous shared data segment. To accomplish this with minimal drawbacks, a program transformation is used to add an extra level of indirection to each shared variable declaration and usage, thus maintaining the semantics of the original program while placing the shared variables all together in a single memory segment for DSM.

[0039] To avoid variable reshuffling at the source code level, one level of indirection is added to each shared variable declaration. For example, as in FIG. 2(a), the array A is found to be shared. FIG. 2(b) demonstrates a level of indirection added to the declaration. Finally, taking advantage of the flexibility of C++ to defer initializations until run-time, all shared variables are initialized at declaration to point to the area of shared memory returned by the static shared memory allocation function shcreate ( ), as in FIG. 2(c).

[0040] Turning to variable initializations, declarations of variables may use the initialized value of previously declared variables, as in FIG. 3(a). To provide a way of initializing the variable at declaration in the transformed code, a dummy variable is introduced, as shown in FIG. 3(b). This initialization technique works as well for aggregates, as is shown in FIG. 4.

[0041] Every shared variable can be initialized consistently in this manner, with the exception of procedure parameters. Shared parameters must be augmented with an additional indirect declaration within the function body, which is then initialized normally and assigned the actual parameter value. The indirect version is then substituted for all uses of the parameter.

[0042] This straightforward procedure must be altered slightly, by adding an additional layer of indirection, in order to make use of the memory profiling scheme that is described later. Aggregate variables must be separated into value context and address context. The value context aggregate is where one of its elements is being referenced, and thus must be transformed; the address context aggregate is where the address of some offset inside the aggregate is being taken, and thus must be preserved. For example, consider FIG. 5. In FIG. 5(a), the first statement assigns to an element of A, or is value context. The second statement assigns the address of A[i] to the variable i, and is an address context. In FIG. 5(b), the appropriate transformations have been made. The sophisticated transformation A must ripple through the code to change every variable which is used to hold an offset of A, including assignments and function call sites.

[0043] Structure aggregates add an interesting twist because adding indirections at the element level fundamentally changes the data type. Transforming this code to implement speculative sharing (i.e., the memory profiling scheme that is described later) involves generating a new datatype agg_p from agg, where each member is given an indirection, as shown in FIG. 6.

[0044] Thus, the program generated by the parallelizer has both a transformed application program, the server, and a number of parallelizable loop mini-apps, the clients., The server application has a call to a scheduling module with loop bounds, step and client application name as arguments in place of each parallel loop. Each mini-app is parameterized by loop iteration count, because many independent copies of it may be spawned at runtime on all available machines. To provide a common shared memory image between all clients within a given parallel step, the shared data is encapsulated into a Network File System (NFS)-mounted file and mapped at both the server and all clients. NFS, a widely available protocol for file sharing, can be used, together with file-mapping kernel primitives, for shared memory management to obtain an effective runtime system.

[0045] Because the estimate of which variables must be shared has been made conservatively, the shared memory layout can be precomputed, and then used to determine the precise offset in the shared memory segment where each variable will reside. The first call to the shcreate( ) function allocates the entire memory segment required, subsequent calls merely allocate various pieces to initialize the appropriate variables. On the client side, shopen ( ) performs a similar task, returning the appropriate offset into the same shared memory file for each shared variable.

[0046] On the server side, the shared memory file is mapped using the MAP_SHARED flag of the mmap( ) system call because all clients initialize their shared memory segments by mapping in the same memory file and need to be able to see all updates to the shared memory which precede the parallelized loop invocation. Because the client must know the name of the shared memory file and the address to which it was set, information which cannot be passed as arguments to the client application, environment variables communicate these values. At the client, the shared memory is mapped using the MAP_PRIVATE flag of mmap( ), because client execution must remain idempotent and cannot be allowed to write to directly to shared memory space.

[0047] To make the best use of the strengths of the NFS protocol, iteration space is partitioned to ensure that a number of different grain sizes are present, and the larger grains (or jobs) cover earlier iterations than later grains. This ensures a proper balance between the conflicting goals of minimizing overhead, via large grains, and achieving proper load balancing, supported by the smaller grains. Every client machine is started with a good sized chunk of work which is estimated to keep it busy for some fraction of the ultimate duration of the parallel step. As some machines finish faster, they can be given the smaller remaining chunks in the remaining time of the parallel step. Because the larger grains compute earlier iterations in the iteration space, the incorporation of the results of these iterations can be overlapped with the computation of later iterations. To support file appends within a parallelizable loop, the appends are stored in temporary files until one of the client copies successfully completes, and then only after all earlier grains of the loop have been completed can all these be combined into one stream.

[0048] Upon successful completion of each job, the entire job list is looped through. Jobs may be classified as either “done” or “flushed.” All jobs which have already been flushed are skipped; jobs which are not done break the loop. All other jobs encountered on the job list are marked flushed and the corresponding commitments are performed, basically concatenating temporary output files to the appropriate output stream, updating a second copy of the shared memory with the changes recorded in the client-side, and deleting the corresponding temporary files.

[0049] Finally, the legitimacy of the parallelization at run-time must be checked. Instead of using shadow arrays, this method uses memory profiling, keeping statistics for every iteration of which locations were read only, read first, and written before being read. By using a granularity that includes several consecutive iterations in each grain, the test need not be performed for every pair of iterations, because within a particular grain, dependencies will be automatically satisfied. Three bits are associated with each memory element: Read-Only, Write-First, and Read/Write. For each read access, if no bits are set Read-Only is marked. For each write-access, if no bits are set, Write-First is marked. Otherwise, if the Read-Only bit is set, the Read/Write is marked.

[0050] To provide an efficient, language-independent, platform-independent methodology for element-by-element memory profiling, a methodology called MultiView may be used. See Ayal Itzkovitz et al., “Fine-Grain Distributed Virtual Shared Memory,” PCT International Application Number PCT/IL99/00391, which is incorporated herein by reference. Multiview is used for fine-grained memory access control of DSM using standard OS page fault mechanism and can support access faults at the variable level. MultiView constructs separate and independent mappings which map to identical memory areas. This technique can be adapted to provide access statistics for each memory element at every client processor. Rather than handing out pointers to the original mapping space of the shared memory, a separate mapping for each variable is created and the appropriate offset into it is returned. At the beginning of a grain's execution, no read/write permissions are set on any of the mappings. As page faults are generated, the appropriate access is turned on and the appropriate bit set. Locations which are only read or are written before being read will generate only a single page fault. Those that are read before being written will generate two faults. As the parallel grain size increases, the cost of this method decreases significantly, and thus provides a good profiling scheme.

[0051] An exemplary embodiment of the present invention has been illustrated and described. It will be understood, however, that changes and modifications may be made to the invention without deviating from the spirit and scope of the invention, as defined by the following claims.