Removal of Conflicts in Hardware Transactional Memory Systems
Tóm tắt
This paper analyzes the sources of performance losses in hardware transactional memory and investigates techniques to reduce the losses. It dissects the root causes of data conflicts in hardware transactional memory systems (HTM) into four classes of conflicts: true sharing, false sharing, silent store, and write-write conflicts. These conflicts can cause performance and energy losses due to aborts and extra communication. To quantify losses, the paper proposes the 5C cache-miss classification model that extends the well-established 4C model with a new class of cache misses known as contamination misses. The paper also contributes with two techniques for removal of data conflicts: One for removal of false sharing conflicts and another for removal of silent store conflicts. In addition, it revisits and adapts a technique that is able to reduce losses due to both true and false conflicts. All of the proposed techniques can be accommodated in a lazy versioning and lazy conflict resolution HTM built on top of a MESI cache-coherence infrastructure with quite modest extensions. Their ability to reduce performance is quantitatively established, individually as well as in combination. Performance and energy consumption are improved substantially.
Tài liệu tham khảo
Alameldeen, A.R., Wood, D.A.: Variability in architectural simulations of multi-threaded workloads. In: Proceedings of the 9th Annual International Symposium on High-Performance Computer Architecture, Anaheim, CA, 8–12 Feb 2003
Ananian, C.S., Asanovi’c, K., Kuszmaul, B.C., Leiserson, C.E., Lie, S.: Unbounded transactional memory. In: Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA’05), pp. 316–327, San Francisco, CA, Feb 2005
Bobba, J., Moore, K.E., Yen, L., Volos, H., Hill, M.D., Swift, M.M., Wood, D.A.: Performance pathologies in hardware transactional memory. In: Proceedings of the 34th International Symposium on Computer Architecture, June 2007
Ceze, L., Tuck, J., Cascaval, C., Torrellas, J.: Bulk disambiguation of speculative threads in multiprocessors. In: Proceedings of the 33rd International Symposium on Computer Architecture, June 2006
Chen, Y.S., Dubios, M.: Cache protocols with partial block invalidations. In: Proceedings of 7th International Parallel Processing Symposium, CA, USA, April 1993
Colohan, C.B., Aliamaki, A., Steffan, J.G., Mowry, T.C.: Tolerating dependences between large speculative threads via sub-threads. In: Proceedings of the 33rd International Symposium on Computer Architecture, pp. 216–226, Boston, MA, June 2006
Culler D.E., Gupta A., Singh J.P.: Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann Publishers Inc., California (1998)
Dahlgren, F., Dubois, M., Stenstrom, P.: Sequential hardware prefetching in shared-memory multiprocessors. IEEE Trans. Parallel Distrib. Syst. 6(7), 733–746 (1995)
Dubois, M., Skeppstedt, J., Ricciulli, L., Ramamurthy, K., Stenstrom, P.: The detection and elimination of useless misses in multiprocessors. In: Proceedings of the 20th International Symposium on Computer Architecture, San Diego, CA, USA (1993)
Hammond, L., Wong, V., Chen, M., Hertzberg, B., Carlstrom, B., Davis, J., Prabhu, M., Wijaya, H., Kozyrakis C., Olukotun, K.: Transactional memory coherence and consistency. In: Proceedings of the 31st Annual International Symposium on Computer Architecture, pp. 102–113, München, Germany, 19–23 June 2004
Harris, T., Larus, J., Rajwar, R.: Transactional memory. Synthesis Lectures on Computer Architecture, vol. 5, no. 1, June 2010
Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th International Symposium on Computer Architecture, pp. 289–300 May 1993
Kamble, M.B., Ghose, K.: Analytical energy dissipation models for low power caches. In: Proceedings of the International Symposium on Low Power Electronics and Design, pp. 143–148, Aug 1997
Lepak, K.M., Bell, G.B., Lipasti, M.H.: Silent stores and store value locality. IEEE Trans. Comput. 50(11) (2001)
Lupon, M., Magklis, G., Gonzalez, A.: FASTM: a log-based hardware transactional memory with fast abort recovery. In: Proceedings of the 18th International Conference on Parallel Architectures and Compilation Techniques, 12–16 Sept 2009
Magnusson P.S., Christensson M., Eskilson J., Forsgren D., Hallberg G., Hogberg J., Larsson F., Moestedt A., Werner B.: Simics: a full system simulation platform. IEEE Comput. 3(5), 50–58 (2002)
McDonald, A., Chung, J., Carlstrom, B.D., Minh, C.C., Chafi, H., Kozyrakis, C., Olukotun K.: Architectural semantics for practical transactional memory. In: Proceedings of the 33rd annual international symposium on computer architecture, Boston, MA, 17–21 June 2006
Minh, C.C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: stanford transactional applications for multi-processing. In: Proceedings of the International Symposium on Workload Characterization, September 2008
Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., Wood D.A.: LogTM: log-based transactional memory. In: Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture (HPCA-12), pp. 258–269, Austin, TX, 11–15 Feb 2006
Moravan, M.J., Bobba, J., Moore, K.E., Yen, L., Hill, M.D., Liblit, B., Seift, M.M., Wood, D.A.: Supporting nested transactional memory in LogTM. In: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOSXII), pp. 359–370 (2006)
Negi, A., Waliullah, M.M., Stenstrom, P.: LV*: a low complexity lazy versioning HTM infrastructure. In: Proceedings of 10th IEEE IC-SAMOS, July 2010
Rajwar, R., Herlihy, M., Lai, L.: Virtualizing transactional memory. In: Proceedings of the 32nd International Symposium on Computer Architecture, pp. 494–505, June 2005
Shriraman A., Dwarkadas S.: Analyzing conflicts in hardware-supported memory transactions. Int. J. Parallel Program 9(1), 33–61 (2010)
Tabba, F., Hay, A.W., Goodman, J.R.: Transactional value prediction. In: Proceedings of the ACM SIGPLAN Workshop on Transactional Computing, Feb 2009
Tomić, S., Perfumo, C., Kulkarni, C., Armejach, A., Cristal, A., Unsal, O., Haris, T., Valero, M.: EazyHTM: eager-lazy hardware transactional memory. In: Proceedings of the 42nd International Symposium on Microarchitecture, New York, Dec 2009
Waliullah, M.M., Stenstrom, P.: Intermediate checkpointing with conflicting access prediction in transactional memory systems. In: Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008
Waliullah, M.M., Stenstrom, P.: Classification and elimination of conflicts in hardware transactional memory systems. In: 23rd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’2011), Vitória, Espírito Santo, Brazil, Oct 2011