João Barreto

Aleksandar Dragojevic
email: aleksandar.dragojevic@epfl.ch

Paulo Ferreira
email: paulo.ferreira]@inesc-id.pt

Ricardo Filipe
email: rfilipe@gsd.inesc-id.pt

Rachid Guerraoui
email: rachid.guerraoui]@epfl.ch

Unifying Thread-Level Speculation and Transactional Memory

The motivation of this work is to ask whether Transactional Memory (TM) and Thread-Level Speculation (TLS), two prominent concurrency paradigms usually considered separately, can be combined into a hybrid approach that extracts untapped parallelism and speed-up from common programs. We show that the answer is positive by describing an algorithm, called TLSTM, that leverages an existing TM with TLS capabilities. We also show that our approach is able to achieve up to a 48% increase in throughput over the base TM, on read dominated workloads of long transactions in a multi-threaded application, among other results.

Introduction

Multicore architectures are already the norm for most commodity computing devices. This trend calls for concurrent programs that expose enough parallelism to maximize the utilization of such increasing computational resources. Yet, concurrent programs are significantly more difficult to code than sequential ones.

In recent years we have witnessed increasing efforts from the research community to develop new emerging paradigms that ease the challenge of extracting parallelism from non-trivial programs. Thread-Level Speculation (TLS) [START_REF] Sohi | Multiscalar processors. In: 25 years of the international symposia on Computer architecture[END_REF][START_REF] Hammond | Data speculation support for a chip multiprocessor[END_REF] and Transactional Memory (TM) [START_REF] Herlihy | Transactional memory: Architectural support for lockfree data structures[END_REF] are perhaps the most prominent examples of such efforts. State-of-the-art solutions from both paradigms have already proved to extract considerable parallelism from a wide range of programs, while hiding complex concurrency issues away from the programmer [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF][START_REF] Dragojević | Why stm can be more than a research toy[END_REF].

However, more than easily coding concurrent programs that yield some parallelism, we want concurrent programs that expose as much parallelism as the ever increasing hardware thread count. This goal becomes dramatically more challenging as affordable multicore machines include more and more cores each year. While 4-core processors supporting up to eight simultaneous hardware threads are already regarded as commodity hardware, 8-core, 16-core and even chips with tens or hundreds of cores promise to be an affordable reality soon [START_REF] Howard | A 48-core ia-32 message-passing processor with dvfs in 45nm cmos[END_REF].

Unfortunately, when examined individually, both TLS and TM have crucial limitations that hinder one's ability to extract high parallelism from most sequential programs.

On the one hand, TLS departs from a sequential program, breaks it into fine-grained tasks, and tries to automatically parallelize such tasks in a speculative fashion. For the sake of correctness, TLS ensures that any data dependencies stemming from the original sequential program order are respected in the speculatively parallelized execution. However, experience from the TLS systems proposed so far suggests that, for most programs, such data dependencies severely restrict the number of tasks that any TLS can parallelize effectively (i.e., without incurring in expensive rollbacks) [START_REF] Oplinger | In search of speculative thread-level parallelism[END_REF]. Recent results show that even the most successful TLS systems rarely go beyond a relatively modest horizon of parallelization depth without rollback (e.g. less than 6 parallel tasks with SpLIP TLS [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF]).

On the other hand, TM involves the programmer in the parallelization effort, by requiring him to explicitly fork the program into multiple threads. By carefully reasoning about the semantics of the application being parallelized, the programmer can thereby eliminate many data dependencies that were originally implicit across the original sequential program. Hence, in theory, higher levels parallelism are now attainable.

However, hand-parallelizing a program into many fine-grained threads is far from trivial. It requires a careful reasoning about the semantics of the application being parallelized, since the programmer must assert if the work performed by the parallelized tasks is actually commutative. Furthermore, it demands a thrifty understanding of the actual overheads of thread creation and management, so that the programmer can determine whether fine-grained tasks will actually introduce speed-up if parallelized. Hence, the programmer will typically choose a monolithic organization of coarse-grained threads. This is evident in the most representative TM benchmarks [START_REF] Guerraoui | Stmbench7: a benchmark for software transactional memory[END_REF][START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF][START_REF] Ansari | Leetm: A non-trivial benchmark suite for transactional memory[END_REF] and applications [START_REF] Zyulkyarov | Atomic quake: using transactional memory in an interactive multiplayer game server[END_REF][START_REF] Carvalho | Versioned transactional shared memory for the fénixedu web application[END_REF]. In other words, the programmer is dissuaded from exposing the full fine-grained parallelism that the underlying application effectively contains.

Therefore, when facing the challenge of parallelizing a sequential program to run on a next-generation multicore machine, the programmer will most likely get disappointing results with either approach separately, TLS or TM.

While the research community places its efforts in exclusively improving one approach alone, we advocate that the time has come to question a hybrid direction: Can TLS and TM be combined into a unified solution that would extract untapped parallelism (and speed-up) from our common applications? If this hybrid approach proves to be feasible, programmers would first be asked to handparallelize their programs into coarse-grained threads using the TM paradigm. Each thread in the multi-threaded program would then be further parallelized into finer-grained parallel tasks, in a TLS fashion.

