Towards concurrent data structure development with relaxed synchronization

Naw Safrin Sattar; Tasmia Aqila; Rifat Shahriyar

doi:10.1109/ICECE.2016.7853907

Towards concurrent data structure development with relaxed synchronization

Naw Safrin Sattar, Tasmia Aqila, Rifat Shahriyar

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

1 Scopus citations

Abstract

Concurrent data structures may introduce a performance and scalability holdup and thus prevent the effective use of parallel hardware. There is a trade-off between scalable performance and precision in implementing concurrent data structures. A remedy to the scalability problem is to relax the interpretation of concurrent data structures. The construal is given by some notion equivalent to the sequential behaviour. The equivalence is determined by a consistency condition, most commonly linearity, and the sequential behaviour is inherited from the sequential version of the data structure (e.g. The sequential behaviour of a concurrent stack is a regular stack). Therefore, relaxing the semantics of a concurrent data structure extents to either weakening the consistency condition or redefining or relaxing its sequential specification. In this paper, we present a framework for relaxing the synchronization of a Stack data structure in a quantitative manner. A fundamental challenge in using relaxed synchronization is guaranteeing that the relaxed program always produces results with a specified quality. We propose a methodology that addresses this challenge in programming with relaxed synchronization. Using our methodology, results that are of the same quality as the original program, can be produced with a speedup in time.

Original language	English
Title of host publication	Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	267-270
Number of pages	4
ISBN (Electronic)	9781509029631
DOIs	https://doi.org/10.1109/ICECE.2016.7853907
State	Published - Feb 13 2017
Externally published	Yes
Event	9th International Conference on Electrical and Computer Engineering, ICECE 2016 - Dhaka, Bangladesh Duration: Dec 20 2016 → Dec 22 2016

Publication series

Name	Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016

Conference

Conference	9th International Conference on Electrical and Computer Engineering, ICECE 2016
Country/Territory	Bangladesh
City	Dhaka
Period	12/20/16 → 12/22/16

Keywords

Concurrency
Read-write locks
Synchronization
Timeout

Access to Document

10.1109/ICECE.2016.7853907

Cite this

