以協程架構實現切換性軟體事務性記憶體的效能提升

Abstract

本研究探討以協程 (coroutine) 實現軟體事務性記憶體 (Software Transactional Memory) 的運算排程，透過在協程間切換來提升其運算效能及可擴展性，軟體事務性記憶體用於處理協調衝突的方法，能夠大致區分為兩種架構:專注於衝突解決的衝突管理器 (Contention Manager) 或者是專注於衝突避免的排程器 (scheduler)， 衝突管理器根據衝突解決策略決定衝突的事務 (transaction) 該中止或繼續執行，而排程器則透過排程來防止衝突再次發生，然而兩者都對可擴展性造成了極大的限制，許多文獻探討的機制將導致執行緒進行無謂的閒置，或者進行無效工作最終被中止，從而低效地利用計算資源。 本文提出了一種新穎的計算框架，稱為切換性軟體事務性記憶體 (switch-STM)，將任務封裝為協程進行計算。當發生衝突時，切換協程以繼續計算，防止執行緒不必要地閒置。該框架不受任務排程限制，並具有高度的可擴展性。此外，它與衝突管理器兼容，可同時使用進一步提升計算效率。本文提出了三種協程切換策略，通過探索這些切換策略，推進軟體事務性記憶體計算框架的可擴展性和性能。

This study explores the computational scheduling of Software Transactional Memory (STM) using coroutines, aiming to enhance its computational efficiency and scalability by switching between coroutines. Methods employed by STM to handle coordination conflicts can be broadly classified into two architectures: the Contention Manager, which focuses on conflict resolution, and the Scheduler, which focuses on conflict avoidance. While Contention Manager determines whether conflicting transactions should proceed or halt based on conflict resolution policies, Scheduler prevents conflicts from reoccurring by scheduling. However, both architectures impose significant limitations on scalability. Many existing mechanisms result in thread idleness or futile work that will ultimately be terminated, thereby inefficiently utilizing computational resources. This paper proposes a novel computational framework called Switchable Software Transactional Memory (SwitchSTM), which encapsulates tasks into coroutines for compu- tation. When conflicts arise, coroutines are switched to continue computation, preventing unnecessary thread idling. This framework is not constrained by task scheduling limita- tions and exhibits high scalability. Additionally, it is compatible with Contention Man- ager, further enhancing computational efficiency. Three coroutine-switching strategies are proposed in the paper, advancing the scalability and performance of STM computational frameworks through the exploration of these switching strategies.