FORM 2
THE PATENTS ACT 1970
(39 of 1970)
AND
The Patents Rules, 2003
COMPLETE SPECIFICATION
(See section 10 and rule 13)
1. TITLE OF THE INVENTION:
"METHOD FOR IMPLEMENTING HYBRID LOCK-FREE SYNCHRONIZATION MECHANISM"
2. APPLICANT (S):
(a) NAME: KPIT Cummins Infosystems Limited
(b) NATIONALITY: Indian Company incorporated under the
Companies Act, 1956
(c) ADDRESS: 35 & 36 Rajiv Gandhi Infotech Park, Phase 1, MIDC,
Hinjewadi, Pune 411057, India.
3. PREAMBLE TO THE DESCRIPTION:
The following specification describes the invention and the manner in which it is to be performed.

Field of the invention
This invention relates generally to the field of parallel computing or concurrent access to shared resources and more particularly, to methods and systems for implementing lock-free synchronization mechanism in computer applications.
Background of the invention
In the past few years there has been a tremendous change in the way we compute. Parallel computing power is being exploited favourably with the progress in multi-core technology. The trade-off between increasing demand of processing power while keeping the heat dissipation and power requirements under control has led to parallel computing become a crucial component. The shift in hardware architecture has necessitated the change in the way software is being written and partially forced many of the legacy code to be re-written to exploit the parallel multi-core architectures. This clearly defines the need of programming paradigm shift, which in turn poses new challenges for software programmer-users in the form of building expertise in parallel programming, understanding the difficulties and writing error free parallel execution software programs.
The most important aspect for parallel programs is the synchronization. Parallel programs need to be written carefully since they may lead into situations such as deadlocks and erroneous function of the systems due to synchronization issues. Hence, the need to use the right kind of synchronization method while developing parallel applications is critical.
Synchronization ensures that one execution context does not use intermediate or partial results generated by any other context of execution in parallel programs. This mechanism ensures proper interaction between two or more execution contexts and is useful in practical implementations of the parallel applications. Practical implementations of synchronization techniques use locking mechanisms such as mutual exclusion or semaphores. These mechanism many times degrade the performance of the system and also causes problems like deadlocks, live-locks and the like. Since the execution of application also depends upon many run time parameters like hard disk, network and any other hardware and software parameters, the correctness of the output is not always guaranteed.

Conventionally, locks are implemented using mutexes or semaphores. The use of locks may result in deadlock situations which are generally handled using watch dog timers. When a lock is acquired, a timer is initialized to a certain waiting period. If there is a deadlock indicating infinite waiting period for two or more execution contexts the timer expires and resets the program execution to a particular location which is generally the start of program execution. This is how any deadlock is handled, but in such situations the data and context of execution is lost. It also means that the section of code that led to the deadlock has executed incompletely and there is no trace of the context.
Currently for synchronization, locking mechanisms are used. These mechanisms are some variants of the above mentioned types. Because of the inherent problems of locks, (e.g. deadlock being one of them), these methods are inefficient and cannot guarantee the complete and correct execution of the program at the execution time. This execution also depends upon many run time parameters (e.g. hard disk, network and such other hardware parameters and also on many software parameters, scheduling priority between execution contexts being one of them). Because of this run-time-dependant execution, the correctness of the output is not always guaranteed.
Traditionally, lock free synchronization mechanisms are implemented utilising only software or only hardware only. Recently there have been attempts to use a hybrid approach. This approach basically takes advantage of both the software and hardware implementation. All these techniques still lack the basic mechanism that would also be used while debugging parallel programs. They also fail to mention how the system can work in tandem with other locking mechanism to achieve efficient and functionally error free execution of applications in real time.
US7496716 describes the use of hybrid transactional memory to track the status of the shared data and software transactional memory to record all operations or local modifications done in cache. Data values are committed after checking the displacements. US20010056420 mentions a linked list based method to use a double ended queue and push and pop operations for transaction. US20090070774 mentions a method of detecting live-locks based on priority and counting logic.US20080010532 proposes use of

