# Adaptive Versioning in Transactional Memory Systems +
## 4 Basic Adaptive Versioning
### Adaptive for Non-Persistent Transactional Memories  
The idea in the design of Adaptive for non-persistent memories is to compute the total time spent by transactions executing using eager and lazy versioning, separately, and switch between the versioning methods when the execution time increases. Ideally, again, we would like to use the versioning method in Adaptive that gives optimum performance in terms of execution time for any specific workload. From the working principle of a TM system, we can see that a transaction spends significant amount of time on moving data between the original memory location and the log areas in addition to the constant computation time. Figure 2 illustrates the working principle of a TM system. Moreover, it is likely that the total execution time increases with the increase in total number of aborts requiring more number of transaction restarts. Thus, we use abort to commit ratio (ACR) in the design of Adaptive for non-persistent memories. For eager (and lazy) versioning, we can compute \(ACR_{Eager}\) (and \(ACR_{Lazy}\)) based on the number of transactions committed and aborted using eager (lazy) versioning as follows. \[ACR_{Eager} =\frac{N_{Eabort}}{N_{Ecommit}} \tag{12}\] \[ACR_{Lazy} =\frac{N_{Labort}}{N_{Lcommit}} \tag{13}\]  
To facilitate when to switch from one to another, we identify a _threshold_ on ACR for both eager and lazy. We denote them by \(Threshold_{Eager}\) and \(Threshold_{Lazy}\), respectively. Let a transaction \(T\) be running at current time \(t\) using lazy versioning. If \(ACR_{Lazy}<Threshold_{Lazy}\), then the versioning method is switched to Eager for transactions that start (or restart) execution after time \(t^{\prime}>t\). An analogous approach is used if currently \(T\) is executing using eager versioning. Based on \(N_{Ecommit}\), \(N_{Lcommit}\), \(N_{Eabort}\), and \(N_{Labort}\), we compute \(ACR_{Eager}\) and \(ACR_{Lazy}\) at each time step \(t>t_{0}\). These ratios \(ACR_{Eager}\) and \(ACR_{Lazy}\) are then compared with \(Threshold_{Eager}\) and \(Threshold_{Lazy}\) parameters (computed in the next section). Therefore, at any time \(t>t_{0}\), the transaction \(T\) that is ready-to-execute will be executed as follows. * Suppose the versioning currently used is \(V_{cur}=Eager\). If \(ACR_{Eager}>Threshold_{Eager}\), then \(V_{cur}\) is switched to \(Lazy\) (i.e., \(V_{cur}\gets Lazy\)) and \(T\) will be executed using lazy versioning. * Suppose the versioning method currently used is \(V_{cur}=Lazy\). If \(ACR_{Lazy}<Threshold_{Lazy}\), then \(V_{cur}\) is switched to \(Eager\) (i.e., \(V_{cur}\gets Eager\)) and \(T\) will be executed using eager versioning. Computing Switching Thresholds\(Threshold_{Eager}\) and \(Threshold_{Lazy}\)  
Let \(N\) be the total number of transactions in any workload. When the workload finishes execution and all transactions commit, we have that \(N_{commit}=N\) and \(N_{abort}\geq 0\) (if each transaction commits without aborting, then \(N_{abort}=0\), otherwise \(N_{abort}>0\)). Suppose, each transaction \(T\) spends \(\alpha\) amount of time while moving data from one memory location to other. Consider the case of executing \(T\) using eager versioning. Let \(\tau_{Eager}\) be the total amount of time spent while (i) versioning data from the original memory locations to the undo log area and (ii) updating data from the undo log area back to the original memory locations. The first kind of operations are shown as 1 in Figure 1(a) and the second kind of operations are shown as 2 in Figure 1(a). The first kind of operations are always done in eager versioning and the second kind of operations are done only when the transaction aborts. That means, for an aborted transaction, data movement is performed two times, one for versioning, other for rollback. Therefore, for eager versioning,  
\[\tau_{Eager}=(N_{commit}+2N_{abort})\cdot\alpha \tag{14}\]  
Similarly, consider the case of executing \(T\) using lazy versioning.