Transaction Scheduling Using Conflict Avoidance And Contention Intensity

In the last few years, Transactional Memories (TMs) have been shown to be a parallel programming model that can effectively combine performance improvement with ease of programming. Moreover, the recent introduction of TM-based ISA extensions, by major microprocessor manufacturers, also seems to endorse TM as a programming model for today's parallel applications. One of the central issues in designing Software TM (STM) systems is to identify mechanisms/heuristics that can minimize contention arising from conflicting transactions. Although a number of mechanisms have been proposed to tackle contention, such techniques have a limited scope, as conflict is avoided by either interrupting or serializing transaction execution, thus considerably impacting performance. To deal with this limitation, we have proposed a new effective transaction scheduler, along with a conflict-avoidance heuristic, that implements a fully cooperative scheduler that switches a conflicting transaction by another with a lower conflicting probability. This paper extends such framework and introduces a new heuristic, built from the combination of our previous conflict avoidance technique with the Contention Intensity heuristic proposed by Yoo and Lee. Experimental results, obtained using the STMBench7 and STAMP benchmarks atop tinySTM, show that the proposed heuristic produces significant speedups when compared to other four solutions. © 2013 IEEE.236245IEEE Computer Society's Technical',ACM,Committee on Parallel Processing (TCPP),et al.,Shell IndiaHerlihy, M., Moss, J.E.B., Transactional memory: Architectural support for lock-free data structures (1993) Proceedings of the 20th Annual International Symposium on Computer Architecture, pp. 289-300. , JunWang, A., Gaudet, M., Wu, P., Amaral, J.N., Ohmacht, M., Barton, C., Silvera, R., Michael, M., Evaluation of blue gene/q hardware support for transactional memories (2012) Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques, pp. 127-136Christie, D., Chung, J.-W., Diestelhorst, S., Hohmuth, M., Pohlack, M., Fetzer, C., Nowack, M., Rivière, E., Evaluation of amd's advanced synchronization facility within a complete transactional memory stack (2010) Proceedings of the 5th European Conference on Computer Systems, pp. 27-40Chung, J., Yen, L., Diestelhorst, S., Pohlack, M., Hohmuth, M., Christie, D., Grossman, D., ASF: AMD64 extension for lock-free data structures and transactional memory (2010) Proceedings of the 43rd ACM/IEEE International Symposium on Microarchitecture, pp. 39-50. , Dec(2012) Intel Architecture Instruction Set Extensions Programming Reference, , Intel, FebHarris, T., Larus, J., Rajwar, R., (2010) Transactional Memory, , 2nd ed. Morgan & Claypool Publishers, JunGuerraoui, R., Herlihy, M., Pochon, B., Towards a theory of transactional contention managers (2006) Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 316-317Ansari, M., Lujan, M., Kotselidis, C., Jarvis, K., Kirkham, C., Watson, I., Steal-on-Abort: Improving transactional memory performance through dynamic transaction reordering (2009) Proceedings of the 4th International Conference on High Performance Embedded Architectures and Compilers, pp. 4-18. , JanDolev, S., Hendler, D., Suissa, A., CAR-STM: Scheduling-based collision avoidance and resolution for software transactional memory (2008) Proceedings of the 27th Annual Symposium on Principles of Distributed Computing, pp. 125-134. , AugYoo, R.M., Lee, H.-H.S., Adaptive transaction scheduling for transactional memory systems (2008) Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 169-178. , JunDragojevic, A., Guerraoui, R., Singh, A.V., Singh, V., Preventing versus curing: Avoiding conflicts in transactional memories (2009) Proceedings of the 28th Annual Symposium on Principles of Distributed Computing, pp. 7-16. , AugNicácio, D., Baldassin, A., Araújo, G., LUTS: A lightweight userlevel transaction scheduler (2011) Proceedings of the 11th International Conference on Algorithms and Architectures for Parallel Processing, pp. 144-157. , OctNicácio, D., Baldassin, A., Araujo, G., Transaction scheduling using dynamic conflict avoidance (2013) International Journal of Parallel Programming, 41 (1), pp. 89-110Guerraoui, R., Kapalka, M., Vitek, J., STMBench7: A benchmark for software transactional memory (2007) Proceedings of the 2nd European Conference on Computer Systems, pp. 315-324. , MarMinh, C.C., Chung, J., Kozyrakis, C., Olukotun, K., STAMP: Stanford transactional applications for multi-processing (2008) Proceedings of the IEEE International Symposium on Workload Characterization, pp. 35-46. , SepChristie, D., Chung, J.-W., Diestelhorst, S., Hohmuth, M., Pohlack, M., Fetzer, C., Nowack, M., Riviere, E., Evaluation of AMD's advanced synchronization facility within a complete transactional memory stack (2010) Proceedings of the 5th European Conference on Computer Systems, pp. 27-40. , AprHerlihy, M., Luchangco, V., Moir, M., Scherer, W.N., Software transactional memory for dynamic-sized data structures (2003) Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pp. 92-101. , JulGuerraoui, R., Herlihy, M., Pochon, B., Polymorphic contention management (2005) 19th International Symposium on Distributed Computing, pp. 303-323. , SepScherer, W.N., Scott, M.L., Advanced contention management for dynamic software transactional memory (2005) Proceedings of the 24th Annual Symposium on Principles of Distributed Computing, pp. 240-248Attiya, H., Epstein, L., Shachnai, H., Tamir, T., Transactional contention management as a non-clairvoyant scheduling problem (2006) Proceedings of the 25th Annual Symposium on Principles of Distributed Computing, pp. 308-315. , JulSpear, M.F., Dalessandro, L., Marathe, V.J., Scott, M.L., A comprehensive strategy for contention management in software transactional memory (2009) Proceedings of the 14th Symposium on Principles and Practice of Parallel Programming, pp. 141-150. , FebSharma, G., Busch, C., Window-based greedy contention management for transactional memory: Theory and practice (2012) Distributed Computing, 25 (3), pp. 225-248. , JunAttiya, H., Milani, A., Transactional scheduling for read-dominated workloads (2012) Journal of Parallel and Distributed Computing, 72 (10), pp. 1386-1396. , OctMaldonado, W., Marlier, P., Felber, P., Suissa, A., Hendler, D., Fedorova, A., Lawall, J.L., Muller, G., Scheduling support for transactional memory contention management (2010) Proceedings of the 15th Symposium on Principles and Practice of Parallel Programming, pp. 79-90. , JanBlake, G., Dreslinski, R.G., Mudge, T., Proactive transaction scheduling for contention management (2009) Proceedings of the 42nd ACM/IEEE International Symposium on Microarchitecture, pp. 156-167. , DecAtoofian, E., Improving performance of software transactional memory through contention locality (2013) The Journal of Supercomputing, 64 (2), pp. 527-547. , MayHeber, T., Hendler, D., Suissa, A., On the impact of serializing contention management on stm performance (2012) Journal of Parallel and Distributed Computing, 72 (6), pp. 739-750. , Ju