conventional debuggers able to instrument code using transactional memory which can be used for debugging or more specifically for break-pointing.
Thus, the existing methods do not implement the use of special purpose register or LOG registers that would help for debugging parallel applications. Additionally, they do not teach any mechanism for deadlock detection or similar situations and their efficient resolution or handling. As seen here above, the present state of the art leaves room for a hybrid system which benefits from a hardware and software solution working in tandem with each other to provide a lock-free synchronisation mechanism.
Summary of the Invention:
A method and system to implement a lock-free mechanism for synchronization that uses a hybrid, i.e. both hardware and software functionality is disclosed. The present lock-free synchronization mechanism of the invention utilizes existing cache memory hardware with minimal modification resulting into a transactional memory cache, along with provision of the library functions for use. The invention implements new special purpose registers, LOG registers and similar hardware modification so as to incorporate debugging information. The invention provides for working in cooperation with other locking mechanism to achieve efficient and functionally error free execution of applications in real time. The invention, additionally, describes a method to identify a deadlock or similar situations and a mechanism to achieving an efficient deadlock handling.
Brief Description of the Drawing:
Figure 1 illustrates a modified cache memory according to the embodiment of the
invention.
Figure 2 illustrates a program context.
Figure 3 illustrates a process flow for deadlock handling, according to the embodiment of
the invention.
Figure 4 illustrates a pseudo code for the process flow for deadlock handling of Fig. 3.
Figure 5 illustrates a flowchart of a conventional approach to resolve a deadlock.
Figure 6 illustrates a flowchart for implementation of lock free mechanism to replace
locks that create deadlock situation according to the embodiment of the invention.

Description of the invention
The present invention describes a method to implement a lock-free mechanism for synchronization that uses hardware and software functionality. The present invention comprises of a hybrid mechanism defined by the use of modified hardware and auxiliary methods, which comprises of library functions, operating in tandem with each other. This hybrid mechanism facilitates implementation of the lock-free synchronisation technique in easy yet efficient way. The method of the invention allows a programmer-user to write code assuming that multiple execution contexts can modify/access shared resources in an atomic manner. The method of the invention provides for an optimistic and promising approach to solve the problems posed by synchronization implemented using locks. It allows programmer-user to concentrate on the application instead of addressing the performance issues. To execute an atomic section of code using any lock-free synchronization mechanism, a transaction is initiated and then executed. A check is performed later to either commit or abort the transaction. If a transaction commits, the results can be seen to be achieved atomically but if it fails then the transaction is either rolled back or retried,
Figure 1 illustrates modified cache memory hardware, according to the embodiment of invention. As seen, the existing cache memory hardware is minimally modified resulting into a transactional memory cache (TMCache) provided with primitive instructions for the programmer-user to use the lock free synchronization mechanism. The TMCache, according to the embodiment of invention, includes additional tags (240), address Tag (210), duplicate context (230) and the execution context (220). The TMCache is provided along with library functions to the programmer-user for using the lock-free synchronizing mechanism. These library functions may include, but are not limited to, load, store, commit, abort and validate transactions. The present invention proposes to use any existing cache coherence protocol like, but not limited to, MES1 to detect the accessibility conflicts in the lock free synchronization mechanism and the abort-retry mechanism to resolve the conflicts. Based on successful or failed commit, the duplicated context (110) can be destroyed or copied back to original context (100), respectively.

New registers, LOG registers or similar hardware modification is implemented in the TMCache so as to incorporate debugging information. The LOG registers of the invention are utilized to realize the additional tags (240) and address Tag (210) in hardware. In case of a lock free synchronization mechanism the transactions would be transparent to user in an atomic manner and hence providing hardware support for debugging of the transactions would be helpful. The debugging or context information stored in the specially provided registers would be made available by providing minimal changes in the compiler. Based on successful commit, the duplicated context can be copied back to main context or destroyed. However, this does not give any information about the situation that caused deadlock. As such, special log registers according to the embodiment of the invention are used to log the information which caused the conflict.
Operation of the LOG registers is as described. When the commit fails, it signifies that some other execution context has modified the data being used by the current execution context. This write time conflict is detected by using any cache coherency protocols. For example, the MESI protocol detects just the presence of conflict. When the 2nd execution context writes the data, it also invalidates the cache entry of the current execution context's cache. In addition, the program counter of that 2nd execution context, at that time instance is also logged, so that, the block of the code which actually overwrote the shared data is detected. This Jog can be used to detect the reason of failed commit and hence to detect the data conflict situations and possible deadlocks. Whenever there is a write by 2nd execution context, resulting into the cache invalidate of current execution context, the program counter of the writing execution context (2nd execution context in this case) is logged. If the current execution context also tries to write the same location, it causes a failed commit. Hence by recording such situations of failed commits, the data conflicts are detected.
Figure 2 illustrates a program context which comprises an original program context (100) and a duplicate program context (110). If a commit is successful, the duplicate program context (110) is destroyed and if the commits fails for some reason the duplicate program context (110) is copied back to the original program context (100). The benefits of the implementation as illustrated in Fig. 2 are as follows:

