Fast and correct load-link/store-conditional instruction handling in DBT systems

Martin Kristien; Tom Spink; Brian Campbell; Susmit Sarkar; Ian Stark; Björn Franke; Igor Böhm; Nigel Topham

doi:10.1109/TCAD.2020.3013048

Fast and correct load-link/store-conditional instruction handling in DBT systems

Martin Kristien^*, Tom Spink, Brian Campbell, Susmit Sarkar, Ian Stark, Björn Franke, Igor Böhm, Nigel Topham

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Dynamic Binary Translation (DBT) requires the implementation of load-link/store-conditional (LL/SC) primitives for guest systems that rely on this form of synchronization. When targeting e.g. x86 host systems, LL/SC guest instructions are typically emulated using atomic Compare-and-Swap (CAS) instructions on the host. Whilst this direct mapping is efficient, this approach is problematic due to subtle differences between LL/SC and CAS semantics. In this paper, we demonstrate that this is a real problem, and we provide code examples that fail to execute correctly on QEMU and a commercial DBT system, which both use the CAS approach to LL/SC emulation. We then develop two novel and provably correct LL/SC emulation schemes: (1) A purely software based scheme, which uses the DBT system’s page translation cache for correctly selecting between fast, but unsynchronized, and slow, but fully synchronized memory accesses, and (2) a hardware accelerated scheme that leverages hardware transactional memory (HTM) provided by the host. We have implemented these two schemes in the Synopsys DesignWare® ARC® nSIM DBT system, and we evaluate our implementations against full applications, and targeted micro-benchmarks. We demonstrate that our novel schemes are not only correct, but also deliver competitive performance on-par or better than the widely used, but broken CAS scheme.

Original language	English
Title of host publication	CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems
Publisher	IEEE Computer Society
Number of pages	11
Volume	Early Access
DOIs	https://doi.org/10.1109/TCAD.2020.3013048
Publication status	Published - 2 Oct 2020
Event	International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '20) - Virtual conference Duration: 20 Sept 2020 → 25 Sept 2020 https://esweek.org/cases/

Publication series

Name	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Number	11
Volume	39
ISSN (Print)	0278-0070
ISSN (Electronic)	1937-4151

Conference

Conference	International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '20)
Abbreviated title	CASES '20
Period	20/09/20 → 25/09/20
Internet address	https://esweek.org/cases/

Keywords

Parallel architectures
Platform visualization

Access to Document

10.1109/TCAD.2020.3013048

fast-and-correct
Copyright © 2020 IEEE. This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1109/TCAD.2020.3013048.
Accepted author manuscript, 788 KB

Cite this

Kristien, M., Spink, T., Campbell, B., Sarkar, S., Stark, I., Franke, B., Böhm, I., & Topham, N. (2020). Fast and correct load-link/store-conditional instruction handling in DBT systems. In CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems (Vol. Early Access). (IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; Vol. 39, No. 11). IEEE Computer Society. https://doi.org/10.1109/TCAD.2020.3013048

Kristien, Martin ; Spink, Tom ; Campbell, Brian et al. / Fast and correct load-link/store-conditional instruction handling in DBT systems. CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. Vol. Early Access IEEE Computer Society, 2020. (IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; 11).

@inproceedings{112b05cb3b3f44148ca37fdc6602340b,

title = "Fast and correct load-link/store-conditional instruction handling in DBT systems",

abstract = "Dynamic Binary Translation (DBT) requires the implementation of load-link/store-conditional (LL/SC) primitives for guest systems that rely on this form of synchronization. When targeting e.g. x86 host systems, LL/SC guest instructions are typically emulated using atomic Compare-and-Swap (CAS) instructions on the host. Whilst this direct mapping is efficient, this approach is problematic due to subtle differences between LL/SC and CAS semantics. In this paper, we demonstrate that this is a real problem, and we provide code examples that fail to execute correctly on QEMU and a commercial DBT system, which both use the CAS approach to LL/SC emulation. We then develop two novel and provably correct LL/SC emulation schemes: (1) A purely software based scheme, which uses the DBT system{\textquoteright}s page translation cache for correctly selecting between fast, but unsynchronized, and slow, but fully synchronized memory accesses, and (2) a hardware accelerated scheme that leverages hardware transactional memory (HTM) provided by the host. We have implemented these two schemes in the Synopsys DesignWare{\textregistered} ARC{\textregistered} nSIM DBT system, and we evaluate our implementations against full applications, and targeted micro-benchmarks. We demonstrate that our novel schemes are not only correct, but also deliver competitive performance on-par or better than the widely used, but broken CAS scheme.",

keywords = "Parallel architectures, Platform visualization",

author = "Martin Kristien and Tom Spink and Brian Campbell and Susmit Sarkar and Ian Stark and Bj{\"o}rn Franke and Igor B{\"o}hm and Nigel Topham",

note = "Funding: This work was supported in part by Engineering and Physical Sciences Research Council (EPSRC) and in part by Synopsys Inc.; International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '20), CASES '20 ; Conference date: 20-09-2020 Through 25-09-2020",

year = "2020",

month = oct,

day = "2",

doi = "10.1109/TCAD.2020.3013048",

language = "English",

volume = "Early Access",

series = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

publisher = "IEEE Computer Society",

number = "11",

booktitle = "CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems",

address = "United States",

url = "https://esweek.org/cases/",

}

