Method and system in a distributed shared-memory data processing system for determining utilization of nodes by each executed thread

[0002] 1. Technical Field

[0003] The present invention relates to data processing systems and, in particular, to a distributed shared-memory data processing system for determining a utilization of each of a plurality of processing nodes in the system by one of plurality of threads. Still more particularly, the present invention relates to a method and system in a distributed shared-memory data processing system for determining a utilization of each of a plurality of processing nodes in the system by one of plurality of threads by determining a quantity of times the thread accesses each shared-memory in the system.

[0004] 2. Description of the Related Art

[0005] One type of data processing system is a uniprocessor system which has only one central processing unit (CPU) which executes an operating system. This type of system is typically utilized in older computer systems.

[0006] Another type of data processing system is a multiprocessor system which has more than one CPU. A particular type of multiprocessor system is a symmetric multiprocessor system (SMP). An SMP system includes a plurality of processors, each having equal access to shared-memory and input/output (I/O) devices shared by the processors. In an SMP system, a single operating system is executed simultaneously by the plurality of processors. The operating system can divide a software application into separate processes that may be executed simultaneously on all of the processors in the system. In this manner, because different processes of the application can be simultaneously executed, the application can be executed in an SMP system faster than it could be executed in a uniprocessor system.

[0007] A multiprocessor system must have a method and system for keeping track of the different processes being executed by the different processors. The multiprocessor system utilizes threads to represent the separately dispatchable units of these processes. Threads are utilized by the operating system to keep track of the location and status of each unit of work executing on the plurality of processors.

[0008] Multiple SMP systems can be clustered together to form a more powerful data processing system. A clustered SMP system includes multiple nodes which are coupled together via an interconnection network. Each node includes one or more processors and a shared-memory which may be accessed equally by the processors within the node.

[0009] One method and system for maintaining a cluster of multiple SMP systems is called a distributed shared-memory system. A distributed shared-memory system is also called a non-uniform memory access (NUMA) system. A NUMA system includes multiple nodes as described above. Each processor in a node in the NUMA system may access the shared-memory in any of the other nodes in the system. Therefore, the memory access may be non-uniform across the nodes.

[0010] In a symmetric multiprocessor system, a single operating system is simultaneously executed by a plurality of interconnected processors. The operating system selects threads to dispatch to various processors within the SMP data processing system. A part of the operating system executing on a first processor may select a particular thread to process. The first processor may decide that the selected thread should be executed by any of the other processors in the data processing system. However, typically, the first processor will decide that the selected thread will be executed by the first processor. In the event a processor other than the first processor is selected to execute the thread, the first processor notifies the other processor that the other processor has been selected to execute the thread. The other processor then selects this thread. The other processor dispatches and executes the thread. In this manner, a processor in the system may select any of the processors in the system to execute a thread. The processor selected to execute a thread then dispatches and executes that thread.

[0011] To optimize performance of a multiprocessor system, load balancing determinations may be made. These load balance determinations are typically made utilizing a measured activity of each processor in the system. Determinations then can be made regarding processors which might remain idle for extended periods of time compared to the other processors in the system.

[0012] However, in NUMA systems, balancing the load on the processors by moving threads to different nodes must be done with great care. A thread's LOAM)/STORE references, the memory references, might cross node boundaries, i.e. might be remote memory references. A remote memory reference is a reference from one processor in a first node to a shared-memory location in a second node. A local memory reference is a reference from one processor in a first node to a shared-memory location in the first node. Remote memory references result: in poor performance.

[0013] Processor utilization data alone might call for redistributing threads by balancing the load on each processor as evenly as possible. However, balancing the load utilizing only processor utilization data could increase processor utilization while actually reducing throughput of the system if the wrong threads are redistributed.

[0014] Therefore a need exists for a method and system in a data processing system for determining utilization of each of a plurality of nodes in the data processing system by each thread which is executed.

[0015] It is therefore one object of the present invention to provide an improved data processing system.

[0016] It is another object of the present invention to provide a method and system in a distributed shared-memory data processing system for determining a utilization of each of a plurality of processing nodes in the system by one of a plurality of threads.

[0017] It is yet another object of the present invention to provide a method and system in a distributed shared-memory data processing system for determining a utilization of each of a plurality of processing nodes in the system by one of plurality of threads by determining a quantity of times the thread accesses each shared-memory in the system.

