With the rapid increase in the number of CPU cores, software that can utilize these many cores is required. A lock-free algorithm based on compare-and-swap (CAS) operations is one of the concurrency control methods to implement such multi-threading software. A multi-word CAS (MwCAS) operation is an extension of a CAS operation to swap multiple words atomically. However, we noticed that the performance of the existing MwCAS implementation is limited because of garbage collection even if in a low-contention environment. To achieve high performance in low-contention workloads, we propose a new MwCAS algorithm without garbage collection. Experimental results show that our approach is three to five times faster than implementation with garbage collection in low-contention workloads. Moreover, the performance of the proposed method is also superior in a high-contention environment.
Kento SUGIURA
Nagoya University
Yoshiharu ISHIKAWA
Nagoya University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kento SUGIURA, Yoshiharu ISHIKAWA, "Implementation of a Multi-Word Compare-and-Swap Operation without Garbage Collection" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 5, pp. 946-954, May 2022, doi: 10.1587/transinf.2021DAP0011.
Abstract: With the rapid increase in the number of CPU cores, software that can utilize these many cores is required. A lock-free algorithm based on compare-and-swap (CAS) operations is one of the concurrency control methods to implement such multi-threading software. A multi-word CAS (MwCAS) operation is an extension of a CAS operation to swap multiple words atomically. However, we noticed that the performance of the existing MwCAS implementation is limited because of garbage collection even if in a low-contention environment. To achieve high performance in low-contention workloads, we propose a new MwCAS algorithm without garbage collection. Experimental results show that our approach is three to five times faster than implementation with garbage collection in low-contention workloads. Moreover, the performance of the proposed method is also superior in a high-contention environment.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021DAP0011/_p
Copy
@ARTICLE{e105-d_5_946,
author={Kento SUGIURA, Yoshiharu ISHIKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Implementation of a Multi-Word Compare-and-Swap Operation without Garbage Collection},
year={2022},
volume={E105-D},
number={5},
pages={946-954},
abstract={With the rapid increase in the number of CPU cores, software that can utilize these many cores is required. A lock-free algorithm based on compare-and-swap (CAS) operations is one of the concurrency control methods to implement such multi-threading software. A multi-word CAS (MwCAS) operation is an extension of a CAS operation to swap multiple words atomically. However, we noticed that the performance of the existing MwCAS implementation is limited because of garbage collection even if in a low-contention environment. To achieve high performance in low-contention workloads, we propose a new MwCAS algorithm without garbage collection. Experimental results show that our approach is three to five times faster than implementation with garbage collection in low-contention workloads. Moreover, the performance of the proposed method is also superior in a high-contention environment.},
keywords={},
doi={10.1587/transinf.2021DAP0011},
ISSN={1745-1361},
month={May},}
Copy
TY - JOUR
TI - Implementation of a Multi-Word Compare-and-Swap Operation without Garbage Collection
T2 - IEICE TRANSACTIONS on Information
SP - 946
EP - 954
AU - Kento SUGIURA
AU - Yoshiharu ISHIKAWA
PY - 2022
DO - 10.1587/transinf.2021DAP0011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2022
AB - With the rapid increase in the number of CPU cores, software that can utilize these many cores is required. A lock-free algorithm based on compare-and-swap (CAS) operations is one of the concurrency control methods to implement such multi-threading software. A multi-word CAS (MwCAS) operation is an extension of a CAS operation to swap multiple words atomically. However, we noticed that the performance of the existing MwCAS implementation is limited because of garbage collection even if in a low-contention environment. To achieve high performance in low-contention workloads, we propose a new MwCAS algorithm without garbage collection. Experimental results show that our approach is three to five times faster than implementation with garbage collection in low-contention workloads. Moreover, the performance of the proposed method is also superior in a high-contention environment.
ER -