To the best of our knowledge, this paper is the first to give a positive answer to the above question, proving that TM and TLS do add up. We take a middleware approach, focusing on Software Transactional Memory (STM) and Software Thread-Level Speculation (STLS). Our main contribution is a unified STM+STLS middleware called TLSTM. TLSTM relies on standard techniques, such as compile time code inspection, to speculatively break each transaction in a multi-threaded STM program into multiple tasks that will run in parallel. If no conflicts arise among the multiple tasks, then the transaction can commit earlier. TLSTM can even be more optimistic and speculatively execute future transactions of a thread, even when the current transaction in that thread is still active. If the speculation proves to be successful and every transaction commits, then further parallelism is accomplished.

TLSTM extends an existing STM, SwissTM [START_REF] Dragojević | Stretching transactional memory[END_REF]. The key insight is that a SwissTM transaction is used as speculative execution unit that supports two concepts: STM transactions (defined by the user) and TLS speculative tasks (automatically created at compile or run-time). An STM transaction is seen as a sequence of one or more TLS speculative tasks, which can run out-of-order in a speculative fashion, until they commit sequentially.

Our implementation of TLSTM3 achieves up to a 48% speedup over Swis-sTM, when running on a multi-threaded benchmark of long transactions, with three speculative tasks inside each transactional memory thread. Furthermore, we also study several scenarios and applications where STLS does not provide any help to the STM runtime.

The remainder of the paper is organized as follows. Section 2 defines the STM+TLS model we wish to support. Section 3 then describes the TLSTM algorithm. We evaluate TLSTM on Section 4. Section 5 surveys related work on STM and STLS. Finally, Section 6 draws conclusions and discusses future work.

A Unified TM+TLS Model

We start by defining the novel model we want to support. Programmers can manually fork and join user-threads in their programs. Since critical sections might exist due to shared memory locations, programmers are also responsible for hand delimiting such critical sections as user-transactions. Together, the user-threads and their user-transactions comprise the hand-parallelized program. For presentation simplicity, we assume that user-transactions are flat (i.e., nonnested); however, the model can easily be extended to consider user-transaction nesting.

When executed, each user-thread's program will be further decomposed into speculative tasks, which will run in parallel in a speculative fashion. A task's boundaries lie either outside of a user-transaction's code, or inside a user-transaction's code. In case the task's boundaries lie inside of a user-transaction's code, they can either be the same as the user-transaction's boundaries or they can represent just a fraction of that user-transaction.

The life cycle of a successful task goes through a number of states: initially, the task is running; once the task has executed its last instruction, it is said to be completed; finally, it becomes committed when the task's effects become visible to all other tasks and cannot be undone. We say that a task is active if it is either running or completed. If the speculative execution of some task tsk is found to be inconsistent with the expected outcome of the sequential execution of tsk's user-thread (causing an intra-thread conflict), or tsk's execution is inconsistent with the execution of other user-threads (inter-thread conflict), then tsk must rollback, and is said to have aborted.

Hereafter, when a task tsk 1 runs code that precedes (in program order) the code executed by task tsk 2 , we say that tsk 1 is from the past of tsk 2 (whereas tsk 2 is from the future of tsk 1 ). Within the collection of active tasks of a user-thread, we distinguish one current task, which corresponds to the earliest running task of the user-thread. This corresponds to the task that is running the code that the user-thread would be running if executing with no thread level parallelism. All the active tasks in the future of the current task are called out-of-order tasks. As soon as the current task completes, the next task in program order becomes the new current task.

The accesses performed by tasks belonging to the same user-thread must behave as if they ran sequentially. More precisely, our model ensures that any read from a task tsk 1 observes all the writes that tasks from tsk 1 's past should perform and does not observe values written by future tasks.

Our model ensures that user-transactional correctness (more concretely, the opacity criteria [START_REF] Guerraoui | On the correctness of transactional memory[END_REF]) is preserved across user-transactions, even when user-transactions are actually executed by multiple tasks running out of order. Only after every task belonging to the same user-transaction has completed its execution can the user-transaction commit.

TLSTM, A First Unified STM+TLS Middleware

A first naive solution to the STM+TLS problem that one might consider would be to simply run TLS on top of each thread of an existing multi-threaded STM application (either software-based or hardware-based), with no modifications on any of the two components. However, the correctness of conventional TLS algorithms relies on the assumption that the underlying (single-threaded) program exclusively accesses thread-local variables. Clearly, this no longer holds in the STM+TLS model.

Hence, we must look towards an integrated approach, i.e. a single runtime that fully supports the unified TM+TLS model that Section 2 introduced. TL-STM is a hybrid runtime that extends an existing STM, SwissTM [START_REF] Dragojević | Stretching transactional memory[END_REF], with TLS capabilities in order to support the unified STM+TLS model we described. SwissTM is a state-of-the-art STM system that supports optimistic read-write conflict detection and pessimistic write/write conflict detection, which has been shown to outperform other relevant STMs.

Therefore, before presenting TLSTM, Section 3.1 starts by describing the baseline SwissTM algorithm. Section 3.2 then discusses the hard challenges that we needed to tackle when leveraging SwissTM with support for TLS. Section 3.3 finally introduces the TLSTM algorithm.

The baseline STM: SwissTM