Sattar, N. S., Aqila, T., & Shahriyar, R. (2017). Towards concurrent data structure development with relaxed synchronization. In Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016 (pp. 267-270). Article 7853907 (Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICECE.2016.7853907

Sattar, Naw Safrin ; Aqila, Tasmia ; Shahriyar, Rifat. / Towards concurrent data structure development with relaxed synchronization. Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 267-270 (Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016).

@inproceedings{537be05c785a482ba7547fae2df0aa4c,

title = "Towards concurrent data structure development with relaxed synchronization",

abstract = "Concurrent data structures may introduce a performance and scalability holdup and thus prevent the effective use of parallel hardware. There is a trade-off between scalable performance and precision in implementing concurrent data structures. A remedy to the scalability problem is to relax the interpretation of concurrent data structures. The construal is given by some notion equivalent to the sequential behaviour. The equivalence is determined by a consistency condition, most commonly linearity, and the sequential behaviour is inherited from the sequential version of the data structure (e.g. The sequential behaviour of a concurrent stack is a regular stack). Therefore, relaxing the semantics of a concurrent data structure extents to either weakening the consistency condition or redefining or relaxing its sequential specification. In this paper, we present a framework for relaxing the synchronization of a Stack data structure in a quantitative manner. A fundamental challenge in using relaxed synchronization is guaranteeing that the relaxed program always produces results with a specified quality. We propose a methodology that addresses this challenge in programming with relaxed synchronization. Using our methodology, results that are of the same quality as the original program, can be produced with a speedup in time.",

keywords = "Concurrency, Read-write locks, Synchronization, Timeout",

author = "Sattar, {Naw Safrin} and Tasmia Aqila and Rifat Shahriyar",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 9th International Conference on Electrical and Computer Engineering, ICECE 2016 ; Conference date: 20-12-2016 Through 22-12-2016",

year = "2017",

month = feb,

day = "13",

doi = "10.1109/ICECE.2016.7853907",

language = "English",

series = "Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "267--270",

booktitle = "Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016",

}

Sattar, NS, Aqila, T & Shahriyar, R 2017, Towards concurrent data structure development with relaxed synchronization. in Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016., 7853907, Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016, Institute of Electrical and Electronics Engineers Inc., pp. 267-270, 9th International Conference on Electrical and Computer Engineering, ICECE 2016, Dhaka, Bangladesh, 12/20/16. https://doi.org/10.1109/ICECE.2016.7853907

Towards concurrent data structure development with relaxed synchronization. / Sattar, Naw Safrin; Aqila, Tasmia; Shahriyar, Rifat.
Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 267-270 7853907 (Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016).

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

TY - GEN

T1 - Towards concurrent data structure development with relaxed synchronization

AU - Sattar, Naw Safrin

AU - Aqila, Tasmia

AU - Shahriyar, Rifat

PY - 2017/2/13

Y1 - 2017/2/13

N2 - Concurrent data structures may introduce a performance and scalability holdup and thus prevent the effective use of parallel hardware. There is a trade-off between scalable performance and precision in implementing concurrent data structures. A remedy to the scalability problem is to relax the interpretation of concurrent data structures. The construal is given by some notion equivalent to the sequential behaviour. The equivalence is determined by a consistency condition, most commonly linearity, and the sequential behaviour is inherited from the sequential version of the data structure (e.g. The sequential behaviour of a concurrent stack is a regular stack). Therefore, relaxing the semantics of a concurrent data structure extents to either weakening the consistency condition or redefining or relaxing its sequential specification. In this paper, we present a framework for relaxing the synchronization of a Stack data structure in a quantitative manner. A fundamental challenge in using relaxed synchronization is guaranteeing that the relaxed program always produces results with a specified quality. We propose a methodology that addresses this challenge in programming with relaxed synchronization. Using our methodology, results that are of the same quality as the original program, can be produced with a speedup in time.

AB - Concurrent data structures may introduce a performance and scalability holdup and thus prevent the effective use of parallel hardware. There is a trade-off between scalable performance and precision in implementing concurrent data structures. A remedy to the scalability problem is to relax the interpretation of concurrent data structures. The construal is given by some notion equivalent to the sequential behaviour. The equivalence is determined by a consistency condition, most commonly linearity, and the sequential behaviour is inherited from the sequential version of the data structure (e.g. The sequential behaviour of a concurrent stack is a regular stack). Therefore, relaxing the semantics of a concurrent data structure extents to either weakening the consistency condition or redefining or relaxing its sequential specification. In this paper, we present a framework for relaxing the synchronization of a Stack data structure in a quantitative manner. A fundamental challenge in using relaxed synchronization is guaranteeing that the relaxed program always produces results with a specified quality. We propose a methodology that addresses this challenge in programming with relaxed synchronization. Using our methodology, results that are of the same quality as the original program, can be produced with a speedup in time.

KW - Concurrency

KW - Read-write locks

KW - Synchronization

KW - Timeout

UR - http://www.scopus.com/inward/record.url?scp=85016195291&partnerID=8YFLogxK

U2 - 10.1109/ICECE.2016.7853907

DO - 10.1109/ICECE.2016.7853907

M3 - Conference contribution

AN - SCOPUS:85016195291

T3 - Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016

SP - 267

EP - 270

BT - Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 9th International Conference on Electrical and Computer Engineering, ICECE 2016

Y2 - 20 December 2016 through 22 December 2016

ER -

Sattar NS, Aqila T, Shahriyar R. Towards concurrent data structure development with relaxed synchronization. In Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016. Institute of Electrical and Electronics Engineers Inc. 2017. p. 267-270. 7853907. (Proceedings of 9th International Conference on Electrical and Computer Engineering, ICECE 2016). doi: 10.1109/ICECE.2016.7853907

Towards concurrent data structure development with relaxed synchronization

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this