[0018] The foregoing objects are achieved as is now described. A method and system in a distributed shared-memory data processing system are disclosed for determining a utilization of each of EL plurality of coupled processing nodes by one of a plurality of executed threads. The system includes a single operating system being executing simultaneously by a plurality of processors included within each of the processing nodes. The operating system processes one of the plurality of threads utilizing one of the plurality of nodes. During the processing, for each of the nodes, a quantity of times the one of the plurality of threads accesses a shared-memory included with each of the plurality of nodes is determined.

[0019] The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.

[0020] The novel features are set forth in the appended claims. The present invention itself, however, as well as a preferred mode of use, further objectives, and advantages thereof, will best be understood by reference to the following detailed description of a preferred embodiment when read in conjunction with the accompanying drawings, wherein:

[0021] FIG. 1 depicts a block diagram of a distributed shared-memory data processing system embodying the present invention;

[0022] FIG. 2 illustrates a high-level block diagram of a counter hardware included within FIG. 1 in accordance with the method and system of the present invention;

[0023] FIG. 3 is a high level flow chart illustrating the establishment of an array of counters within each node of FIG. 1 in accordance with the method and system of the present invention;

[0024] FIG. 4 is a high level flow chart depicting the process of the hardware reading one of the array of counters of FIG. 2 in accordance with the method and system of the present invention;

[0025] FIG. 5 is a high level flow chart illustrating the determination of a quantity of times a particular thread accesses shared-memory in a particular node in the distributed data processing system in accordance with the present invention; and

[0026] FIG. 6 is a high level flow chart depicting the accumulation of a total quantity of times a particular thread accesses each shared-memory in each of the nodes of the distributed data processing system in accordance with the present invention.

[0027] A preferred embodiment of the present invention and its advantages are better understood by referring to FIGS. 1-6 of the drawings, like numerals being used for like and corresponding parts of the accompanying drawings.

[0028] The method and system of the present invention may be utilized to determine the utilization of each of a plurality of nodes in a distributed shared-memory data processing system by each thread which is executed by the system. These node processing statistics are determined at run-time. The statistics show, for each migrateable thread, that particular thread's propensity to utilize the shared-memory from each of the nodes in the system. The statistics include the quantity of times a particular processor accessed a shared-memory in each of the nodes in the system. This data is maintained for each thread. Therefore, for each thread, a counter value is maintained and accumulated for each node which is equal to the quantity of times this thread accessed the shared-memory for that node.

[0029] These counter values are maintained utilizing an array of counters. An array of counters is established within each node in the system. Each counter array includes a plurality of counters. Each counter is associated with one of the processors in the node which includes this counter array, and is also associated with one of each of the nodes in the system. Therefore, each counter is associated with both a processor and a node. Each counter represents the quantity of times the processor associated with the counter accessed shared-memory memory in the node also associated with the counter. Each counter array can be read by the process described below so that the counter values may be utilized to determine which threads might be migrated to another processor in order to improve throughput and performance of the system.

[0030] Whenever a new thread is about to be dispatched by a processor, the row of counters in the array associated with the processor is read. The current value of the counters in that row are stored and are associated with the current thread. The process of reading the counters resets the counters associated to a value of zero. The new thread is then dispatched, and becomes the currently running thread. While each transaction associated with the thread is processed, the counters accumulate the number of times their associated nodes were accessed by this thread. Then, when a different thread is selected to be dispatched on this processor, the row of counters associated with this processor is again read. The values previously stored associated with this thread are then added to the counter values determined for this processor. The total values for each node are again stored and are associated with this thread. The new thread is then dispatched.

[0031] In this manner, an accurate count is maintained for each thread being processed which includes the number of times that thread accessed shared-memory in a particular node. This information could be utilized to determine that a thread needs to be moved to a different processor.

[0032] FIG. 1 depicts a block diagram of a distributed shared-memory data processing system 10 embodying the present invention. System 10 includes a plurality processing nodes 12, 14, and 16 which are coupled together utilizing an interconnect network 18.

[0033] Each node 12, 14, and 16 includes a NUMA interconnect which includes counter hardware. For example, node 12 includes interconnect 20. Node 14 includes interconnect 22. Node 16 includes interconnect 24. Preferably, each interconnect 20, 22, or 24 is implemented utilizing SYNFINITY™ NUMA and SYNFINITY™ NET, both available from Fujitsu System Technologies of Campbell, Calif.