In SwissTM, a global commit counter, called commit-ts, is used as a wall clock that is incremented by every non-read-only user-transaction on commit. Swis-sTM maintains a global lock table. Each location is mapped to a pair of locks, r-lock (read) and w-lock (write) from the global table. r-lock can either hold a version number or the locked value. w-lock can either hold a write-log entry or the unlocked value. Any user-transaction wishing to write must first obtain the location's w-lock. This eagerly prevents write/write conflicts between user-transactions.

Writes are performed in temporary copies, and only applied on the actual location once the associated user-transaction commits. During commit, the usertransaction acquires the r-lock of each location that the user-transaction wrote to. This prevents other user-transactions from reading the written locations and, as a result, observing inconsistent states. Upon successful commit, the r-lock is unlocked and contains the new commit-ts value, hence denoting the instant where the new value of the location was made visible to every other user-transaction.

SwissTM uses lazy counter-based validation [START_REF] Dice | locking ii[END_REF][START_REF] Felber | Dynamic performance tuning of word-based software transactional memory[END_REF] to detect read/write conflicts. Each user-transaction maintains a version timestamp, valid-ts, denoting a point in the logical commit time for which all the values that the user-transaction has observed so far are guaranteed to be valid. Whenever the user-transaction reads some location that has a higher version than its valid-ts, the user-transaction needs to extend its valid-ts to the version being read. This requires traversing the user-transaction's read-log to validate that each version read so far remains valid at the new valid-ts, i.e. it has not been overwritten in the meantime.

Leveraging SwissTM with Thread-Level Speculation: Main Challenges

The key insight is that what used to be a SwissTM transaction is now used as a task in TLSTM. A user-transaction will now consist of a sequence of one or more tasks, which are automatically/manually created at compile or runtime, and can run out-of-order in a speculative fashion. However, extending an STM (such as SwissTM) with TLS support is far from trivial. In the following, we discuss all the main challenges and give an intuitive overview of how TLSTM tackles each of them.

Ensure low overhead. A major part of the unified runtime's overhead comes from conflict detection. Besides the inter-thread conflicts of SwissTM, TLSTM must also detect and resolve the intra-thread conflicts resulting from TLS. There are several TLS techniques we can employ, but bluntly doing so would incur unacceptable overheads in conflict detection. Thus we must ensure that the overhead of the unified runtime is much smaller than the overhead of the sum of its parts. This requires that TLSTM reuses most of SwissTM's data structures and procedures, and adds minimal complexity to conflict detection.

Conceptually, two types of intra-user-thread conflicts may arise: write-afterread (WAR), where a task writes to a location that a future task already read from; and write-after-write (WAW), where a task wants to write to a location already written by a future task.

WAR conflicts are discovered through a new task validation procedure that starts by validating the read-log inherited from SwissTM, which records the reads performed from committed state. Then this procedure validates a new task-read-log, similar to SwissTM's read-log, which records the reads performed from writer tasks of the task's past. First, this validation checks if any of the values read from committed state were speculatively written by running tasks from the task's past. Second, this validation must ensure that each value the task has read from a past writer task has not been updated by a task from the writer task's future. If any of these situations has occurred, we abort the task performing validation. We check the need for this validation at read, write and commit time.

In the case of WAW conflicts we cannot rely on SwissTM's write-write conflict handling alone. If we did so, we could easily have intra-thread deadlocks when a future task wrote to a location and waited for its past tasks to complete in order to commit. This task might be stuck waiting forever if a past task wishes to write to that same location, which in turn would be indefinitely waiting for the location's write-lock to be released.

This problem requires a very small addition to SwissTM's write-write conflict handling. If a task wishes to acquire a write-lock that is held by a past task from the same user-thread, the task wishing to acquire the lock aborts. If, otherwise, it was a future task that write-locked the location, that future task will be signaled to abort. By following this task contention management approach we have only one running task writing on a certain location at a time.

Before committing a task, TLSTM must also ensure that all past tasks have completed and cannot be aborted because of intra-thread conflicts. TLSTM achieves this by serializing commits of tasks belonging to the same user-thread, along with the previously explained intra-thread conflict detection.

We ensure this by associating each task with a monotonically increasing serial number in the scope of the task's user-thread, and once the commit step of some task starts, the task waits for tasks from the same user-thread with lower serial numbers to complete before committing.

Transaction commit. The transaction commit procedure in TLSTM needs to take into account the reads and writes performed by every single task of the user-transaction, in order to preserve atomicity. Thus, transaction commit differs substantially from SwissTM's, since it is performed by the last task of the user-transaction in program order, which we call the commit-task.

When committing a user-transaction, the commit-task validates the reads of all tasks of the user-transaction. When committing to memory the values of a write user-transaction, the commit-task needs to update all values written by all tasks of the user-transaction. Intermediate tasks take no part in validating reads or updating writes of the user-transaction, while waiting for the commit-task to commit the user-transaction.

Transaction abort. As in commits, transaction abort in TLSTM involves a coordinated effort from the multiple parallel tasks that comprise the user-transaction. This challenge is especially difficult as some of such tasks might still be running when the abort decision is taken.