1. This insures that the program execution would complete in the subsequent execution attempts.
2. The context of the program execution at the time of deadlock can be saved and used during debugging of the application.
The present invention provides a better way for effective synchronization. The concept of transactional memory and software locks (viz. semaphores, mutexes and all such others) are used together to get better performance. Using transactional memory, the effect of such external dependencies are minimised. According the embodiment of the invention, use of features of software locks and transactional memory together are planned, in order to obtain performance free from deadlocks and all such drawbacks.
During application of the embodiment of the present invention, the programmer-user writes his program in usual way using locks or by using special transactional memory constructs, such as, but not limited to, 'transaction_start' and 'transaction_end' If the transactional memory constructs are used, the synchronization and data integrity protection is done using transactional memory directly. If the programmer-user uses the traditional style i.e. locks method for this purpose, in the initial iteration, the synchronization is performed using locks. However, if the locks mechanism results in deadlock or any other of the problems are posed by the mechanism, the implementation of these locking constructs are internally switched to transactional memory. This switch is done at the time of prediction of the problem. The prediction of possible deadlocks (or other problems) can be done by using any of the existing algorithms known in the art.
Figure 3 illustrates a process flow for deadlock handling, according to the embodiment of the invention, wherein, the locking construct execution is dynamically replaced with a lock-free construct execution. As seen in Fig. 3, various execution contexts have a shared access to various shared resources. Whenever an access request is received, deadlock detection is carried out. If a deadlock is not detected access to the shared resource is provided to the demanding execution context. However, if a deadlock is detected, the lock mechanism is replaced with a lock-free mechanism. This approach ensures that the program execution would complete in the subsequent execution attempts and the context

of the program execution at the time of deadlock or similar problem can be saved and used during debugging of the application.
Figure 4 illustrates a pseudo code for the process of Fig, 3, wherein modification is provided in the library code, while the user code would be written by the application programmer-user in usual way using locks or by using special transactional memory constructs. If the lock-free synchronization mechanism constructs are used, the synchronization and data integrity protection is done using lock-free synchronization mechanism directly. If the programmer-user used the traditional style i.e. locks method for this purpose, in the initial iteration, the synchronization is performed using locks. However, if the locks mechanism results in deadlock or any other of the problems posed by the mechanism, the implementation of these locking constructs is dynamically switched to transactional memory. This switch is done while acquiring the lock that might result in a deadlock situation as illustrated in Fig 3. Deadlocks may be determined using any of the existing algorithms or specified algorithm.
Figure 5 shows the existing approach, when executing applications enter a deadlock. A timer is initialized and starts counting. After a pre-determined time is over and if the system still does not respond then the whole system or program is reset to its original state. This normal procedure has many drawbacks for example the state of the system which caused the deadlock is not known and it is very difficult to regenerate the situation for debugging. Hence, instead of using a timer to reset the system one can at runtime replace the locking instructions with lock-free instructions so that the chances of complete the task under execution are improved and at the same time system can record the context and reproduce the situation for debugging and bug-fixing.
Figure 6 illustrates a flow chart for implementing lock free mechanism to replace locks that create a deadlock situation, according to the embodiment of the invention. When multithreaded or parallel applications are used there is a possibility of deadlocks due to misplaced locks or more number of locks in use. Many algorithms are available that can perform static or runtime analysis to predict if there is a possibility of deadlock. For e.g., signal processing applications represented as synchronous data flow (SDF) graphs can predict deadlocks. By achieving a pre-warning, such deadlocks can be eliminated. Thus, it

is beneficial to use lock free mechanism for synchronization to avoid deadlocks but still let the different contexts sync up with each other. Locks and lock-free mechanism can work together in tandem taking benefits of both the methods.
The examples of the present invention as mentioned herein above are meant to illustrate the working of the method and system of the present invention and should be considered in no way to limit its scope .

We Claim,
1. A hybrid lock-free synchronisation mechanism comprising modified cache memory hardware and auxiliary methods operating in tandem with each other, wherein, the lock-free implementation in the modified cache is enabled to detect and resolve synchronisation issues in parallel processing.
2. A hybrid lock-free synchronisation mechanism as claimed in claim 1, wherein, modified cache memory hardware is realized with special registers to debug synchronisation issues in parallel processing.
3. A hybrid lock-free synchronisation mechanism as claimed in claim 1, wherein, the said auxiliary methods are, but not limited to, load, store, commit, abort and validate transactions.
4. A hybrid lock-free synchronisation mechanism as claimed in claim 1, wherein, the said mechanism is enabled to process locked and lock-free implementations of parallel applications by replacing the locked implementation with lock-free implementation during runtime in case of a deadlock.
5. A hybrid lock-free synchronisation mechanism as claimed in claim 1, wherein, the said modified cache is facilitated for debugging of multiple contexts in parallel processing.