Abstract:
Machine readable media, methods, apparatus and system for MPI program optimization. In some embodiments, shared data may be retrieved from a message passing interface (MPI) program, wherein the shared data is sharable by a plurality of processes. Then, the shared data may be allocated to a shared memory, wherein the shared memory is accessible by the plurality of processes. A single copy of the shared data may be maintained in the shared data in a global buffer of the processes of the plurality of processes can read or write the single copy of the shared data from or to the shared memory.

Description:
BACKGROUND 
       [0001]    Message passing interface (MPI) may be a widely used programming model for high performance computing. Originally, MPI may be designed for communication among nodes running a parallel program on a distributed memory system. With the development of multiprocessors (MP) running individual processes, the use of MPI may be extended to communication among processes on a shared memory system. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0002]    The invention described herein is illustrated by way of example and not by way of limitation in the accompanying figures. For simplicity and clarity of illustration, elements illustrated in the figures are not necessarily drawn to scale. For example, the dimensions of some elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference labels have been repeated among the figures to indicate corresponding or analogous elements. 
           [0003]      FIG. 1  illustrates an embodiment of a MP computing platform using MPI programs. 
           [0004]      FIG. 2  illustrates an embodiment of a MPI program optimizer. 
           [0005]      FIG. 3  illustrates an embodiment of a method of MPI program optimization during the compiling stage. 
           [0006]      FIG. 4  illustrates an embodiment of a method of MPI program optimization during the runtime stage. 
           [0007]      FIG. 5  illustrated an embodiment of a method of executing optimized MPI program. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0008]    The following description describes techniques for MPI program optimization. In the following description, numerous specific details such as logic implementations, pseudo-code, means to specify operands, resource partitioning/sharing/duplication implementations, types and interrelationships of system components, and logic partitioning/integration choices are set forth in order to provide a more thorough understanding of the current invention. However, the invention may be practiced without such specific details. In other instances, control structures, gate level circuits and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation. 
         [0009]    References in the specification to “one embodiment”, “an embodiment”, “an example embodiment”, etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. 
         [0010]    Embodiments of the invention may be implemented in hardware, firmware, software, or any combination thereof. Embodiments of the invention may also be implemented as instructions stored on a machine-readable medium, that may be read and executed by one or more processors. A machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computing device). For example, a machine-readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other forms of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.) and others. 
         [0011]      FIG. 1  shows an embodiment of a MP computing platform. Platform  10  may comprise a plurality of processors  11   1 - 11   n , a shared cache  12  and a shared memory  13 , and possibly other components for data transceiving and/or data processing. 
         [0012]    Processors  11   1 - 11   n  may be used to run individual processes. Shared cache  12  and shared memory  13  may be associated with and sharable by processors  11   1 - 11   n . Shared cache  12  may be a bridge between processors  11   1 - 11   n  and shared memory  13  and may allow instructions and data transferred from shared memory  13  to be read or written by processors  11   1 - 11   n  at a faster speed. 
         [0013]    It should be appreciated that computing platform  10  may apply cache hierarchy architecture, namely, each of processors  111 - 11   n  may be associated with a first level cache (not shown), a group of processors may be associated with a second level cache (not shown) and shared cache  12  may be a shared last level cache (LLC) that may be associated with all of processors  11   1 - 11   n . 
         [0014]    MPI may be a de facto standard for communication among the processes running a parallel program on a shared memory system. Conventionally, the parallel program may adopt single program multiple data (SPMD) pattern, namely, all processes running on processors may use the same program but each may has its own data. Therefore, multiple copies of the data may be maintained in the memory system, which could be a big challenge for memory bandwidth and cache performance. Conventionally, MPI standard may provide various patterns for data communication among the processes, for example, point-to-point communications or collective communications. However, no matter which communication pattern is used, a complete copy of data may be transferred between processes, which may create redundant data for each process. 
         [0015]      FIG. 2  illustrates an embodiment of a MPI program optimizer  20 . MPI program optimizer  20  may optimize performance of data communication between processes. MPI program optimizer  20  may comprise analyzer  21 , retriever  22 , annotator  23 , library  24 , and parser  25 . 
         [0016]    Analyzer  21  may analyze a MPI program to detect if there is data from the MPI program sharable by a number or all of the processes running on processors  11   1 - 11   n . Various applications may determine various types of data sharable by the processes. For an information extraction application that may be used to locate boundaries of sentences and extract name entities, dictionary data may be sharable by the processes. For an MFold algorithm application that may be used to predict Ribonucleic acid (RNA) secondary structure, matrix variables may be sharable by the processes. For an integer sort application that may be a part of parallel benchmark NPB, variables used for functions such as MPI_Allreduce, MPI_Alltall and MPI_Alltoallv may be sharable by the processes. 
         [0017]    Analyzer  21  may further analyze the MPI communication pattern for the shared data. As stated above, MPI standard may define various communication patterns, such as point-to-point communications or collective communications. 
         [0018]    Retriever  22  may retrieve the shared data from the MPI program to provide a shared data list. Annotator  23  may annotate the shared data list with a shared directive. For example, annotator  23  may annotate the shared data with a directive “#pragma shmpi shared”. 
         [0019]    Functionalities of analyzer  21 , retriever  22  and annotator  23  may be implemented by a programmer, a complier or other devices for compiling the MPI program. 
         [0020]    Library  24  may identify the shared data from the MPI program based upon the shared directive. Library  24  may further allocate the shared data in shared memory  13 , e.g., by using inter-process communication (IPC)/shared memory (shm) routines. For data allocation, library  24  may first assign a buffer (buffer  130  of  FIG. 1 ) from shared memory  13  to locate the shared data, in which buffer  130  may comprise a plurality of storage units with consecutive logical addresses. Then, library  24  may map a memory address of buffer  130  to the processes that may use the shared data. Compared with conventional data replication, only one copy of the shared data may be maintained in shared memory  13 . 
         [0021]    Parser  25  may transform the MPI communication pattern for the shared data into single-data-copy-access pattern. More specifically, processes may read or write the single copy of the shared data from or to the dedicated buffer  130  of shared memory  13 . If a process needs the shared data updated by another process, the process can read the shared data from shared memory  13  after the another process completes updating and writing the shared data into shared memory  13 . If two or more processes read the same shared data, they can do it simultaneously. 
         [0022]      FIG. 3  shows an embodiment of a method of MPI program optimization during the compiling stage. In block  301 , analyzer  21  may analyze the MPI program about its communication pattern and data sharing information. Analyzer  21  may analyze what kind of data sharable by the processes based upon the program application. In block  302 , retriever  22  may retrieve the shared data from the MPI program. In block  303 , annotator  23  may annotate the shared data with a shared directive, e.g., “#pragma shmpi shared” directive. 
         [0023]    It should be appreciated that the above method can be implemented in other stages. 
         [0024]      FIG. 4  shows an embodiment of a method of MPI program optimization during the runtime stage. In block  401 , library  24  may identify the shared data from the MPI program based upon the shared directive. In block  402 , library  24  may allocate the shared data in buffer  130  of shared memory  13 . In block  403 , library  24  may map buffer  130  to the processes that may share the data. For example, library  24  may map the address of buffer  130  to the processes. In block  404 , parser  25  may transform the MPI communication patter for the shared data into the above-sated single-data-copy-access pattern. 
         [0025]    It should be appreciated that the above method can be implemented in other stages. 
         [0026]      FIG. 5  shows an embodiment of a method of executing optimized MPI program. In block  501 , a process may run the MPI program. In block  502 , it may be determined whether the MPI program instructs to read or write the shared data. If so, the process may obtain the address of the shared data in shared memory  13  in block  503 . The process may obtain the address of the shared data based upon the address of buffer  130  storing the shared data that may be mapped to the process by using the library routines. In block  504 , the process may read or write the shared data from or to shared memory  13 . 
         [0027]    In order to avoid data conflict, different processes may read the shared data from shared memory  13  simultaneously. However, if a process needs the shared data that is updated by another process, the process can read the shared data after the another process completes updating and writing the shared data into shared memory  13 . Various mechanisms may be used to ensure that the data is accessed appropriately, for example, but not limited to, exclusive mutual access mechanisms. 
         [0028]    Although the current invention has been described in conjunction with certain embodiments, it shall be understood that modifications and variations may be resorted to without departing from the spirit and scope of the invention as those skilled in the art readily understand. Such modifications and variations are considered to be within the scope of the invention and the appended claims.