When a task receives the abort transaction signal it waits until all tasks from its user-transaction have received that signal. Then, the last task of the aborting user-transaction clears every write-lock of all tasks in its user-transaction and resets the tasks' state to their last known correct values. Finally, the last task signals every past task of its user-transaction to restart, before restarting itself.

Preventing inter-thread deadlocks. Since TLSTM supports multiple threads, TLSTM must ensure that there are no deadlocks between tasks of different userthreads writing to several locations.

Imagine the scenario of an application with two user-threads running two tasks each (T A,1 represents task 1 from thread A and so on): T A,1 , T A,2 , T B,1 , T B,2 . T A,2 holds the write-lock to location X and T B,2 holds the write-lock to location Y. Assume that T A,1 wants to write to Y and T B,1 wants to write to X and that TLSTM inherits the inter-thread contention manager from SwissTM. Hence, when a task holds the write-lock of a location and tasks from other userthreads want to write to that location, they have to wait for the current writer to commit.

Both tasks T A,1 and T B,1 will be blocked waiting for the lock owners to abort or commit, but the contention manager will not signal the lock owners to abort and the lock owner tasks will not commit because they are waiting for their past tasks to complete (as a consequence of serializing commits).

In order to solve this problem, the inter-thread contention manager must be task-aware, so that it makes decisions according to the user-thread's set of tasks and not for each task individually.

Whenever an inter-thread conflict is detected between two tasks, the contention manager aborts the more speculative one, i.e. the one that has fewer tasks from its past that are still running. Not only does this strategy favor tasks with higher probability of completing successfully, but it also prevents starvation. If contending user-transactions have the same number of completed tasks, then TLSTM employs traditional STM contention management algorithms. Currently, TLSTM implements the two phase greedy contention manager for this case.

Inconsistent Reads. TLS and STM can induce out of order reads that may trigger undesirable effects. For example, picture T A,1 writing NULL to location X and then allocating a new object to X. If T A,2 reads the intermediate value of X it will crash because of a NULL pointer exception.

While in STM these are prevented through atomicity, as read operations only read values from the user-transaction itself or from committed state. In TLS values can be read from running tasks, which may result in reading intermediate and inaccurate values [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF].

Therefore, in a unified runtime it is not possible to prevent all inconsistent reads, so TLSTM needs to detect and take care of those coming from TLS. In TLSTM, when a task reads a location the task needs to check if the location it is reading from is valid. Unfortunately, this validation also takes a toll on correct read operations.

Algorithm

We now describe in detail how TLSTM overcomes the challenges discussed in the previous section, thereby leveraging SwissTM with TLS support. Algorithms 1 to 3 present the pseudo-code of TLSTM. The following sections explain each aspect of the algorithm in detail.

For each user-thread, the runtime supports up to a fixed number of simultaneously active tasks, called speculative depth (SPECDEPTH). Each task is assigned a unique user-thread identifier and a unique serial number which represents the task's position in program order.

Any technique for decomposing each user-thread into tasks can be employed, which is orthogonal to our model and out of the scope of this paper, as long as it ensures that a task does not span across the boundaries we presented earlier. Several standard techniques can be used for user-thread decomposition, from loop iteration speculation (e.g. spec-DOALL and spec-DOACROSS [START_REF] Kim | Scalable speculative parallelization on commodity clusters[END_REF]), to procedure fall-through speculation [START_REF] Chen | Exploiting method-level parallelism in single-threaded java programs[END_REF], at either compile-time and/or executiontime.

Task, User-Transaction and User-Thread State. Each task maintains the following state inherited from SwissTM:

valid-ts, a timestamp denoting the instant where the read accesses performed by this task are guaranteed to be valid; read-log and write-log tables, each one used to store location entries that were read (resp. written) by the task;

Furthermore, each task also maintains the following new state:

tid, the task's user-thread identifier; serial, the program order of this task within its user-thread; tx-start-serial and tx-commit-serial, which denote the first and last task, respectively, from the task's user-transaction in program order; try-commit, a flag that indicates whether this is the last task in the usertransaction; last-writer, which holds the serial of the last known writer task of the userthread. Used to check if task validation is required;

Each user-thread maintains the following state, shared by every task running on behalf of this user-thread:

completed-task and completed-writer, denoting the serial identifiers of the last completed task and last completed writer task of the user-thread; owners[SP ECDEP T H], an array of pointers to the state of each task in the user-thread.

For a given task tsk of user-thread thr, its state can be obtained at index [tsk.serial mod SP ECDEP T H] of the thr.owners array.

Starting a Task. By definition, a task can only start when the number of active tasks in the given user-thread is lower than the SP ECDEP T H limit. Once that condition is satisfied, the task is assigned the next serial number in its user-thread and its initial state is saved in the corresponding position of the owners array (line 2 alg. 1). If the task belongs to an user-transaction, its start and commit-serial are assigned. The last-writer of the new task is assigned the value of the last completed writer of that task's user-thread (line 3 alg. 1). The valid-ts of the new task is initialized with the current value of the global counter commit-ts (line 4 alg. 1).

Reading. Before reading, the task consults the location's write-lock. In TLSTM, a location's write-lock is either unlocked or points to the location's redo-log. In sum, the location's redo-log has the last speculative write-log entry for that location. TLSTM's write-log entry complements that of SwissTM with the serial number and user-thread identifier of the task that owns the write-log entry, as well as links to entries from past tasks which also wrote to that entry's location.

