For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A False-Sharing Free Distributed Shared Memory Management Scheme
Alexander I-Chi LAI Chin-Laung LEI Hann-Huei CHIOU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
distributed shared memory, aggressive consistency, distributed synchronization, threaded splay tree, false sharing,
Full Text: PDF>>
Distributed shared memory (DSM) systems on top of network of workstations are especially vulnerable to the impact of false sharing because of their higher memory transaction overheads and thus higher false sharing penalties. In this paper we develop a dynamic-granularity shared memory management scheme that eliminates false sharing without sacrificing the transparency to conventional shared-memory applications. Our approach utilizes a special threaded splay tree (TST) for shared memory information management, and a dynamic token-based path-compression synchronization algorithm for data transferring. The combination of the TST and path compression is quite efficient; asymptotically, in an n-processor system with m shared memory segments, synchronizing at most s segments takes O(s log m log n) amortized computation steps and generates O(s log n) communication messages, respectively. Based on the proposed scheme we constructed an experimental DSM prototype which consists of several Ethernet-connected Pentium-based computers running Linux. Preliminary benchmark results on our prototype indicate that our scheme is quite efficient, significantly outperforming traditional schemes and scaling up well.