Abstract:
A system and method for process synchronization in a multi-core computer system. A separate non-caching memory enables a method to synchronize processes executing on multiple processor cores. Since only a very small amount (a few number of bytes), is needed for the synchronization, it is possible to extend the method for inter-processor core message passing by allocating dedicated address space of the on-chip memory for each processor with exclusive write access. Each of the multiple processor cores maintains a dedicated cache while maintaining coherency with the non-cache shared memory.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to efficient utilization of a multi-core processing system and more specifically to an apparatus and method directed to process synchronization of embedded applications in multi-core processing systems while maintaining memory coherency. 
       BACKGROUND 
       [0002]    The shift toward multi-core processor chips poses challenges to synchronizing the operations running on each core in order to fully utilize the enhanced performance opportunities presented by multi-core processors (e.g., running different applications on different processor cores at the same time and running different operations of the same application on different processor cores). However, present methods of synchronizing operations such as lock/semaphore require atomic instructions (e.g., test-and-set, swap, etc.) or interrupt disabling are difficult to implement and can lead to race conditions, deadlocks and inefficient use of the processors. Accordingly, there exists a need in the art to mitigate the deficiencies and limitations described hereinabove. 
       SUMMARY 
       [0003]    A first aspect of the present invention is a system for process synchronization in a multi-core computer system, comprising: a primary processor core to control scheduling, completion and synchronization of a plurality of processing threads for the SOC, the primary processor core having a dedicated memory region to facilitate control of processes; a plurality of secondary processor cores each coupled to the primary processor core via address and control line bus architecture, the plurality of secondary processor cores responsive to command inputs from the primary processor core to execute instructions and each having dedicated memory to facilitate control of processes; a first memory wherein the primary processor core and each secondary processors core of the plurality of secondary processor cores have read access to all addresses of said first memory, and wherein write access to the first memory by the primary processor core and each secondary processor core of the plurality of secondary processor cores is restricted to respective address regions; and a switch matrix enabling intra-core communication between the primary processor core and any secondary processor core of the plurality of secondary processor cores and between any pair of secondary processor cores of the plurality of secondary processor cores, according to a pre-defined transmission protocol. 
         [0004]    A second aspect of the present invention is a method for process synchronization in a multi-core computer system, comprising: providing a first memory having a dedicated domain for each processor core of a plurality of processor cores, each of the dedicated domains readable by any of the plurality of processor cores; providing a second memory having a dedicated domain for each processor core of a plurality of processor cores; writing a value to an address allocated to a first processor core of the plurality of processor cores in the first memory such that a busy or idle state of the first core may be read by each of the remaining plurality of processor cores; maintaining a value matrix in the second memory for each of the plurality of processor cores enabling a corresponding processor core to monitor the busy and idle states of each of the other processor cores; applying an exclusive ‘OR’ to the value matrix entry for each one of the plurality of processor cores when a busy or idle state of the corresponding one of the plurality of processors changes; and writing the result of the exclusive ‘OR’ operation to a corresponding domain of the first memory to update the status of the corresponding one of the plurality of processor cores. 
         [0005]    These and other aspects of the invention are described below. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]    The features of the invention are set forth in the appended claims. The invention itself, however, will be best understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: 
           [0007]      FIG. 1  illustrates a block diagram an exemplary computer system architecture having a multi-core microprocessor according to embodiments of the present invention; 
           [0008]      FIG. 2  illustrates the links between processor cores of the multi-core microprocessor system and on-chip memory to provide addressable space for writing, storing and reading set and reset data for each processor core of the multi-core microprocessor architecture according to embodiments of the present invention; 
           [0009]      FIG. 3A  illustrates the writing of a synchronization signal initiated by a first processor core and subsequent reading of the synchronization signal by a second processor core of the multi-core microprocessor architecture according to embodiments of the present invention; 
           [0010]      FIG. 3B  illustrates the writing of a synchronization signal initiated by second processor core and subsequent reading of the synchronization signal by the first processor core of  FIG. 3A ; 
           [0011]      FIG. 4A  is a flowchart illustrating the steps of writing from dedicated memory to on-chip memory according to embodiments of the present invention; 
           [0012]      FIG. 4B  is a flowchart illustrating the steps of reading from on-chip memory to dedicated memory according to embodiments of the present invention; 
           [0013]      FIG. 5  illustrates a block diagram an exemplary computer system architecture having a multi-core microprocessor distributed on multiple micro-processor chips according to embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0014]    The present invention provides a first memory having dedicated write address space for each processor core of a multi-core processor and common read access to all address space by all processor cores. The present invention also provides a multiplicity of processor dedicated second memories that are linked to the first memory. The first and second memories provide a mechanism for indicating synchronization information such as processor status (e.g., busy, idle, error), an event occurrence or an instruction is pending and between which of the multiple processor cores the synchronization information is to be communicated. 
         [0015]      FIG. 1  illustrates a block diagram an exemplary computer system architecture having a multi-core microprocessor according to embodiments of the present invention. In  FIG. 1 , a computer system  100  includes a system memory  105  and a system-on-chip (SOC)  110  connected to a system bus  115 . System bus  115  comprises an address and control line architecture. SOC  110  includes processor core  120 A (i.e., core  0 ), processor core  120 B (i.e., core  01 ), processor core  120 C (i.e., core  2 ), and processor core  120 D (i.e., core  3 ) and an on-chip-memory (OCM)  125 . OCM  125  is a shared, non-cache first memory. A shared memory is a memory all processor cores  120 A through  120 D have read access to, though, as described infra with respect to  FIG. 2 , there are limitations on the write access for each processor core. Each processor core  120 A through  120 D is provided with a respective dedicated memory  130 A through  130 D, either in the system memory or by means of a local memory. A dedicated memory is a memory to which read/write access is limited to a specific core processor. Dedicated memories provide address space to facilitate control of single or multi-threaded processes. Dedicated memories  130 A through  130 D further include respective dedicated write domains  135 A through  135 D. Write domains  135 A through  135 D are second memories dedicated to communication with OCM  125  as illustrated in  FIGS. 3A and 3B  and described infra. 
         [0016]    In one example, processor core  120 A is a primary processor core and processor cores  120 B,  120 C and  120 D are secondary processor cores. A primary processor core controls scheduling, completion and synchronization of processing threads on all processor cores to ensure each process has reached a required state before further processing can occur. Secondary processor cores are responsive to command outputs from the primary processor core to execute instructions. Secondary processor cores can also synchronize with each other. Synchronization can be implemented as synchronization points where all secondary processor cores wait for a signal from the primary processor core. On reaching the synchronization point the primary processor core sets the signal to all secondary processor cores and waits for acknowledgement from all the secondary processor cores. On receiving the acknowledgement from the secondary processor cores, the primary processor core instructs the secondary processor core to proceed (e.g., to the next synchronization point). 
         [0017]    In one example processor cores  120 A,  120 B,  120 C and  120 D are multi-threaded processors. A multithreading processor runs more than one task&#39;s instruction stream (thread) at a time. To do so, the processor core has more than one program counter and more than one set of programmable registers. The embodiments of the present invention are applicable to single thread processors and can be extended to multi-threaded processors by treating each thread as a core. 
         [0018]    It should be understood that dedicated memories  130 A,  130 B  130 C and  130 D and OCM memory need not be physically different memory cores but in one example, partitions of the same memory core. In another example, dedicated memories  130 A,  130 B,  130 C and  130 D are partitions of a first memory core and OCM is a second memory core. 
         [0019]      FIG. 2  illustrates the links between processor cores of the multi-core microprocessor system and on-chip memory to provide addressable space for writing, storing and reading set and reset data for each processor core of the multi-core microprocessor architecture according to embodiments of the present invention. In  FIG. 2 , SOC  110  includes cores  120 A through  120 D and OCM  125 . OCM  125  is an m by m array (i.e., a square array of order m) of n-byte address spaces where m is the number of processor cores in the system (in the example of  FIG. 2 , m=4) n is an integer equal to or greater than 1. Write domains  135 A,  135 B,  135 C and  135 D are also m by m arrays (i.e., square arrays of order m) of n-byte address spaces. 
         [0020]    Each processor core  120 A through  120 D can write to only one dedicated (and different row) of OCM  125  while all processor cores  120 A through  120 D can read all rows of OCM  125 . Alternatively, throughout the description of the invention “column” may substituted for all instances of “row” and “row” substituted for all instances of “column.” The lines labeled R and W are implemented as a switch matrix enabling processor core to processor core communication. As described infra, the source of information written to OCM  125  is from write domains  135 A through  135 D (see  FIG. 1 ). Each row of OCM  125  may be considered a domain allocated to a specific processor core. 
         [0021]      FIG. 3A  illustrates the writing of a synchronization signal initiated by a first processor core and subsequent reading of the synchronization signal by a second processor core of the multi-core microprocessor architecture according to embodiments of the present invention. In the example of  FIG. 3A , processor core  1  (i.e., processor core  130 B of  FIG. 2 ) is synchronizing with processor core  2  (i.e., processor core  130 C of  FIG. 2 ) using write domains  135 B and  135 C and OCM  125 . As described supra, OCM  125  is an m by m array of n-byte address space where m is the number of processor core of the system (in the example of  FIG. 2 , m=4) n is an integer equal to or greater than 1. However, write domains are also m by m arrays of n-byte memory addresses. The organization of write domains  135 B and  135 C (also write domains  135 A and  135 D, see  FIG. 2 ) and OCM  125  are identical. Each array element of write domains  135 B and  135 C (also write domains  135 A and  135 D, see  FIG. 2 ) and OCM  125  represents a unique two processor core combination. There is one array element for each processor core combination. Reading and writing of write domains and OCM is through the processor cores. 
         [0022]    In the example of  FIG. 3A , rows logically indicate the sending processor core and columns logically indicate the receiving processor core. A row/column intersection defines the send/receive processor core pair as well as which is the sender and which is the receiver. In  FIG. 3A  core  1  is synchronizing (sending) to core  2 . The processor core combination is therefore (1,2) and that array location in all three of write domain  135 B, OCM  125  and write domain  135 C is used. The data (a synchronization signal) in location (1,2) of write domain  135 B is written to location (1,2) of OCM  125  by the processor core to which write domain  135 B is dedicated (i.e., processor core  130 B of  FIG. 2 ). It will be remembered that each processor core can only write to one row of OCM  125 . In  FIG. 3A  this is row 1 (addresses 1,0; 1,1; 1,2; and 1,3). The data in location (1,2) of OCM  125  is read from location (1,2) of OCM  125  and written to location (1,2) of write domain  135 C by the processor core that write domain  135 C is dedicated to (i.e., processor core  130 C of  FIG. 2 ). It will be remembered that each processor core can read any row of OCM  125 . Processor core  130 C “knows” the synchronization signal was sent by processor core  130 B based on the row and “knows” the synchronization signal is intended for it based on the column. Rows in write domains  135 B and  136 C may be called value vectors because they represent the current value of the state of the processor core and rows in OCM  125  may be called signal vectors because they are used to signal a toggle of the value of the state of the processor core. 
         [0023]      FIG. 3B  illustrates the writing of a synchronization signal initiated by second processor core and subsequent reading of the synchronization signal by the first processor core of  FIG. 3A . In  FIG. 3B  core  2  is synchronizing (sending) to core  1 . The processor core combination is therefore (2,1) and that array location in all three of write domain  135 B, OCM  125  and write domain  135 C is used. The data (a synchronization signal) in location (2,1) of write domain  135 C is written to location (2,1) of OCM  125  by the processor core  130 C (of  FIG. 2 ). It will be remembered that each processor core can only write to one row of OCM  125 . In  FIG. 3B  this is row 2 (addresses 2,0; 2,1; 2,2; and 2,3). The data in location (2,1) of OCM  125  is read from location (2,1) of OCM  125  and written to location (2,1) of write domain  135 B by processor core  130 C (of  FIG. 2 ). Processor core  130 B “knows” the synchronization signal was sent by processor core  130 C based on the row and “knows” the synchronization signal is intended for it based on the column. 
         [0024]    In the more general case of m processor cores having respective m dedicated write domains (where i=0 to m −1  and j=0 to m −1 ), when processor core i wants to send a synchronization signal to processor core j it uses the (i,j) th  location of the i th  write domain and the (i,j) th  location of the OCM to do so. After sending the synchronization signal to the OCM, processor core i changes the value (toggles between 0 and 1 if n=1) in the (i,j) th  location of write domain (i). Similarly, processor core j waits for the (i,j) th  location of the OCM to change from the value currently in the (i,j) th  location of the OCM to a different value then currently in the (i,j) th  location of write domain (j). When the value changes, this new value is written to the (i,j) th  location of write domain (j) overwriting the old value. 
         [0025]    When n=1, the synchronization is a two state machine and the synchronization signal is reduced to changing the state of the (i,j) th  locations. A powerful use of the present invention in a two state mode (i.e., busy and idle) is the ability of the primary core to know when a secondary processor is idle and then issue instructions for the idle secondary processor to initiate another process. In such a two state system, the primary processor core can direct the timing of the execution of processes on the secondary processor cores by waiting until all secondary processor cores are idle, to ensure processes that must be completed before other processes can start have been completed. In other words, to automatically and quickly detect that a process-synchronization point has been obtained. The secondary processor cores can then be assigned further processes by instructions sent by the primary core processors by normal command routes. When n is greater than 2, then the synchronization is a 2 11  state machine. Toggling may be accomplished using an exclusive “OR.” The system is initialized by writing the same value to all (i,j) th  locations of all write domains of all dedicated memories and to all (i,j) th  locations of the OCM. 
         [0026]      FIG. 4A  is a flowchart illustrating the steps of writing from dedicated dedicated memory to on-chip memory according to embodiments of the present invention. In step  150 , the value from location (i,j) of dedicated (i) write domain is retrieved. In step  155 , the retrieved value is written to the (i,j) th  location of the OCM. In step  160 , the value in the (i,j) th  location of dedicated (i) write domain is toggled. Steps  150 ,  155  and  160  are part of a larger loop where each core (i) is cycling through all the (j, i) combinations. 
         [0027]      FIG. 4B  is a flowchart illustrating the steps of reading from on-chip memory to dedicated memory according to embodiments of the present invention. In step  165 , core (j) reads OCM location (i,j). In step  170  the value in the (i,j) th  location of the OCM is compared to the value in the (i,j) th  location of cache (j) write domain. If the two values are the same, then the method proceeds to step  175 , otherwise the method loops to step  165 . When the values are the same, there is no “message” from the i th  processor core for the i th  processor core. The loop is back to step  165  so core (j) can sample other (i,j) th  locations (i.e., synchronization signals from other processor cores. In other words, steps  165 ,  170  and  175  are part of a larger loop where each core (j) is cycling through all the (j, i) combinations. In step  175 , the value in the (i,j) th  location of the dedicated (j) write domain is toggled. 
         [0028]    In a general single processor core system, maintaining coherency is the responsibility of the operating system, and the application developer need not worry about that. However, in a multi-processor core system, the developer has to take care of these issues. These issues were studied using a system simulator model for an eight core system-on-chip with 1 MB on-chip non-caching shared memory. Open source GNU (GNU&#39;s NOT UNIX) tools for developing embedded PowerPC applications were used for software development. The system was programmed in programming language ‘C’, embedding assembler code for cache related operations. 
         [0029]    The model included: (1) Processors are numbered from 0 to (m−1), where m is the number of processors. (2) Processor  0  is the primary processor and the other processors are secondary processors. The master processor performs I/O operations. (3) Programs which are expected to be executed by various processors are loaded in specific ranges of memory as configured in the scripts for the memory loader. (4) Since programs are loaded in specific ranges the processor identification number was obtained by a small routine GetMyid( ). (5) The synchronization signal scheme described in relation to  FIGS. 3A ,  3 B,  4 A and  4 B. (6) When a number of core processors write the same range of memory the range of memory is declared as write through and invalidating its cache after finishing memory writes, forcing load caching before using the value. 
         [0030]    Various routines used are listed and include: 
         [0031]    int GetMyid(void)—used by processors to get their process identification (ID) number; 
         [0032]    void setsignal(int id)—the processor sets the signal using its processor ID number; 
         [0033]    void waitsignal(int id)—a processor waits for a signal from a processor with its processor ID number; 
         [0034]    void sync(void)—synchronization mechanism, while processor ID  0  sets the signal, all other processors wait for a signal from processor ID  0 . On receiving the signal from processor ID  0 , a processor other than processor ID  0  sets a signal to processor ID  0  and processor ID  0  waits for signal from all others processors; 
         [0035]    void signaltoproc(int toid)—used by a processor to set a signal for a particular processor; 
         [0036]    void waitforproc(int fromid)—used by a processor to wait for a signal from a particular processor; 
         [0037]    void checksignal(int fromid)—used by a processor to check whether a signal is ready from processor fromid, but value location is not modified for which a waitforproc(fromid) is needed; 
         [0038]    void clearsignals(void)—used by the primary processor to clear the signal locations, before ending the execution. The routine can also be used by a serial program to clear the signal memory before running the real parallel application; 
         [0039]    void store Cache(unsigned long addr)—store the cache line which holds the memory address addr; 
         [0040]    void invalidate Cache(unsigned long addr)—invalidate the cache line which holds the memory address addr; and 
         [0041]    void flushCache(unsigned long addr)—flush the cache line which holds the memory address addr. 
         [0042]    On-chip memory was portioned into several sections. The signal vector and matrix was stored in a non-cached on-chip shared memory section starting at address 0xc0000000. (This is memory  125  of  FIG. 2 ). Input matrices were stored in a shared memory at 0x00b00000 and 0x00c00000 respectively, which was configured as cached. An output matrix was allocated a shared memory at address 0x00d00000, which was configured as cached and write through. Programs for processors  0  to  7  were stored in 0x00100000, 0x00200000, 0x0030000, 0x00400000, 0x00500000, 0x00600000, 0x00700000 and 0x00800000. An address mask 0x00f0000 was used by processors to get its processor ID number. Signal values 0xfe and 0xff were used as toggle values for the synchronization signals. The same source code was used to program all processors and each program identified its role from their processor ID numbers. 
         [0043]    The programming sequence was: (1) Each processor received its processor ID number. (2) Processor ID  0  initialized the input section stored in OCM and in a separate loop the memory locations were stored to cache memory, so that the OCM was synchronized with cache. Storing was done in a separate loop to avoid storing of already stored cache lines. Then processor ID  0  synchronization signals for all other processors. No explicit cache operations are needed for other processors since the other processors had not yet used any values from OCM (3) All processors computed their share of computation by avoiding frequent reference to a write-through memory. Hence summing was done on a local variable and finally the results were stored in the output section of OCM. (4) Processor ID  0  invalidated the cache value of the output section of OCM, so that further computation loaded the correct value from the OCM. 
         [0044]    An unexpected efficiency of the eight processor core system using the architecture of present invention was about 95%. The speed-up of the eight processor core system using the present invention was about 7.5. Speed-up is defined as the ratio of the execution time of a system with one processor core to the execution time of a system with m processor cores. Efficiency is 100 times (Speed-up/m). 
         [0045]      FIG. 5  illustrates a block diagram an exemplary computer system architecture having a multi-core microprocessor distributed on multiple micro-processor chips according to embodiments of the present invention. In  FIG. 5 , a computer system  200  includes a first processor chip  205 , a second processor chip  210  and a third processor chip  215  connected to a system memory  220  by a system bus  225 . First processor chip  205  includes processor cores  230 A,  230 B,  230 C and  230 D connected to respective caches  235 A,  235 B,  235 C and  235 D. Second processor chip  210  includes processor cores  230 E and  230 F connected to respective caches  235 E and  235 F. Third processor chip  215  includes processor cores  230 G and  230 H connected to respective caches  235 G and  235 H System memory  220  includes a shared non-cacheable memory region  240 . Memory region  240  is similar to OCM  125  of  FIG. 2  and is configured similarly and supports the same function. However, since computer system  200  is an eight processor core system (m=8) memory region  240  is an 8 by 8 arrays of n-byte memory addresses. 
         [0046]    Because the shared memory for the first memory is not on the same chip as the processor cores, there is a performance penalty because of the overhead associated with system bus  225 . 
         [0047]    Computer system  200  also includes arbiter  245  for arbitrating traffic on system bus  225 , a bridge  250  between system bus  225  and a peripheral bus  255 , an arbiter  260  for arbitrating traffic on peripheral bus  255 , and peripheral cores  265 A,  265 B,  265 C and  265 D. 
         [0048]    The description of the embodiments of the present invention is given above for the understanding of the present invention. It will be understood that the invention is not limited to the particular embodiments described herein, but is capable of various modifications, rearrangements and substitutions as will now become apparent to those skilled in the art without departing from the scope of the invention. Therefore, it is intended that the following claims cover all such modifications and changes as fall within the true spirit and scope of the invention.