There are two possible branches for a read operation on a location, depending on whether the location is write-locked by the task's own user-thread or not. If the location is not write-locked by the task's user-thread, i.e. the location is either write-locked by another user-thread or unlocked, TLSTM follows the same procedure as SwissTM: the task reads the location's committed value from memory (line 16 alg. 1).

If, otherwise, the location has been write-locked by the task's user-thread, the task needs to read from the most recent speculative value. This value was either written by the task itself or a past task. The task traverses the redo-log until it finds the entry the task itself wrote to, or a past task wrote to (line 8 alg. 1). If it was the task itself to write to that location, the task can simply return the written value (line 10 alg. 1), since the task's reads from its own writes do not need to be validated.

If, instead, the last speculative value was written by a past task, the task first checks if that past task has already completed. If the past writer task has not completed yet, the task waits until the past task has completed in order to proceed (line 11 alg. 1). TLSTM implements this restriction to simplify the WAR conflict validation procedure. This procedure would have to additionally check the number of writes a past task had performed on the location, in order to validate intra-thread reads done from running tasks.

Afterwards, the task performs validation looking for WAR conflicts, which may have occurred between the current task and the past task that just completed (line 13 alg. 1). If all went well, the task creates a new entry in the task-read-log and adds the location and the validation information (task's serial number) to that log (line 14 alg. 1).

In order to detect dangerous inconsistent reads that could crash the application TLSTM uses several known techniques from previous STLSs [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF].

Writing. The task starts by checking if the location has been write-locked by the task itself (line 36 alg. 2). If it has, it just needs to update the logged value, like SwissTM does.

If this is not the case, three situations may occur, depending on whether the lock is:

Write-locked by another task from the same user-thread. If the location is write-locked by a future task, the future task is signaled to abort, since the task is from the past of the location's current writer in program order (line If the location is write-locked by a past task, TLSTM needs to check if that past task has already completed (line 45 alg. 2). If the past task is still running, the task will rollback since it is from the future of the location's current writer in program order. If the past task has completed, TLSTM locks the location for writing and adds a new entry to the redo-log which previously owned the write-lock (line 51 alg. 2).

Write-locked by a task from another user-thread. In this case (line 41 alg. 2), the task calls the contention manager in order to decide whether the writer task or the current owner of the write-lock must abort. If the contention manager decides the owner of the write-lock must abort, the writer task waits until the write-lock is eventually unlocked.

Unlocked. This means the present task is the only active task writing to that location. Here the task atomically locks the location's write-lock by compare-and-swap, creates a new redo-log that owns the location, assigns the redo-log to the write-lock and continues. Finally, the task performs inter-thread validation, just like SwissTM. Additionally, the task performs intra-thread validation looking for WAR conflicts that may have occurred in the meantime.

Commit. The commit of a user-transaction is carried out by its last task (in program order), called the commit-task , once the commit-task and all preceding tasks have completed (line 66 alg. 3). The commit step is very similar to SwissTM, with a few modifications. The commit-task must now consider the read-logs and write-logs of every task of the user-transaction (and not just its own logs) when validating read-logs or committing writes.

Every user-transaction now needs to check for possible validation at commit time, whereas on SwissTM only write user-transactions needed to (line 78 alg. 3). The reason why read user-transactions can no longer proceed without checking for validation is because each task of the user-transaction may have completed at different points in time. This means some tasks of the same user-transaction may have different valid-ts values, thus TLSTM cannot rely on the commit-task's valid-ts alone. If all tasks of a user-transaction have the same valid-ts, then the commit-task can skip this validation.

The commit of the user-transaction then proceeds as in SwissTM, locking the write-logs' read-locks (line 82 alg. 3), incrementing the commit timestamp and validating the user-transaction (line 85 alg. 3). Then, the commit-task updates the values in main memory with the new values from the write-logs of all the user-transaction's tasks (line 89 alg. 3). At the end, the commit-task releases the read and write locks associated with the updated values (line 92 alg. 3).

Finally, the commit-task updates the completed-writer counter if it belongs to a write user-transactions, and updates the completed-task counter to signal the completion of the task and user-transaction (line 93 alg. 3).

Intermediate tasks of a user-transaction just have to update the completedwriter counter, if they have written anything, and the completed-task counter (line 74 alg. 3). Then, they start waiting until all future tasks of the user-transaction have completed, and thus the user-transaction has committed, so that the task can exit safely. Aborts. Aborting a single task follows the same procedure of SwissTM's usertransaction abort. TLSTM needs to abort a single task when an intra-thread WAR or WAW conflict is detected. Intra-thread WAW conflicts are checked for in two distinct places. First, WAW conflict verification is performed when a task wishes to write to a location (line 34 alg. 2). TLSTM could perform this verification on read operations too, but that would incur in more overhead for the most common read operation. Second, TLSTM checks for intra-thread WAW conflicts at commit time, while waiting for all past tasks to complete. When all past tasks have completed and the task has not aborted due to a WAW conflict, the task needs to be validated for previously undetected WAR conflicts (as explained in Section 3.2). If WAR conflict validation fails, the task must be individually aborted.

There are also situations where a task may need to abort its entire usertransaction (every single task of the user-transaction to which the aborting task belongs to) because of an inter-thread write-write conflict. The first situation occurs at commit time, if the task passed WAR conflict validation (line 68 alg.

3). The second situation occurs also at commit time, while an intermediate task waits for the future tasks of its user-transaction to commit (line 76 alg. 3).

We chose to abort every single task of the aborting user-transaction because of the simplicity of this approach. The alternative would be to abort only the user-transaction's tasks that wrote to the location that triggered the write-write conflict, and the user-transaction's tasks that read those speculative values. Discovering all these tasks would be very complex, since TLSTM would need to traverse the write-log of each task in the user-transaction in search of the location that triggered the abort and mark those tasks for abort. Then TLSTM would need to traverse the task-read-log of each task of the user-transaction in search for the locations written by the tasks marked to abort and also mark the tasks where TLSTM finds those locations.

Evaluation

This section evaluates a TLSTM prototype, which was implemented in C++, based on the C++ implementation of the SwissTM STM, using POSIX threads. The measurements discussed next were obtained using a quad AMD Opteron 6272 with 64 cores total for the STAMP Vacation application and a SPARC Enterprise T5120 server with up to 64 hardware threads for the remainder of the benchmarks. Each result measures the throughput of the respective runtime in operations per second and is the average of three repeated experiments.

We want to determine answers to two main questions: 1) can our unified TLS+STM approach effectively achieve speed-up from simple STM programs? ; and 2) in which kind of applications is TLSTM more advantageous, and in which applications is it not a good approach?

