New hardware support transactional memory and parallel debugging in multicore processors

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Departamento de Electrónica e Computación Centro de Investigación en Tecnoloxías da información (CITIUS) PhD Dissertation NEW HARDWARE SUPPORT FOR TRANSACTIONAL MEMORY AND PARALLEL DEBUGGING IN MULTICORE PROCESSORS Author: Lois Orosa Nogueira Phd Advisors: Javier Díaz Bruguera Elisardo Antelo Suárez Santiago de Compostela, June 2013 Javier Díaz Bruguera, Profesor Catedrático de Universidade da Área de Arquitectura e Tecnoloxía de Computadores da Universidade de Santiago de Compostela Elisardo Antelo Suárez, Profesor Titular de Universidade da Área de Arquitectura e Tecnoloxía de Computadores da Universidade de Santiago de Compostela FAN CONSTAR: Que a memoria titulada NEW HARDWARE SUPPORT FOR TRANSACTIONAL MEMORY AND PARALLEL DEBUGGING IN MULTICORE PROCESSORS foi realizada por D. Lois Orosa Nogueira baixo a nosa dirección no Departamento de Electrónica e Computación e no Centro Singular de Investigación en Tecnoloxías da Información (CITIUS) da Universidade de Santiago de Compostela, e constitue a Tese que presenta para optar ao grado de Doutor pola Universidade de Santiago de Compostela. Santiago de Compostela, Xuño 2013 Javier Díaz Bruguera Codirector da tese Elisardo Antelo Suárez Codirector da tese Lois Orosa Nogueira Autor da tese Aos meus pais Everything that can be invented has been invented. Charles H. Duell, U.S. patent office, 1899 It would appear that we have reached the limits of what it is possible to achieve with computer technology, although one should be careful with such statements, as they tend to sound pretty silly in 5 years. John Von Neumann, 1949 O verdadeiro heroísmo está en transformar os desexos en realidades e as ideas en feitos. Castelao Acknowledgements Five years ago I gave a radical turn to my life: I quit a stable job in a private company to start this research adventure. The way was long, it had ups and downs, but at the end, it was worth it. It was an invaluable experience that changed and marked me forever, personally and professionally, and I would not have been able to do it alone. It is at this point that I want to thank all the people that made this thesis possible. First of all, and the most important, I want to thank my advisors Elisardo Antelo and Javier Bruguera. They trusted in me from the beginning of this adventure, and we start and finish this trip together. Without them, this thesis would simply not be possible. Their constant support was essential to finish it, as also the advices and motivating talks of Elisardo. Thank you very much. To Professor Josep Torrellas, who supervised my work in my stay in the University of Illinois at Urbana-Champaign, and to all the members of his group for their kind welcome. Special thanks to Shanxiang Qi and Norimasa Otsuki for the good work environment and the intriguing discussions. To the people of IBM R&D research Lab in Haifa for their friendly welcome during my HiPEAC internship there. My acknowledgements goes specially to Olga Golovanevsky, Marina Biberstein and Bilha Mendelson for their daily support and the motivating work made there. To Recore Systems, specially to Gerard Rauwerda, for trusting me to perform a very engaging project during my HiPEAC internship, and to John Donker, Jordy Potman and Eduard Fernández for their every day support and knowledge, which enriched my stay. I also want to express my gratitude with the funding institutions. The work related to this PhD thesis was partially supported by the Spanish Ministry of Science and Education under Project TIN2007-67537-C03-01. I also wish to thank the European Network of Excellence on 2 List of Figures Fig. 3.9 Speed-up of LogTM-SE + CFM-TM. . . . . . . . . . . . . . . . . . . . . . 86 Fig. 3.10 Variation of L1 cache misses when the CFM-TM is activated. . . . . . . . . 86 Fig. 3.11 Normalized breakdown of execution cycles. . . . . . . . . . . . . . . . . . 88 Fig. 3.12 Benchmarks breakdown. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Fig. 4.1 Examples of asymmetric data races where the unsafe thread can proceed (OK)ornot(NOTOK). ............................ 94 Fig. 4.2 Overview architecture of Pacman. . . . . . . . . . . . . . . . . . . . . . . . 96 Fig. 4.3 Examples to understand the Pacman’s operation. . . . . . . . . . . . . . . . 98 Fig. 4.4 Examples to understand Cache State Prior to Entering the Critical Section. . 98 Fig. 4.5 Examples of data race bugs which lead to deadlock. . . . . . . . . . . . . . 101 Fig. 4.6 Breaking atomicity due to false sharing. . . . . . . . . . . . . . . . . . . . . 102 Fig. 4.7 Pacman Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Fig. 4.8 Execution time overhead of Pacman. . . . . . . . . . . . . . . . . . . . . . 113 Fig. 4.9 An asymmetric race in "Bodytrack" benchmark. . . . . . . . . . . . . . . . 114 Fig. 4.10 An asymmetric race in "FMM" benchmark. . . . . . . . . . . . . . . . . . . 114 Fig. 5.1 Block diagram of FlexSig............................ 120 Fig. 5.2 FlexSig module architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Fig. 5.3 Insertion, check and deallocation request in FlexSig.............. 122 Fig. 5.4 Example of the symmetric allocation algorithm of FlexSig........... 123 Fig. 5.5 Example of conventional signatures used in a system with a maximum of 16 simultaneous signature requesters. . . . . . . . . . . . . . . . . . . . . . . . 123 Fig. 5.6 False positive rate in FlexSig for different signature sizes. . . . . . . . . . . 126 Fig. 5.7 Example of register grouping. . . . . . . . . . . . . . . . . . . . . . . . . . 127 Fig. 5.8 Parallel controller implementation. . . . . . . . . . . . . . . . . . . . . . . 130 Fig. 5.9 Percentage of decrease of the absolute number of false positives in FlexSigconf1 compared with conventional signatures for all benchmarks. . . . . . . 136 Fig. 5.10 Percentage of decrease of the absolute number of false positives in FlexSigconf2 compared with conventional signatures for all benchmarks. . . . . . . 136 Fig. 5.11 Increment of the signature size in FlexSig-conf2................ 138 Fig. 6.1 Example of an asymmetric R/W allocation algorithm. . . . . . . . . . . . . 146 Fig. 6.2 Example of an asymmetric allocation algorithm based on transaction identifier. 148 List of Figures 3 Fig. 6.3 Example of an asymmetric allocation algorithm combining PCOUT and PCINpriorityclasses. ............................. 149 Fig. 6.4 The basic FlexSig elements in a two-way implementation (issue 2 instructions). 150 Fig. 6.5 Generation of the allocation signal and the update of the registers that count the number of transactions. . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Fig. 6.6 Calculation of the maximum number of Bloom filters for high and low prioritytransactions............................... 154 Fig. 6.7 Calculation of the maximum number of Bloom filters per signature, depending on its priority and the priority of the transaction which it belongs. 154 Fig. 6.8 Control logic for each Bloom filter. . . . . . . . . . . . . . . . . . . . . . . 156 Fig. 6.9 Generation of the Nxvalues with a parallel prefix popcount compressor tree. 157 Fig. 6.10 Percentage of decrease of false positives in symmetric FlexSig. . . . . . . . 161 Fig. 6.11 Percentage of decrease on false positives in FlexSig with asymmetric allocation policies (PCIN priority class). . . . . . . . . . . . . . . . . . . . 162 Fig. 6.12 Percentage of reduction of false positives for single PCIN priority and for Multiple (one per transaction) PCIN priorities. . . . . . . . . . . . . . . . . 164 Fig. 6.13 Percentage of decrease on false positives in FlexSig implementing priorities for PCIN priority class, for PCOUT priority class, and combining both PCIN and PCOUT priority classes. . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Fig. 6.14 Percentage of decrease of false positives in asymmetric FlexSig (PCIN priority class) with up to 128 threads. . . . . . . . . . . . . . . . . . . . . . 167 Fig. 6.15 Number of bits required for registers in asymmetric FlexSig (PCIN priority class) and Bloom signatures. . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Fig. 6.16 Percentage of decrease of false positives in asymmetric FlexSig implementing the PCIN priority class, compared with Bloom and ASYM signatures. ................................... 170 List of Tables Tabla 2.1 System configuration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Tabla 2.2 RSTM implementations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Tabla2.3 Benchmarks. ................................. 62 Tabla 3.1 Workload characteristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Tabla 3.2 Benchmark inputs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Tabla 3.3 Signature’s size configuration with and without CFM-TM. . . . . . . . . . 84 Tabla 4.1 Real examples of harmful asymmetric data races. . . . . . . . . . . . . . . 93 Tabla 4.2 Size of the SigTable’s fields. . . . . . . . . . . . . . . . . . . . . . . . . . 104 Tabla 4.3 Default architecture parameters. . . . . . . . . . . . . . . . . . . . . . . . 108 Tabla 4.4 SigTable parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Tabla 4.5 Characteristics of the critical sections (CS) in the applications. . . . . . . 110 Tabla 4.6 Quantification of the overheads. . . . . . . . . . . . . . . . . . . . . . . . 112 Tabla 5.1 Benchmark Inputs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Tabla 5.2 Benchmark set A, characterization with 16 threads. . . . . . . . . . . . . . 132 Tabla 5.3 Benchmark set B, characterization with 16 threads. . . . . . . . . . . . . . 133 Tabla 5.4 Configuration used with unified signatures. . . . . . . . . . . . . . . . . . 133 Tabla 5.5 Benchmark Set A. False positives comparison (in %) for Unified Signatures. 134 Tabla 5.6 Benchmark Set B. False positives comparison (in %) for Unified Signatures. 134 Tabla 6.1 Values calculated by FlexSig in the examples of the Figures 6.1, 6.2 and 6.3. 146 Tabla 6.2 Benchmark Inputs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Tabla 6.3 Size of the read and write sets for different benchmarks. . . . . . . . . . . 159 6 List of Tables Tabla 6.4 Configuration of the signatures used. . . . . . . . . . . . . . . . . . . . . . 160 Tabla 6.5 s_f actorin (prioHighin|prioLowin) for 2, 4, 8 and 16 threads. . . . . . . . 161 Tabla 6.6 Priorities used for single and multiple PCIN priorities. . . . . . . . . . . . 163 Tabla 6.7 s_f actor used to evaluate both PCOUT and PCIN priority classes. . . . . . 165 Tabla 6.8 s_f actorin used to evaluate the scalability of FlexSig............. 166 Tabla 6.9 Configuration of FlexSig and Bloom signatures. . . . . . . . . . . . . . . . 167 Tabla 6.10 Number of Bloom filters for read and write set in ASYM signatures. . . . . 170 Preface In the multicore era, parallel programming is becoming a must for general purpose programmers. However, the parallelization of programs is not intrinsically intuitive and prone to errors. To face these drawbacks, new tools have arisen to make this task easier by providing new programming models and debugging tools. Usually, these new tools add complexity that needs to be addressed with hardware support to achieve a good performance. Transactional Memory and data race detection are two of the most popular. Transactional Memory (TM) is a software abstraction to make parallel programming easier, by providing an abstraction less prone to errors than locks. TM provides an speculative synchronization mechanism to the programmer, who has to enclose critical sections in transactions which will be executed atomically and in isolation by the TM system. Furthermore, transactions are executed in parallel and speculatively, so it is pretty common to use hardware support to accelerate the system. A data race occurs when two or more threads access the same shared variable without the proper synchronization. Data races can produce errors which are very difficult to debug, because it is usual that the error manifests itself much later than the actual race is produced. Therefore, to efficiently detecting these bugs has become very important, and also for these tools, it is not strange to use hardware support to not degrade the performance of the system. Among the hardware resources for accelerating this kind of tools, one of the most generally used in research papers, and therefore, with a lot of potential to be included in future general purpose processors, are signatures. Signatures are a fixed piece of hardware that can host an unbounded number of addresses in a bounded space. To do that, each address is hash encoded and inserted in the signature, which may produce aliasing among address. This leads to the possibility of reporting false positives when the signature checks for the ownership of an address. However, it never reports false negatives. 8 Preface This thesis contributes with new hardware support for TM and data race detection in multicore processors. The hypothesis to build this thesis are: – Hardware signatures are not optimized for the many applications and tools that use them (very different ones in the same system). – Signatures can be used in a large number of applications related with parallel programming of multicore processors, and some of them are unexplored. – Signatures are a promising hardware resource because of their efficiency, but they have drawbacks that have not been explored: they are not flexible to adapt to the different requirements of the applications and tools that may require them in a multicore processor. Under this hypothesis, we set up and perform experiments to address these observations and problems. In Chapter 3 we configure a Hardware Transactional Memory (HTM) system where signatures are part of the hardware support and we propose a new hardware filter based on minor modifications of the hardware, which allows a considerable reduction of the signature size either their false positive rate (we call this filter CFM-TM). Under certain circumstances, the performance of the system is also significantly improved. We observe from this work that to optimize the resources and the false positive rate, we require signatures with different sizes. In Chapter 4 we build the first hardware asymmetric data race detector (which also tolerates these races), called Pacman 1. Asymmetric data races are a very common type of data race that may cause dangerous concurrent bugs, and that until this work, have only been explored as a software approach. The hardware support of our detector is essentially based on a centralized module of hardware signatures. We demonstrate that Pacman introduces negligible slowdowns in the system, and that it is able to efficiently detect and tolerate asymmetric data races. Chapter 5 and Chapter 6 propose a novel hardware signature module (called FlexSig) that solves some of the problems that we found when building the previous tools for multicore architectures based on signatures. Specifically, we design a signature module that can host a large number of signatures when there is a high demand of signatures, and it can also achieve 1This work was developed at the University of Illinois at Urbana-Champaign in collaboration with the members of the I-ACOMA group. Preface 9 a very low false positive rate when the demand of signatures is modest. We explore several strategies to allocate signatures in FlexSig to adapt to the different characteristics of the tools and applications that use them. Summarizing, we optimized the use of signatures in a HTM system by introducing our CFM-TM filter, we developed a new debugging tool with signatures as main hardware support, and we built a new hardware signature module that allows a great flexibility in the size and number of signatures allocated. This fits in a real scenario represented by a general purpose multicore processor executing a wide range of signature-demanding applications and tools. We have gathered the contributions in the next publications: Lois Orosa, Javier D. Bruguera, and Elisardo Antelo. A Cache Filtering Mechanism for Hardware Transactional Memory Systems Decoupled from Caches. In XX Jornadas de Paralelismo, A Coruña (Spain), September 2009. Shanxiang Qi, Norimasa Otsuki, Lois Orosa, Abdullah Muzahid, and Josep Torrellas. Pacman: Tolerating Asymmetric Data Races with Unintrusive Hardware. In High Performance Computer Architecture (HPCA), 2012 IEEE 18th International Symposium on, pages 1 –12, feb. 2012. Lois Orosa, Elisardo Antelo, and Javier D. Bruguera. Flexsig: Implementing Flexible Hardware Signatures.ACM Trans. Archit. Code Optim., 8(4):30:1–30:20, January 2012. Lois Orosa, Javier D. Bruguera and Elisardo Antelo. Asymmetric Allocation in a Flexible Signature Module for Multicore Processors.Submitted. CHAPTER 1 INTRODUCTION Sequential single-core wide superscalar processors were the dominant architecture in commodity products during many years for their capacity of improving performance by just scaling the clock frequency (with contributions from both technological and pipeline depth scaling), and keeping the cycles per instruction. The software for these processors is an ordered sequence of instructions, being easy to write and reason about it, and therefore, the performance scales naturally with clock frequency. Parallel computers were already used many years ago, but mainly for scientific applications. The programming skills required were very high because of the difficulty of debugging and reasoning about parallel programs. Nowadays, parallel architectures have become a mainstream research topic among industry and academia for general purpose computing, specially focusing on integrating many processor units in the same chip (multicore processor). The interest in multicore architectures arose mainly for two reasons: the Instruction Level Parallelism (ILP) was no longer cost effective (ILP wall), and the power consumption resulting from increasing the clock frequency started to become a limiting effect (Power Wall). Multicore processors encourage thread parallelism, that scales better than ILP (if the applications are efficiently parallelized), and also allows us to maintain the clock frequency in moderate rates and improve performance by augmenting the number of cores in the chip. However, there is another problem that could limit the multicore scaling: not all the transistors of the chip can be powered at the same time because of power limitations; the area of the chip that can not be powered is known as dark 18 Chapter 1. Introduction ily interleaved. Although sequential consistency presents a simple programming paradigm, its implementation reduces the performance, specially when the number of cores in the processor is high. There are some examples of parallel architectures with a sequential consistency model [29] [90]. Relaxing the consistence memory model is the way to improve performance and to reduce hardware overhead. The idea is to allow reads and writes to update main memory or a shared cache out of program order, and to use synchronization operations (introduced by the programmer) to enforce ordering, so that a synchronized program behaves as a sequentially consistent processor. There are a variety of relaxed models that are classified by the relaxed read and write orderings. Sequential consistency requires maintaining all possible orderings: R->W (a write can not be executed until preceding reads have been completed), R->R (a read can not be executed until preceding reads have been completed), W->R (a read can not be executed until preceding writes have been completed) and W->W (a write can not be executed until preceding writes have been completed). The total store ordering (TSO) [74] is characterized for relaxing the W->R; because this ordering retains ordering among writes, many programs that operate under sequential consistency operate under this model without extra synchronization. The partial store order (PSO) [74] relaxes the W->W ordering. The release consistency (RC) [55] relaxes R->W and R->R. By relaxing these orderings, the processor can achieve performance advantages over sequential consistency at the cost of more programming and debugging effort. 1.2 Parallel Programming Architectures with many cores in the same chip scale their performance with the number of cores only if the software executed is parallelized efficiently. For parallel programming success among general purpose programmers, it has to be easy to code, debug, and easily understood by an average programmer (not an expert in parallel programming). The natural way of thinking about algorithms to solve problems is sequentially. The solution of a problem is always envisioned as a series of steps that are performed one after the other, and many times parallelism is not an option for many programmers. Changing the mentality into parallel reasoning is a challenge that should be driven through new software abstractions and tools (easy to understand), and efficient parallel debugging tools. 1.2. Parallel Programming 19 However, programs usually have sections of code that can not be parallelized. The Amdahl law [7] states that the theoretical maximum speedup of a program using multiple cores is limited by the time needed for the sequential fraction of the program (and the overhead introduced by parallelization, such as synchronization or message latencies). Therefore, the performance of a parallel program does not depend only on the hardware architecture, but also on the amount of parallelizable sections of code, and in the ability of the programmer to identify and efficiently parallelize these sections. To get an idea of why parallel programming is difficult, we will expose some ideas that are advocated by several authors [166][56]. Below, we depict some historical facts which impacted parallel programing. – The community concentrated on improving performance instead of reducing software development cost. – Early parallel machines had poor support for communication among processors, and much of the compiler and programming effort was to reduce communications cost, rather than high level ideas about how to simplify applications and algorithms. – The emphasis was to produce simple modifications to sequential languages, such as adding libraries, rather than thinking in parallelism from scratch. These could be some reasons that explain the current state of the art in parallel programming. Furthermore, parallel programming is also intrinsically difficult because: –Finding parallelism might be difficult and add programing complexity. There are some steps needed to create a parallel program not needed in sequential codes, such as synchronization issues, concurrency detection, task decomposition, load balancing, etc. –It is error-prone. To decompose the problem or algorithm into tasks may lead to errors (main problems are synchronization and non deterministic data races). With several threads running concurrently, and accessing the same data, a new type of bug is introduced: the data races. The threads have to be perfectly coordinated and synchronized to avoid them. –Tuning performance. In the world of multicore processors, things like cache behavior, how the cores are connected, etc. makes a much bigger difference for performance. Due to these issues, programmers may spend a significant time tuning for performance. 20 Chapter 1. Introduction –Future proofing. In sequential applications the performance increases with the clock frequency, but in parallel applications it is not so easy, because the scaling in the number of cores and the changes of the cache system may affect the previous tuning. –Too little knowledge of parallel programming systems. OpenMP, Erlang, Haskell, X10, Thread Building Blocks (TBB) or Cilk are not widely know by general purpose programmers. Nowadays, the best known parallel languages/APIs are PThreads [131], MPI [110], OpenMP [120], CUDA [40], OpenCL [119], TBB [141], X10 [149] or Cilk [88]. Despite the fact that concurrent programming may look like a very new paradigm, parallel programming languages has existed from the seventies [65]. The architecture of parallel machines have been changing along the years, and with them also the parallel languages. In the era of vector machines, the parallel languages were only loop annotations; when SIMD processors were the mainstream, data parallel languages becomes popular (CMF, *Lisp, C*, Global Arrays, High Performance Fortran, ...); when shared memory multiprocessors appeared, shared memory models also appeared, such as PosixThreads, OpenMP, etc; and with clusters and Massive Parallel Processors (MPP), message passing become dominant (MPI for instance). However, there is an alternative to release the programmer from explicit parallelization: automatic parallelization of sequential programs by compilers [21] [162]. Automatic parallelization converts a serial code into parallel code to execute in a shared memory parallel processor. However, fully automatic parallelization of code is still a big challenge because it needs a very complex code analysis, and it has a limited effectiveness without the explicit help of the programmer. 1.2.1 Data Communication The different threads of an application running in a multicore processor require communication. There are two ways of communication among threads. One is by reading and writing in memory (typically in shared memory multiprocessors), and the other by sending messages (typically in distributed memory multiprocessors) [75]. These two techniques can also be combined and use shared memory communication in a system with distributed memory (Distributed Shared Memory). 1.2. Parallel Programming 21 Shared Memory Communication In shared memory parallel programming [57], the communication among threads or processes is done by just shared memory values, since all of them have a common address space. However, to ensure correctness, it is necessary to add mechanisms for correct synchronization. Without proper synchronization among threads, the integrity of data may be destroyed. The problem of synchronization will be discussed in Section 1.3.1. This model is the most popular in mainstream processors because it is easier to program, and the one that better fits for shared memory multicore processors. Message Passing In distributed memory programming [24], the synchronization among processors is done by explicit message passing. Message passing libraries allow the writing of parallel programs for distributed memory systems efficiently. These libraries provide routines to configure the messaging environment and to send and receive packets of data (point to point or collective). The most popular high-level message passing library is MPI (Message Passing Interface). MPI has become the facto standard for message passing parallel programming. This kind of communication has the drawback of being difficult to program because the programmer has to include explicit messages for communication in the code. 1.2.2 Problem Decomposition Depending on how a problem is decomposed to parallelize it, we distinguish between data and task decomposition. Data Decomposition The data parallel model focuses on distributing the data among different computing nodes. It is achieved when the same task is applied over different data in different cores. Data parallelism emphasizes the parallelized nature of the data. Task Decomposition Task decomposition refers to dividing the problem in tasks to execute them in different computing nodes (in threads, processes, etc). In general, these processes or threads commu- 22 Chapter 1. Introduction Figure 1.3: Dinning philosophers problem. nicate with each other (with some form of communication, as showed in Section 1.2.1). Task parallelism emphasizes the parallelized nature of the processing. 1.3 Parallel Programming Issues in Shared Memory Multicore processors with the shared memory communication model (Section 1.2.1) have some programming issues that have to be considered to program efficiently in parallel. Specifically, synchronization is one of them: it provides mechanisms to programmers for control access to shared data (where there are several threads running concurrently and accessing the same resources) with the aim of avoiding unexpected behaviors caused by thread interleavings not desired by the programmer. Another issue is debugging, as concurrency bugs are difficult to detect and fix so more sophisticated tools are needed to debug programs efficiently. In both cases, hardware support is usually necessary to achieve good performance while keeping correctness. This thesis is focused on contributing to reduce the overhead of these issues. CFM-TM (Chapter 3) makes a contribution in a speculative synchronization mechanism and Pacman (Chapter 4) in debugging. 1.3.1 Synchronization The most common synchronization mechanism are locks, which are used for another user level abstractions to build high level synchronization mechanisms (such as semaphores or monitors). To illustrate the synchronization problem, we will expose a classic example (see Figure 1.3): 1.3. Parallel Programming Issues in Shared Memory 23 EXAMPLE: Dining philosophers problem – Five silent philosophers sit at a table around a bowl of rice. – A chopsticks is placed between each pair of adjacent philosophers. – Each philosopher must alternately think and eat. – Eating is not limited by the amount of rice left: assume an infinite supply. – A philosopher can only eat while holding both the chopsticks to the left and the chopsticks to the right. – Each philosopher can pick up an adjacent chopsticks, when available, and put it down, when holding it. These are separate actions: chopsticks must be picked up and put down one by one. The problem is how to design a discipline of behavior (a concurrent algorithm) so that each philosopher doesn’t starve, and they can forever continue to alternate between eating and thinking without a deadlock situation. If we translate this problem to a shared memory multicore system, we could identify the philosophers as the cores, and the chopsticks as the shared resources. There are several possible solutions for this problem [30] [47], but all of them require some synchronization mechanism to avoid problems like deadlock, one of the most frequent synchronization bugs. In this example, a deadlock could be produced when all the philosophers are frozen with one chopstick in the right hand, and waiting for another chopstick for the left hand (not eating, not thinking). Locks Locks are the most common synchronization mechanism [164], used to restrict the concurrent access to some shared data to only one thread at a time. To synchronize threads with them, the critical sections have to be enclosed with locks. Before a thread enters in the critical section, it has to acquire the lock, and when it finishes, it has to release it to allow other threads 24 Chapter 1. Introduction executing their critical sections. Only one thread can acquire a lock at a time, and the other threads trying to acquire it have to wait. As locks serialize operations on shared data, the programmer try to either minimize the use of synchronization, or use fine grain locks (multiple locks protect different shared data). With the use of fine grain synchronization, the performance is optimized, but the code becomes prone to errors and difficult to program. On the other hand, if a single lock is used to protect large regions of code (coarse grain synchronization), programming is simpler, but scalability is drastically reduced. It is not appropriate to use coarse grain synchronization with locks for this reason. The most common bugs due to the use of locks are summarized as follow: – Deadlock: occurs when a thread is blocked because a resource requested by it is being held by another waiting thread. Figure 1.4 shows an example of deadlock. – Priority inversion: a high priority thread can not proceed because it is waiting for a lock which is held by a low priority thread. – Convoying: when multiple threads of equal priority contend repeatedly for the same lock. The threads in a lock convoy do progress, however, each time a thread tries to acquire a lock and fails, it renounces the remainder of its scheduling quantum and forces a context switch. The overhead of this repeated context switching and the underutilization of the quantums degrades performance. – Livelock: It is similar to deadlock, but the state of the different threads is changing continuously despite there being no progress. These bugs are very well known, and result in a serious problem for programming productivity. Locks are built in software, but for performance reasons, they rely on hardware synchronization instructions. The key hardware capability is an uninterruptible instruction capable of atomically retrieving and changing a value. One of these synchronization instructions is the atomic exchange, which interchanges a value in a register with a value in memory. Another common operation is test-and-set, which tests the value, and sets it if the value passes the test. For example, we could define an operation that tested for 0 and set the value to 1 (that can be used in a similar way to atomic exchange). 1.3. Parallel Programming Issues in Shared Memory 25 Thread 1 Thread 2 Thread 3 lock(m1) lock(m2) lock(m3) lock(m3) lock(m1) lock(m2) . . . . . . . . . . . . . . . . . . A B (A is blocked by B) Figure 1.4: Deadlock scenario: the three threads are holding a lock that other thread is trying to get. Another atomic synchronization primitive is test-and-increment: it returns the value of a memory location and atomically increments it (it can be also used in a similar way to atomic exchange). However, even with these primitives, implementing a single atomic memory operation introduces some challenges, since it requires both a memory read and write in a single, uninterruptible instruction. This requirement complicates the implementation of the coherence, since the hardware can not allow any other operations between the read and the write, and yet it must not deadlock. An alternative is to have a pair of instructions where the second instruction returns a value from which it can be deduced whether the pair of instructions is effectively atomic if it appears as if all other operations executed by any processor occurred before or after the pair. These pair of instructions includes a special load called load linked and a special store called store conditional. These instructions are used in sequence: if the contents of the memory location specified by the load linked are changed before the store conditional to the same address occurs, then the store conditional fails. The store conditional is defined to return 1 if it was successful and 0 otherwise. Semaphores and Monitors Semaphores and monitors are high-level synchronization mechanisms build on top of locks. Semaphores are pretty close to locks, but add some functionality (for instance, allowing more than one thread access to the critical section). Monitors are a set of multiple routines that are protected by locks and these locks are acquired and released automatically 26 Chapter 1. Introduction when the routines are used (it is not the responsibility of the programmer). Both are used for the same purposes, the difference is the level of control and abstraction that the programmer has. Alternatives The synchronization mechanism based on locks are perfectly valid for modern multicore processors. However, it is difficult to program with them, and they are prone to errors. To improve these approaches, in recent years some proposals like Lock Elision [138] (speculatively removing unnecessary lock-induced serialization in run time) or Transactional Memory [72] have arisen as promising alternatives. We will describe Transactional Memory in detail in Section 1.4. 1.3.2 Debugging Concurrency Bugs in Parallel Programs Thread interleaving in parallel programs is unpredictable on most of the architectures, which makes it hard to debug because of the difficulty of reproducing a concurrency bug. The production phase of parallel software takes a lot of time, and many errors are not even detected until years of correct execution. In many cases, the time invested in debugging is higher than that invested in coding. Usually these concurrent bugs are showed up only under certain timing conditions, and their effects manifest many instructions after the real bug is produced. For these reasons, parallel debugging is very important and needs to be supported by appropriate tools to help and accelerate this task. Without them, parallel programming will not become mainstream. Classical bug techniques (like the "printf" technique) are practical for some easy-to-solve bugs, but with concurrency bugs usually it is very impractical to debug in this way, because of the non-deterministic nature of parallel software. Most previous concurrency bug detection schemes were focused on detecting data races [33] [48] [151] [130], deadlocks [22] [48] [151] or atomicity violations [92] [94]. There are also other approaches to support and help debugging, such as deterministic replay [107] [10] [114] [115] [181] [128] [34], which can replay a bug deterministically, or parallel architectures that implement more easy to understand memory models, such as BulkSC [29], with a sequential consistency model. 1.3. Parallel Programming Issues in Shared Memory 27 Thread 1 Thread 2 Thread 1 Thread 2 lock(l1) unlock(l1) pvar->x=X; pvar=NULL; var1=var2; var3=var1; var1=var4; ... (a) (b) pvar->y=Y; if(pvar!=NULL){ } Figure 1.5: Examples of data races. (a) An example of a common data race, and (b) An example of asymmetric data race. Detecting Data Races A key type of concurrency bug is a data race. A data race occurs when two or more concurrent accesses to one shared variable (with at least one write) are executed without proper synchronization, and therefore it may result in an undesired behavior. Figure 1.5(a) shows an example of a data race; Thread 1 uses var1 to save the value of var2 and then assigning it to var3 in an atomic way, but the atomicity of this action is broken by Thread 2. However, in practice some of these races are not harmful and are intentionally introduced by the programmer in their code for optimization reasons. There are many approaches in the literature for hardware data race detection [113] [132] [94] and software data race detection [151] [48] [49] [92] [172]. Detecting Asymmetric Data Races One type of typically harmful data race are the asymmetric data races, which may occur when some threads are properly synchronized and others are not. In these races, there is a well-tested, correct thread that accesses shared variables with appropriate synchronization. In addition, there is a second thread, typically external to the well-tested application, which is insufficiently tested and accesses shared variables without correct synchronization protection. These threads are called the safe and the unsafe thread, respectively. An asymmetric race occurs when the safe thread is executing a critical section protected by synchronization and the unsafe thread corrupts the state of the critical section or reads inconsistent data. In these cases, the program can lead to unexpected results. 34 Chapter 1. Introduction –Closed nested transactions: A closed transaction can abort without aborting the outer transaction, and when it commits, the results are seen by the outer transaction (but not for the rest of the system). –Open nested transactions: When an open transaction commits, its changes are seen by the outer transaction and also by the whole system. On aborts, open transactions have the same behavior as closed transactions. These basic mechanisms are enough to implement a complete TM system. Next we will review some representative hardware, software and hybrid implementations. 1.4.2 Hardware Transactional Memory (HTM) TM implementations in hardware are the best in terms of performance. Many of them were developed in academia [72] [62] [183], but also industry has developed several HTM approaches in recent years [167] [6] [80] [66] [39], which reflect the potential of TM for the future of parallel programming. In the following, we describe three academic implementations and five commercial HTM proposals. The First HTM System: the Herlihy and Moss Implementation The first HTM implementation was proposed by Herlihy and Moss [72] in 1993. The hardware added is restricted to the first level caches and some new instructions, and TM is implemented by modifying the cache coherence protocol and exploiting the access rights (implemented in most of the cache coherence protocols). The implementation proposed is based on a snoopy protocol, a separate cache for the speculative data and new transactional cache states. Moreover, the processor maintains a state that indicates if there is or not an active transaction in the processor. The transactional cache behaves as a normal cache if the local core is not executing a transaction. The basic behavior is the following: the transactional cache holds all the tentative writes, without propagating them to other processors or to main memory unless the transaction commits. If the transaction aborts, the lines holding tentative writes are dropped (invalidated); if the transaction commits, the lines may then be snooped by other processors and written back to memory upon replacement. The transactional cache augments the classical cache states 1.4. Transactional Memory (TM) 35 (shared, modified) with some additional tags to handle speculative data and tracks conflicts by slightly modifying the cache coherence protocol (by adding information to distinguish transactional messages). The conflicts are detected by the transactional cache coherence controller, which snoops all the coherence messages to know the possible conflictive remote accesses. The idea of taking advantage of the cache coherence protocol to detect conflicts of data among transactions would be used later by many other proposals (LogTM[109], LogTMSE[183], etc.). Transactional Coherence and Consistency (TCC) Transactional coherence and consistency (TCC) [62] is a shared memory model based on TM, and one of the most representative lazy HTM systems (lazy conflict detection and lazy version manager). In this system all the instructions execute inside transactions, which are always the basic unit of work, communication, cache coherence and memory consistency. To develop software for this system, the programmer (or the compiler) has to divide the program into transactions. Optionally, the programmer can also specify order among transactions, which allows speculative parallelization of sequential programs. In TCC, the write buffer stores all the updates until they commit or abort. The read bits in the cache maintain the read set, the modified bits in the cache tracks the write set and the rename bits are optional bits to optimize the protocol. Each transaction produces a set of writes that are committed atomically to shared memory only when the transaction finishes successfully. Once a transaction completes, the system has to arbitrate for the permission to commit its writes. When the permission is granted, the processor broadcasts the writes to all the system. TCC has a greatly simplified coherence protocol, since it only needs to manage sequencing among entire transactions, and not among individual loads and stores. Also, it is consistent because it imposes sequential order among all the transaction commits. Moreover, it is coherent: stores are kept in a buffer until the end of the transaction (to maintain atomicity), and several processors can keep and modify the same data. At the end of the transaction, the processor notifies to all the other processors about the changes, and makes the proper invalidations and updates to keep the coherence, and at the same time determines if there are data conflicts that force the transaction to abort and restart and reload the correct data. 36 Chapter 1. Introduction The main drawback of TCC is the high broadcast bandwidth required to send the commit packages, which include all the modified data of the committed transaction LogTM-SE: Log-based Transactional Memory - Signature Edition LogTM [109] is the most representative of the eager systems (eager conflict detection and eager version manager). There is a later version of LogTM called LogTM-SE [183], which includes signatures (see Section 1.5) to manage conflicts. We describe this implementation in detail because it is the basis of one of the contributions of this thesis (Chapter 3). Signatures, usually composed of a register and one or several hash functions, can keep a probabilistic representation of an unbounded number of addresses in a bounded space, at the cost of false positives (a positive that actually is not). The addresses are inserted in the signature by hash encoding the address and setting the positions on the register that corresponds with the result of the hash function. Checking if an address is in the signature is an analogous operation, but checking the positions instead of setting (if all of them are one, the result of the check is positive). Notice that signatures never report a false negative (a genuine match is always reported). Beside signatures, LogTM-SE has the characteristic of supporting transactional data overflowing from the local cache without aborting the transaction, because the old versions of speculative data are saved in a software log, and not in the lower levels of the cache hierarchy as in other implementations. LogTM-SE builds upon a conventional shared memory multiprocessor with two (or more) levels of private caches that keep coherent by a MESI directory protocol [41]. The old values are saved in a per-thread log in cacheable virtual memory, which is allocated on the thread creation. On a store, LogTM-SE appends to the log the virtual address of the stored line and the line’s old value. Writing log entries generates less overhead than one might expect. Log writes will often be cache hits, because the log is cacheable, thread private, and most transactions write few lines. To abort, LogTM-SE must undo the transaction by writing old values back to their appropriate virtual addresses from the log. Figure 1.7 shows the basic hardware organization of LogTM-SE. The read and write sets are tracked with two signatures, which implement insert, check and clear operations (see Section 1.5), and the eager conflict detection is performed using the MESI cache coherence protocol implemented in the system. In LogTM-SE, the MESI protocol is implemented using a directory. 1.4. Transactional Memory (TM) 37 Register Checkpoint User Registers PC Log Base Log Pointer TM Nest Begin PC Handler PC R/W Sig Summary Sig Log Filter Thread Context 0 Core 0 1 2... Figure 1.7: LogTM-SE hardware organization. The shaded elements are the LogTM-SE specific state. In this protocol, each read/write miss generates a request to the directory, and the directory forwards this request if necessary. In case the line is shared by several L1 caches, or owned in exclusivity by one of them, the directory forwards the request to the involved caches. In case the line is not in L2 cache, a L2 miss is produced, and the data is requested to memory. LogTM-SE performs eager conflict detection in several steps: (a) the requesting processor sends a coherence request to the directory, (b) the directory responds and possibly forwards the request to one or more processors, (c) each responding processor examines some local state to detect a conflict, (d) each responding processors ack (no conflict), or nack (conflict) the request, and (e) the requesting processor resolves any conflict. To support conflict detection, LogTM-SE introduces some changes on the original MESI directory protocol. If a L1 cache data is evicted, the L2 does not update the exclusive pointer or sharer’s list (sticky states). This ensures that a subsequent request will still be forwarded to the evicted L1 line, allowing the conflict detection. If the L2 replaces transactional data, it loses the corresponding directory information, as the main memory does not maintain directory information. As a result of the inclusion property, subsequent requests to the same data result in a L2 miss. But to preserve correctness, the L2 conservatively broadcasts the coherence request to the L1s, allowing them to check 38 Chapter 1. Introduction their signatures. To avoid multiple broadcasts for the same line, the L2 rebuilds the directory state by recording the L1s’ responses. If an L1 NACKs the request due to a conflict, the L2 directory goes to a new state that requires L1 signature checks for all subsequent requests. A line leaves this state when the request finally succeeds. For conflict resolution, the contention manager is activated and it executes a timestamp resolution policy, so that if the requester transaction is younger, it should be stalled until the older transaction finishes (commits or aborts), but if the requester is older, the younger transaction aborts. Furthermore, LogTM-SE does not allow us to cache a line in the L1 cache that is in the write set of another core, which ensures isolation. LogTM-SE is also able to operate in multi-threaded cores, adding additional mechanisms to detect conflicts among threads in the same core. Each thread context maintains its own read and write signatures. Regarding the version management, the eager approach uses a software log allocated in thread-private memory. LogTM-SE uses an array of recently logged lines for each thread context as a simple but effective log filter. When a thread stores to a line not found in its log filter, LogTM-SE logs the line and adds its address to the log filter. Stores to addresses in the log filter are not logged. Commits in LogTM-SE are a local and fast operation, which consists of clearing the local signatures and resetting the log pointer. Aborts are managed using a software handler, which walks the log in FIFO order restoring transactional modified lines, and after that, the read and write signatures are cleared. With a naive directory protocol, cache victimization could lead LogTM-SE to miss some signature checks and hence miss some conflicts. LogTM-SE avoids this case by extending the directory protocol to use LogTM’s sticky states [109]. LogTM-SE’s caches silently replace lines in states E and S and write back lines in state M. When evicting a cache line, however, LogTM-SE does not change the directory state, so that the directory continues to forward conflicting requests to the evicting core. Thus, LogTM-SE allows transactions to overflow the cache without a loss in performance. Sun Rock TM Implementation The Sun Rock [167] [168] [45] [32] was the first commercial HTM implementation. It has very modest TM support (best effort approach), and can be used for lock elision or for some 1.4. Transactional Memory (TM) 39 hybrid implementations. Unfortunately, the Sun Rock was canceled in 2009, but it showed the way to follow for other manufacturers. Rock uses two new instructions to support TM, one that denotes the beginning of a transaction and the other that denotes the end. Rock also adds a s-bit in cache lines. The transactional loads set the s-bit in the corresponding cache memory line, and if a cache line with its s-bit set is evicted, the transaction is aborted. Stores within a transaction are placed in the store queue in program order. The addresses of stores are sent to the L2 cache, which then tracks conflicts with loads or stores from other threads. If the L2 cache detects such a conflict, it reports the conflict to the core, which then aborts the transaction. When the commit instruction executes, the L2 locks all lines being written by the transaction. Locked lines cannot be read or written by any other threads. This is the point at which other threads view the transaction’s loads and stores as being performed, thus guaranteeing atomicity. The stores then drain from the store queue and update the lines, with the last store to each line releasing the lock on that line. The support for locking lines stored by a committed transaction is the primary hardware mechanism added to Rock to implement TM. Unlike many other HTM systems, the Rock processor implementation ensures weak isolation (detection of conflicts only among transactions). AMD ASF (Advanced Synchronization Facility) The Advanced Synchronization Facility (ASF) [6] [37] is an AMD64 extension to provide a very limited form of HTM support. It exposes a mechanism for atomically updating multiple independent memory locations, and allowing software to implement the intended synchronization semantics. ASF is a high level specification, and it does not provide any specific hardware implementation. ASF specify the execution of the atomic sections of code in a speculative way, and if a conflict is produced, ASF report it to the software, which can retry the transaction as desired. Furthermore, despite the fact that ASF protects memory at cache-line granularity, software can work on the level of memory objects because: – ASF-protected memory objects have a size of up to 64 bytes and are naturally aligned (all ASF implementations should have cache lines of at least 64 bytes). 40 Chapter 1. Introduction – The speculative region does not reference more than four objects (this is the minimum guarantee, but more may be supported depending on the architecture). – Memory objects protected using ASF do not share cache lines with memory objects that are not protected. (False sharing may lead to unwanted protection, exceptions and unnecessary aborts). Some limitations are that ASF supports only a limited form of nested speculative regions, and that only operates on cacheable data and has a weakened memory-access-ordering model in certain aspects. Chung et all [38] proposed an ASF hardware design to implement in a future AMD outof-order processor, which is close to the classical approaches on cache-based HTM designs [183] [62]. Intel Haswell TM Implementation The new Intel Haswell architecture [80] includes some synchronization extensions to take advantage of the underlying TM system. The Intel’s Transactional Synchronization extension (TSX) describes two software interfaces for HTM in Haswell, one is for Hardware Lock Elision (HLE) [138], and the second mode is Restricted Transactional Memory (RTM), which is similar to classical TM proposals. The HTM implementations following the specifications of TSX have cache line granularity and strong isolation. Typically, conflicts cause the transaction to abort, and false conflicts can occur because of cache-line granularity. TSX also supports nested transactions, which are managed by flattening the nested transactions in a single transaction. Transactions can only be used with write-back cacheable memory operations, and not all the instructions can be used safely inside a transaction (for example instructions related with interrupts, I/O, virtualization, etc). There are also limits to the size of the transaction (probably because the size of the transaction is restricted to the L1 cache). The first of the interfaces defined is RTM, which exposes nested transactional memory to the programmer. For implementing RTM, there are three new instructions, one for starting the transaction, one to indicate the end of a transaction and a explicit instruction to trigger an abort. The other interface defined is HLE, which introduces two new instructions to denote the bounds of the lock elision (see Section 1.4.5). One instruction indicates the beginning of a 1.4. Transactional Memory (TM) 41 region for lock elision, and the other instruction is for releasing the lock address when the HLE region finishes. The HLE region is treated as a transaction, and the memory address of the lock instruction is added to the read set (but the lock is not acquired). If a conflict occurs, the transaction is aborted, and the HLE region is executed again, but this time acquiring the locks (without HLE hardware support). Regarding the architectural support, unfortunately Intel has not revealed many details about the architecture, but we can outline some ideas suggested by D. Kanter [80] and that probably match the actual architecture. The Haswell coherency changes are probably restricted to L1 and L2 cache (in a three level cache system). Probably a read and a write bit are used per cache line and thread to indicate that the line belongs to the read or the write set of the transaction. The L3 cache would store the old data. It is also likely that the size of transactions is restricted to the L1 data cache. The conflicts would be detected eagerly through the existing cache coherency protocol. To commit a transaction, the L1 data cache and L2 cache controllers make sure that any cache line in the write set (WS) is in the Modified state and clean the WS bits. Similarly, any cache line that is in the read set (RS) -but not the WSmust be in the Shared state and the RS bits are cleared. To abort a transaction, the cache controllers change all the WS lines to the Invalid state and clear the WS bits and the RS bits. IBM Blue Gene/Q TM Implementation The last generation of the IBM Blue Gene [66] [175] is a 18-core high-performance energyefficient computing system that also incorporates HTM. The main TM characteristic of the Blue Gene is the multiversioned L2 cache used to support speculative execution, TM and atomic operations. During memory speculation, the L2 cache tracks state changes caused by speculative threads and keeps them separate from the main memory state. The speculative data is only visible for the thread that writes it. At the end of the speculative code, the changes can either be made permanent (commit), or be reverted (abort). Also, the L2 track for Read-after-Write (RAW), Write-after-Write (WAW) and Write-after-Read (WAR) conflicts. The L2 can be configured to react to a conflict with an invalidation, with a notification to the software, or both. In the second case, the software decides which transaction to abort to resolve the conflict. 42 Chapter 1. Introduction IBM System Z TM Implementation The last generation of the IBM system z CPU [77] also implements a pure HTM system and incorporates architectural features to support debugging and testing. It introduces six new transactional instructions: TBEGIN (it indicates the beginning of the transaction), TBEGINC (it mostly behaves like TBEGIN), TEND (it indicates the end of the transaction), ETND (it is used to load the current nesting depth into a general register), NTSTG (non-transactional store; unlike a normal store, it is committed to memory even in the case of transaction abort, mainly for debugging purposes) and TABORT (it causes an immediate abort). The main implementation components of the TM system are a register file to save the old versions of transactional data, a cache directory to track the cache lines accessed during the transaction, a store cache to buffer transactional stores until the transaction ends, and firmware routines to perform various complex functions. Furthermore, it includes other architectural registers to support and track different events of the transactional behavior. 1.4.3 Software Transactional Memory (STM) The main advantage of STM over HTM is the flexibility to implement different strategies of conflict detection and version management, as well as the capacity to manage unbounded transactions. Also, STM is easier to modify and evolve than HTM, and it can be integrated easily with the existing software systems. The main drawback of STM is its large runtime overhead. The STM precursor scheme was proposed by Lomet in 1977 [91], who proposes a programming language construct very similar to STM, but with a different name. Lomet analyze the disadvantages of synchronization mechanisms (locks, semaphores. monitors, etc), and noted that programmers use these mechanisms to execute sets of code atomically. However, the term STM first appeared in a paper of Shavit and Touitou [153] in 1995, which is considered the first STM implementation. In this first implementation the programmer had to declare which locations might be accessed by the transactions and to propose the memory updates in advance. This approach inspired many early non-blocking STM implementations. There are some basic core techniques that are used across most of the STM systems: concurrency control metadata, version management and read and write track. To associate the metadata (data that describes the data) with the locations that the program is accessing, 1.4. Transactional Memory (TM) 43 there are two basic approaches: an object-based STM approach (held with each object) or a word-based STM approach (associated with each memory location). Regarding version management, STM needs and undo-log for eager version management (to save the old values that would be restored if an abort occurs), and a redo-log for lazy version management (with the values that will be written to memory if the transaction commits). There are two types of concurrency control. Pessimistic concurrency control needs a mechanism to track read and write sets, so that the transaction can release any lock that has acquired. In optimistic concurrency control, it is the transaction which detects the conflicts. Beyond these core techniques, we can classify the STM systems in four groups, depending on the specific implementation: Lock-based STM with Local version numbers, Lock-based STM with Global Clock, Lock-based STM with Global Metadata and Nonblocking STM Systems. Below, we briefly describe each one of these groups: Lock-based STM with Local Version Numbers This variant combines a pessimistic concurrency control for writes (using locks acquired dynamically) with optimistic concurrency control for reads, implemented by checking version numbers during validation, which are incremented independently in each piece of STM metadata. The main algorithmic choices are eager or lazy conflict detection, and they lock the locations when they are accessed (encounter-time locking or ETL) or in the commit phase (commit-time locking or CTL). ETL supports both eager or lazy version manager, detecting conflicts among running transactions (whether or not they commit). CTL only support lazy version management, which allows supporting lazy conflict detection. This approach has been used in many STM systems [1] [2] [68] [145] [146]. Lock-based STM with Global Clock Unlike local version numbers, this implementation uses a global clock to maintain the version numbers, which is incremented globally in the process. These implementations can easily provide opacity (the property of guaranteeing that a transaction always sees a consistent view of memory as it runs). One good example of this approach is TL2 [46]. 50 Chapter 1. Introduction are all set to one. In case at least one bit is set to zero, the address is not in the signature. If all the bits are set to one, the address was previously inserted (or it is a false positive). Each hash function in the Bloom filter set or check one bit of the register. All khash functions are independent, and they map the addresses into krandomly distributed bits of the register. The most critical design decisions in a true Bloom filter are the size of the register (m) and the number of hash functions (k). Large registers decrease the probability of a false positive, but increase the hardware resources and power/energy required. On the other hand, the probability of false positives depends also on the number of hash functions and the number of elements inserted [147] [20]. The number of false positives is influenced as well by how the hash functions are implemented (H3, bit-selection, etc). A theoretical approach for the false positive rate [147] assumes that the hash values are independent and uniformly distributed (very similar to H3 functions). This leads to the following expression for the lower bound of the false positive rate (PFP): PFP = (1−e−nk m)k(1.5) where nis the number of addresses inserted and assuming m>> 1. The effect of the number of hash functions is shown in the example of Figure 1.10 (a), where the false positive rate of a signature with m=1024 is represented , with the number of inserted addresses from 0 to 500, and k=1,2,4,8,16. We see that the best value of k(minimum false positive rate) depends on the number of addresses inserted: with a high number of addresses inserted, the better results are achieved with a small value of k, and with a low number of addresses inserted, the signature requires a higher value of kto minimize the false positive rate. Figure 1.10 (b) shows the evolution of the false positive rate depending on the kvalue, and for 5 different values of n. We see more clearly in this figure that there is an optimal value of kdepending on the number of addresses inserted (n). Specifically, the absolute minimum of the Equation (1.5) is obtained for k=ln(2)×m n[163], and the lower bound of the false positive rate using this value is given by: PFP =2−ln(2)×m n Since k, in practice can take only integer values, the value of kthat minimizes the false positive rate (kopt ) is the closest integer to ln(2)×m nthat minimizes the value of PFP (Equation 1.5. Background on Signatures 51 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 100 200 300 400 500 false positive rate Addresses inserted (n) K=1 K=2 K=4 K=8 K=16 (a) False positive rate vs ndefault values of k. 0 0.05 0.1 0.15 0.2 1 2 4 8 16 32 false positive rate k n=40 n=80n=120 n=180 n=240 (b) False positive rate vs kfor default values of n. Figure 1.10: False positive rate for parallel Bloom filter with m=1024. (1.5)). For the particular example of Figure 1.10 (b) with m=1024 and n=180, the optimal value is kopt =4. 1.5.3 Parallel Bloom Signature Figure 1.9 (b) shows an alternative to the true Bloom signature, the parallel Bloom signature [147] [31]. In this case, the m–bit register is split into kregisters of m/kbits, each with a hash function associated. In this approach, each hash function operates on one of the m/k–bit registers. Hence, the parallel Bloom signature can be seen as ktrue Bloom signatures with one hash function and a m/k–bit register (or like ksingle Bloom filters). The insert operation hashes the addresses and inserts one bit in each m/k–bit register, and the check operation reports that an address is in the signature only if all individual single Bloom filters have the hash mapped bit of their register set to one. The advantage of parallel signatures is that hash functions are simpler and are implemented with fewer resources. Therefore, each of the individual SRAMs of the Bloom filters can be single-ported, thereby reducing significantly the hardware area/power/latency. The false positive rate depends on the size of the signature m, the number of hash functions k(which is the same as the number of single Bloom filters) and the number of inserted addresses n. Particularly, the theoretical false positive rate is given by the following expression [147] [31]: PFP ≈(1−(1−k m)n)k 52 Chapter 1. Introduction and applying the Taylor series approximation of exthe equation results in PFP ≈(1−e−nk m)kwhen k m1 This is approximately the same expression obtained for the true Bloom signatures when the size of the signature is much bigger than the number of single Bloom filters (k/m1). Therefore, Figures 1.10 (a) and (b) are also representative of the behavior of parallel Bloom filters. 1.5.4 Other Signature Implementations There are other interesting signature approaches that improve some aspect of signatures based on Bloom filters, or at least they adapt better to a specific tool. We describe some of them below. Scalable Bloom Filters Scalable Bloom Filters [4] are software signatures that can adapt dynamically their size depending on the number of elements. It allows the signature to grow arbitrarily: when a Bloom filter reaches a certain number of addresses inserted (that is correlated with the false positive rate), another Bloom filter is added. This concept of signature requires an arbitrarily number of Bloom filters, and therefore it is more appropriate to implement it in software than in hardware. AdaptSig [129] or Dynamic Bloom Filters [61] are inspired by this idea, but also both approaches are intended for software implementations. Cucko Bloom Signatures Cucko Bloom Signatures [147] represent small read/write sets by adapting Cucko hashing [126]. Cucko Bloom signatures are formed by a hash function that tracks the addresses when their number is low, and eventually is transformed in a Bloom filter when the number of addresses increases. These signatures match the low false positive rates of Bloom signatures with many hash functions when the number of addresses is small, and show the good asymptotic behavior of Bloom signatures with few hash functions when the number of addresses is large. 1.5. Background on Signatures 53 Register h0 Register h1 Register hk-2 Register hk-1 01k-2 k-1 . . . 0 a-1 a k-1 Read Set Write Set Figure 1.11: High level scheme of the ASYM signature. Locality-sensitive Signatures Locality-sensitive signatures [135] are specially designed to exploit locality in transactional memory systems. The design is based on new hash function mappings, so that nearby located addresses are mapped sharing some bits. These signatures are particularly favorable for large transactions that usually exhibit some amount of spatial locality. Their implementation do not require extra hardware. ASYM Signatures ASYM signatures [136] are new schemes specially designed for TM systems. Among these signatures, ASYM signatures are of special interest for us because they are related with our FlexSig module implementing asymmetric allocation policies. In Chapter 6 we will discuss the differences between both proposals and the advantages of our approach. ASYM signature deals with the asymmetry of the read and write sets in TM systems. The high level idea is that the ASYM signature configures the number of Bloom filters devoted to each data set. As we show in Figure 1.11, the ASYM signature is composed of khash functions, each one associated with a register, and a mask register that provides the parameter awhich establishes the sizes of the read and write signatures. Specifically, assuming an ASYM signature with k (hash,register)-pairs, and a∈[1,k−1], the hashes h0,h1,...,ha−1are assigned to the read set, and the hashes ha,ha+1,...,hk−1are assigned to the write set. The a parameter is dynamically reconfigurable at run-time (it can change among transactions). With a good configuration of the aparameter (it depends on the transaction and the application), the false positive rate of ASYM signatures is improved regarding conventional signatures. 54 Chapter 1. Introduction 1.6 Conclusions Parallel programming is the way to continue scaling the performance of programs in multicore processors, but it is not an easy task. Some tools, abstractions and programming languages have been proposed to make this task more accessible for programmers. One of the most popular software abstractions adopted by academia and industry is TM, which simplifies the synchronization of shared memory by defining atomic blocks and ensuring their isolation and atomicity. Furthermore, the development of new tools to support and help debugging (specially related with synchronization bugs) is also important, because with multiple threads accessing shared data, this task has become very complex. Moreover, these new tools and abstractions usually are supported by hardware to achieve a better performance; one common hardware resource used in many tools and applications are hardware signatures, which keep a probabilistic representation of an unbounded number of addresses in a bounded space (low hardware cost), and which can significantly improve the performance of these tools. CHAPTER 2 EVALUATION METHODOLOGY Simulation is essential for evaluating new architectures, protocols, or other hardware modifications and additions, because it is more flexible and cheaper than making a prototype in hardware. Furthermore, it is very useful for obtaining information and statistics about performance and events in the system. One of the main advantages of simulation is the flexibility: some simulators allow a very fast execution at the expense of simulation detail, or alternatively, other simulators execute very detailed simulation and obtain a lot of traces and event information (at the cost of simulation time). In computer architecture, a common way to test the improvement of a contribution is to compare a well known implementation with the new solution. The simulation framework consists in a system simulator and a series of benchmarks running on it. In this chapter we present the experimental setup used in the evaluation of the different proposals of this thesis. In Section 2.1 we describe the framework used to simulate our proposals, and in Section 2.2 we described the set of benchmarks used. 2.1 Simulator Framework This section describes the simulators and tools used for this thesis. Section 2.1.1 describes Simics [98] and GEMS [102], the system simulators used for evaluating our CFM-TM proposal in Chapter 3. This framework provides a cycle accurate simulation environment, with support for TM, which we use to obtain detailed statistics of the memory system and of the TM system. 56 Chapter 2. Evaluation Methodology Section 2.1.2 is dedicated to the PIN instrumentation tool [81], which is used for the evaluation of Pacman (Chapter 4) and FlexSig (Chapters 5 and 6). PIN has the capacity of enabling the creation of dynamic program analysis tools. With these tools, we build the simulation framework by monitoring the data accessed in transactional and lock based applications, and making the appropriate simulations with the observed data. Furthermore, in Section 2.1.3 we describe the Rochester STM system [100], which forms part of the experimental framework for the FlexSig evaluation. RSTM is an open source STM library, which we use to run transactional code which we monitor with PIN. Finally, in Section 2.1.4 we describe SESC [124], a cycle accurate simulator used in the evaluation of Pacman. 2.1.1 Simics and GEMS The ensemble composed of Simics and GEMS is the simulation framework in the evaluation of our TM work in Chapter 3. Figure 2.1 shows an overview of this framework. The main advantages of using Simics and Gems are that they simulate a complete Sparc architecture that can run a complete operating system with a deep level of detail (cycle accurate simulation). Furthermore, with GEMS we obtain a detailed memory system simulator. Despite there being other good alternative simulators, like SESC [124], we choose this environment to simulate for its performance, the strong support of the community of users, and its support for transactional memory. Virtutech Simics Simics is a full system functional multiprocessor simulator that tries to maintain the balance between accuracy and performance. It can simulate processors at instruction-set level (with models for Ultrasparc, Alpha, x86, etc), and it can run operating systems, including Solaris, Linux or Windows. Furthermore, Simics allows us to add new user-developed modules to expand the simulator with new features. In our experiments, we run Simics 2.2.19 with a target system composed of a 16-core UltraSparc-III processor running the Solaris 9 operating system. Simics provides a deterministic environment for a variety of hardware and software engineering tasks. However, it does not provide micro-architecture timing detail nor cache/memory subsystem timings. To overcome these limitations, GEMS have added these functionalities through a software module for Simics. 2.1. Simulator Framework 57 BENCHMARKS SIMICS GEMS Ruby - Memory systems simulator L1 L2 Main Memory M S I LogTM-SE Interconnection network Caches & Memory Coherence controllers Transactional Memory Figure 2.1: SIMICS+GEMS overview. GEMS GEMS is a software module developed as part of the Multifacet project at the University of Wisconsin. GEMS is built on top of Simics, enables the simulation of multicore systems, and as shown in Figure 2.1, provides detailed models and timing information of the memory system, coherence controllers and the interconnection network, and supports HTM (specifically LogTM-SE [183] and ROCK [168]). GEMS is composed by two basic modules: Ruby and Opal. Ruby models the memory hierarchy, using for that a specific language call SLICC, and Opal models the timing of an out-of-order SPARC processor. In this thesis we use only Ruby for simulation, because OPAL does not support TM programs. Simulated Architecture The configuration of Simics and GEMS for our experiments is shown in Table 2.1. The simulated multicore processor is composed of 16 single-issue in order cores, with a 32Kb data cache (L1D), and a 32Kb instruction cache (L1I). Both caches are 4-way set associative, with 2-cycles of latency and 64 bytes size lines. The shared L2 cache has a total size of 8 megabytes, and it is distributed along all the cores of the chip (512 Kb per core). Furthermore, the L2 cache is an 8-way set associative cache with a latency of 15 cycles. The directory, placed in L2, has an access delay of 6 cycles. The 58 Chapter 2. Evaluation Methodology Table 2.1: System configuration. Cores 16, single issue, in-order Cache Data Line 64 bytes L1 I&D caches 32KB, 4-way, 2-cycles latency L2 cache 8MB, 8-way, 15-cycles latency Memory 4GB, 500-cycles latency Directory 6-cycles latency Network Topology point to point Link latency 1-cycle main memory has 4 Gigabytes and an access latency of 500 cycles. The network topology in our simulation is a point-to-point network (full connected crossbar) with an access latency of 1 cycle. Moreover, our simulated architecture is configured to support the LogTM-SE HTM [183]. In our CFM-TM proposal we modify this base system to perform our experiments. Compilation Infrastructure The compilation infrastructure for the transactional memory benchmarks is a Solaris gcc compiler without modifications. The transactional boundaries are simulated through the Simics "magic instructions", which are special assembly instructions which are functionally no-op in a real machine, but they are reinterpreted by Simics to simulate the TM system. 2.1.2 PIN PIN is an instrumentation tool used in our experiments with Pacman (Chapter 4) and FlexSig (Chapters 5 and 6). It can access information such as register contents, symbols or debugging information. PIN runs attached to program code, instruments just before it runs (discovers code at runtime), and it does not need to recompile or re-link. With PIN it is possible to set up instrumentation tools (called PinTools), which are composed by two kinds of routines: the instrumentation routines define where the instrumentation is inserted and the analysis routines define the actions to take when the instrumentation is activated. Therefore, a PinTool can 2.1. Simulator Framework 59 PIN PINTOOL FLEXSIG Rochester STM Benchmarks Figure 2.2: Simulation framework of Chapters 5 and 6, composed of our FlexSig PinTool for PIN, which instruments the benchmarks running on RSTM. replace functions in the program by other functions (defined by the PinTool) or examine all the application instructions. In the particular case of our experiments with Pacman, we used instrumentation routines in PIN to detect the beginning and end of a critical section (when the lock is acquired and released), and analysis routines to monitor the data accesses inside the critical sections (including the code to simulate our hardware module implementation). In our evaluation of FlexSig, we used instrumentation routines in PIN to detect the beginning and the end of the transactions, an analysis routines to track all the transactional accesses and to implement the new signature hardware module. Figure 2.2 shows a high level representation of the simulation framework in this particular case. The reason to choose PIN for the evaluation of these chapters is because of its flexibility to simulate only the hardware elements which we are interested in, allowing a very good performance and a high level of detail of the simulated modules. 2.1.3 Rochester STM Rochester Software Transactional Memory (RSTM) [100] is a STM library that can be configured with a wide variety of STM implementations. Specifically, it implements word-based and object based implementations, which are summarized in Table 2.2. We use RSTM to build a transactional environment and run transactional benchmarks for testing our FlexSig work. In our evaluation we use a lazy acquisition and lazy versioning with extendable timestamps [143] to configure RSTM (ET implementation in Table 2.2). 66 Chapter 2. Evaluation Methodology the thread wants to add the new path to the grid, making the validation. If the validation fails, the transaction aborts, and it starts again with an updated copy of the grid. –Vacation: This benchmark emulates a travel reservation system, implemented as a set of trees that keep track of customers and their reservations. The execution of the benchmark consists of several threads (clients) interacting with the travel system database in three different ways: reservations, cancellations and updates. Each one of these interactions is enclosed in one transaction, and consequently, "Vacation" spends a lot of time on transactions. These transactions are medium length with moderate read and write set sizes, and they have low to moderate levels of contention (depending on the input). –Genome: This benchmark takes a large number of DNA segments and matches them to reconstruct the original source genome. The process is divided in two phases. The first phase creates a set of unique segments (some segments are duplicated), and each addition to the set of unique elements is enclosed by a transaction. In the second phase, each thread tries to remove a segment from a global pool of unmatched segments and add it to its partition of currently matched segments. The access to the global pool are also enclosed by a transaction. –Kmeans: This benchmark groups objects in a N-dimensional space into K clusters, and it is usually used to partition data items into related subsets. In each iteration, the update of the cluster center is protected by a transaction. The amount of contention depends on the input parameters, the read and write sets are relatively small, and the total time spent on transactions is low. –Ssca: Scalable Synthetic Compact Applications 2 (SSCA2) [11] is comprised of four kernels, but the STAMP implementation focuses only on one of them. This kernel constructs a graph data structure using adjacency arrays and auxiliary arrays. Transactions are used to protect the access to adjacency arrays, and since this action is relatively small, not much time is spent on transactions. Additionally, the length of the transactions and the sizes of their read and write sets is also small, as well as the amount of contention. –Yada: This benchmark implements an algorithm for Delaunay mesh refinement [144]. The main structures are a graph to store all the mesh triangles, a set with the boundary segments and a task queue with the elements that need to be refined. In each step of the 2.2. Benchmarks 67 algorithm, a triangle is removed from the queue, its retriangulation is performed on the mesh and the new triangles formed are added to the work queue. The transactions are used to enclose the access to the queue, and as almost all the execution time is spent recalculating the retriangulation, this benchmark has relatively long transactions and almost all of the execution time is spent on them. This benchmark also has large read and write sets and moderate contention. –Bayes: This benchmark implements an algorithm for learning the structure of Bayesian networks. The bayesian network is represented as a directed acyclic graph with a node for each variable and an edge for each conditional dependence between variables. The algorithm implemented gradually learns dependencies among variables by analyzing the observed data. A transaction is used to protect the calculation and addition of a new dependency. "Bayes" spends almost all its time in transactions, which have large read/write sets and high contention. 2.2.3 PARSEC The Princeton Application Repository for Shared-Memory Computers (PARSEC) [16] is a benchmark suit to study multicore processors, which unlike SPLASH-2 or STAMP, includes applications in recognition, mining and synthesis (RMS). Some of the benchmarks are from Intel ("Blackscholes", "Bodytrack", "Facesim", "Fluidanimate", "Raytrace" and "Swaptions"), some of them from the Princeton University ("Ferret", "Canneal", "Dedup" and "Streamcluster"), and others are based on well known applications ("VIPS" and "x264") . PARSEC benchmarks are written in C language, and the critical sections are enclosed with locks for the simulation of Pacman. Below we describe all the PARSEC benchmarks used in this thesis. –Blackscholes: This application calculates an estimation of the current value of European options with the Black-Scholes formula, the derivative of a partial differential equation (PDE) [17] which governs the price of the option over time. –Bodytrack: This is a computer vision application which tracks a 3D pose of a human body with multiple cameras through an image sequence [13] [43]. –Facesim:This application (originally developed by the Stanford University) takes a model of a human face and a time sequence of muscle activations and computes a 68 Chapter 2. Evaluation Methodology visually realistic animation of the modelled face by simulating the underlying physics [156] [165]. The goal is to create a visually realistic result. –Ferret: This application is based on the Ferret toolkit which is used for content-based similarity search of feature-rich data such as audio recordings, digital images, sensor data, 3D shapes and so on [97]. –Fluidanimate: This application uses an extension of the Smoothed Particle Hydrodynamics (SPH) method to simulate fluid dynamics for interactive animation purposes [111]. –Raytrace: This application renders an animated 3D scene for real-time animations (such as computer games). Ray tracing is a technique that generates a visually realistic image by tracing the path of light through a scene [177]. This application is also included in SPLASH-2 benchmarks (Section 2.2.1). –Swaptions: The swaptions application uses the Heath-Jarrow-Morton (HJM) framework to price a portfolio of swaptions. The HJM framework describes how interest rates evolve for risk management and asset liability management [69] for a class of models. It employs MonteCarlo simulation to compute the prices. –Vips: This application is based on the VASARI Image Processing System (VIPS) [103]. The benchmark is an imaging processing system, which includes fundamental image operations such as an affine transformation and a convolution. –x264:This application is an H.264/AVC (Advanced Video Coding) video encoder. It is based on the ITU-T H.264 standard which is now also part of ISO/IEC MPEG-4. It improves on previous video encoding standards with new features such as increased sample bit depth precision, higher-resolution colour information, variable block-size motion compensation (VBSMC) or context-adaptive binary arithmetic coding (CABAC). –Canneal: This kernel uses cache-aware simulated annealing (SA) to minimize the routing cost of a chip design [14]. SA is a common method to approximate the global optimum in a large search space. –Dedup: This kernel compresses a data stream with a combination of global compression and local compression in order to achieve high compression ratios. Such a compression is called ’deduplication’. 2.2. Benchmarks 69 –Streamcluster: This kernel solves the online clustering problem [85]: for a stream of input points, it finds a predetermined number of medians so that each point is assigned to its nearest center. The quality of the clustering is measured by the sum of squared distances (SSQ) metric. It is used in network intrusion detection, pattern recognition and data mining. 2.2.4 EigenBench "EigenBench" [73] is a lightweight, flexible and powerful synthetic benchmark designed to evaluate and understand TM systems by forcing different TM orthogonal characteristics. These characteristics are the basics to understand TM behavior, and it is also useful to reproduce some TM pathologies, or evaluate corner cases that are not easily reachable with standard applications. These characteristics are the following: –Concurrency: Number of concurrently running threads. –Working-set size: size of the frequently used memory. –Transaction length: Number of shared accesses per transaction. –Pollution: Fraction of shared writes to shared accesses. –Temporal locality: Probability of repeated address per shared access. –Contention: Probability of conflict of a transaction. –Predominance: Fraction of shared access cycles to total execution cycles. –Density: Fraction of non-shared cycles executed outside transactions to total nonshared cycles. There exists an actual mapping from a real application to a set of these orthogonal characteristics [73]. Furthermore, "EigenBench" is written in C, and it uses the same TM API as used by STAMP. In our case, we use a certain set of C Macros that maps TM accesses with RSTM. We use this benchmark to explore some TM scenarios in our evaluation of asymmetric FlexSig (in Chapter 6). 70 Chapter 2. Evaluation Methodology 2.2.5 Other Benchmarks We use two additional benchmarks to evaluate Pacman, which we describe below. Apache "Apache" [50] is the most used web server software. At a high level, the Apache server architecture is composed of a core that implements the most basic functionality of a web server and a set of standard modules that actually service the phases of handling an HTTP request. Sphinx3 "Sphinx3" is a decoder for speech recognition research written in C [150]. It includes both an acoustic trainer and various decoders, i.e., text recognition, phoneme recognition, N-best list generation, etc. 2.3 Conclusions We present in this chapter the simulator environment and the benchmarks used in this thesis. The techniques of simulation used are very well know, and very popular for analyzing computer architecture innovations. Furthermore, the benchmarks represent a high variety in their characteristics, and also are very representative of the current workloads which can be potentially used in real world environments. CHAPTER 3 REDUCING THE USE OF SIGNATURES IN A HTM SYSTEM Hardware Transactional Memory (HTM) systems have been very popular due to their performance advantages. However, this performance improvement comes at the cost of increasing the hardware resources. Typical hardware additions in a HTM are cache add-ons, cache coherence support, special caches for speculative data or hardware signatures. In this chapter we propose a method to save resources in a HTM system. Specifically, we propose a simple Cache Filtering Mechanism (CFM-TM) for HTM systems [123], which acts like a filter by managing part of the write set of the application, with the aim of reducing the use of signatures (see Section 1.5) and log information in the transactional memory baseline system. In addition, to fully take advantage of this method, the CMP system should have signatures with different sizes, or, preferably, it should have signatures of variable size using a system like the schemes proposed in Chapters 5 and 6. We test our CFM-TM with LogTM-SE [183] as the baseline system (Section 1.4.2), because it is a popular implementation that uses signatures for conflict detection. Based on our experimental evaluation, by using this filtering mechanism the size of signatures are significantly reduced with no significant degradation of performance (in one of the benchmarks used in the evaluation, there is even an important improvement). 72 Chapter 3. Reducing the Use of Signatures in a HTM system 3.1 System Architecture The system architecture is composed by the LogTM-SE implementation [183] as the baseline system, and our CFM-TM attached to this system. The general vision of the architecture is a multicore system with private L1 data caches and shared L2 cache memory. The caches are inclusive, and therefore, if a line is stored in the L1 cache, it has to be also stored in the L2 cache. In this environment the LogTM-SE HTM system implements an eager conflict detector that detects conflicts among transactions with signatures, and an eager version manager, which logs old versions of transactional writes in per-thread private memory. Furthermore, LogTM-SE uses the same structure and tags for the cache lines, but introduce some changes in a conventional cache coherence protocol (it is expanded with sticky states [183]). More details about LogTM-SE can be found in Section 1.4.2. The goal of CFM-TM is to manage transactional writes faster, and free the LogTM-SE system from these operations. The architecture of CFM-TM is based on modifications of the private L1 cache memory, cache coherence protocol and the replacement algorithm. The baseline cache coherence scheme used in this work is the directory-based MESI protocol explained in Sections 1.1.3 and 1.4.2, with the directory placed at the shared L2 cache. 3.1.1 Managing Transactional Writes with CFM-TM The CFM-TM filters some transactional writes to the LogTM-SE base system. This filter is implemented with several changes in the base architecture, which we describe below. The WTx Bit CFM-TM adds a WTx bit at every L1 private cache line with to aims: detecting conflicts and hosting speculative data in L1. A transactional modified line is managed by the CFM-TM if its WTx bit is active (set to one). This bit is only accessible by the local core, and when it is set to 1, the cache line can not be evicted from L1 during the transaction (to maintain both versions of the data, the speculative version in L1, and the old version in L2). When a core is trying to access to a remote transactional line managed by the CFM-TM (WTx=1), the filter detects a conflict of data that is managed by the contention manager. If a line has the WTx unset, it is managed by the transactional baseline system with the regular protocol (the line is not managed by the CFM-TM filter). However, a cache line with 3.1. System Architecture 73 the WTx bit set to 1 has to be in state Exclusive or Modified (the copy of the line has to be present only in this L1 cache). Associativity Reduction CFM-TM works at the cost of reducing some cache capacity for other cache lines not hosted in the filter. When the WTx bit is set in a cache line, this line can not be evicted from the L1 private cache until the transaction commits or aborts, and because of this, the maximum number of speculative data in an associativity set has to be limited. This limit, which sets up the maximum amount of transactional data in the associativity set that can not be evicted, is called MNW (Maximum Non-evicted Ways). The MNW value is bounded by the number of ways of the associativity set of the L1 cache. According to our tests, a value of MNW of 25% of the associativity ways is the most appropriate. The value of MNW can be modified by software through a new instruction. Since the transactional data with the WTx bit set is not evicted, the number of ways of the associativity set might be dynamically and temporary reduced to other data lines. The MNW parameter can be changed dynamically at execution time (before each transaction starts). If MNW is zero, the filter never hosts transactional writes, and it remains deactivated. Check for Conflicts Figure 3.1 shows a flowchart that illustrates the checking for conflicts in the write set using CFM-TM and LogTM-SE. First, the value MNW is checked to know if the CFM-TM is active. In case the value of MNW is zero, the filter is deactivated, and the transactional memory system use the baseline LogTM-SE system. In case the value MNW is not zero, the filter is active, and it has to check if the WTx bit associated with the cache line is set to one. In affirmative case, a conflict is produced, and it is not necessary to activate the conflict detection system of the baseline TM system. In case the WTx is zero, the line is not managed by the CFM-TM, and the LogTM-SE system has to check the signatures looking for data conflicts. Managing L2 Transactional Data Since the memory cache system is inclusive, if a transactional write can not be evicted from L1 (WTx bit is set), then it can not be evicted from L2. Therefore, an associativity set of the L2 cache memory might be filled with non-evictable cache lines if we do not prevent 74 Chapter 3. Reducing the Use of Signatures in a HTM system Address MNW!=0 ? no no WT ==1 ? Con  ict yes yes LogTM-SE Check for Con  icts x Figure 3.1: Check for conflicts in the write set in a LogTM-SE system using the CFM-TM filter. this situation. To solve this, a control bit WTxL2 analogous to WTx is defined in the directory, and a new parameter MNWL2 (analogous to MNW) is managed by the system. The parameter MNWL2 (Maximum Non-evicted Ways in L2) indicates the maximum amount of transactional data in the associativity set that can not be evicted in L2. If the WTxL2 bit is set in the L2 cache, it means that the line is transactional, and the corresponding speculative data is in L1. The WTxL2 parameter is also used for preventing a speculative line from being evicted when the eviction starts at the L2 cache controller. Transactional Write Actions Figure 3.2 shows a flowchart that illustrates the actions taken when a transactional write is produced. As we see in the figure, first, the system checks if the CFM-TM filter is active (MNW greater than zero). If the filter is deactivated, the system uses directly the LogTMSE system, but when it is active, in order to check if CFM-TM can host the transactional cache line, the L1 cache controller checks if the limit of MNW speculative writes has been reached. In case the limit is reached, the LogTM-SE system takes the control. Otherwise, the L1 cache controller requests the L2 for the line (in case the line is in invalid state) or informs the directory that needs the exclusivity of the line (in case the line is in shared state). When the directory responds to the requester, it informs if the L2 can host the speculative line according to the MNWL2 parameter. When a transactional write is produced in a line that is in an Exclusive or Modified state with its WTx bit unset, the baseline coherence protocol does not make any request because the state does not change (with respect to the directory). 3.1. System Architecture 75 MNW=0 ? #WTx<MNW L1 ? ? or Shared Invalid L1 Extra control request LogTM−SE Transactional Write yes no yes no yes no L1 L2 set WTxL2 set WTx yes no L2 ? #WTxL2< MNWL2 Figure 3.2: A transactional write action in the LogTM-SE system using the CFM-TM filter. Furthermore, in order to test the conditions established by the MNWL2 parameter, an extra control request to the directory is necessary. 82 Chapter 3. Reducing the Use of Signatures in a HTM system 3.2 Signatures As mentioned above, LogTM-SE uses read and write hardware signatures (see Section 1.5) to detect conflicts. When LogTM-SE works with CFM-TM, the write signature may be reduced, because CFM-TM manages some transactional writes which does not reach the write signature of LogTM-SE. This contributes to use a smaller write signature without increasing the false positives rate. Other papers deal also with this problem, like Notary [184], where new techniques are proposed for reducing hardware cost and false conflicts (by privatization) that result in more efficient signatures. Signatures have the problem of having a fixed size and being not scalable. Specifically, a single size is not well suited to all kind of applications, i.e. signatures of 1024 bits might be oversized for a benchmark with small transactions [178], but too small for long size transactions [106]. To solve this problem, more signatures with different sizes could be provided, so that the application chooses the signature of minimum size that allows good performance. One contribution of this thesis proposes a new module of signatures, called FlexSig (see Chapter 5 and Chapter 6). This work goes further, and try to adapt the resources available for signatures to the demand of the request. To achieve this, priorities can be established depending on the needs of the requesters. FlexSig is an appropriate solution to manage the read and write signatures of a TM system with a CFM-TM filter, because it provides a flexible module that can assign few resources to the write signature, and to use the remaining resources for other purposes (for instance, a bigger read signature and the read and write signatures of other transactions). FlexSig can change the assigned resources in run time, it allows a more efficient use of the signature resources and it reduces the false positive rate (which improves the overall performance), which make it a good option for combining with the CFM-TM filter. 3.3 Evaluation In this section we evaluate the proposed CFM-TM filter. To evaluate the system, we compare LogTM-SE with and without CFM-TM. 3.3. Evaluation 83 3.3.1 System Model We evaluate CFM-TM and LogTM-SE by using GEMS [102] and the Simics [98] full system simulator (the framework described in Section 2.1.1) with the configuration of Table 2.1. The sizes of signatures are between 128 bits and 8192 bits, and are chosen depending on the application, trying to obtain a reduced false positive rate, with the minimum signature size. The size of signatures are chosen in order to maintain a rate of false positives similar in both systems. 3.3.2 Workloads We use three STAMP benchmarks [106] 1("Vacation", "Intruder" and "Labyrinth"), described at Section 2.2.2, and the "Barnes" SPLASH-2 workload [178], described in Section 2.2.1. Table 3.1 shows the workload characteristics, indicating the number of transactions and the average sizes of the read and write sets. Table 3.2 shows the inputs for each benchmark evaluated. Table 3.1: Workload characteristics. Benchmark #Tx Av.RS Av.WS Intruder 11224 7.23 3.36 Barnes 2330 5.8 4.4 Vacation 24776 19.7 3.6 Labyrinth 158 136.8 90.82 Table 3.2: Benchmark inputs. Benchmark INPUT Intruder -a10 -l4 -n2038 -s1 Barnes 4096 bodies Vacation -n4 -q60 -n90 -r16384 -t4096 Labyrinth -i random-x32-y32-z3-n64.txt 1with Luke Yen’s patches from the University of Wisconsin. 84 Chapter 3. Reducing the Use of Signatures in a HTM system 0 0.2 0.4 0.6 0.8 1 1.2 Intruder Barnes Vacation Labyrinth Normalized number of aborts LogTM−SE CFM−TM Figure 3.7: Normalized number of aborts. 3.3.3 Results For each benchmark and system configuration we determined the minimum signature size that allowed a rate of false positives less than 1%. We obtain a general reduction in the size of the write signature, and for some benchmarks even a performance improvement. It is very difficult to calculate so precisely the size of the signatures for achieve a number of aborts equal in all the benchmarks. This variability in the number of aborts is reflected in Figure 3.7. Following this rule, as Table 3.3 shows, the write signatures are reduced 75% in 3 of the benchmarks (from 512 to 128 bits), and it is reduced a 50% for the "Labyrinth" case (from 8192 to 4096 bits). Table 3.3: Read/Write signature’s size configuration in LogTM-SE with and without CFM-TM. Benchmark LogTM-SE RS/WS CFM-TM RS/WS WS reduction Intruder 512/512 512/128 75% Barnes 512/512 512/128 75% Vacation 1024/512 1024/128 75% Labyrinth 8192/8192 8192/4096 50% 3.3. Evaluation 85 0% 20% 40% 60% 80% 100% Intruder Barnes Vacation Labyrinth Writes Writes managed by LogTM−SE Writes managed by CFM−TM Figure 3.8: Write management distribution. To illustrate the influence of CFM-TM in the system, Figure 3.8 shows the proportion of writes managed by CFM-TM, and the writes managed by the LogTM-SE system (when the CFM-TM can not manage those writes). As the figure shows, most of the writes are managed by the CFM-TM system in "Intruder", "Barnes" and "Vacation", and near 50% is managed in "Labyrinth". Figure 3.9 shows the speedup of LogTM-SE + CFM-TM with respect to using LogTM-SE alone. Three of the benchmarks have roughly the same performance, whereas "Intruder" is more than 40% faster with the CFM-TM. For the benchmark "Barnes" we obtain a reduction of the signature size by a factor of four with roughly the same performance. It has an average read/write set that CFM-TM manage without problems. "Intruder" behaves specially well with CFM-TM. It is a high contention benchmark with an average read/write set that LogTM-SE doesn’t manage well because it does not have a sophisticated contention management policy, leading to a high number of transactions that abort. When CFM-TM is active, performance is improved in more than 40% because the average write set of the benchmark is managed almost completely by the filter, which allows fast aborts. Furthermore, the write signature reduction is 75%. 86 Chapter 3. Reducing the Use of Signatures in a HTM system 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Intruder Barnes Vacation Labyrinth Speed−up LogTM−SE LogTM−SE + CFM−TM Figure 3.9: Speed-up of LogTM-SE + CFM-TM. −35 −30 −25 −20 −15 −10 −5 0 5 10 Intruder Barnes Vacation Labyrinth Variation of #misses (%) Figure 3.10: Variation of L1 cache misses when the CFM-TM is activated (with respect to LogTM-SE alone). For benchmarks "Vacation" and "Labyrinth", with larger transactions, CFM-TM performance is slightly worse, but the signature size is reduced 75% for "Vacation" and is reduced 50% for "Labyrinth". Figure 3.10 shows the variability in the number of L1 cache misses due to a reduced associativity by transactional execution. For "Vacation" and "Intruder" there is a small increase of 5% in the number of misses. However, for "Barnes" and "Intruder" even the number of L1 cache misses are reduced because the logging is not performed. 3.3. Evaluation 87 Cycle Breakdown The cycle breakdowns provides detailed information about the execution time. Figure 3.11 shows the normalized cycle breakdown for each benchmark, with both configurations: the LogTM-SE alone and with the CFM-TM. The cycles are grouped in different phases: NON_TRANS represents the cycles used in non transactional code, BAD_TRANS represents the transactional cycles that were wasted in transactions that finally aborted, GOOD_TRANS are the good transactional cycles that lead to successful transactions, ABORTING are the cycles expended in the abort process, COMMITTING are the cycles expended in commits, BACKOFF are the backoff cycles (randomized number of cycles to reduce contention after aborts), BARRIER are the cycles spent in barriers and STALL are the cycles that transactions are stalled (when a conflict is produced, and trying to resolve the conflict without aborting). Figure 3.12 shows the normalized cycle breakdown of each benchmark, showing the specific phase in the xaxis. The values are normalized to compare the time spent in each situation with and without the CFM-TM. In these normalized graphs we can appreciate much better the improvement or deterioration of the behavior in each specific phase for each benchmark. Figure 3.12 (a) shows the results for the "Intruder" benchmark. The cycles are reduced in BAD_TRANS, ABORTING, BACKOFF, BARRIER and STALL phases because the number of aborts is less (see Figure 3.7) as well as the time spent in them. In the "Intruder" benchmark there is a barrier at the end of the transactional processing, which explains that the BARRIER time is also decreased (if there are less aborts, the barrier has to wait less time for the transactions). Figure 3.12 (b) shows the results of the "Barnes" benchmark. We see that the BAD_TRANS are increased with CFM-TM, because without the filter, some false positives are detected before the actual conflict is produced, and therefore these transactions abort before, and save some cycles. The GOOD_TRANS variability may be caused because fluctuations in the benchmark and the small relative time spent in transactions (see Figure 3.11). The ABORTING and BACKOFF reduction time are caused because the action of the CFM-TM filter. Figure 3.12 (c) shows the results for the "Vacation" benchmark. ABORTING cycles are less with CFM-TM (as expected), and it has worse behavior in BAD_TRANS, BACKOFF and STALL, because the number of aborts is slightly superior. Figure 3.12 (d) shows the results for the "Labyrinth" benchmark. We see again that the biggest difference is with the ABORTING cycles, due to the CFM-TM. 88 Chapter 3. Reducing the Use of Signatures in a HTM system 0 0.2 0.4 0.6 0.8 1 LogTM−SE CFM−TM LogTM−SE CFM−TM LogTM−SE CFM−TM LogTM−SE CFM−TM Normalized execution time (breakdown) Intruder Barnes Vacation Labyrinth stall barrier backoff commiting aborting good_trans bad_trans non_trans Figure 3.11: Normalized breakdown of execution cycles. 0 0.2 0.4 0.6 0.8 1 1.2 NON_TRANS BAD_TRANS GOOD_TRANS ABORTING COMMITING BACKOFF BARRIER STALL Normalized execution time LogTM−SE CFM−TM (a) "Intruder" breakdown. 0 0.2 0.4 0.6 0.8 1 1.2 NON_TRANS BAD_TRANS GOOD_TRANS ABORTING COMMITING BACKOFF BARRIER STALL Normalized execution time LogTM−SE CFM−TM (b) "Barnes" breakdown. 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 NON_TRANS BAD_TRANS GOOD_TRANS ABORTING COMMITING BACKOFF BARRIER STALL Normalized execution time LogTM−SE CFM−TM (c) "Vacation" breakdown. 0 0.2 0.4 0.6 0.8 1 1.2 NON_TRANS BAD_TRANS GOOD_TRANS ABORTING COMMITING BACKOFF BARRIER STALL Normalized execution time LogTM−SE CFM−TM (d) "Labyrinth" breakdown. Figure 3.12: Benchmarks breakdown. 3.4. Related Work 89 It is clearly visible from Figure 3.12 that the number of cycles spent in the abort process is drastically reduced. 3.4 Related Work The CFM-TM scheme tries to reduce write signature utilization and enhance the performance of TM systems that are decoupled from caches. In our paper we choose LogTM-SE as baseline system, because it is a very representative decoupled HTM system and it is easily virtualizable. Moreover, some HTM systems use the cache buffering capability in a similar way as CFM-TM (FlexTM [155] and UTM [8]). FlexTM is a flexible HTM that, among other things, uses signatures for conflict detection, uses L1 as a buffer for speculative data, and uses a per thread log when the cache overflows. The difference with CFM-TM is that FlexTM uses signatures all the time to detect conflicts, meanwhile CFM-TM detects conflicts using a WTx bit in L1 private cache. Unbounded Transactional Memory (UTM) uses a special structure held in memory to log old versions, and add two bits for each line that may be visible in all the memory hierarchy, in order to track transactional data. If the transaction fits in cache, the system does not log old versions (similar to CFM-TM) unless the line is evicted. CFM-TM differs from the previous HTM systems by hosting transactional data in L1 private cache until the transaction commits or aborts, that allows the system to use signatures in a conservative way (they are used as little as possible). FASTM: A Log-based Hardware Transactional Memory with Fast Abort Recovery FASTM [95] proposed a similar solution to CFM-TM, and it was published at the same time. It also proposes to use the cache memory to maintain the speculative data whereas the old data remains in higher levels of the cache memory. The difference with CFM-TM is that FASTM does not fix the transactional data to the cache, and it does not reduce the associativity temporally. Instead, when it has to evict a transactional write, the address is inserted in the signature. FASTM achieves a speed-up of 43% compared to LogTM-SE using the same signature sizes. 90 Chapter 3. Reducing the Use of Signatures in a HTM system 3.5 Conclusion In this paper we presented CFM-TM, a Cache Filtering Mechanism for Transactional Memory systems in order to reduce the hardware resources of the baseline TM system without reducing performance. We evaluate CFM-TM with LogTM-SE as baseline system using some benchmarks. We showed that in most of the cases the system performs better when the CFM-TM is activated, and what is more important, it is possible to reduce the size of the write signature used by LogTM-SE. CFM-TM can be deactivated by software at any time if virtualization is needed. To fully take advantage of the proposed filter, the multicore processor system should support a flexible management of signatures, and allowing signatures of variable size, such as our proposals in Chapters 5 and 6. CHAPTER 4 TOLERATING ASYMMETRIC DATA RACES WITH A HARDWARE SIGNATURE MODULE1 Parallel debugging is one of the keys to improve the productivity of parallel programmers. Concurrent errors are difficult to detect and debug, and it is an important source of low productivity. To solve this problem, many approaches have been proposed to deal with different kind of concurrent bugs. Data races are one of the most frequent causes of bugs, and they have received a significant attention by the research community [113] [132] [94] [151] [48] [49] [92] [172]. However, an important type of data races that have not received much attention are Asymmetric data races, described in Section 1.3.2. In these type of races, the state of well-tested, correct threads is corrupted by racing threads from external, typically third-party code. Figure 1.11 shows an example of an asymmetric data race, where a correctly synchronized thread (the safe thread) is corrupted by a thread that is not (the unsafe thread). In this example, the safe thread (T1) access to the content of a pointer in a correctly synchronized critical section, whereas T2 access the same pointer without synchronization, which produces a unpredictable behavior in T1 when it tries to update the contents of the pointer. The idea of this work is to detect when an unsafe thread tries to modify the state being accessed by a safe thread and prevent it from doing so. The result is a correct critical section. Correctness means 1This work was developed at the University of Illinois at Urbana-Champaign in collaboration with the members of the I-ACOMA group. Specifically, my contribution was: active participation in the discussion of the general and advanced ideas, evaluation and experimental results, as well as writing and reviewing the resulting conference paper. 98 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module T1 T2 lock(l1) unlock(l1) wr(x) rd(x)/wr(x) rd(x)/wr(x) Miss Nack Done T1 T2 lock(l1) unlock(l1) rd(x) rd(x) Miss Nack Done wr(x) wr(x) (a) (b) Figure 4.3: Examples to understand the Pacman’s operation. T1 T2 lock(l1) unlock(l1) wr(x) rd(x)/wr(x) T1 T2 lock(l1) unlock(l1) rd(x) Nack wr(x) (a) x in Modified or Exclusive state before enter the critical section. (b) x in Shared state before enter the critical section. Nack Writte back Inv. Figure 4.4: Examples to understand Cache State Prior to Entering the Critical Section. These two cases are straightforward, and Pacman is able to manage them without architectural modifications. Next we will describe three cache coherence situations that are more complex to deal with: cache state prior to enter the critical section, cache replacements during the critical section, and synchronization operations. Cache State Prior to Entering the Critical Section When a thread enters in a critical section, some cache lines may be in a state that enables the core to silently access them. Specifically, there are two cases: when x is Dirty (or Exclusive) in T1’s cache in Figures 4.4(a) and (b), and when x is Shared in T1’s cache in Figure 4.4(b). In these cases, the Pacman module will not observe T1’s access to x. None of the two cases prevent Pacman from ensuring the atomicity of the critical section. Consider the case when x is in M or E state in T1. When T2 attempts to access the line and a miss is produced, the coherence protocol forces T1 to write back the line. When the Pacman module detects that a core with a SigTable entry writes back a line, it assumes that the core had accessed the line. Consequently, while allowing the line to be written back to memory, it inserts the line’s address in the entry’s Signature and Nacks the requesting 4.2. PACMAN: Tolerating Asymmetric Data Races 99 (unsafe) core (hence ensuring critical section atomicity). No functional changes to the caches or coherence protocol is needed. If T1 had not accessed the data in the critical section, Pacman acts conservatively but not incorrectly. In the second case, being xin Shared state in T1, if T2 writes x, the hardware issues a coherence transaction that invalidates T1’s copy. In this case, Pacman requires a simple hardware extension. Specifically, it requires that T1’s cache informs, in its response to the invalidation, that indeed, it has invalidated a line. When the Pacman module detects that a core with a SigTable entry has invalidated a line, it assumes that the core has accessed the line in its critical section. Again, it may occur that this line has not been access in the critical section, but Pacman acts conservatively but in a correct way2. Supporting this change is simple. In a directory-based protocol, when a cache invalidates a line, it must set a bit in the invalidation acknowledgement returned to the directory. In a snoopy-based protocol, the cache that invalidates the line must set a bit in the network that is visible to the Pacman module. Cache Replacements During the Critical Section Consider the case when a core is executing a critical section and its cache evicts a line that was in the cache before the core entered the critical section. Such line is not in the signature, but it must be conservatively put there as the core may have accessed it silently during the critical section. There are two kinds of replacements: if the cache line is dirty (M state), the line is written back to memory, so the Pacman module detects this transaction. However, if the replaced line is clean, the Pacman module does not have any notification of the event. Therefore, another modification of Pacman is required: to send a notification (including the address line) when a cache replaces a clean line in a critical section, with the aim of including it in the corresponding SigTable entry. This modification can be implemented easily. Specifically, a new counter named Mode is added to the controller of the last level private cache. When Mode is not zero, the cache is in notification mode, and it sends a notification each time that replaces a clean line. Every successful lock acquire increments the counter and every unlock decrements it. This ensures that, in nested critical sections, the cache remains in notification mode throughout the outermost critical section. 2In all of these cases, a Nacked write has already invalidated the line from all the caches. This can hurt performance slightly if caches have to re-access the data. However, this occurs only once. 100 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module Synchronization Operations Every acquire and release operation should be notified to the Pacman module to allocate or release a new entry in the SigTable. But when the lock is in a line in M or E state, this does not happen. To solve this problem, we propose to send an extra notification in each successful acquire or release operation that do not need a network access. Another alternative would be to change the lock macros or libraries to add an explicit uncached write inside them. 4.2.4 Advanced Pacman Protocol to Avoid Deadlocks and Stalls To deal with more involved cases, we describe possible deadlock situations and the mechanism that Pacman uses to avoid them. Stalls and Deadlocks The potential deadlock situations in a Pacman basic protocol are three: 1. Some race bugs where all the threads synchronize. 2. False sharing. 3. False positives. Figure 4.5 shows two examples of the first situation. In Figure 4.5(a), T1 and T2 acquire two different locks (l1 and l2) and enter in their respective critical sections. As both are safe threads, both are protected against external accesses to the critical data, and both threads accessing at the same data (a1 and a2) with a timing that produces the stall of both threads. Figure 4.5(b) shows two threads (T1 and T2) acquiring two different locks (l1 and l2) accessing the same variable (a2). T2 successes accessing a2 and T1 gets Nacked, but T2 tries to acquire l1 (acquired by T1) and gets also stalled. The second possible deadlock situation is false sharing. For example, this would be the case of Figure 4.5(b), if T1, instead of accessing a2, access to another variable that share the cache line with a2. The third situation of deadlock is due to the false positives in signatures due to aliasing (see Section 1.5) or due to the cache state prior to entering the critical section (see Section 4.2.3). 4.2. PACMAN: Tolerating Asymmetric Data Races 101 T1 T2 T1 T2 lock(l1) lock(l2) a1= a2= a2= a1=Nacked lock(l1) lock(l2) lock(l1)a2= a2= Nacked (a) (b) Figure 4.5: Examples of data race bugs which lead to deadlock. Mechanism to Avoid Deadlocks The mechanism used by Pacman to avoid deadlocks are described here. To handle deadlocks, we add two new fields to each entry of the SigTable: 1. Stall_index: tells if the thread that owns the entry is being Nacked. Specifically, Stall_index stall the index of the SigTable entry that sends Nacks to the owner thread. 2. Lock_Acquire?: indicates if the thread that owns the entry is being Nacked while trying to acquire a lock (if Stall_index is not null). The algorithm to avoid the deadlock is the following: – When a core Ciis Nacked by the core corresponding to the jentry of the SigTable, the Pacman module checks if Cialso has a entry in the SigTable. If so, it sets the value of Stall_index to jin the entry corresponding to the Cicore. – It sets also Lock_Acquire? bit in case Ciis trying to acquire a lock. – The Pacman module follows the Stall_index pointer by checking entry jin the SigTable and reading its own Stall_index. – If, by following the Stall_index pointers in this way, the hardware ends up in entry i, it has detected a cycle. Once the deadlock is detected, the hardware needs to decide which thread among those in the cycle is allowed to perform one access without being Nacked. A simple approach is to pick one of the threads that holds locks requested by other threads (such as T2 in Figure 4.5(b)). Such threads are detected from the Lock_acquire? bit of other entries, and they need 102 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module T1 T2 lock(l1) lock(l2) g0= g1= g1'= g0'= unlock(l2) =g0 Nacked Figure 4.6: Breaking atomicity due to false sharing. to make progress to break the cycle. If there is no such thread, the hardware picks one thread at random. The next time that the Pacman module detects a request from the picked thread, it does not Nack it. Breaking Atomicity of Critical Sections With the algorithm described in the previous section, Pacman immediately finds and breaks any deadlock — unless it was already present in the original application. However, by letting one stalled thread complete one access, it can conceivably break the atomicity of a critical section. To understand the problem, we consider each of the three sources of deadlock listed in Section 4.2.4. In the first case (all the threads synchronize), Pacman can potentially break the atomicity of one of the critical sections. While Pacman could be designed to break only the atomicity of unsafe threads, such approach would not work for all the race bugs. An example is when T1 in Figure 4.5(b) is the unsafe thread. Overall, given the very low probability of breaking atomicity in this way, we do not attempt to avoid it. In the second case (false sharing), atomicity can potentially be broken unless special care is taken. To see why, consider Figure 4.6, which is a slightly modified version of Figure 4.5(a). In this example, variables g0 and g0’ share the same cache line, while g1 and g1’ share another line. Because of false sharing, threads T1 and T2 deadlock. By breaking the deadlock through letting T2 read g0’, Pacman is allowing the line to go to T2’s cache. Right after the end of T2 critical section, T2 could attempt to silently access g0 from its cache, which could break T1’s atomicity. To prevent this case from occurring, we could augment Pacman so that, when Pacman lets one access break a deadlock, it marks it as non-cacheable. The requesting core would be allowed to use (read or write) the word, but its cache would not be allowed to keep the line. 4.3. Implementation Issues 103 H-Block Controller SigTable Pacman Module Ring Cycle detection & Breakup Nack Request Ring H-Block h1 h2 hk . . . . . . Signature_in Hash functions SigTable CID Signature NL SI LA CID Signature NL SI LA . . . PID_in = Nack ? ? =PID_in . . . 1 (a) Pacman Module. (b) SigTable and H-Block. Nack 1Nack 2 address Wr.-back/Inv. = Nack2 Figure 4.7: Pacman Implementation. As a result, accesses to other words would miss in the cache. This extension would avoid breaking atomicity when false sharing occurs between words. However, a more elaborated solution would be needed when false sharing occurs between bytes of the same word. Given the very low probability of breaking atomicity due to false sharing, Pacman does not include this support (it can not handle this case). In the third case (false positives), letting one thread proceed does not break the atomicity of any critical section. 4.3 Implementation Issues The Pacman module is a hardware module connected to the on chip network (see Figure 4.7(a)). It comprises the SigTable and its controller. The controller is composed of one simple hash block (H-Block) and the cycle detection & breakup module. The latter chases the Stall_index links as described in Section 4.2.4 to detect and break deadlocks. Figure 4.7(b) shows the H-Block and the SigTable. The implementation is optimized to reduce the complexity of the controller. In case of an ordinary request in the network, the H-Block takes the address of the incoming request and insert it into an empty signature using 104 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module CID N bits Signature 1k bits NestingLevel (NL) 5 bits Stall_index (SI) N bits Lock_acquire? (LA) 1 bit Table 4.2: Size of the SigTable’s fields. a parallel Bloom filter (Signature_in in Figure 4.7(b)). The hash-encoded address (stored in Signature_in) is then checked for membership in valid SigTable entries from other cores (∈ or check operation in Figure 4.7(b)). Overall, in case of an ordinary request in the network, the H-Block’s operations can be performed in 2-3 cycles and are hidden under the first half of the network transaction. In the second half of the network transaction, when the caches have finished snooping, the network may receive a write back or invalidation response (Section 4.2.3). In this case, the H-Block checks if the core ID that writes back or is invalidated has a SigTable entry. If so, it bit-wise ORs the hashed address with the correct signature and raises the signal Nack2 . In this case, the H-Block’s operation takes 1-2 cycles. If Nack1 or Nack2 are raised and the cycle detection and breakup module does not prevent it, a Nack signal is returned on the network. All of the operations of the Pacman module except for cycle detection are simple enough to be overlapped with the network transaction. In a directory protocol, they overlap with directory module accesses. The cycle detection may take over 10 cycles, which is acceptable since it is done in background. In our current implementation, the sizes of the SigTable’s fields of Figure 4.7(b) are shown in Table 4.2. The size of CID and Stall_index depend on how many threads may be monitored at a time (the maximum number of threads is 2N). For Signature, we found that, with 1,024 bits, false positives are typically less than 1%. For NestingLevel, we allocate 5 bits, which is enough for all the benchmarks used in the evaluation. Finally, the Pacman module is enabled and disabled by the Pacman on and Pacman off commands, respectively. These can be implemented as writes to memory-mapped registers. These commands can be used to exclude the program regions that are serial or otherwise uninteresting. These two commands would be mainly used to exclude serial regions of programs and shared libraries. This way, overheads and signature pollution are reduced when Pacman is not necessary. 4.3. Implementation Issues 105 4.3.1 Other Issues Current systems usually support two functionalities that we did not mention up to now: multithreading and OS thread migration. Multithreading is when a core supports multiple threads at the same time, and thread migration is when the OS migrates one thread from one core to another. The previous discussion of Pacman assumes a single threaded core without virtualization support. In this section, we discuss how Pacman supports these two functionalities in a simple way. Furthermore, we also show a distributed version of the Pacman module. Virtualization: Pre-emption and Thread Migration Support While executing a critical section, a thread can be pre-empted and even migrated to another core. In an advanced design that requires OS support, we would like that (i) while a thread is pre-empted in a critical section, we keep protecting its critical section, and (ii) when it resumes in a potentially different core, we keep storing its accesses in the same signature. To support this, when the OS pre-empts a thread from core i, it checks the SigTable for an entry with CID equal to i. If it finds one, it changes its CID field. Specifically, if the thread does not run anywhere, it sets the CID field to a special code (e.g., OUT); if it finally runs on core j, then it sets the CID field to j. With this scheme, if a thread gets pre-empted and not running, it still has its critical section protected from asymmetric races. Indeed, its SigTable entry is still valid and coherence messages are checked against its signature. The checks may result in sending Nacks. Then, when the thread is scheduled on a different core, its accesses are still stored into the same old signature. This approach is efficient, since there is no copying or saving/restoring of SigTable entries. Moreover, the hardware is kept simple, since it always does the same thing: store accesses from core iinto the SigTable entry tagged with CID i.Stall_index does not get stale, since it contains a table index. If the program has more threads than cores, there may be several SigTable entries with a CID equal to OUT. In addition, at a given time, the SigTable entries may belong to threads from several different programs. Pacman works correctly because it uses physical addresses. There is an issue with the cache state left behind by a thread that migrates while executing a critical section. Recall from Section 4.2.3 that the thread may have entered the critical section with a cache state that it is later accessed while in the critical section without notifying 106 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module the Pacman module. We showed that Pacman (conservatively) captures this information at cache replacements or at write-backs/invalidations triggered by other core. However, if we now migrate the thread, we cannot capture such events. To keep the design simple, we accept this limitation. This means that Pacman misses the few cases listed in Section 4.2.3 for threads that migrate while in a critical section. A more aggressive approach would be to write back to memory all the dirty cache lines at the time the thread migrates while in a critical section. The addresses of these writebacks would be put in the signature. A more drastic approach would be not to allow migration during critical section execution. Overall, since critical sections are typically small, migration during their execution is rare and does not justify additional actions. Like all data-race handling techniques, Pacman is a best-effort approach (the probability of not tolerating an asymmetric data race is very low). Multithreading Support Multithreaded cores have multiple hardware contexts and run multiple threads at a time. It is possible that different threads executing on different contexts of the same core concurrently execute different critical sections. In this environment, Pacman requires an extension where the messages sent by cores to the SigTable include both the core ID and the hardware context ID within the core. Similarly, SigTable entries have both a CID and a ContextID field. The cache-state issues of Section 4.2.3 are handled conservatively. If multiple contexts in a core are concurrently executing critical sections, any writeback, invalidation, or replacement that needs to insert an address in a signature, lead to insert it in all the SigTable entries owned by that core. Since the SigTable is connected to the network, it can only observe data sharing across cores, not across contexts in a core. Consequently, for Pacman to tolerate races as described, a program can only use one context per core — although multiple programs can use the multiple contexts of a core. To allow a program to use multiple contexts in a core, bigger changes would be needed, such as stalling all the other threads in the core when one thread is executing a critical section. Extensions for a Distributed Pacman Module The discussion so far assumed a centralized Pacman module, which is reasonable for a snoopy protocol. To use Pacman in a system with a directory-based protocol, we need to distribute the Pacman module across the different directory modules. Since such a design is outside 4.4. Evaluation 107 our scope, we only outline it briefly. Like the directory, the module naturally lends itself to a distributed environment, with partitions based on address ranges. Consequently, each directory module has an associated Pacman module, which is in charge of the range of physical addresses assigned to the local directory module. When a thread enters a critical section, the hardware allocates an entry for the core in the SigTable of all the Pacman modules; when it exits it, all the entries are deallocated. When a thread misses on an address, the request naturally reaches the home directory of that address. There, the address is checked against the entries in the local Pacman module using the usual algorithm. The Pacman modules in the other directory modules are not checked. 4.4 Evaluation 4.4.1 Experimental Setup To evaluate the potential and performance of Pacman, we model Pacman by using the software framework for dynamic library instrumentation Pin [81] connected to a cycle-by-cycle execution driven architecture simulator based on SESC [142]. The simulator models a chip multiprocessor of 4 or 8 cores, configured by default by the parameters in Table 4.3. The cores are two-issue, in-order, and overlap memory accesses with instruction execution. Each core has a private cache hierarchy kept coherent by a basic MESI coherence protocol on an on-chip bus. The bus is connected to the Pacman module and to off-chip main memory. Unless otherwise indicated, the sizes of the fields in a SigTable entry are those shown in Table 4.4. To generate a signature, Pacman uses eight 128-bit Bloom filters in parallel using the H3 hash function from [147], for a total of 1,024 bits per signature. For sensitivity analysis, we consider two cache hierarchy models, namely one where each core only has an L1 cache, and one where it has both a private L1 and a private L2. The first model puts more pressure on Pacman. We evaluate Pacman with all the fourteen SPLASH-2 applications, the twelve PARSEC applications that support pthreads, the "Sphinx3" speech recognition software [150], and "Apache 2.2.3". The SPLASH-2 codes use their default inputs, while the PARSEC codes use the simmedium inputs. For "Sphinx3", we use the test input provided, which executes over 500 million instructions, while for "Apache", we set up clients that keep sending requests to the server, so that the server executes around 40 million instructions. 114 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module T1 lock(l1) . . . while(nWakeupTickets == 0){ . . . } nWakeupTickets--; unlock(l1) T2 if(slack>0){ nWakeupTickets++; } Figure 4.9: An asymmetric race in "Bodytrack" benchmark. T1 void ComputeSubTreeCost(...){ ... pb=b->parent; lock(l1) pb->subtree_cost+=b->subtree_cost; pb->interaction_synch +=1; unlock(l1) ... } T2 void ComputeSubTreeCost(...){ ... b->interaction_synch=0; b->subtree_cost+=b->cost; ... ... ... Figure 4.10: An asymmetric race in "FMM" benchmark. node from two different places (pb in T1 is the same as b in T2), and an asymmetric data race may happen. Artificial Inserted Bugs We also modified some SPLASH-2 benchmarks to have intentional asymmetric race collisions on their shared variables. We assume that all original threads in SPLASH-2 are safe threads. We concurrently create an extra unsafe thread that continuously write random values to the shared variables without any locks. These accesses cause asymmetric race problems during the execution. In the tests on Pacman simulation, we checked that Pacman detects and tolerates all asymmetric race cases introduced. 4.5. Related Work 115 4.5 Related Work 4.5.1 Software Proposals for Asymmetric Races To put our work in perspective, we describe in detail two existing proposals to tolerate asymmetric data races, namely, ToleRace [140] and ISOLATOR [137]. Both schemes are softwareonly (i.e., no hardware support is provided). We then summarize Pacman’s advantages over them. In ToleRace, when a safe thread Tsenters a critical section, it makes two copies in software of all the shared variables in the critical section. Let us call the original variablesVand the two copies V’ and V”. The safe thread then executes the critical section reading and writing V’. In the meantime, any unsafe thread Tucan access the original variables V. When Tscompletes the critical section, it compares Vand V”. Based on whether Vand V” are the same and on a knowledge of the access pattern interleaving of Tsand Tu, the safe thread makes one of three choices: (i) when Tu’s execution can be serialized before Ts’s, it copies in software V’ to V, (ii) when Ts’s execution can be serialized before Tu’s, it leaves Vas it is, and (iii) when the execution of Tuand Tscannot be serialized in any way, it interrupts the program. In cases (i) and (ii), the race has been tolerated; in case (iii) the race induces a sequentially inconsistent execution and, therefore, ToleRace is unable to handle it. ToleRace has several shortcomings. First, a race type of case (iii) cannot be handled adequately: leaving version Vor V’ produces an inconsistent execution (a detailed example is described in [137]). Second, when the critical section contains multiple variables and accesses, the analysis of what is the race case may become complicated. Third, analysis of access patterns is either conservative (if static) or slow (if dynamic). Finally, comparisons and copies are slow and race-prone. ISOLATOR [137] takes a different approach. When a safe thread Tsenters a critical section, it makes a copy in software of the pages that contain the shared variables that will be accessed in the critical section (Shadow Pages). Then, it changes the protection bits of the original pages to make them inaccessible. Tsoperates on the shadow pages. If an unsafe thread Tuaccesses the original pages, it gets an exception and gets de-scheduled. When Ts leaves the critical section, it copies the shadow pages back to the original pages and unprotects the latter. ISOLATOR has the advantage of always producing consistent executions. In addition, thanks to an optimization, the number of page copies can be reduced. However, it has several 116 Chapter 4. Tolerating Asymmetric Data Races with a Hardware Signature Module shortcomings. The first one is the substantial compiler and operating system (OS) support (or code re-writing by the user) required to place variables in the correct pages and adapt to changing access patterns in the program. To apply ISOLATOR to PARSEC, we would have to rewrite the code and change the variable allocations significantly. A second shortcoming is that, if such rewriting is not provided, ISOLATOR will often need to copy large amounts of data at critical section entries and exits. For example, such data copying is the main reason why ISOLATOR reports up to 8x overhead for the microbenchmarks in [137]. Finally, ISOLATOR is prone to deadlocks and livelocks due to false sharing at page level — e.g., assume that the unsafe thread Tugets de-scheduled and then Tsattempts to access a variable in a page that Tuhas protected. Moreover, the timeout-based mechanism that is used to detect such deadlocks is very slow. Overall, we conclude that neither ToleRace nor ISOLATOR provides the desired solution to handle asymmetric races. 4.5.2 Other Related Work Pacman is related to Transactional Memory (TM) (Section 1.4) in that it presents a concept analogous to strong atomicity [101] between a transaction and a non-transactional access. However, Pacman operates on lock-based code. Moreover, compared to HTM, Pacman does not need speculation, rollback, timestamp support, or version management. Even to detect inter-thread conflicts, Pacman cannot leverage HTM’s tagging of cache lines: since Pacman is non-speculative, data can overflow into memory. Hence, Pacman needs to keep a SigTable in memory. Compared to STM, Pacman does not need to analyze the code. Pacman is also related to hardware-based mechanisms for fine-grain memory protection, such as UFO [15] and iWatcher [187]. In UFO, each memory line has some bits that specify protection information. Such bits travel with the line to caches. It is possible to support Pacman-like functionality with UFO. However, UFO is substantially more intrusive, as it requires maintaining these distributed bits and building exception handlers for them. iWatcher is similar although it targets single core processors. Moreover, Pacman is also related to the many software or hardware schemes that detect and avoid atomicity violations, such as AVIO [92], AtomAid [94], AtomTracker [112], or LifeTx [185]. While Pacman focuses on avoiding races rather than atomicity violations, its hardware is effectively being used to keep atomicity, albeit for only user-defined critical sections. As a result of the latter, Pacman needs no training runs. Finally, there are some 4.6. Conclusions 117 software-only schemes to tolerate races and bugs, such as Rx [133] or Frost [172]. Such techniques, while effective, have substantially higher overheads. We find Pacman to have negligible overhead. Pacman differ from the previous proposals in that is the first hardware approach that detects asymmetric races, it is not based on data replication to maintain correctness in critical sections, and introduce a low overhead hardware solution based on signatures. Pacman also solve the inconsistency problems of ToleRace and the deadlocks of ISOLATOR. 4.6 Conclusions In this chapter we propose Pacman, the first scheme designed to tolerate asymmetric data races in production runs with negligible execution overhead. Pacman leverages cache coherence hardware to temporarily protect the variables that a thread accesses in a critical section. Unlike the previous, software-based schemes, Pacman induces negligible slowdown, needs no compiler or (in the base line design) OS support, and requires no application source code changes. Moreover, its hardware is unintrusive since it is concentrated in a module in the network, rather than in the cores. We evaluated Pacman for SPLASH-2, PARSEC, "Sphinx3", and "Apache" and showed that it has negligible overhead. Moreover, we uncovered two unreported asymmetric data races. CHAPTER 5 IMPLEMENTING A FLEXIBLE HARDWARE SIGNATURE MODULE Signatures are a hardware resource that can keep an unbounded number of addresses in a bounded space (see Section 1.5) and they can be used for many hardware tools related with parallel computer architecture, to optimize their resources and to enhance their performance. Examples of these tools are TM systems, data race detectors, deterministic replay or code analysis and optimization. A drawback of hardware signatures is the lack of flexibility. If signatures are designed for a specific purpose or application (with a specific size, number of hashes, etc.), probably doesn’t fit well for other different purposes. The contribution of the thesis presented in this chapter contributes to make signatures more flexible, proposing a new hardware signature module specifically designed to work in a concurrent environment, that we call FlexSig [122]. The aim is to make the best use of the hardware resources available, by hosting a large number of signatures in a limited and reduced amount of hardware resources, and to achieve a low false positive rate. This chapter presents a basic FlexSig module with symmetric allocation algorithms, whereas in Chapter 6 we present a more advanced FlexSig with asymmetric allocation algorithms and a higher performance parallel hardware implementation. The chapter is organized as follow: Section 5.1 describes our flexible signature module, Section 5.2 depicts a high-level implementation of the module, Section 5.3 evaluates the proposal, Section 5.4 discusses related work and Section 5.5 concludes the chapter. 120 Chapter 5. Implementing a Flexible Hardware Signature Module . . . 000 hT . . . 0 0 h4 0 FREE 0. . . 0 . . . h h h 1 2 3 1. . . 1 0 000 . . . . . . . . . 00 01 ID1 (Address, ID1) IDx M/T bits No operation performed hT−1 Figure 5.1: Block diagram of FlexSig. Each allocated signature in FlexSig has a variable number of hash functions kbetween 1 and T, depending on the number of signatures allocated concurrently. Each signature is identified with an ID. The total register space assigned to each signature is m=k∗M/Tbits. 5.1 FlexSig: Implementing Flexible Hardware Signatures FlexSig is based on parallel Bloom filters (see Section 1.5), but introducing mechanisms to use all the signature resources as much as possible and with a large flexibility to adapt to different signature demands, allowing a better efficiency and reconfigurability. Figure 5.1 shows the block diagram of FlexSig. It is composed of TBloom filters, each one composed of a M/T–bit register (Mis the total size of FlexSig) and a hash function, that can host between 1 and Tsignatures, each signature being composed of one or more Bloom filters. Each Bloom Filter has an identifier (ID) of the signature to which it belongs. The number of Bloom filters assigned to each signature depends on the number of signatures allocated. Moreover, the resources assigned to a given signature may change dynamically. The modules h1,h2,...hTare independent H3hash functions, each operating on one register. The registers in FlexSig are usually relatively small (for instance 64 bits), because a signature is composed of several of them. Every time FlexSig receives a request to insert a new address in one of its signatures, each hash function assigned to the signature sets one bit in its register. On the other hand, to check if an address is already stored in the signature, all the bits read by the corresponding hash functions should be 1. Deallocation requests clear all the IDs and registers assigned to the signature. Each time a new signature allocation request arrives, FlexSig assigns kBloom filters, k≤T, to the new signature. Then, the kBloom filters operate as a parallel Bloom filter inside FlexSig. The number of Bloom filters assigned depends on the current resource avail- 5.1. FlexSig : Implementing Flexible Hardware Signatures 121 1 ... Reg Reg Reg ID ID ID FLEXIBLE SIGNATURE MODULE Request h1 1 control Controller addrs 0 : hash functions (there is T hash functions).hx : we call Bloom Filter to the set composed by one register and one hash. Reg Bloom Filter ID different signatures with the thread, and by sID that identifies different signatures with the same thID. : implements the FlexSig logic. T : number of Bloom Filters. : one register per hash (T registers). : identifier of the owner. It is composed by thID that identifies the thread, and by sID that identifies Controller Insert-Check-Clear h2hT Figure 5.2: FlexSig module architecture. ability, that is, on the already allocated Bloom filters to previous signatures. If the hardware resources in FlexSig are fully used by previous signatures, FlexSig has to free several Bloom filters, already assigned, to allocate the new signature. This means that FlexSig has to reduce dynamically the size of any signature by releasing Bloom filters. In this case, the false positive rate may increase, but false negatives are never produced. Figure 5.2 shows the FlexSig module architecture. As said before, there are TBloom filters, each one composed of a register and a hash function. Attached to each register there is a thread identifier (thID) and a signature identifier (sID) (a thread might have more than one signature allocated), used to identify the registers assigned to a given signature. Therefore, being num_threads the maximum number of threads managed by the filter, and being max_sigs_per_thread the maximum number of signatures that a thread can allocate, thID and sID are log2(num_threads)–bit and log2(max_sigs_per_thread)–bit wide, respectively. Both thID and sID form the signature owner identifier (ID). The maximum number of Bloom filters per signature is T(when only one signature is allocated), and the minimum size is T/#max_csigs (the Bloom filters are distributed equally among signatures), being #max_csigs the maximum number of concurrent signatures in the module. The controller implements the allocation algorithm and the rest of functions needed for the correct operation of FlexSig. The complexity and efficiency of the controller is determined by the algorithm to allocate signature registers. 122 Chapter 5. Implementing a Flexible Hardware Signature Module ids register hash ID1 ID2 ID3 ID2 ID3 ID1 ID1 ID1 ids register hash ID1 ID2 ID3 ID2 ID3 ID1 ID1 ID1 FlexSig check(addr,ID1) ids register hash ID1 ID2 ID3 ID2 ID3 ID1 ID1 ID1 FlexSig deallocate(ID1) FlexSig insert(addr,ID1) Figure 5.3: Insertion, check and deallocation request in FlexSig. Figure 5.3 shows how to perform the insertion, check and deallocation requests. The insertion request must include the ID of the signature, so that the address is only inserted in the registers that matches this ID. The check operation is very similar to the insertion operation, but it is read-only. The deallocation consists of clearing the registers and IDs. 5.1.1 Allocation Algorithm The allocation algorithm is required to make room for a new signature. This algorithm may be very complicated, for example, by defining priorities to assign more or less Bloom filters depending on the requirements of the allocated signature. In this chapter we show a simple allocation algorithm with no priorities. In Chapter 6 we will extend FlexSig with priorities implementing several asymmetric allocation algorithms. Figure 5.4 shows a very simple graphical example of the allocation algorithm. At the beginning, the module is empty, and to allocate the new signature ID1, the controller just assigns all the resources to it. Next, to allocate ID2, the controller calculates the number of necessary resources for the new signature (8 Bloom filters) and it frees them from ID1. Finally, to allocate resources for ID3, the controller calculates the number of necessary resources for the new signature (5 Bloom filters) and it frees them from ID1 and ID2. To illustrate the advantages of FlexSig, the same example but in a system with conventional signatures (implemented with Bloom filters) is shown in Figure 5.5: a fixed number of 5.1. FlexSig : Implementing Flexible Hardware Signatures 123 Allocate(ID2) Allocate(ID3) Allocate(ID1) Figure 5.4: Example of the symmetric allocation algorithm of FlexSig. Allocate(ID2) Allocate(ID3) Allocate(ID1) Figure 5.5: Example of conventional signatures used in a system with a maximum of 16 simultaneous signature requesters. Bloom filters are assigned in each allocation request (only one Bloom filter in this case, to allow a maximum of 16 concurrent allocated signatures, the same as in the FlexSig example of Figure 5.4). This example illustrates the advantage of FlexSig with respect to conventional signatures, that make an inefficient use of resources because only for maximum concurrency (when the number of concurrent allocated signatures is 16 in this example) all the resources are used. Therefore, by generalizing the example of Figure 5.4, the controller of FlexSig should determine the average number of Bloom filters per signature taking into account the incoming request, that is T/n_sig, with Tbeing the number of Bloom filters and n_sig the number of signatures. Since Tmay not be a multiple of n_sig, in general it is not possible to assign exactly the same number of Bloom filters to each signature (for example the Allocate(ID3) in Figure 5.4). Moreover, there might be signatures in FlexSig with fewer than T/n_sig Bloom filters, due to previous allocations and deallocations and the fact that signatures can only reduce their size, but are not allowed to grow. One implementation that seeks to allocate resources as evenly as possible, would use the following policy to take into account these factors. The FlexSig controller computes the 130 Chapter 5. Implementing a Flexible Hardware Signature Module addrs ids type finite−state machine (FSM) request issue logic allocate ... Request Input queue ... 1 ids type P ids type execution execution insert/check/deallocate logic for request logic for request addrs addrs Parallel Controller Figure 5.8: Parallel controller implementation. to detect conflicts among transactions. Each transaction inserts in signatures its read and write addresses to maintain a summary of its read/write set. Conflicts with other transactions reads/writes are detected through the check operation. Since our purpose is to evaluate only signatures, our figure of merit is the false positive rate of the signature system. Higher false positive rates degrade performance, because for each false positive, the TM system has to do an unnecessary abort (rollback to the initial state and restart the transaction). For simplifying the allocation algorithm, we use unified signatures (see Section 5.3.1) to evaluate FlexSig, so we only need one signature per transaction for the read and write set, which allows us to implement the simple allocation algorithm described in Section 5.1.1. 5.3.1 Unified signatures: Simplifying FlexSig Implementation in TM TM uses two signatures per transaction, one for the read set and another one for the write set. Usually the read set is larger than the write set, and therefore, in order to use efficiently the resources, the signature of the read set should be larger than the signature of the write set. However, having signatures of different sizes for the write set and the read set introduces additional difficulties in the allocation algorithm and makes its implementation more complex. Unified signatures [36] propose to use only one signature for both the read set and the write 5.3. Evaluation in a TM System 131 Bench. input Genome -g128 Intruder -a10 -l16 -n4096 -s1 Kmeans-high -m15 -n15 -t0.05 -i random-n2048-d16-c16.txt Kmeans-low -m40 -n40 -t0.05 -i random-n2048-d16-c16.txt Labyrinth -i random-x256-y256-z3-n256.txt Ssca -s14 -i1.0 -u1.0 -l9 -p9 Vacation-high -n4 -q60 -u90 -r1048576 -t4096 Vacation-low -n2 -q90 -u98 -r1048576 -t4096 Yada -a10 -i ttimeu10000.2 Streamcluster 10 20 32 4096 4096 1000 Canneal 2000 2000 10.nets Table 5.1: Benchmark Inputs. set. This approach may generate read-read conflicts, however, these conflicts rarely lead to a performance lost [148][36]. Using unified signatures each thread only needs to allocate one signature per transaction, and the complexity of the controller is reduced. This is the approach we have used for evaluating FlexSig. 5.3.2 Experimental Setup To evaluate the FlexSig scheme we use a TM system with signatures used to track data accesses in transactions. Our aim is not to implement a fully functional TM system, but to work out a challenging scenario for FlexSig, and compare it with conventional parallel Bloom filters in the same situation. For the TM system we use the software implementation RSTM [159]. RSTM is a software TM system that allows many different configurations. In our evaluation we use a lazy acquisition and lazy versioning with extendable timestamps [143] to configure RSTM. We use PIN [81] to track all transactions and memory accesses of RSTM and to emulate the hardware signatures. This conforms the simulation of a Hybrid Transactional Memory system. We run several benchmarks over the RSTM system. Specifically, we use all the STAMP Benchmarks [25], two PARSEC Benchmarks [16] and nine micro benchmarks (included in the RSTM distribution). Table 5.1 shows the inputs of the benchmarks. The benchmarks not included in the table run with the default input. For this evaluation, we classify the bench- 132 Chapter 5. Implementing a Flexible Hardware Signature Module Benchmark #Tx TxTime RS WS Intruder 101780 32% 19 2 Vacation-high 4096 94% 384 7 Vacation-low 4096 94% 283 5 Yada 14316 68% 59 17 LinkedList 175 52% 141 0.3 DList 152 55% 138 0.6 PrivList 94 81% 256 1 Table 5.2: Benchmark set A, characterization with 16 threads. marks in two categories. One group is composed by benchmarks with a high false positive rate (Benchmark set A), and the other with a modest false positive rate (Benchmark set B). The purpose of this is to run each group of benchmarks with a different signature configuration to show the advantages of FlexSig for workloads with different characteristics. Tables 5.2 and 5.3 show the characterization of the benchmarks. The parameter #T x is the number of transactions of the benchmark, T xTime is the percentage of time spent on transactions, and RS and W S are the average number of reads and writes per transaction. The time spent in transactions is, in general, very significant. This parameter is affected by the instrumentation tool, because only transactions are instrumented. This scenario is a pessimistic approximation, since in a real system the time spent inside the transactions should be less, and therefore, it should be less likely that those transactions demand signatures at the same time in the FlexSig system. Therefore, the results should be better than in the simulated case. 5.3.3 Configuration For the evaluation we use the configurations shown in Table 5.4. The hardware configuration for parallel Bloom filters (kand mare the parameters in Figure 1.9) was chosen specifically to manage up to 16 threads (that is, the conventional signature system has 16 parallel Bloom filters of fixed size). We run experiments with 2, 4, 8 and 16 threads. Two configurations are used for FlexSig: configuration conf1 uses the same resources as their equivalent parallel Bloom filter, and conf2 uses half of the resources. For the benchmarks belonging to the set A, the registers are of 512 bits for the unified parallel Bloom filter (a total of 8192 bits for a 16 thread system); for FlexSig we have 32 registers of 128 bits for conf2, and 64 registers of 128 5.3. Evaluation in a TM System 133 Benchmark #Tx TxTime RS WS Bayes 644 46% 8 2 Genome 353994 76% 26 0 Kmeans-high 8238 43% 13 13 Kmeans-low 8557 70% 13 13 Labyrinth 544 54% 84 80 Ssca 93731 49% 1 2 Streamcluster 592 17% 1 0 Canneal 4000 44% 2 1 Counter 759 23% 1 1 HashTable 2772 47% 2 0.3 RBTree 16385 68% 18 2 RBTreeLarge 134 61% 27 3 LFUCache 62 61% 7 2 RandomGraph 53 59% 506 2 Table 5.3: Benchmark set B, characterization with 16 threads. Signature Description Unified Parallel Bloom (set B) 16 registers with k=4 and m=32 bits (512 bits total) Unified Parallel Bloom (set A) 16 registers with k=4 and m=512 bits (8192 bits total) Unified FlexSig conf2 (set B) 32 registers of 8 bits (256 bits total) Unified FlexSig conf1 (set B) 64 registers of 8 bits (512 bits total) Unified FlexSig conf2 (set A) 32 registers of 128 bits (4096 bits total) Unified FlexSig conf1 (set A) 64 registers of 128 bits (8192 bits total) Table 5.4: Configuration used with unified signatures. bits for conf1. Similarly, for the benchmarks belonging to the set B, the size of the registers for the unified parallel Bloom filter is 32 bits and the corresponding FlexSig configurations conf1 and conf2 are described in Table 5.4. To group registers (see Section 5.1.4), we choose groups of one register for 8 and 16 threads, and groups of two registers for executions with 2 and 4 threads. This decision was taken to have an efficient configuration (see Figure 1.10(b)). 134 Chapter 5. Implementing a Flexible Hardware Signature Module Benchmark 2 threads 4 threads 8 threads 16 threads Bloom conf2 conf1 Bloom conf2 conf1 Bloom conf2 conf1 Bloom conf2 conf1 Intruder 1.5 0.0 0.0 2.0 0.2 0.0 2.4 2.4 0.2 2.9 12.0 2.7 Vacation-high 38.1 3.7 0.5 37.9 13.0 3.7 38.1 38.0 24.2 38.3 52.9 38.2 Vacation-low 25.3 0.8 0.0 25.3 6.0 0.8 25.4 25.3 11.1 25.2 42.5 25.1 Yada 18.8 0.6 0.0 19.7 4.7 0.7 20.4 20.4 8.9 20.1 34.4 20.1 LinkedList 4.6 0.1 0.0 2.6 0.4 0.0 1.5 1.5 0.2 0.7 4.7 0.7 DList 4.0 0.1 0.0 2.9 0.5 0.0 2.0 2.0 0.2 0.7 2.9 0.7 PrivList 6.2 0.5 0.1 8.1 3.8 1.5 3.5 3.5 2.1 4.2 7.1 4.2 Table 5.5: Benchmark Set A. False positives comparison (in %) for Unified Signatures. Benchmark 2threads 4threads 8threads 16 threads Bloom conf2 conf1 Bloom conf2 conf1 Bloom conf2 conf1 Bloom conf2 conf1 Bayes 43.2 7.1 3.0 33.1 13.0 6.5 32.4 31.7 23.5 24.9 34.1 24.4 Genome 41.8 4.8 0.7 40.7 13.6 4.6 43.3 42.0 29.2 9.7 54.4 9.4 Kmeans-low45.1 11.2 1.0 41.2 17.9 10.6 40.0 40.0 36.4 36.7 69.8 36.6 Kmeans-high 40.6 7.6 0.7 37.6 16.4 8.3 36.6 36.6 33.8 37.5 66.1 37.4 Labyrinth 19.0 17.9 14.7 16.7 15.8 15.6 41.9 41.9 41.6 72.2 77.3 72.2 Ssca 1.1 0.0 0.0 1.1 0.1 0.0 1.2 1.1 0.0 1.2 7.7 1.1 Streamcluster 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 Canneal 3.3 0.0 0.0 3.2 0.0 0.0 3.5 3.5 0.5 3.3 9.6 3.1 Counter 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 HashTable 2.5 0.0 0.0 2.0 0.1 0.0 1.9 1.9 0.2 1.9 8.8 1.7 RBTree 49.7 16.7 8.3 53.6 30.8 19.7 46.8 46.8 40.3 44.0 50.1 44.0 RBTreeLarge 48.8 16.5 8.3 47.1 25.1 16.3 44.5 44.5 35.8 37.4 46.4 37.3 LFUCache 26.2 8.8 4.7 28.3 12.8 10.5 29.7 29.7 26.2 27.6 31.6 27.6 RandomGraph 17.9 13.4 11.8 17.0 12.7 10.7 16.6 16.6 14.4 16.9 20.3 16.9 Table 5.6: Benchmark Set B. False positives comparison (in %) for Unified Signatures. 5.3.4 Results Tables 5.5 and 5.6 show the false positive rate of FlexSig with configurations conf1 and conf2 compared with the results obtained with parallel Bloom filters (see Table 5.4), for the case of 2, 4, 8 and 16 threads. A white cell (in conf1 and conf2 columns) means that the false positive rate is roughly the same as the one obtained with the parallel Bloom filter, a gray cell means that the false positive rate of FlexSig is better (lower), and a dark gray means that the false positive rate of FlexSig is worse (higher). First, we comment the results with conf1 for both benchmark sets A and B. As Tables 5.5 and 5.6 show, the FlexSig-conf1 outperforms parallel Bloom filters in almost all the cases. For 2, 4 and 8 threads, the improvement is very high; for instance, for the case of "Vacation-high" running with 2 threads, the false positive rate is reduced from 38,1% to 0,5%. As the number of threads increases, the advantage of FlexSig decreases. However, even in the worst case 5.3. Evaluation in a TM System 135 (16 threads), FlexSig improves with respect to conventional Bloom filters in many cases, and never performs worse. The results are better as fewer threads are running, because FlexSig tries to use all the resources, while the parallel Bloom filter implementation has fixed size for each signature independently of the number of threads. The results of FlexSig-conf1 with 16 threads are very similar to the implementation with parallel Bloom filters since for this case all the signatures are used. FlexSig achieves better results because not all the threads allocate signatures at the same time, and it can use the free resources also in this case. The results are only slightly better because the benchmarks are highly concurrent (in part due to the instrumentation performed by PIN). FlexSig-conf2 uses half of the resources of the parallel Bloom filter implementation. Even with this configuration, FlexSig clearly outperforms the parallel Bloom filter implementation for 2 and 4 threads. For instance, for "Vacation-high" the false positive rate with two threads is reduced from 38,1% to 3,7%. For the case of 8 threads, the results are similar in both implementations, but FlexSig outperforms the parallel Bloom filter implementation in many cases, and at least matches it. For 16 threads, FlexSig has worse performance, but it has the flexibility to manage the 16 threads with half the resources. It is of interest to show the reduction of the number of false positives in absolute terms, since each false positive may lead to an unnecessary abort in a TM system. Figure 5.9 shows the percentage of decrease of the number of false positives in FlexSig-conf1 compared with conventional signatures for all benchmarks, which is specially high for 2,4 and 8 threads. Figure 5.10 shows the percentage of decrease of the absolute number of false positives in FlexSig-conf2 (with half of the resources of conventional signatures) compared with conventional signatures for all benchmarks, with very good results, except for 16 threads (the negative values represents – changing the sign to positive – the percentage of decrease of the absolute number of false positives in conventional signatures compared with FlexSig-conf2). For "StreamCluster" and "Counter" benchmarks, the number of false positives does not decrease in Figure 5.9 nor Figure 5.10, because in both simulations the number of false positives is zero for FlexSig and conventional signatures. Notice that the advantage of FlexSig when compared to conventional signatures is reduced as the number of threads increases. As we show in Section 6.3.5 (for FlexSig supporting priorities), this is not due to any scalability issue. The reason is that FlexSig always take advantage of all the resources of the module for any number of threads, and therefore increasing the number of threads reduces the average size of signatures for each thread. 136 Chapter 5. Implementing a Flexible Hardware Signature Module 0% 20% 40% 60% 80% 100% Intruder Vac.−high Vac.−low Yada Link.List DList PrivList Bayes Genome Km.−low Km.−high Labyrinth Ssca Streamcl. Canneal Counter HashTable RBTree RBTreeL. LFUCache R.Graph Reduction of false positives 2 threads 4 threads 8 threads 16 threads Figure 5.9: Percentage of decrease of the absolute number of false positives in FlexSig-conf1 compared with conventional signatures for all benchmarks. −80% −60% −40% −20% 0% 20% 40% 60% 80% 100% Intruder Vac.−high Vac.−low Yada Link.List DList PrivList Bayes Genome Km.−low Km.−high Labyrinth Ssca Streamcl. Canneal Counter HashTable RBTree RBTreeL. LFUCache R.Graph Reduction of false positives 2 threads 4 threads 8 threads 16 threads Figure 5.10: Percentage of decrease of the absolute number of false positives in FlexSig-conf2 compared with conventional signatures for all benchmarks. 5.3. Evaluation in a TM System 137 It is of interest to have an estimation of the average signature size that is used per transaction in FlexSig. The average signature size is the weighted average in time of the signature size, and is given by ave_sig_size =∑num_changes_size e=1sig_sizee∗time_intervale ∑num_changes_size e=1time_intervale (5.3) where num_changes_size is the number of times a signature changes its size (number of registers) before deallocation, and time_interval is the number of time units that a signature has a size sig_size. Figure 5.11 shows the improvement in the average signature size of FlexSig-conf1 running 16 threads compared with conventional signatures. The configuration of the signatures is shown in Table 5.4. This figure tries to show the advantage of FlexSig over conventional signatures with the same resources than FlexSig even in the situation where conventional signatures can use all their resources (in this case, with 16 running threads). Moreover, in a situation with less threads running, the advantage of FlexSig is much bigger. The improvement shown in the figure is achieved because not all the threads use signatures simultaneously, and therefore, threads can take resources that others are not using. The average signature size for FlexSig depends basically on the concurrent nature of the benchmark (less concurrent threads lead to a better performance of FlexSig). The best result in terms of FlexSig average signature size improvement is for "Streamcluster", with a more than 50% improvement, due to the low transaction concurrency in this benchmark. In this case, the improvement of the signature size doesn’t imply a significant reduction of the false positive rate because this is already very low in absolute terms. As a conclusion, the FlexSig system improves the false positive rate when compared with conventional parallel Bloom filters. In a system configured to run 16 threads, our signature system clearly outperforms the parallel Bloom filter implementation when the number of threads is lower than 16 (for the conf1 with the same resources), due to the flexibility of FlexSig to assign the physical resources depending on the demand (number of concurrent threads). General purpose multicore and multiprocessors are able to run a large number of concurrent threads, but many applications use only a few threads. FlexSig is flexible enough to provide these applications all the available signature resources to achieve better performance. We used very hard conditions in our evaluation to demonstrate that FlexSig can perform well even in an unfavourable scenario. The benchmarks used are highly concurrent, which means that many transactions use signatures at the same time. Moreover, because of the instru- 138 Chapter 5. Implementing a Flexible Hardware Signature Module 0% 10% 20% 30% 40% 50% Intruder Vac.−high Vac.−low Yada Link.List DList PrivList Bayes Genome Km.−low Km.−high Labyrinth Ssca Streamcl. Canneal Counter HashTable RBTree RBTreeL. LFUCache R.Graph Improvement in size of the Signature Figure 5.11: Increment of the average signature size in FlexSig-conf1 with 16 threads compared to regular signatures for Benchmark Set A and Set B. mentation tool, the benchmarks spend more time inside transactions, increasing transactional concurrency. 5.4 Related Work Most of the papers dealing with signatures are focused on improving performance, reducing chip area or reducing the false positive rate [147][134][182][154][184]. However none of these papers focus on flexibility and scalability. The Scalable Bloom Filters (SBF) proposed by [4] tries to make an approximation of scalable signatures. They use one signature, and when a fill ratio is reached, another signature is used. SBF was proposed to avoid the problem of oversize signatures due to the fact that the size of the signature must be defined previously based on the number of elements to be stored and the desired upper bound of the false positive rate. The SBF method can reduce the specific size of the signature used. However, it may use several signatures depending on the number of elements to be stored, and therefore, in reference to our context, the system has to be oversized anyway (with regard to the number of 5.5. Conclusions 139 signatures). FlexSig does not fully avoid the problem of oversized signatures, but it is more flexible and efficient in the sense that it uses as many hardware resources as possible, having a significant effect on the false positive rate for a TM system. In recent publications we find TM systems that fit very well for using FlexSig. In [104] proposes a STM system with a centralized conflict detection mechanism (based on software signatures) placed in one core. One way to improve this scheme would be to use FlexSig instead of their software signatures. This would improve performance maintaining the flexibility of the software signatures. Another example is the scheme proposed by [28], that describes a new centralized hardware outside the processor chip to accelerate STM systems. This special hardware includes signatures. They also propose two algorithms for conflict detection, one using two signatures per transaction and other using three signatures. FlexSig would allow to implement both with the same hardware and also performance would be improved. The idea behind FlexSig is similar to the recent trend of incorporating a shared last level cache in multicore systems. The cache size used by each core varies dynamically depending on the application. This leads to a more flexible system than having a fixed size slice of the last level cache assigned to each core. FlexSig follows this trend for a resource that might be of interest for future multicore implementations. 5.5 Conclusions In this chapter we propose a module for hardware signatures to improve conventional signatures in terms of flexibility, scalability and fault tolerance. The main feature of FlexSig is that it can host a high number of signatures for cases with applications with a high number of threads and significant contention, and for the cases for low contention or few threads, it can achieve a very low false positive rate. We described the module and its implementation, defined a detailed algorithm to allocate signatures and evaluated FlexSig in the context of a TM system and compared it to an implementation with conventional parallel Bloom filters. From the evaluation performed, we show that, when the number of threads is low, FlexSig achieves a significant improvement because of the flexibility to use all the available resources. When the number of threads is high, the results are similar to the conventional implementation due to the highly concurrent nature of the benchmarks. However, with the same amount of resources, FlexSig never behave worse than conventional parallel Bloom filters.