在事務型軟體式記憶體管理(sofrware transactional memory)中，若以保護的單元為分類基準，資源保護演算法能夠分類成粗顆粒(coarse-grained)和細顆粒(fine-grained)的演算法。依照我們的定義，細顆粒的演算法指的是以字元或是以物件等等不同的保護單元，以保護單元為基礎的演算法。至於粗顆粒的演算法則是指使用了全域鎖(global lock)的演算法。其中，粗顆粒的演算法的缺點是在競爭高的情況下缺少延展性；而細顆粒的演算法相較於粗顆粒演算法，使用時有較多的額外負載。根據不同的使用環境的需求，這兩種演算法都有適用的時機。
本論文提出了一個使用群組方式的細顆粒演算法。該演算法在執行期時將會以事務(transaction)為分類單位，讓各個被事務取用的保護單元，加入到第一個使用該保護單元的事務管理之下，使得事務能夠減少管理的額外負載。從實驗結果中我們發現，我們的演算法除了保持了細顆粒演算法的延展性外，也有效的減少了使用時所產生的額外負載。
我們也另外提出了一個驗證的演算法。在事務型軟體式記憶體管理中，驗證演算法主要負責在並行執行的事務型軟體式記憶體管理單元中，確保資料的一致性，以保證結果的正確。目前典型的驗證演算法在驗證時，會對理應通過驗證的事務型軟體式記憶體管理單元，產生該次驗證為不合法的結果。我們的新驗證演算法，經由使用兩階段驗證和考慮事務型軟體式記憶體管理單元的行為，能夠減少這種狀況的發生。

In software transactional memory(STM) systems, the transactional locking scheme is commonly separated into fine-grained and coarse-grained schemes by protection granularity. In our definition, the protection granularity of fine-grained schemes is varied depending on implementation. Types of protection granularity include per-word, per-object, etc. The protection mechanism of coarse-grained scheme is using a global lock for all shared resources. These two types of schemes are preferred under different test environments. The coarse-grained scheme lacks scalability under high contention situation and the fine-grained scheme produces higher overhead than coarse-grained scheme.
We propose a new type of fine-grained scheme which adds an intermediate locking level. The new scheme separates shared resources into different groups. Groups are organized under the number of executing transactions, and resources are joined to the first accessed transaction group. In experiment of new scheme, the results showed that the new scheme preserves the scalability and reduces the overhead of fine-grained scheme.
We also propose a new algorithm for validating data consistency in STM. The validation system is used to detect data inconsistency for concurrently executing transactions. The classic validation system had false validation when validating a transaction. The false validation turns a possible commit transaction to an unavoidable abort transaction. Our new scheme reduces the situation of false validation by using two steps of validation and considering interactions between transactions.