We started by looking at a modified version of the traditional Red-black Tree micro-benchmark in order to figure out if task size had any impact on the unified runtime's performance. In this modified version each thread runs a transaction that performs a number of lookup operations, which are read-only, to the Red-Black Tree. We can easily split those transactions into several tasks that execute fewer operations each, e.g. if a transaction runs four operations in total, we can split it into two tasks that run two operations each.

From this experiment we can see that task size does indeed have an impact on the runtime's performance (Figure 1.a). For larger task sizes we obtain a better throughput ratio, for both two and four tasks per user-thread, from which we can deduce that our approach has better performance in applications with large transactions which can be split into large tasks.

Therefore, we started looking at the STAMP application suite [START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF] in search of applications with large transactions that could be easily split into several parallel tasks. However, most of STAMP's applications had either very small transactions or no further parallelization potential. One application stood out though, the Vacation application which implements an online transaction processing system for travel reservations. A client can issue several operations to the system, e.g. reserve a plane ticket, reserve an hotel or rent a car, and each operation is encapsulated in a transaction.

Since these operations are quite small, similar in size to the red-black tree micro-benchmark operations, we modified the Vacation benchmark taking into account the red-black tree results. We picture each client issuing eight operations at a time, which now incorporate an application server transaction and can be easily split into two tasks, executing four operations each. We still mimic the low and high contention scenarios of the original Vacation application.

The results of this experiment (Figure 1.b) show us that a unified TLS+STM runtime using two task per user-thread improves the throughput of applications with a self-imposed limit to the number of spawned user-threads, in this case the number of concurrent clients being served. Interestingly, both low and high contention scenarios of this application show the same behavior, which we assume to occur because of the very low contention between operations, even in the higher contention scenario. We can also see that TLSTM with one task per userthread has a very similar throughput to SwissTM, with both lines overlapping most of the time, on both scenarios. This suggests that there are applications where TLSTM can be used as a replacement to SwissTM.

Another interesting reference benchmark for STMs that includes large transactions is STMBench7 [START_REF] Guerraoui | Stmbench7: a benchmark for software transactional memory[END_REF], which has a wide range of operations on a very large shared data structure. From these operations we targeted those which could be automatically split into tasks by a compiler or runtime, in which the set of "Long Traversals" operations stood out. It was also the most computationally intensive set of operations, which made it a perfect candidate to parallelize even further. Most of the remainder operations were either non-divisible or very short, so they would not benefit from parallelization too much. The shared data structure of STMBench7 is built as a tree of objects, with three branches departing from the root, each with arbitrary depth. Therefore, it made sense to split the "Long Traversals" which traverse the whole tree in multiples of three tasks. The experiment on figure 2.a compares the performance of running one and three user-threads in SwissTM to one user-thread in TLSTM with three tasks. By comparing TLSTM with three tasks and one user-thread to SwissTM with three user-threads we can see how much does the programmer gain if he is capable of hand-parallelizing more code into transactions, instead of relying on automated code division and a unified TLS+STM runtime. But if he does rely on such a runtime, we can see that TLSTM is most beneficial for read-dominated workloads. In fact, for 100% read-only transactions TLSTM achieves practically full speedup. In contrast, TLSTM already performs worse than the base STM for write-dominated workloads.

The problem lies within STMBench7's write "Long Traversals". These writetransactions have a high intra-thread conflict rate (several tasks writing to the same location). Such conflicts translate into the observed decrease in performance, since these transactions will execute almost serially. This is the worst case scenario for TLSTM. In write-transactions with a low conflict rate, such as those of the STAMP's Vacation application, we see that TLSTM performs close to the observed behavior on read-only transactions.