[0034] Each interconnect 20, 22, and 24 has been modified by adding counter hardware 26, 28, and. 30, respectively. Counter hardware 26, 28, and 30 is described in more detail in FIG. 2. Counter hardware 26, 28, and 30 is utilized to determine the quantity of times the processor in the node which includes the particular counter hardware accesses shared-memory in each of the nodes.

[0035] Each node also includes a plurality of processors coupled together with shared-memory and the interconnect via a system bus. Node 12 includes two processors 36, 38 and shared-memory 30 coupled to interconnect 20 via system bus 21. Node 14 includes two processors 40, 42 and shared-memory 32 coupled to interconnect 22 via system bus 23. Node 16 includes two processors 44, 46 and shared-memory 34 coupled to interconnect 24 via system bus 25.

[0036] Each processor in a node is granted equal access to the shared-memory in that node. A local memory access occurs when a processor accesses the shared-memory in the node which includes that processor. The shared-memory in the node is called the local shared-memory.

[0037] Each processor in a node may also access the shared-memory which is located in a node other than the node which includes that processor. A remote memory access occurs when a processor accesses the shared-memory in a node other than the one which includes that processor.

[0038] For example, when either processor 36 or 38 accesses shared-memory 30, it is a local memory access. When either processor 36 or 38 accesses either shared-memory 32 or 34, it is a remote memory access.

[0039] The present invention describes a method and system for determining the quantity of times each processor in system 10 accesses each of the shared-memories in system 10. Because each executed thread is associated with a particular processor, the quantity of time a particular thread assesses each of the shared-memories in system 10 may be determined.

[0040] Each thread that is executed in system 10 is executed on a selected processor. A thread includes a plurality of transactions which are passed from one node to another utilizing interconnect network 18. Each transaction is associated with its thread and includes both a processor identifier which identifies the processor on which the thread has been dispatched, and a memory address.

[0041] FIG. 2 illustrates a high-level block diagram of counter hardware included within FIG. 1 in accordance with the method and system of the present invention. As each transaction is passed through interconnect network 18, it is monitored by interconnect 20, 22, and 24. FIG. 2 includes a generic interconnect 200 which may be utilized for each interconnect 20, 22, and 24. Interconnect 200 includes a system bus 204 which will be system bus 21, 23, or 25. Each transaction transmitted via system bus 204 includes a processor identifier and a memory address. The processor identifier is received directly within counter array 214. The processor identifier identifies the processor associated with each transaction. The processor identifier is utilized to select a particular row within counter array 214 which is associated with the received processor identifier.

[0042] A counter array in a particular node includes a row for each processor included within that node. For example, if interconnect 200 is implemented in node 12, one row of counter array will be associated with processor _0,0, or processor 36. The second row of counter array will be associated with processor _0,1, or processor 38. When a transaction is received which is associated with either processor _0,0or processor _0,1, the appropriate row of counter array 214 will be selected.

[0043] The address of the shared-memory which this transaction must access is also included within this transaction. The memory address is received within decoder 212. Decoder 212 decodes the memory address associated with each transaction to determine the node which includes the shared-memory in which the memory address is located. The node identifier is then utilized to select a particular column within counter array 214 associated with the decoded node identifier.

[0044] Therefore, in this manner, the processor identifier and memory address associated with each transaction are utilized to determine a particular counter within counter array 214 to increment. The particular counter is determined by selecting the counter associated with both the process identifier and memory address. Adder 220 is clocked by clock 224 and receives a value of “1” and the current value of the selected counter via line 228 to increment the selected counter via line 230.

[0045] For example, if interconnect 200 is implemented in node 12, the processor identifier will be received for each transaction. If a received transaction includes a processor identifier which identifies either processor 36 or 38, the row of counter array 214 associated with that processor will be selected. In addition, decoder 212 will receive each memory address associated with each transaction. The memory address will be decoded to determine the node which includes the shared-memory associated with that memory address. Decoder 212 will then select the column of counter array 214 associated with the determined node. In this mariner, when one of the counters of counter array 214 is associated with both the determined node identifier and either processor 36 or 38, that counter is selected and incremented.

[0046] For example, if processor 36 dispatches a thread which needs to access a memory location within shared-memory 34, each transaction associated with this thread will be associated with both processor 36 and an address in shared-memory 34. Counter hardware 26 will monitor transactions in interconnect 20. When the transaction described above is monitored, it is determined that it is associated with processor 36 and row 216 in counter array 214 will be selected. In addition, decoder 212 will determine that the memory address is associated with shared-memory 34 which is included within node 16. Decoder 212 will then select column 218. In this manner, only one counter, counter 220, is selected to be incremented.