[1] M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of transactional memory and
automatic mutual exclusion. SIGPLAN Not., 43(1):63--74, 2008.
[2] E. Atoofian, A. Baniasadi, and Y. Coady. Adaptive read validation in time-based software
transactional memory. In Euro-Par Workshops, pages 152--162, 2008.
[3] U. Aydonat and T. Abdelrahman. Serializability of transactions in software transactional
memory. In TRANSACT '08: 3rd Workshop on Transactional Computing, feb 2008.
[4] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in
database systems. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,
1987.
[5] L. Dalessandro, M. F. Spear, and M. L. Scott. NOrec: Streamlining STM by abolishing
ownership records. In PPoPP '10: Proc. 15th ACM Symp. on Principles and Practice
of Parallel Programming, Jan 2010.
[6] P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid
transactional memory. In ASPLOS-XII: Proceedings of the 12th international conference
on Architectural support for programming languages and operating systems,
pages 336--346, New York, NY, USA, 2006. ACM.
[7] D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In DISC '06:Proc. of the
20th International Symposium on Distributed Computing (), pages 194--208, 2006.
[8] D. Dice and N. Shavit. What really makes transactions faster? In TRANSACT '06:
Proc. of the 1st Transactional Computing. ACM SIGPLAN, 2006. Electronic, no. page
numbers.
[9] A. Dragojevi c, R. Guerraoui, and M. Kapalka. Stretching transactional memory. In
PLDI '09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language
design and implementation, pages 155--165, New York, NY, USA, 2009. ACM.
[10] J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.
[11] R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic contention management. In
DISC '05: Proceedings of the nineteenth International Symposium on Distributed Computing,
pages 303--323. LNCS, Springer, Sep 2005.
[12] R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP
'08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of
parallel programming, pages 175--184, New York, NY, USA, 2008. ACM.
[13] R. Guerraoui and M. Kapalka. The semantics of progress in lock-based transactional
memory. In POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium
on Principles of programming languages, pages 404--415, New York, NY,
USA, 2009. ACM.
[14] L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K.
Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional memory coherence
and consistency. SIGARCH Comput. Archit. News, 32(2):102, 2004.
[15] A. Heindl and G. Pokam. An analytic model for optimistic stm with lazy locking.
In ASMTA '09: Proceedings of the 16th International Conference on Analytical and
Stochastic Modeling Techniques and Applications, pages 339--353, Berlin, Heidelberg,
2009. Springer-Verlag.
[16] M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free
data structures. SIGARCH Comput. Archit. News, 21(2):289--300, 1993.
[17] M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann,
March 2008.
[18] M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent
objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.
[19] V. J. Marathe, W. N. Scherer, and M. L. Scott. Design tradeoffs in modern software
transactional memory systems. In LCR '04: Proceedings of the 7th workshop on Workshop
on languages, compilers, and run-time support for scalable systems, pages 1--7,
New York, NY, USA, 2004. ACM.
[20] V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III,
and M. L. Scott. Lowering the overhead of nonblocking software transactional memory.
In TRANSACT: the 1st ACM SIGPLAN Workshop on Languages, Compilers, and
Hardware Support for Transactional Computing, June 2006.
[21] C. C. Minh, M. Trautmann, J. Chung, A. McDonald, N. Bronson, J. Casper,
C. Kozyrakis, and K. Olukotun. An effective hybrid transactional memory system with
strong isolation guarantees. In ISCA '07: Proceedings of the 34th annual international
symposium on Computer architecture, pages 69--80, New York, NY, USA, 2007. ACM.
[22] K. E. Moore. Log-based transactional memory. PhD thesis, The University of Wisconsin
- Madison, Madison, WI, USA, 2007. Adviser-Wood, David A.
[23] D. Nicácio and G. Araújo. Reducing false aborts in stm systems. In ICA3PP 2010:
10th International Conference, ICA3PP 2010, Busan, Korea, May 21-23, 2010. Proceedings.,
volume Volume 6081/2010, pages 499--510. Springer Berlin / Heidelberg,
2010.
[24] W. N. Scherer, III and M. L. Scott. Advanced contention management for dynamic
software transactional memory. In PODC '05: Proceedings of the twenty-fourth annual
ACM symposium on Principles of distributed computing, pages 240--248, New York,
NY, USA, 2005. ACM.
[25] N. Shavit and D. Touitou. Software transactional memory. In PODC '95: Proceedings
of the fourteenth annual ACM symposium on Principles of distributed computing, pages
204--213, New York, NY, USA, 1995. ACM.
[26] A. Shriraman and S. Dwarkadas. Refereeing conflicts in transactional memory systems.
Technical report, University of Rochester. Computer Science Department., Sep. 2008.
[27] M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization techniques for
software transactional memory. In PODC '07: Proceedings of the twenty-sixth annual
ACM symposium on Principles of distributed computing, pages 338--339, New York,
NY, USA, 2007. ACM.
[28] M. F. Spear, V. J. Marathe, W. N. S. Iii, and M. L. Scott. Conflict detection and validation
strategies for software transactional memory. In Proc. of the 20th Intl. Symp.
on Distributed Computing, volume Volume 4167/2006 of Lecture Notes in Computer
Science, pages 179--193. Springer Berlin / Heidelberg, October 2006.
[29] M. F. Spear, M. M. Michael, and C. von Praun. Ringstm: scalable transactions with a
single atomic instruction. In SPAA '08: Proceedings of the twentieth annual symposium
on Parallelism in algorithms and architectures, pages 275--284, New York, NY, USA,
2008. ACM.
[30] A. Welc and B. Saha. Software transactional memory validation – time and space
considerations. In SHCMP '08: Workshop on Software and Hardware Challenges of
Manycore Platforms, June 2008.