For the last of our experiments, we consider the default settings that STM-Bench7 originally defines [START_REF] Guerraoui | Stmbench7: a benchmark for software transactional memory[END_REF]: write-dominated workload (10% read operations); read-write workload (60% read operations); and read-dominated workload (90% read operations).

This last experiment aims at studying how TLSTM behaves as the number of user-threads grows, and how such performance compares to SwissTM running the same number of user-threads. We can see in figure 2.b that TLSTM with three tasks decreases its performance when going from two to three user-threads, whereas SwissTM scales quite acceptably on read-write and read-dominated workloads. This is an effect of the increased contention in the workload. The inter-thread abort procedure is substantially more complex in TLSTM than in SwissTM, thus hindering its performance in scenarios where contention is higher (more conflicts and rollbacks).

However, we can see that for read-dominated workloads TLSTM with three tasks outperforms SwissTM by 80% on one user-thread and 48% on two userthreads. By increasing the number of user-threads we increase the level of contention even further, thus providing diminishing returns. When executing an inter-thread abort, all of the user-thread's tasks must be aborted. Thus, the inter-thread abort procedure's performance is directly influenced by the number of tasks in the user-thread. In order to measure this influence, we experimented on TLSTM with nine tasks and up to three user-threads (Figure 2.b).

In the case of one user-thread in the read-dominated workload, we can achieve even more speedup with nine TLSTM tasks than with three. But as soon as we get to use two user-threads, the inter-thread contention becomes high enough to harm TLSTM's performance. We can see this is a trend for increasing numbers of user-threads, on any type of workload. This fact suggests that the interthread abort procedure is one of the major bottlenecks in the unified approach of TLSTM.

We conclude that each application using TLSTM will have to find a sweet spot between the number of user-threads and tasks in use. Too many userthreads may prevent scalability of the application, while too many tasks may dramatically hinder the performance of the hybrid runtime. For STMBench7's "Long Traversals" this spot seems to be two user-threads with three tasks each, in order to achieve maximum performance.

Related Work

Originally introduced in the seminal paper from Herlihy and Moss [START_REF] Herlihy | Transactional memory: Architectural support for lockfree data structures[END_REF], the interest and advancement in the STM area has grown dramatically in recent years, incited by the advent of affordable multicore processors. Still, most STM programs are still organized as a monolithic collection of a relatively small number of coarsegrained threads. Evidence of this is found in most benchmarks (e.g. [START_REF] Guerraoui | Stmbench7: a benchmark for software transactional memory[END_REF][START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF][START_REF] Gajinov | Quaketm: parallelizing a complex sequential application using transactional memory[END_REF][START_REF] Watson | A study of a transactional parallel routing algorithm[END_REF]) and representative applications of STM.

A distinct research direction that has similar goals as STM is automatic parallelization of sequential programs. Classically, this approach focused on automatically identifying tasks that have no data dependencies (e.g. independent loop iterations) and executing them in parallel. On the other hand, the approach of Thread-Level Speculation (TLS) developed over the last decade has a more aggressive technique for extracting parallelism from sequential programs [START_REF] Sohi | Multiscalar processors. In: 25 years of the international symposia on Computer architecture[END_REF][START_REF] Hammond | Data speculation support for a chip multiprocessor[END_REF][START_REF] Steffan | A scalable approach to threadlevel speculation[END_REF][START_REF] Steffan | The stampede approach to thread-level speculation[END_REF][START_REF] Liu | Posh: a tls compiler that exploits program structure[END_REF]. Rather than parallelizing only provable independent tasks, TLS executes tasks in parallel speculatively and relies on the runtime detection of violations to the sequential semantics of the original program to discard the changes to the program state and restart the affected tasks.

While the first proposed TLS solutions relied on hardware support, recently there has been a growing focus on software approaches. Solutions such as [START_REF] Kim | Scalable speculative parallelization on commodity clusters[END_REF][START_REF] Oancea | Software thread-level speculation: an optimistic library implementation[END_REF][START_REF] Devabhaktuni | Softspec: Software-based speculative parallelism via stride prediction[END_REF][START_REF] Cintra | Toward efficient and robust software speculative parallelization on multiprocessors[END_REF][START_REF] Rundberg | An all-software thread-level data dependence speculation system for multiprocessors[END_REF][START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF] are examples of successful efforts towards Software TLS that can yield substantial speed-ups from sequential programs. Still, the conservative nature of TLS constitutes a key limitation to the level of parallelism that it can extract. While proposed TLS systems have been shown to achieve considerable speed-ups (e.g. 77% on average according to Oancea et. al. [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF]), most non-trivial programs that do not fit in the category of embarrassingly parallel problems have relatively low bounds on the level of conflict-free speculation.

Most of the run-time support of Software TLS has close resemblance with an STM run-time. For instance, writes are speculative, as they may need to be undone; accesses must be validated for conflicts; tasks have a commit stage; and tasks can be aborted, and restarted. Departing naturally from such an observation, a number of recent Software TLS solutions rely on an underlying simplified STM run-time to offer TLS to single-threaded programs [START_REF] Mehrara | Parallelizing sequential applications on commodity hardware using a low-cost software transactional memory[END_REF]. These solutions are radically different than our proposal: while TLSTM combines STM and TLS, allowing each thread in a transactional multi-threaded programs to be automatically parallelized, TLS solutions relying on STM only address the case of single-threaded programs.

