Patent Publication Number: US-9405595-B2

Title: Synchronizing multiple threads efficiently

Description:
BACKGROUND 
     This application is a continuation of U.S. patent application Ser. No. 13/912,777, filed Jun. 7, 2013, which is a continuation of U.S. patent application Ser. No. 13/069,684, filed Mar. 23, 2011, now U.S. Pat. No. 8,473,963, issued Jun. 25, 2013, which is a continuation of U.S. patent application Ser. No. 11/026,207, filed Dec. 29, 2004, now U.S. Pat. No. 7,937,709, issued May 3, 2011, the content of which is hereby incorporated by reference. 
    
    
     BACKGROUND 
     The present invention relates to computer systems, and more particularly to such systems executing multiple threads. 
     Computer systems including multiprocessor (MP) and single processor systems may include a plurality of “threads,” each of which executes program instructions independently from other threads. Use of multiple processors allows various tasks or functions, and even multiple applications, to be handled more efficiently and with greater speed. Utilizing multiple threads or processors means that two or more processors or threads can share the same data stored within the system. However, care must be taken to maintain memory ordering when sharing data. 
     For data consistency purposes, if multiple threads or processors desire to read, modify, and write to a single memory location, the multiple agents should not be allowed to perform operations on the data simultaneously. Further complicating the use of multiple processors is that data is often is stored in a cache associated with a processor. Because such caches are typically localized to a specific processor, multiple caches in a multiprocessor computer system can contain different copies of a given data item. Any agent accessing this data should receive a valid or updated (i.e., latest) data value, and data being written from the cache back into memory must be the current data so that cache coherency is maintained. 
     Memory instruction processing acts in accordance with a target instruction set architecture (ISA) memory order model. For reference, Intel Corporation&#39;s two main ISAs: Intel® architecture (IA-32 or x86) and Intel&#39;s ITANIUM® processor family (IPF) have very different memory order models. In IA-32, load (i.e., read) and store (i.e., write) operations must be visible in program order, while in the IPF architecture, they do not in general. Further, while executing multiple threads in a chip multiprocessor (CMP) or other MP system, ordered memory instructions are used in synchronization and communication between different threads. 
     Multithreaded (MT) software uses different mechanisms to interact and coordinate between different threads. Two common forms of MP synchronization are barriers and semaphore spin-locks. A barrier mechanism helps a program synchronize different threads at predefined points in the program. Typically, each thread either increments or decrements a memory variable in an atomic fashion when it reaches such a point. Every thread then waits for the memory variable to reach a predetermined barrier level. Synchronization is achieved once all threads have completed the updates. When the barrier is reached, all threads can then proceed. 
     A semaphore spin-lock mechanism is used to guarantee mutual exclusion across multiple threads while accessing a shared memory variable or structure (i.e., a shared element). In order to provide a unique and consistent view of the shared element, it is guarded by a lock variable. Every thread needing access to the shared element must acquire the guarding lock (i.e., locking) via an atomic semaphore operation. When a lock is acquired, the remaining threads can only acquire the lock after it is released (i.e., unlocking) by the original requester. Only the thread that acquired the lock performs operations/updates on the shared element (software convention), thus mutual exclusion is ensured. Locking is performed by designating a particular value to represent a locked state, and a different value to represent an unlocked state. Each thread seeking to access the shared element acquires the lock by updating the lock variable atomically to the lock value (after possibly checking that the lock has not already been acquired). 
     Most ISA&#39;s provide specific semaphore instructions to achieve MP synchronization between multiple threads or processors. Among these, an atomic-add is a popular instruction for a barrier synchronization mechanism. However, known barrier synchronization methods and semaphore spin-locks cause inefficiencies. Barrier mechanisms typically require significant traffic, such as inter-processor cache traffic, as the lock variable moves to different cores of the multiprocessor. Similarly, spin-lock mechanisms require significant traffic between different processor cores. Still further, an atomic-add instruction requires that the shared variable be brought deep into processor cores to perform the add operation, again requiring significant traffic, as well as utilizing processor resources. Accordingly, a need exists for improved manners of synchronization between multiple threads. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a flow diagram of a method in accordance with one embodiment of the present invention. 
         FIG. 2  is a flow diagram of a synchronization method in accordance with one embodiment of the present invention. 
         FIG. 3  is a flow diagram of a locking method in accordance with one embodiment of the present invention. 
         FIG. 4  is a block diagram of a representative system in accordance with one embodiment of the invention. 
         FIG. 5  is a block diagram of a multiprocessor system in accordance with another embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     In various embodiments, a shared memory variable (“shared variable”) may be used to maintain synchronization between multiple threads. The shared variable may have multiple portions, with each portion being independently associated with one of the threads. In such manner, the shared variable may represent the synchronization status of each of the threads independently. 
     In some embodiments, the shared variable may be updated using a set mechanism, rather than an arithmetic operation, such as an increment or decrement operation. In such manner, the status of various threads may be updated without causing the shared variable to be cached or otherwise brought into a processor core. That is, set/reset operations may be performed in a remote or last level cache. Furthermore, these operations may be performed without expensive adders or other circuitry that would need to be located near an execution core. 
     In one embodiment, an instruction referred to herein as a fetchset instruction may be a low-cost instruction to improve MT synchronization, particularly in cases of low thread count. The fetchset instruction as executed by a given thread performs a read on a shared variable and sets or stores a predetermined value into a portion of the shared variable corresponding to the thread. For example, in an embodiment in which eight or fewer threads are executing, the shared variable may be eight bytes. Each byte of the shared variable may correspond to one of the threads. In one embodiment, the predetermined value to be set may be all “ones”. For example, fetchset1 stores FF hex  (i.e., 11111111) at the specified memory address of a given portion. Such an instruction may be low cost, since setting (i.e., overwriting) memory state is less expensive than performing read-add-update operations. 
     While discussed above as devoting a byte per thread, in other embodiments a different arrangement may exist. For example in one embodiment, a single bit may be used to represent a thread. Further, while described above as setting the predetermined value to ones, in other embodiments any other desired value may be used. 
     Referring now to  FIG. 1 , shown is a flow diagram of a method in accordance with one embodiment of the present invention. More specifically,  FIG. 1  shows a method  10  for performing a fetchset instruction in accordance with one embodiment. Such a fetchset instruction may be used to access a shared memory variable and store a value in a portion of the variable corresponding to a given thread. As shown in  FIG. 1 , a fetchset operation may be initiated (oval  20 ). Then a first memory variable may be read (block  30 ). The first memory variable may correspond to a shared variable used to indicate synchronization status for multiple threads at a barrier. A thread may read the variable to determine whether all portions of the variable equal a given value, or to determine whether a particular portion of the variable is in a locked state, as will be discussed further below. 
     Still referring to  FIG. 1 , next a portion of the first memory variable corresponding to a current thread may be set with the predetermined value (block  40 ). For example, a first portion of the memory variable (e.g., a first byte) may correspond to a first thread of a program. Upon executing a fetchset instruction, the first thread may set that portion. In one embodiment, the portion may be set with all ones. Method  10  then ends (oval  50 ). 
     While not shown in  FIG. 1 , it is to be understood that upon arriving at the barrier, each thread performs a fetchset instruction on the variable, and the predetermined value is stored at the specified slot within the variable. Synchronization is established when all bytes of the memory variable are set. 
     Referring now to  FIG. 2 , shown is a flow diagram of a synchronization method in accordance with one embodiment of the present invention. As shown in  FIG. 2 , method  100  may be used to synchronize multiple threads of a program. Method  100  begins (oval  105 ) by executing instructions of a given thread (block  110 ). Next it may be determined whether the thread reaches a barrier (diamond  120 ). For example, a barrier may correspond to a predetermined portion of the program at which synchronization is desired. If no such barrier is reached, the thread continues execution of instructions by looping back to block  110 . 
     Alternately, if the thread does reach a barrier, control passes to block  130  where a fetchset operation is performed on a first memory variable. The first memory variable may be stored in a cache accessible by the multiple threads. Such a fetchset operation may include the steps described above with respect to  FIG. 1 . That is, the fetchset operation may cause the thread to read the contents of the first memory variable and set a value to a portion of the first memory variable corresponding to the current thread. Next, it may be determined whether the current thread is the last to reach the barrier (diamond  140 ). For example, in one embodiment the thread may read the variable contents and determine whether all portions equal a set value. However, in some embodiments the set value may be present in all portions of the first variable except that portion corresponding to the current thread. If the current thread is not the last to reach the barrier, control passes to block  150 , where the thread spins on a second memory variable until it is updated. The second memory variable may also be stored in the cache. 
     If the current thread is the last to reach the barrier, the second memory variable may be updated (block  160 ). For example, the second memory variable may have its contents updated from zero to one. Control then passes to block  170 , where the synchronization is completed, as all threads of the program have reached the barrier, and the contents of the first and second memory variables are set. Accordingly, method  100  concludes (oval  180 ). 
     Because of the low cost of implementing a fetchset instruction and as it may be defined on byte granularity, setting of the variable may be exported to a shared last level cache (LLC) of a CMP or other processor. In such manner, a cache line including the variable can be prevented from being copied into a core (near the execution pipeline) on every barrier update. Thus, inter-processor cache traffic in moving the lock variable across different cores may be avoided. Software may be used to ensure that the cache line remains pinned in the LLC by avoiding false sharing on the cache block and avoiding any other reads or updates to the memory variable (that would source a copy of the cache line into one of the core caches). 
     Other embodiments may be used to provide fine-grain locking using a single variable. For example, a 16-byte fetchset instruction may represent 16 fine-grain locks. In such an embodiment, a data structure containing 16 data elements can be locked using one shared variable. Each element of the data structure is allocated a byte within the lock variable. Then, only that portion of the structure may be locked using a fetchset instruction. In such manner, non-blocking access to the same structure is permitted, as long as the particular element to be accessed is not locked. If the original value returned by a fetchset operation to a first thread is clear in the particular byte location, then the first thread may successfully lock that element. If however the byte position was already set, the entry was previously locked by a different thread. Accordingly, the locking operation would need to be retried later by the first thread. 
     Referring now to  FIG. 3 , shown is a flow diagram of a locking method in accordance with one embodiment of the present invention. As shown in  FIG. 3 , method  200  may be used to lock a data structure using a plurality of fine-grain locks. Method  200  begins (oval  205 ) by an instruction that seeks access to a data structure that is subject to a lock (block  210 ). A fetchset operation, which may be similar to that shown in  FIG. 1 , may be performed on a shared variable associated with the data structure (block  220 ). However, for the embodiment of  FIG. 3 , block  40  of  FIG. 1  may instead be used to set a predetermined value to a portion of the memory variable corresponding to a given data element of the data structure. 
     After reading the shared variable, it may be determined whether the portion of the variable corresponding to the data element is locked (diamond  230 ). For example, in one embodiment it may be determined whether that portion is set (i.e., has a value of ones). If the portion indicates that the data element is locked, the thread is not allowed to access the data element, and may accordingly retry the fetchset operation later (block  240 ). In such manner, if a different thread has concluded an operation on the data element, the next time the thread accesses the shared variable, the specific portion may be in a reset state. 
     If instead at diamond  230  it is determined that the portion of the shared variable is not locked, that portion may be locked (block  250 ). Then the current thread may update the data element that corresponds to that portion of the data structure (block  260 ). For example, the thread may update the data element and write the updated value back to its memory location. Then, the thread may unlock that portion of the shared variable (block  270 ) so that other threads may obtain a lock on the given data element. Accordingly, method  200  ends (oval  280 ). 
     In various embodiments, because a fetchset or other such instruction supports a predefined update payload (i.e., the predefined value), the payload may be synthesized at the particular cache executing the instruction. As a result, the update to the shared variable is protected against payload corruption through soft errors as the instruction flows through the machine. 
     Furthermore, because the synchronization status of each thread is isolated, it provides a robust barrier synchronization mechanism. Any thread that fails to report to the barrier does not have its byte location set in the shared variable. In such manner, any errant thread resulting in a software failure (either due to software or hardware error) may be isolated and identified based on the status of the shared variable. Software may then selectively perform recovery on the particular thread. 
     A 16 byte variant of the fetchset instruction (i.e., a fetchset.double) may be defined to operate on a 16 byte granularity, and thus provide synchronization among  16  threads. 
     In some embodiments, a hierarchical barrier mechanism may be used to establish synchronization in software with large thread counts. In such embodiments, a fetchset-based mechanism may serve as an effective barrier mechanism at a lower level of the hierarchy to establish synchronization within a CMP processor or within a local cluster of a clustered system. 
     Referring now to Table 1 below, shown is an instruction syntax for a fetchset instruction in accordance with an embodiment of the present invention. As shown in Table 1, the instruction syntax is within the scope of the IPF ISA. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
             
            
               
                   
                   
                 fetchset.dbl.pl.sz.sem r1, [ar.csd] = [r3] 
               
            
           
           
               
               
               
               
            
               
                   
                   
                  dbl: 
                 s — 8byte read 
               
               
                   
                   
                   
                 d — 16byte read. Second 8 byte target ar.csd. 
               
               
                   
                   
                  pl: 
                 0 — clear (‘0 payload) 
               
               
                   
                   
                   
                 1 — set (‘1111 .... payload) 
               
               
                   
                   
                  sz: 
                 0 — 1 byte 
               
               
                   
                   
                   
                 1 — 2 byte 
               
               
                   
                   
                   
                 2 — 4 byte 
               
               
                   
                   
                   
                 3 — 8 byte 
               
               
                   
                   
                   
                 4 — 16 byte (only valid with dbl set to d). 
               
               
                   
                   
                  sem: 
                 acq — acquire 
               
               
                   
                   
                   
                 rel — release. 
               
               
                   
                   
               
               
                   
                 Note: 
               
               
                   
                 ar.csd only applies when dbl is set to d) 
               
            
           
         
       
     
     As shown in Table 1, the instruction syntax indicates: whether an 8 byte or 16 byte read operation is to be performed; the payload to be written into the specified location; the size; and the type of semaphore, for example, whether it is an acquire or release operation. 
     Referring now to Table 2 below, shown is a pseudocode example of establishing a barrier synchronization using a fetchset instruction in accordance with an embodiment of the present invention. Again, this pseudocode is in the IPF context, although the scope of the present invention is not so limited. 
     
       
         
           
               
             
               
                 TABLE 2 
               
               
                   
               
             
            
               
                 //r20 contains the barrier address. 
               
               
                 //r40 contains the shared memory variable. 
               
            
           
           
               
               
            
               
                   
                 stf.spill [r20] = f0 
               
               
                   
                 stf.spill [r40] = f0 
               
               
                   
                 //note: these lines write a 16-byte zero value into the target registers 
               
               
                   
                 mov r30 = ‘hFFFFFFFFFFFFFFFF;; 
               
               
                   
                 mov ar.csd = r30;; 
               
               
                   
                 //note: this line moves the second operand for the fetchset operation into the 
               
            
           
           
               
            
               
                    target register 
               
               
                 // Start independent thread-level execution. 
               
               
                    . 
               
               
                    . 
               
               
                    . 
               
               
                 // Complete thread execution 
               
            
           
           
               
               
            
               
                   
                 fetchset.d.1.rel r10, ar.csd = [r20], 0;; 
               
               
                   
                 cmp.eq p1, p2 = r10, r30 
               
               
                   
                 //note: if the register values are equal, p1 is set to one and p2 is set to zero, 
               
            
           
           
               
            
               
                    otherwise vice versa 
               
            
           
           
               
               
            
               
                   
                 mov r35 = ar.csd;; 
               
               
                   
                 cmp.eq.and p1, p2 = r10, r35;; 
               
               
                   
                 p1: stf.spill [r40] = f1;; 
               
               
                   
                 p1: br sync_cmp 
               
               
                   
                 //note: if p1 equals one, operation branches to sync_cmp (i.e., synchronization 
               
            
           
           
               
            
               
                    is complete) 
               
            
           
           
               
               
            
               
                 spin_loop:  
                 ldff19 = [r40] 
               
               
                   
                 fcmp.eq p1, p2 = f19, f1; 
               
               
                   
                 //note: if target values are equal, p1 equals zero and p2 equals one and  
               
            
           
           
               
            
               
                    operation branches to sync_cmp (i.e., synchronization is complete), otherwise vice  
               
               
                    versa and spin_loop is repeated 
               
            
           
           
               
               
            
               
                   
                 p2: br spin_loop 
               
               
                 sync_cmp:  
                 //synchronization completed. 
               
               
                   
               
            
           
         
       
     
     Generally, the code of Table 2 performs the following activities. First, the code initializes the location in the cache where the shared variable is to be stored and further initializes the shared variable to zero. Then, independent threads are executed. Upon completion of a thread, a fetchset instruction is performed by each thread to read the value of the shared variable and compare it to a predetermined value. If the shared variable equals that value, it means that the current thread is the last thread, and synchronization is completed. If not, the current thread updates its portion of the shared variable, and enters a spin loop until the last thread completes its execution to thus complete synchronization. 
     Referring now to  FIG. 4 , shown is a block diagram of a representative computer system  300  in accordance with one embodiment of the invention. As shown in  FIG. 4 , computer system  300  includes a processor  310  which may be a chip multiprocessor (CMP). As shown in  FIG. 4 , processor  310  may include a first core  310   a  (core A) and a second core  310   b  (core B). Processor  310  may be coupled over a memory system interconnect  320  to a cache coherent shared memory subsystem (“coherent memory”)  330  in one embodiment. In one embodiment, coherent memory  330  may include a dynamic random access memory (DRAM) and may further include coherent memory controller logic to share coherent memory  330  between multiple processors. 
     It is to be understood that in other embodiments additional processors may be coupled to coherent memory  330 . Furthermore in certain embodiments, coherent memory  330  may be implemented in parts and spread out such that a subset of processors within system  300  communicate to some portions of coherent memory  330  and other processors communicate to other portions of coherent memory  330 . 
     As shown in  FIG. 4 , core  310   a  may include a cache  314   a  and execution units  316   a  in accordance with an embodiment of the present invention. Cache  314   a  may be a low level cache (e.g., a level one (L1)) associated with core  310   a . Of course, additional components may reside in core  310   a , such as additional caches. More so, a last level cache (LLC)  305 , which may be a level two (L2) cache, may be coupled to both cores  310   a  and  310   b . LLC  305  may store a lock variable in accordance with an embodiment of the present invention. Furthermore, the value to be set into portions of the lock variable may be synthesized in LLC  305 . As further shown in  FIG. 4 , similar processor components may be present in core  310   b , which may be a second processor core of a multiprocessor system such as a chip multiprocessor (CMP). 
     Coherent memory  330  may also be coupled (via a hub link) to an input/output (I/O) hub  335  that is coupled to an I/O expansion bus  355  and a peripheral bus  350 . In various embodiments, I/O expansion bus  355  may be coupled to various I/O devices such as a keyboard and mouse, among other devices. Peripheral bus  350  may be coupled to various components such as peripheral device  370  which may be a memory device such as a flash memory, add-in card, or the like. Although the description makes reference to specific components of system  300 , numerous modifications of the illustrated embodiments may be possible. 
     In some embodiments, a multiprocessor system may be a point-to-point bus system, such as in a common system interface (CSI) system. Referring now to  FIG. 5 , shown is a block diagram of a multiprocessor system in accordance with another embodiment of the present invention. As shown in  FIG. 5 , the multiprocessor system is a point-to-point bus system, and includes a first processor  470  and a second processor  480  coupled via a point-to-point interconnect  450 . First processor  470  may include multiple processor cores  474   a  and  474   b  (although more such cores may be present), a memory controller hub (MCH)  472 , a cache memory  473 , and point-to-point (P-P) interfaces  476  and  478 . Similarly, second processor  480  includes the same components, namely processor cores  484   a  and  484   b , a MCH  482 , a cache memory  483 , and P-P interfaces  486  and  488 . Caches  473  and  483  may store lock variables in accordance with an embodiment of the present invention. Furthermore, values to be set into portions of the lock variables may be synthesized in caches  473  and  483 . 
     As shown in  FIG. 5 , MCH&#39;s  472  and  482  couple the processors to respective memories, namely a memory  432  and a memory  444 , which may be portions of main memory locally attached to the respective processors. 
     First processor  470  and second processor  480  may be coupled to a chipset  490  via P-P interfaces  452  and  454 , respectively. As shown in  FIG. 5 , chipset  490  includes P-P interfaces  494  and  498 . Furthermore, chipset  490  includes an interface  492  to couple chipset  490  with a high performance graphics engine  438 . In one embodiment, an Advanced Graphics Port (AGP) bus  439  may be used to couple graphics engine  438  to chipset  490 . AGP bus  439  may conform to the  Accelerated Graphics Port Interface Specification, Revision  2.0, published May 4, 1998, by Intel Corporation, Santa Clara, Calif. Alternately, a point-to-point interconnect  439  may couple these components. 
     In turn, chipset  490  may be coupled to a first bus  416  via an interface  496 . In one embodiment, first bus  416  may be a Peripheral Component Interconnect (PCI) bus, as defined by the  PCI Local Bus Specification, Production Version, Revision  2.1, dated June 1995 or a bus such as the PCI Express bus or another third generation I/O interconnect bus, although the scope of the present invention is not so limited. 
     As shown in  FIG. 5 , various input/output (I/O) devices  414  may be coupled to first bus  416 , along with a bus bridge  418  which couples first bus  416  to a second bus  420 . In one embodiment, second bus  420  may be a low pin count (LPC) bus. Various devices may be coupled to second bus  420  including, for example, a keyboard/mouse  422 , communication devices  426  and a data storage unit  428  which may include, in one embodiment code  430 . Further, an audio I/O  424  may be coupled to second bus  420 . 
     Embodiments may be implemented in a computer program that may be stored on a storage medium having instructions to program a computer system to perform the embodiments. The storage medium may include, but is not limited to, any type of disk including floppy disks, optical disks, compact disk read-only memories (CD-ROMs), compact disk rewritables (CD-RWs), and magneto-optical disks, semiconductor devices such as read-only memories (ROMs), random access memories (RAMs) such as dynamic and static RAMs, erasable programmable read-only memories (EPROMs), electrically erasable programmable read-only memories (EEPROMs), flash memories, magnetic or optical cards, or any type of media suitable for storing electronic instructions. Other embodiments may be implemented as software modules executed by a programmable control device. 
     While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.