[0047] FIG. 3 is a high level flow chart illustrating the establishment of an array of counters within each node of FIG. 1 in accordance with the method and system of the present invention. The process starts as depicted at block 300 and thereafter passes to block 302 which illustrates an establishment of an array of counters for each node within the system. The process then passes to block 304 which depicts an association of each row of an array with a different one of a plurality of processors included within this node. For each node, a counter array has been established. The counter array for a particular node includes a row associated with each processor which is included within that particular node. Block 306, then, illustrates an association of each column of the array with a different one of a plurality of nodes. The process then terminates as illustrated at block 308. In this manner, a plurality of counters are established where each counter is associated with both a processor and a node.

[0048] FIG. 4 is a high level flow chart depicting the process of the hardware reading one of the array of counters of FIG. 2 in accordance with the method and system of the present invention. The process starts as depicted at block 400 and thereafter passes to block 402 which illustrates a determination of whether or not contents of the counter array of a particular node are to be read. If a determination is made that contents of a counter array are not to be read, the process loops back to block 402. Referring again to block 402, if a determination is made that contents of an array are to be read, the process passes to block 404 which illustrates the reading of the contents of the selected row or rows of one of the counter arrays. Next, block 406 depicts the clearing, or resetting, of the row or rows whose contents were read. The counters are reset to a value of “0”. The process then terminates as depicted at block 408. The process of FIG. 4 is executed within each node of the system for the counter array of that node.

[0049] FIG. 5 is a high level flow chart illustrating the determination of a quantity of times a particular thread accesses shared-memory in a particular node in the distributed data processing system in accordance with the present invention. The process starts as depicted at block 500 and thereafter passes to block 502 which illustrates the getting of a new bus transaction. A plurality of bus transactions are processed within the data processing system. Each transaction may be associated with one of the processors in the system and with a memory address. The processor for a particular transaction may be located in a first node, while the memory address for that transaction is, located and associated with a second node. Next, block 504 depicts a determination of a memory address associated with this transaction. Block 506 illustrates a determination of which node has shared-memory which is associated with and includes this memory address.

[0050] Thereafter, block 508 depicts a determination of a processor associated with this transaction. The process then passes to block 510 which illustrates a determination of a counter which is associated with the determined processor and node. The counter is associated with one of a plurality of counters. The one of the plurality of counters is, therefore, associated with the determined processor and node. This counter counts the number of times this thread, which was dispatched to the determined processor associated with this counter, accessed the determined node. The processor then passes to block 512 which illustrates the incrementing of this counter. The process then passes back: to block 502.

[0051] FIG. 6 is a high level flow chart depicting the accumulation of a total quantity of times a particular thread accesses each shared-memory in each of the nodes of the distributed data processing system in accordance with the present invention. The process of FIG. 6 is executed for each processor within each node of the data processing system. The process starts as depicted at block 600 and thereafter passes to block 602 which illustrates a determination of whether or not a thread is to be dispatched on this processor. If a determination is made that a thread is to be dispatched on this processor, the process loops back to block 602. Referring again to block 602, if a determination is made that a thread is not to be dispatched on this processor, the process passes to block 604 which depicts the clearing of this processor's associated row of counters in the counter array within the node in which this processor is located.

[0052] Next, block 606 illustrates the dispatching of a thread on this processor. Thereafter, block 608 depicts the execution of the thread. The counters associated with this processor count the memory references this thread makes to each node. The process then passes to block 610 which illustrates a determination of whether or not a new thread is to be executed by this processor. If a determination is made that a new thread is not to be executed by this processor, the process loops back to block 610. If a determination is made that a new thread is to be executed, the process passes to block 612 which depicts the reading of this processor's associated row of counters. When a row of counters is read, the hardware process causes the counters to be reset to zero as described in FIG. 4. Next, block 614 illustrates the storage of the row counter information with this thread. Any counter values already stored for each counter with this thread are added to the new counter values just read from the counters illustrated in block 612. The total counter values for each counter of the associated row is stored with the thread. Block 616 depicts a selection of a new thread to be dispatched on this processor. The process then passes back to block 606.

[0053] While a preferred embodiment has been particularly shown and described, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the present invention.