To the best of our knowledge, the only work that addresses TLS support on multi-threaded programs is due to Martinez and Torrelas [START_REF] Martínez | Speculative synchronization: applying thread-level speculation to explicitly parallel applications[END_REF]. However, their approach is fundamentally different from ours, as it only tries to speculatively execute and synchronize threads that would otherwise be blocked waiting on a barrier, lock or flag. Unifying STM and TLS in a common run-time implies solving a number of fundamentally different problems.

In the context of replicated STMs there are some recent examples of systems that employ automatic speculative parallelization to hide the expensive latency of distributed transaction commit [START_REF] Kemme | Using optimistic atomic broadcast in transaction processing systems[END_REF][START_REF] Palmieri | Osare: Opportunistic speculation in actively replicated transactional systems[END_REF]. In contract to our contribution, these solutions are proposed in a distinct context (distributed STMs) and limit speculation to one transaction that runs in parallel while the preceding transaction is awaiting commitment.

Concluding Remarks

The rapidly increasing core count of commodity machines is demanding highly parallel programs. We claim that the time has come to question a hybrid direction that unifies two prominent research directions of parallel programming that, up to now, have been working (almost) separately with very similar goals.

This paper shows that, although unifying TLS and TM in a hybrid middleware introduces hard challenges, they can be overcome and untapped parallelism potential can be discovered. We describe our experience with a first proof of concept, the TLSTM algorithm. Our results obtained with trivial and non-trivial benchmarks confirm that STM and STLS do add up successfully for some workloads. Our results also show that there is still a considerable amount of improvement to be made towards devising a unified STM+STLS solution that scales gracefully with both the number of hand-parallelized threads and the number of automatically spawned speculative tasks.

Our preliminary work shows that issues such transaction rollback and commit are now much more complex (due to the multiple tasks that may comprise each user-transaction), and future work should focus on their negative impact on the overall throughput. The location redo-logs have also showed to add substantial overhead. Hence, different approaches for handling speculative writes (e.g. in-place writes [START_REF] Oancea | A lightweight in-place implementation for software thread-level speculation[END_REF]) should be studied.

Algorithm 1 : 16 returnAlgorithm 2 :

 1162 Pseudo-code representation of TLSTM 1 function start(serial, program-thread-id, try-commit, start-serial, commit-serial) 2 task-init(serial, ptid, try-commit, start-serial, commit-serial); 3 last-writer ← uthread[tsk.ptid].completed-writer; 4 tsk.valid-ts ← commit-ts; 5 function read-word(tsk, addr) 6 (r-lock, w-lock) ← map-addr-to-locks(addr); 7 if is-locked-by-my-thread(w-lock, tsk) then 8 while w-lock and w-lock.serial > tsk.serial do 9 w-lock = w-lock.previous-entry; 10 if w-lock.serial = tsk.serial then return read(addr); 11 while uthread[tsk.ptid].completed-task < w-lock.serial -1 do 12 if abort-transaction then rollback(tsk); 13 if uthread[tsk.ptid].completed-writer > last-writer and not validate-task(tsk) then rollback(tsk); 14 add-to-task-read-log(tsk, w-lock, w-lock.serial); 15 return read(addr); SwissTM-read-commited-value(addr); 17 function validate-task(tsk) 18 for log-entry in tsk.task-read-log do 19 if is-locked-by-my-thread(log-entry.w-lock) then 20 w-lock = log-entry.w-lock; 21 if w-lock.serial = tsk.serial then 22 w-lock = w-lock.previous-entry; 23 if w-lock = N U LL or log-entry.serial = w-lock.serial then 24 return false; 25 else return false; 26 for log-entry in tsk.read-log do 27 if is-locked-by-my-thread(log-entry.w-lock) then w-lock = log-entry.w-lock; 28 while w-lock do 29 if w-lock.serial >= serial then 30 w-lock = w-lock.previous-entry; Pseudo-code representation of TLSTM 33 function write-word(tsk, addr, value) 34 if aborted-internally then rollback(tsk); 35 (r-lock, w-lock) ← map-addr-to-locks(addr); 36 if is-locked-by-my-task(w-lock, tsk) then

Fig. 1 .

 1 Fig.1. a) Speedup in the red-black tree's throughput for TLSTM with 2 and 4 tasks and 1 thread vs SwissTM with 1 thread; b) Throughput of TLSTM with 1 and 2 tasks per thread vs SwissTM, with an increasing number of threads on STAMP's Vacation

Fig. 2 .

 2 Fig. 2. a) Throughput of TLSTM with 1 thread and 3 tasks vs SwissTM with 1 thread and 3 threads; b) Throughput of SwissTM vs TLSTM with 3 and 9 tasks per thread, with up to 3 threads; Both on STMBench7 long traversals only

This work was partially supported by FCT (INESC-ID multi-annual funding) through the PIDDAC Program funds and by FCT project specSTM (PTDC/EIA-EIA/122785/2010). Contact author.

Open source available at http://www.gsd.inesc-id.pt/project-pages/specSTM

rollback(tsk);