Kristien, M, Spink, T, Campbell, B, Sarkar, S, Stark, I, Franke, B, Böhm, I & Topham, N 2020, Fast and correct load-link/store-conditional instruction handling in DBT systems. in CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. vol. Early Access, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, no. 11, vol. 39, IEEE Computer Society, International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '20), 20/09/20. https://doi.org/10.1109/TCAD.2020.3013048

Fast and correct load-link/store-conditional instruction handling in DBT systems. / Kristien, Martin; Spink, Tom; Campbell, Brian et al.
CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. Vol. Early Access IEEE Computer Society, 2020. (IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; Vol. 39, No. 11).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast and correct load-link/store-conditional instruction handling in DBT systems

AU - Kristien, Martin

AU - Spink, Tom

AU - Campbell, Brian

AU - Sarkar, Susmit

AU - Stark, Ian

AU - Franke, Björn

AU - Böhm, Igor

AU - Topham, Nigel

N1 - Funding: This work was supported in part by Engineering and Physical Sciences Research Council (EPSRC) and in part by Synopsys Inc.

PY - 2020/10/2

Y1 - 2020/10/2

N2 - Dynamic Binary Translation (DBT) requires the implementation of load-link/store-conditional (LL/SC) primitives for guest systems that rely on this form of synchronization. When targeting e.g. x86 host systems, LL/SC guest instructions are typically emulated using atomic Compare-and-Swap (CAS) instructions on the host. Whilst this direct mapping is efficient, this approach is problematic due to subtle differences between LL/SC and CAS semantics. In this paper, we demonstrate that this is a real problem, and we provide code examples that fail to execute correctly on QEMU and a commercial DBT system, which both use the CAS approach to LL/SC emulation. We then develop two novel and provably correct LL/SC emulation schemes: (1) A purely software based scheme, which uses the DBT system’s page translation cache for correctly selecting between fast, but unsynchronized, and slow, but fully synchronized memory accesses, and (2) a hardware accelerated scheme that leverages hardware transactional memory (HTM) provided by the host. We have implemented these two schemes in the Synopsys DesignWare® ARC® nSIM DBT system, and we evaluate our implementations against full applications, and targeted micro-benchmarks. We demonstrate that our novel schemes are not only correct, but also deliver competitive performance on-par or better than the widely used, but broken CAS scheme.

AB - Dynamic Binary Translation (DBT) requires the implementation of load-link/store-conditional (LL/SC) primitives for guest systems that rely on this form of synchronization. When targeting e.g. x86 host systems, LL/SC guest instructions are typically emulated using atomic Compare-and-Swap (CAS) instructions on the host. Whilst this direct mapping is efficient, this approach is problematic due to subtle differences between LL/SC and CAS semantics. In this paper, we demonstrate that this is a real problem, and we provide code examples that fail to execute correctly on QEMU and a commercial DBT system, which both use the CAS approach to LL/SC emulation. We then develop two novel and provably correct LL/SC emulation schemes: (1) A purely software based scheme, which uses the DBT system’s page translation cache for correctly selecting between fast, but unsynchronized, and slow, but fully synchronized memory accesses, and (2) a hardware accelerated scheme that leverages hardware transactional memory (HTM) provided by the host. We have implemented these two schemes in the Synopsys DesignWare® ARC® nSIM DBT system, and we evaluate our implementations against full applications, and targeted micro-benchmarks. We demonstrate that our novel schemes are not only correct, but also deliver competitive performance on-par or better than the widely used, but broken CAS scheme.

KW - Parallel architectures

KW - Platform visualization

U2 - 10.1109/TCAD.2020.3013048

DO - 10.1109/TCAD.2020.3013048

M3 - Conference contribution

VL - Early Access

T3 - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

BT - CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems

PB - IEEE Computer Society

T2 - International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '20)

Y2 - 20 September 2020 through 25 September 2020

ER -

Kristien M, Spink T, Campbell B, Sarkar S, Stark I, Franke B et al. Fast and correct load-link/store-conditional instruction handling in DBT systems. In CASES '20: Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. Vol. Early Access. IEEE Computer Society. 2020. (IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; 11). doi: 10.1109/TCAD.2020.3013048

Fast and correct load-link/store-conditional instruction handling in DBT systems

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this