Patent Publication Number: US-9891655-B2

Title: Parallel operation system, apparatus and medium

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2014-247478, filed on Dec. 5, 2014, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiment discussed herein is related to a parallel operation system, an apparatus and a medium. 
     BACKGROUND 
     There is a conventional technique so-called non-uniform memory access (NUMA) that configures such a system that nodes are provided, each of the nodes has a processor and a memory, and the memory is shared between the nodes. 
     As a related conventional technique, for example, there is a technique of automatically extracting tasks having parallelism from an input program to be processed by a compiler, and arranging the tasks according to characteristics of processor units, in a multiprocessor system. There is also a technique of setting an arrangement having preceding reference data dependency to a work variable, generating a loop, and, after the loop, calculating an execution sentence of the loop where the arrangement having the data dependency is replaced with the work variable. There is also a technique of outputting a transaction for synchronization, after all the transactions of preceding instructions are outputted, to a main memory that serializes memory accesses by the transaction, and to a coherence unit that guarantees completion of cache coherence control by the transaction. There is also a technique of performing a barrier synchronization process, by allocating a synchronization flag area of each processor on a shared memory, updating the synchronization flag area with software in accordance with an execution condition, and causing each processor to compare the synchronization flag areas of other processors taking part in the barrier synchronization with each other. There is also a technique of generating an object code executable on a shared memory type computer with a thread as a unit of parallel processing, by using an intra-thread synchronization overhead information file and a number-of-machine-cycles acquisition library. 
     Known examples of the conventional techniques include Japanese Laid-open Patent Publication Nos. 2006-293768, 2010-191506, 2000-194680, 2005-71109, and 2007-108838. 
     SUMMARY 
     According to an aspect of the invention, a parallel operation system includes: a first node including a first processor configured to execute a first process, a second processor configured to execute a second process, and a first memory; and a second node including a third processor configured to execute a third process, a fourth processor configured to execute a fourth process, and a second memory; and a first signal line that transfers synchronization information between at least one of the first and second processors and at least one of the third and fourth processors, wherein when the first process is to be synchronized with the third process, at least one of the first and the third processors using the first signal line to execute a first synchronization process. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is an explanatory diagram illustrating an operation example of a parallel operation system according to the embodiment; 
         FIG. 2  is an explanatory diagram illustrating a configuration example of a server system; 
         FIG. 3  is an explanatory diagram illustrating a hardware configuration example of a server; 
         FIG. 4  is an explanatory diagram illustrating examples of a CPU synchronization process and a memory synchronization process; 
         FIG. 5  is a block diagram illustrating a functional configuration example of the server; 
         FIG. 6  is an explanatory diagram illustrating an example of a performance measurement program; 
         FIG. 7  is an explanatory diagram illustrating an example of a parameter pattern in the performance measurement program; 
         FIG. 8  is an explanatory diagram illustrating an example of synchronization-method-specific performance information; 
         FIG. 9  is an explanatory diagram illustrating an example of a program including a dependency loop; 
         FIG. 10  is an explanatory diagram illustrating an example of a decision result of a synchronization method; 
         FIG. 11  is an explanatory diagram illustrating an example of a flow of a process including a dependency loop according to a decision result of a synchronization method; 
         FIG. 12  is a flowchart illustrating an example of a dependency-loop detection process procedure; 
         FIG. 13  is a flowchart illustrating an example of a synchronization-method decision process procedure; and 
         FIGS. 14, 15, and 16  are flowcharts illustrating an example of a dependency-loop execution process procedure. 
     
    
    
     DESCRIPTION OF EMBODIMENT 
     According to conventional techniques, when processes executed by the respective processors belonging to different nodes synchronize on a system to which NUMA is applied, processing performance of the system deteriorates, as compared with a case where processes executed by the respective processors belonging to the same node synchronize. 
     In one aspect, the embodiment is intended to improve processing performance of a system when processes executed by respective processors included in the system synchronize. 
     The embodiment will be described in detail below, with reference to the drawings. 
       FIG. 1  is an explanatory diagram illustrating an operation example of a parallel operation system  100  according to the embodiment. The parallel operation system  100  is a system to which NUMA is applied. Specifically, the parallel operation system  100  illustrated in  FIG. 1  has two nodes. Each of the nodes included in the parallel operation system  100  will be hereinafter referred to as “NUMA node”. Further, the two nodes will be referred to as “NUMA-0 node” and “NUMA-1 node”, respectively. 
     The NUMA node has processors and a memory. Here, as the processors, a multi-core processor having one central processing unit (CPU) with processor cores may be used, or single processors may be used. The processors may each be hereinafter merely referred to as “core”. The NUMA-0 node has a core c 0 , a core c 1 , and a memory m 0 . The NUMA-1 node has a core c 2 , a core c 3 , and a memory m 1 . The number of cores included in the NUMA node may be two or more, and the numbers of cores included in the NUMA nodes may be different. Further, the number of memories included in the NUMA node may be two or more, or the numbers of memories included in the NUMA nodes may be different. 
     Here, there is a case where processes executed by the respective cores included in the parallel operation system  100  synchronize. The case where the processes synchronize is a case where it is desirable to secure the order in which each of the processes is executed. As a specific example of the case where the processes synchronize, there is a dependency loop in thread parallelism. As another example, there is a case where processes perform exclusive control with respect to each other. The following example will be described using the dependency loop in the thread parallelism. 
     The dependency loop in the thread parallelism is a loop in which there is a dependence relation between processes per loop. Here, the process per loop may be referred to as “iteration”. The cores included in the parallel operation system  100  are caused to execute one or more iterations as one thread. As an example of the loop with the dependence relation, there is a case where a result of executing the preceding iteration is used as an input of the next iteration. When the dependence relation is present, it is difficult to execute the preceding iteration and the next iteration in parallel, and therefore, the next iteration is executed after completion of the preceding iteration. For example, in a loop construct of OpenMP, a dependency loop may be generated, when an ordered construct is used. 
     In addition, the dependency loop in the thread parallelism is implemented by a post process and a wait process, serving as a synchronization process. A core executing the preceding thread performs, upon completion of an iteration managed by the thread being executed, the post process on a core that executes a thread to be executed after the preceding thread. The core that executes the thread to be executed after the preceding thread is in a wait state due to the wait process, and terminates the wait state upon receiving notification provided by the post process. 
     The post process and the wait process that become the synchronization process will be further described. As each of the post process and the wait process, there is a process using the memory included in the NUMA node. The post process and the wait process each using the memory may be hereinafter referred to collectively as “memory synchronization process”. Further, the post process using the memory will be referred to as “memory-synchronization-based post process”, and the wait process using the memory will be referred to as “memory-synchronization-based wait process”. 
     For example, the core executing the preceding thread increments a variable “counter” shared between the threads by one, each time one iteration is executed. Here, the variable “counter” is stored in a chunk secured in the memory included in the NUMA node. The core executing the preceding thread updates the value of the variable “counter”, each time increment is performed. When the variable “counter” becomes greater than an iteration exit value “end”, the core executing the preceding thread ends the execution. The last update of the variable “counter” is the memory-synchronization-based post process. 
     On the other hand, by referring to the value of the variable “counter”, the thread to be executed after the preceding thread waits when the value of the variable “counter” is smaller than an iteration starting value “start” of the own thread, and executes an iteration of the own thread by terminating the waiting when the value of the variable “counter” is greater than “start”. Such waiting when the value of the variable “counter” is smaller than “start” and terminating the waiting when the value of the variable “counter” is greater than “start” is the memory-synchronization-based wait process. 
     Here, when processes executed by the cores belonging to the different NUMA nodes execute the memory synchronization process, the processing performance of the system deteriorates, as compared with a case where processes executed by the cores belonging to the same NUMA node execute the memory synchronization process. In particular, a waiting time may increase in the core executing the preceding thread and the core executing the next thread, as a chunk size used for the memory synchronization process becomes small. 
     For example, assume that the chunk size is a size that allows storage of only one value of the variable “counter”. In this case, the core executing the preceding thread, after writing the value of the variable “counter” once, is allowed to perform rewriting only after the core executing the next thread refers to the value of the variable “counter”. In this way, when the size allows storage of only one value of the variable “counter”, the core executing the preceding thread is not allowed to write the values of the variable “counter” successively, and thus the waiting time increases. 
     Therefore, when synchronizing the processes to be executed by the cores provided in the different nodes, the parallel operation system  100  performs a first synchronization process using an exclusive signal line that couples the cores provided in the different nodes. This increases system performance of the parallel operation system  100 , further than in performing a second synchronization process using the memory, namely, the above-described memory synchronization process. The synchronization process using the signal line will be described later. In the example illustrated in  FIG. 1 , when threads t 0  and t 1  perform the memory synchronization process, data moves as indicated by a broken line in  FIG. 1 . Therefore, a delay occurs, as compared with the case where the first synchronization process is performed. 
     Operation of the parallel operation system  100  will be described using  FIG. 1 . The parallel operation system  100  has a signal line that couples the processors of the respective NUMA nodes. In the example illustrated in  FIG. 1 , the parallel operation system  100  has a signal line h that couples the core c 1  and the core c 2 . Further, in the example illustrated in  FIG. 1 , the core c 1  serving as a first processor and the core c 2  serving as a second processor are assumed to execute the dependence loop in the thread parallelism. The core c 1  is assumed to execute the thread t 0  as a first process, and the core c 2  is assumed to execute the thread t 1  as a second process. The thread t 0  is assumed to precede the thread t 1 . 
     In this way, the core c 1  and the core c 2  belong to the different NUMA nodes, and therefore, a parallel operation apparatus decides to execute the synchronization process using the signal line h. Here, the parallel operation apparatus making this decision may be configured by treating the core c 1  and the memory m 0  as a computer system, or may be configured by treating the memory m 1  and the core c 2  as a computer system, or may be a computer provided outside the parallel operation system  100 . 
     The first synchronization process using the signal line that couples the cores provided in the different nodes also has the post process and the wait process. The parallel operation system  100  may also have a signal line that couples the cores included in each of the nodes, and in this case, may execute a third synchronization process using the signal line that couples the cores included in each of the nodes. The third synchronization process also has the post process and the wait process. The first synchronization process and the third synchronization process will be hereinafter referred to collectively as “CPU synchronization process”. The post process using the signal line will be referred to as “CPU-synchronization-based post process”, and the wait process using the signal line will be referred to as “CPU-synchronization-based wait process”. The CPU synchronization process and the memory synchronization process will be described with reference to  FIG. 4 , by using examples. The CPU synchronization process and the memory synchronization process will be hereinafter referred to collectively as “synchronization method”. 
     A specific operation example of the CPU synchronization process will be described below. In the CPU synchronization process, a variable shared between the threads is not provided, and each of the threads has a local variable “local_counter”. The core c 1  executing the preceding thread t 0  updates the value of the local variable “local_counter”. When the local variable “local_counter” becomes greater than the iteration exit value “end”, the core c 1  provides notification of a flag indicating completion of the iteration managed by the own thread, via the signal line h. Providing the notification of the flag via the signal line h is the CPU-synchronization-based post process. 
     On the other hand, the core c 2  executing the thread t 1  to be executed after the thread t 0  waits until receiving the notification of the flag, and executes the iteration of the own thread by terminating the waiting, upon receiving the notification of the flag. Waiting until receiving the notification of the flag and terminating the waiting upon receiving the notification of the flag is the CPU-synchronization-based wait process. 
     Next, an example in which the parallel operation system  100  is applied to a server system will be described using  FIG. 2 . 
       FIG. 2  is an explanatory diagram illustrating a configuration example of a server system  200 . The server system  200  has a server  201  and a login node  202 . The server  201  has the parallel operation system  100 . 
     The parallel operation system  100  has the NUMA-0 node and the NUMA-1 node. Here, each hardware synchronization line corresponds to the signal line h illustrated in  FIG. 1 . Hardware of the NUMA-0 node and hardware of the NUMA-1 node are identical and therefore, only the hardware of the NUMA-0 node will be described below. 
     The NUMA-0 node has the core c 0 , the core c 1 , a L1 cache memory I 10 , a L1 cache memory I 11 , a L2 cache memory I 20 , the memory m 0 , and a hardware synchronization line h 0 . The L1 cache memory I 10  is a primary cache memory used by the core c 0 . The L1 cache memory I 11  is a primary cache memory used by the core c 1 . The L2 cache memory I 20  is a secondary cache memory used by the core c 0  and the core c 1 . 
     The hardware synchronization line h 0  and a hardware synchronization line h 1  may each be a signal line that couples all the cores in the parallel operation system  100 , or may be a signal line that couples some of the cores in the parallel operation system  100 . As an example of the signal line that couples some of the cores, the parallel operation system  100  may have a signal line between the cores c 0  and c 1 , a signal line between the cores c 1  and c 2 , a signal line between the cores c 2  and c 3 , and a signal line between the cores c 3  and c 0 , so that these signal lines form a ring. 
     The login node  202  is a computer to be operated by a user who uses the parallel operation system  100 . Specifically, the login node  202  transmits a job that performs scientific calculation, to the parallel operation system  100 , according to operation of the user. 
       FIG. 3  is an explanatory diagram illustrating a hardware configuration example of the server  201 . In  FIG. 3 , the server  201  includes the parallel operation system  100 , a read only memory (ROM)  301 , a disk drive  302 , a disk  303 , and a communication interface  304 . Further, the parallel operation system  100 , the ROM  301 , the disk drive  302 , and the communication interface  304  are interconnected by a bus  305 . 
     The parallel operation system  100  is an arithmetic processing unit group that performs overall control of the server  201 . The ROM  301  is a nonvolatile memory that stores programs such as a boot program. 
     The disk drive  302  is a control device that controls reading and writing of data from and to the disk  303  according to control of the parallel operation system  100 . For example, a disk drive, a solid state drive, or the like may be adopted for the disk drive  302 . The disk  303  is a nonvolatile memory that stores data written by control of the disk drive  302 . When the disk drive  302  is, for example, a magnetic disk drive, a magnetic disk may be adopted for the disk  303 . When the disk drive  302  is a solid state drive, a semiconductor memory formed of a semiconductor element, a so-called semiconductor disk, may be adopted for the disk  303 . 
     The communication interface  304  is a control device that controls an interface between inside and a network such as a local area network (LAN), a wide area network (WAN), and the Internet, and controls input and output of data to and from other apparatus. Specifically, the communication interface  304  is coupled to the login node  202  or the like via the network. For example, a modem, a LAN adapter, or the like may be adopted for the communication interface  304 . 
     When an operator of the server system  200  directly operates the server  201 , the server  201  may have hardware such as a display, a keyboard, and a mouse. 
     Further, although hardware of the login node  202  is not illustrated in particular, the login node  202  has a CPU, a random access memory (RAM), a ROM, a disk drive, a disk, a communication interface, a display, a keyboard, and a mouse. 
       FIG. 4  is an explanatory diagram illustrating examples of the CPU synchronization process and the memory synchronization process. The examples illustrated in  FIG. 4  include an example of each of the CPU synchronization process closed in the NUMA node, the CPU synchronization process involving the NUMA nodes, and the memory synchronization process involving the NUMA nodes. 
     In  FIG. 4 , a notification example of the CPU synchronization process closed in the NUMA node is indicated by an arrow of alternate long and short dashed lines. Further, a notification example of the CPU synchronization process involving the NUMA nodes is indicated by an arrow of a solid line. Furthermore, a notification example of the memory synchronization process involving the NUMA nodes is indicated by an arrow of a broken line. 
     In a comparison between the CPU synchronization process involving the NUMA nodes and the memory synchronization process involving the NUMA nodes, due to a route passing through the memory, the CPU synchronization process involving the NUMA nodes is faster. However, in a comparison between the CPU synchronization process closed in the NUMA node and the memory synchronization process closed in the NUMA node, the memory synchronization process may be faster, when any of the following conditions are satisfied. A first condition is a case where, as for the NUMA-0 node, the L1 cache memories I 10  and I 11  communicate with the L2 cache memory I 20  at a high speed. A second condition is a case where, as for the NUMA-0 node, direct data transmission may be performed between the L1 cache memories I 10  and I 11 . A third condition is a case where the chunk size is large. 
     Therefore, according to parameters such as the chunk size, characteristics of the memory, and the like, the server  201  decides either the CPU synchronization process or the memory synchronization process to be used as the synchronization method, whichever is faster. How to make this decision will be specifically described using  FIG. 5 . 
     (Functional Configuration Example of Server  201 ) 
       FIG. 5  is a block diagram illustrating a functional configuration example of the server  201 . The server  201  has a control unit  500 . The control unit  500  includes a decision section  501  and an execution section  502 . Any of the cores in the parallel operation system  100  may execute a program stored in a storage device, so that the control unit  500  implements a function of each section. The storage device is, specifically, for example, the memory in the parallel operation system  100  illustrated in  FIG. 1 , any of the ROM  301  and the disk  303  illustrated in  FIG. 3 , or the like. Further, a processing result of each section is stored in a register of any of the cores in the parallel operation system  100 , the cache memory in the parallel operation system  100 , or the like. 
     In addition, the server  201  may access synchronization-method-specific performance information  510 . The synchronization-method-specific performance information  510  stores a comparison result between processing performance of the CPU synchronization process and processing performance of the memory synchronization process according to the chunk size secured when the memory synchronization process is performed. Further, the synchronization-method-specific performance information  510  may store a comparison result between processing performance of the CPU synchronization process and processing performance of the memory synchronization process according to the number of times any of processes is repeated. Here, this any of processes may be any kind of process if this process is a process per dependency loop, or may be a process performing nothing.  FIG. 6  illustrates a specific example of this any of processes. The number of times this any of processes is repeated may be the number of iterations included in the dependency loop, or may be the number of iterations per thread when the dependence loop is divided into threads. Further, the synchronization-method-specific performance information  510  may store a comparison result between processing performance of the CPU synchronization process and processing performance of the memory synchronization process according to the number of threads into which the dependency loop is divided. 
     The synchronization-method-specific performance information  510  is stored in the storage device such as the memory in the parallel operation system  100  and the disk  303 . An example of storage contents of the synchronization-method-specific performance information  510  will be described with reference to  FIG. 8 . 
     The decision section  501  decides to execute the CPU synchronization process, when a first core, and a second core, which executes a second thread synchronizing with a first thread, belong to the different NUMA nodes. 
     Further, when the first core and the second core belong to the same node, the decision section  501  may decide to execute the memory synchronization process using the memory included in the NUMA node to which the first core and the second core belong. 
     Assume that the first core and the second core belong to the same node. In this case, the decision section  501  may decide to execute either one of the CPU synchronization process and the memory synchronization process, based on the chunk size to be secured when the memory synchronization process is performed, by referring to the synchronization-method-specific performance information  510 . 
     For example, assume that the comparison result corresponding to the same size as the chunk size to be secured when the memory synchronization process is performed is stored in the synchronization-method-specific performance information  510 . In this case, the decision section  501  acquires the comparison result corresponding to the same size as the chunk size to be secured, and decides to execute the synchronization method indicated as a faster one by the acquired comparison result. Further, for example, assume that the comparison result corresponding to the same size as the chunk size to be secured when the memory synchronization process is performed is not stored in the synchronization-method-specific performance information  510 . In this case, the decision section  501  acquires, for example, the comparison result corresponding to a size closest to the chunk size to be secured, and decides to execute the synchronization method indicated as a faster one by the acquired comparison result. 
     Further, assume that the first core and the second core belong to the same node. In this case, the decision section  501  refers to the synchronization-method-specific performance information  510 , thereby deciding to execute either one of the CPU synchronization process and the memory synchronization process, based on the number of times the first thread and the second thread repeat a predetermined process. Here, the predetermined process is a part of what is generated from a job transmitted from the login node  202 , and corresponds to one iteration. A specific example of the predetermined process is illustrated in  FIG. 9 . Further, the first thread and the second thread may repeat the predetermined process the same number of times, or may repeat the predetermined process the different numbers of times. The number of times the first thread and the second thread repeat the predetermined process may be the total number of times the first thread and the second thread each repeat the predetermined process, or may be an average thereof. 
     The execution section  502  executes the synchronization process decided by the decision section  501 . For example, assume that the decision section  501  decides to execute the CPU synchronization process, and the core having the execution section  502  executes the post process. In this case, the execution section  502  executes the CPU-synchronization-based post process. 
       FIG. 6  is an explanatory diagram illustrating an example of a performance measurement program  601 . The performance measurement program  601  illustrated in  FIG. 6  is a program to be used in generating the synchronization-method-specific performance information  510 . In the example illustrated in  FIG. 6 , the dependency loop is a part specified by the next curly braces specified by “#pragma omp ordered”. 
     In the performance measurement program  601 , “loop”, “chunk”, and “threads” indicate the total number of loops, the chunk size, and the number of threads, respectively, and serve as parameters for the performance measurement program  601 . A value that may be taken by each of “loop”, “chunk”, and “threads” will be described with reference to  FIG. 7 . 
       FIG. 7  is an explanatory diagram illustrating an example of a parameter pattern in the performance measurement program  601 . As illustrated in  FIG. 7 , the value that may be taken by the parameter “chunk” depends on “loop”, and is any of “loop/2”, “loop/4”, “loop/8”, . . . , and 1. Further, the number of values that may be taken by the parameter “chunk” is “floor(log 2  loop)”. Here, “floor(x)” indicates a maximum integer equal to or smaller than x. 
     Here, for simplification of the description, a data size to be “chunk=1” in the embodiment is assumed to be a data size to be used when data is exchanged between the two threads per loop. For example, when the value of the counter is exchanged between the two threads, “chunk=1” is a data size that allows the value of the counter to be stored with one loop. Similarly, “chunk=x” is a data size x times greater than the data size that allows the value of the counter to be stored with one loop. Further, an nth chunk is “(½) n ×loop”, where “(½) n ×loop”≧1. 
     The value that may be taken by the parameter “loop” is any of 100, 1000, 10000, 50000, and 100000. The number of values that may be taken by the parameter “chunk” is 5. 
     The value that may be taken by the parameter “threads” is any of 2, 3, 4, . . . , and the number of cores in the NUMA node. The number of values that may be taken by the parameter “threads” is “(the number of cores in the NUMA node)−1”. 
     Therefore, the number of times of execution by the performance measurement program  601  is “floor(log 2  loop)×5×((the number of cores in NUMA nodes)−1). 
       FIG. 8  is an explanatory diagram illustrating an example of the synchronization-method-specific performance information  510 . The synchronization-method-specific performance information  510  is information indicating which one of the CPU synchronization process and the memory synchronization process is faster, based on each parameter illustrated in  FIG. 7 . The synchronization-method-specific performance information  510  illustrated in  FIG. 8  indicates either the CPU synchronization process or the memory synchronization process whichever is faster, depending on the combination of “chunk” and “loop”, in a certain number of “threads”. Here, for simplification of the description, “C” illustrated in  FIG. 8  is assumed to indicate that the CPU synchronization process is faster, and “M” illustrated in  FIG. 8  is assumed to indicate that the memory synchronization process is faster. 
     The synchronization-method-specific performance information  510  illustrated in  FIG. 8  has records  801 - 1  to  801 - 5 . For example, the record  801 - 1  indicates either the CPU synchronization process or the memory synchronization process whichever is faster, in each of “chunk”=1, 2, 4, 8, . . . , when “loop”=100. 
     Next, a decision result in executing the dependency loop of the synchronization method, and execution of the dependence loop according to the decision result will be described with reference to  FIGS. 9 to 11 , by using an example. 
       FIG. 9  is an explanatory diagram illustrating an example of a program  901  including the dependency loop. The program  901  represents an example of the dependency loop, which is “chunk”=25, “loop”=200, and “threads”=4. In the program  901 , the predetermined process is a part “printf(“i=% d”, i);” specified by the next curly braces specified by “#pragma omp ordered”. 
     Further, the two NUMA nodes are assumed to execute the program  901 , and the cores c 0  and c 1  of the NUMA-0 node, and the cores c 2  and c 3  of the NUMA-1 node are each assumed to execute the threads t 0  to t 3 . Furthermore, the core that executes the thread is assumed to communicate with the core on the right illustrated in  FIG. 2 . Still further, the core on the right of the core that executes the last thread is assumed to be the core c 0 . For example, the core c 0  that executes the thread t 0  communicates with the core c 1  that executes the thread t 1 . Further, the core c 3  that executes the thread t 3  communicates with the core c 0  that executes the thread t 0 . 
     It is assumed that, after executing the 0th to 24th dependency loops, the thread t 0  provides notification to the thread t 1  in the post process, and then enters the wait state by performing the wait process, and subsequently executes the 100th to 124th dependency loops by receiving notification from the thread t 3 . It is also assumed that, after executing the 25th to 49th dependency loops by receiving notification from the thread t 0 , the thread t 1  provides notification to the thread t 2  in the post process, and then enters the wait state by performing the wait process, and subsequently executes the 125th to 149th dependency loops by receiving notification from the thread t 0 . 
     It is also assumed that, after executing the 50th to 74th dependency loops by receiving notification from the thread t 1 , the thread t 2  provides notification to the thread t 3  in the post process, and then enters the wait state by performing the wait process, and subsequently executes the 150th to 174th dependency loops by receiving notification from the thread t 1 . It is also assumed that, after executing the 75th to 99th dependency loops by receiving notification from the thread t 2 , the thread t 3  provides notification to the thread t 0  in the post process, and then enters the wait state by performing the wait process, and subsequently executes the 175th to 199th dependency loops by receiving notification from the thread t 2 . 
     A group of iterations that the thread performs the dependency loop may be hereinafter referred to as “iteration group”. 
       FIG. 10  is an explanatory diagram illustrating an example of the decision result of the synchronization method. The cores c 0  to c 3  each decide the synchronization method to be performed in the post process, and the synchronization method to be performed in the wait process. In the example illustrated in  FIG. 10 , the cores c 0  to c 3  each decide to execute the memory synchronization process when the cores communicating with each other belong to the same NUMA node, and decide to execute the CPU synchronization process when the cores communicating with each other belong to the different NUMA nodes. 
     As illustrated in  FIG. 10 , when, for example, the core c 0  executes the post process and the core c 1  executes the wait process, the core c 0  and the core c 1  belong to the same NUMA node, and therefore, the core c 0  decides to execute the memory synchronization process as the synchronization method. When the core c 3  performs the post process and the core c 0  performs the wait process, the core c 3  and the core c 0  belong to the different NUMA nodes, and therefore, the core c 0  decides to execute the CPU synchronization process as the synchronization method. 
     In this way, in the thread executed by each core, the synchronization methods may be different. However, as for the cores communicating with each other, the one performing the post process and the other performing the wait process, pieces of information to make the decision are identical and therefore the synchronization methods match with each other. 
       FIG. 11  is an explanatory diagram illustrating an example of a flow of the process including the dependency loop according to the decision result of the synchronization method. In  FIG. 11 , the notification based on the post process is indicated by a dotted line, and the wait state based on the wait process is indicated by alternate long and short dashed lines. 
     As illustrated in  FIG. 11 , the core c 0  that executes the thread t 0  executes the 0th to 24th dependence loops, and provides notification based on the memory-synchronization-based post process to the core c 1  that executes the thread t 1 , and then enters the wait state by performing the CPU-synchronization-based wait process. The core c 0  then executes the 100th to 124th dependency loops by receiving notification based on the CPU-synchronization-based post process from the core c 3  that executes the thread t 3 . The core c 1  that executes the thread t 1  first enters the wait state by executing the memory-synchronization-based wait process. The core c 1  then executes the 25th to 49th dependency loops by receiving notification based on the memory-synchronization-based post process from the core c 0 , and then provides notification based on the CPU-synchronization-based post process to the core c 2  that executes the thread t 2 , and subsequently enters the wait state by performing the memory-synchronization-based wait process. 
     The core c 2  that executes the thread t 2  first enters the wait state by performing the CPU-synchronization-based wait process. The core c 2  then executes the 50th to 74th dependency loops by receiving notification based on the CPU-synchronization-based post process from the core c 1 , and then provides notification based on the memory-synchronization-based post process to the core c 3  that executes the thread t 3 , and subsequently enters the wait state by performing the CPU-synchronization-based wait process. The core c 3  that executes the thread t 3  first enters the wait state by performing the memory-synchronization-based wait process. The core c 3  then executes the 75th to 99th dependency loops by receiving notification based on the memory-synchronization-based post process from the core c 2 , and then provides notification based on the CPU-synchronization-based post process to the core c 0  that executes the thread t 0 , and subsequently enters the wait state by performing the memory-synchronization-based wait process. 
     As illustrated in  FIG. 11 , the cores communicating with each other, the one performing the post process and the other performing the wait process, the synchronization methods match with each other, so that the dependence loop may be correctly executed. Next, processes performed by the server system  200  will be described using a flowchart of each of  FIGS. 12, 13, 14, 15 , and  16 . 
       FIG. 12  is a flowchart illustrating an example of a dependency-loop detection process procedure. A dependency-loop detection process is executed when the dependency loop is detected. Each core executes the dependency-loop detection process when detecting the dependency loop. The description with reference to  FIGS. 12, 13, 14, 15, and 16  will be provided taking the execution by the core c 0  as an example. 
     The core c 0  detects the dependency loop in the thread (step S 1201 ). Next, the core c 0  executes a synchronization-method decision process, for the post process or the wait process in the thread (step S 1202 ). The synchronization-method decision process will be described with reference to  FIG. 13 . 
     The core c 0  then executes a dependency-loop execution process by using the decision result (step S 1203 ). The dependency-loop execution process will be described with reference to  FIGS. 14, 15, and 16 . Upon completion of the process in step S 1203 , the core c 0  ends the dependency-loop detection process. The server system  200  may execute the dependency loop faster, by executing the dependency-loop detection process. 
       FIG. 13  is a flowchart illustrating an example of a synchronization-method decision process procedure. The synchronization-method decision process is a process to decide the synchronization method in executing the post process or the wait process. Here, the core c 0  is assumed to know an ID of the core to be a destination of notification, when executing the post process. Similarly, the core c 0  is assumed to know an ID of the core to be a sender of notification, when executing the wait process. Further, the synchronization-method decision process is executed by calling a program provided by a library. Furthermore, the above-described library decides the total number of loops, the number of threads, and the chunk size, when the synchronization-method decision process is executed. 
     The core c 0  determines whether the hardware synchronization line is present, for the core to be the destination of the notification when executing the post process, or the core to be the sender of the notification when executing the wait process (step S 1301 ). In step S 1301 , specifically, an application programming interface (API), which asks the OS whether the hardware synchronization line is present, is described in the program provided by the library. The core c 0  determines whether the hardware synchronization line is present, by calling the above-described API. 
     When the hardware synchronization line is present (step S 1301 : Yes), the core c 0  then determines whether to execute the post process or the wait process (step S 1302 ). When executing the post process (step S 1302 : post process), the core c 0  determines whether the post process involves the NUMA nodes (step S 1303 ). When executing the wait process (step S 1302 : wait process), the core c 0  determines whether the wait process involves the NUMA nodes (step S 1304 ). 
     When the post process does not involve the NUMA nodes (step S 1303 : No), or when the wait process does not involve the NUMA nodes (step S 1304 : No), the core c 0  determines which one of the CPU synchronization process and the memory synchronization process is faster (step S 1305 ). Specifically, for example, the core c 0  determines which one of the CPU synchronization process and the memory synchronization process is faster, based on the total number of loops, the number of threads, and the chunk size decided by the above-described library, by referring to the synchronization-method-specific performance information  510 . 
     When the post process involves the NUMA nodes (step S 1303 : Yes), or when the wait process involves the NUMA nodes (step S 1304 : Yes), or when the CPU synchronization process is faster (step S 1305 : CPU synchronization process), the core c 0  decides the CPU synchronization process as the synchronization method (step S 1306 ). Specifically, the core c 0  decides the CPU synchronization process as the synchronization method of the post process when executing the post process, and decides the CPU synchronization process as the synchronization method of the wait process when executing the wait process. 
     On the other hand, when the memory synchronization process is faster (step S 1305 : memory synchronization process), or when the hardware synchronization line is not present (step S 1301 : No), the core c 0  decides the memory synchronization process as the synchronization method (step S 1307 ). Specifically, the core c 0  decides the memory synchronization process as the synchronization method of the post process when executing the post process, and decides the memory synchronization process as the synchronization method of the wait process when executing the wait process. 
     Upon completion of the process in step S 1306  or step S 1307 , the core c 0  ends the synchronization-method decision process. The core c 0  may select either the CPU synchronization process or the memory synchronization process, whichever is faster, as the synchronization method in executing the post process or the wait process, by executing the synchronization-method decision process. 
       FIGS. 14, 15, and 16  are flowcharts illustrating an example of a dependency-loop execution process procedure. The dependency-loop execution process is a process to execute the dependency loop.  FIGS. 14, 15, and 16  are assumed to represent the process in executing the dependence loop illustrated in  FIGS. 9, 10, and 11 . 
     Here, the variables to be used in the dependency-loop execution process will be described. The variable “counter” is a variable shared between the threads, and is a counter of a shared variable used in the memory synchronization process. The following variables are local in the thread. The variable “local_counter” is a thread-local counter used in the CPU synchronization process. The value “start” and the value “end” are a starting value and an exit value, respectively, of an iteration managed by the thread. The chunk size managed by the thread is represented by “chunk”. An identifier indicating “post” or an identifier indicating “wait” is stored by “role”. 
     The core c 0  sets “counter” to 0 (step S 1401 ). Next, the core c 0  sets “role” to either “post” or “wait” (step S 1402 ). In step S 1402 , specifically, the core executing the thread t 0  that is a top thread sets “role” to “post”, and other cores set “role” to “wait”. Therefore, the core c 0  sets “role” to “post”, to execute the thread t 0 . Further, the cores c 1  to c 3  each set “role” to “wait”. 
     Upon completion of the process in step S 1402  or completion of a process in step S 1509 , the core c 0  determines whether there is a remaining iteration group to be managed by the own thread (step S 1403 ). When there is no remaining iteration group to be managed by the own thread (step S 1403 : No), the core c 0  ends the dependency-loop execution process. 
     On the other hand, when there is a remaining iteration group to be managed by the own thread (step S 1403 : Yes), the core c 0  receives “start”, “end”, and “chunk” of the iteration group to be managed by the core c 0  (step S 1404 ). Here, “start”, “end”, and “chunk” are values decided by the library that provides the program for the synchronization-method decision process. Next, the core c 0  sets “local_counter” to 0 (step S 1405 ). 
     Upon completion of the process in step S 1405  or completion of a process in step S 1605 , the core c 0  determines which one of the following identifiers matches with “role” (step S 1406 ). The identifiers are the identifier indicating “post” and the identifier indicating “wait”. When “role” is the identifier indicating “post” (step S 1406 : post), the core c 0  determines whether the synchronization method of the post process is the memory synchronization process or the CPU synchronization process (step S 1501 ). Here, the synchronization method of the post process is decided in either step S 1306  or step S 1307 . 
     When the synchronization method of the post process is the memory synchronization process (step S 1501 : memory synchronization process), the core c 0  determines whether “counter” is greater than “end” (step S 1502 ). When “counter” is equal to or less than “end” (step S 1502 : No), the core c 0  executes one iteration (step S 1503 ). The core c 0  then sets “counter” to “counter+1” (step S 1504 ). Upon completion of the process in step S 1504 , the core c 0  shifts to the process in step S 1502 . 
     On the other hand, when the synchronization method of the post process is the CPU synchronization process (step S 1501 : CPU synchronization process), the core c 0  determines whether “local_counter” is equal to or greater than “chunk” (step S 1505 ). When “local_counter” is less than “chunk” (step S 1505 : No), the core c 0  executes one iteration (step S 1506 ). Next, the core c 0  sets “local_counter” to “local_counter+1” (step S 1507 ). Upon completion of the process in step S 1507 , the core c 0  shifts to the process in step S 1505 . 
     On the other hand, when “local_counter” is equal to or greater than “chunk” (step S 1505 : Yes), the core c 0  transmits “CPU post” (step S 1508 ). Upon completion of the process in step S 1508 , or when “counter” is greater than “end” (step S 1502 : Yes), the core c 0  sets “role” to the identifier indicating “wait” (step S 1509 ). Upon completion of the process in step S 1509 , the core c 0  shifts to the process in step S 1403 . 
     When “role” is the identifier indicating “wait” (step S 1406 : wait), the core c 0  determines whether the synchronization method of the wait process is the memory synchronization process or the CPU synchronization process (step S 1601 ). Here, the synchronization method of the wait process is the decision made in either step S 1306  or step S 1307 . 
     When the synchronization method of the wait process is the memory synchronization process (step S 1601 : memory synchronization process), the core c 0  determines whether “counter” is smaller than “start” (step S 1602 ). When “counter” is smaller than “start” (step S 1602 : Yes), the core c 0  executes the process in step S 1602  again. 
     When the synchronization method of the wait process is the CPU synchronization process (step S 1601 : CPU synchronization process), the core c 0  performs “CPU wait” (step S 1603 ). By performing the process in step S 1603 , the core c 0  waits until receipt of notification via the hardware synchronization line h. The core c 0  sets “counter” to “start”, upon receiving notification from “post” (step S 1604 ). 
     Upon completion of the process in step S 1604  or when “counter” is equal to or greater than “start” (step S 1602 : No), the core c 0  sets “role” to the identifier indicating “post” (step S 1605 ). Upon completion of the process in step S 1605 , the core c 0  shifts to the process in step S 1406 . The core c 0  may execute the dependency loop by using either the CPU synchronization process or the memory synchronization process, whichever is faster, as the synchronization method, by executing the dependency-loop execution process. 
     As described above, according to the parallel operation system  100 , the CPU synchronization process is executed when the processes executed by the cores provided in the different NUMA nodes execute the synchronization. Therefore, when the processes executed by the cores provided in the different NUMA nodes execute the synchronization, the parallel operation system  100  may improve the processing performance of the parallel operation system  100 , as compared with a case where the memory synchronization process is performed. 
     In addition, according to the parallel operation system  100 , the memory synchronization process is executed, when the processes executed by the cores provided in the same NUMA node execute the synchronization. Therefore, when the processes executed by the cores in the same NUMA node execute the synchronization, the parallel operation system  100  may improve the processing performance of the parallel operation system  100 , as compared with a case where the CPU synchronization process is performed in most of cases. 
     Moreover, according to the parallel operation system  100 , either one of the CPU synchronization process and the memory synchronization process may be decided to be executed based on the chunk size, by referring to the synchronization-method-specific performance information  510 . Therefore, the parallel operation system  100  may decide to execute the memory synchronization process when the chunk size is large, and may decide to execute the CPU synchronization process when the chunk size is small. 
     Further, according to the parallel operation system  100 , either one of the CPU synchronization process and the memory synchronization process may be decided to be executed based on the number of iterations, by referring to the synchronization-method-specific performance information  510 . Therefore, the parallel operation system  100  may decide to execute the CPU synchronization process when the number of iterations is small, and may decide to execute the memory synchronization process when the number of iterations is large. 
     Assume that the first core and the second core included in the parallel operation system  100  execute the dependency loop. In addition, assume that either one of the first core and the second core satisfies the above-described decision criterion, specifically, for example, assume that the first core and the second core belong to the same NUMA node and execution of the CPU synchronization process is decided. In this case, since the first core and the second core belong to the same NUMA node, the other core of the first core and the second core may decide to execute the CPU synchronization process. Therefore, the decision result may not be transmitted to the other core. 
     A parallel operation method described in the embodiment may be implemented by causing a computer such as a personal computer and a workstation to execute a program prepared beforehand. A parallel operation program described in the embodiment is recorded in a computer readable recording medium such as a hard disk, a flexible disk, a compact disc-read only memory (CD-ROM), and a digital versatile disk (DVD), and read by the computer to be executed. In addition, the parallel operation program may be distributed via a network such as the Internet. 
     All examples and conditional language provided herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.