TY - GEN
T1 - Fast scheduling in distributed transactional memory
AU - Busch, Costas
AU - Herlihy, Maurice
AU - Popovic, Miroslav
AU - Sharma, Gokarna
N1 - Funding Information:
Œis work is supported by the National Science Foundation grants 1320835 and 1420673, and partly supported by the Serbian Ministry of Education & Science, through grants No. III 44009, and TR 32031.
Publisher Copyright:
© 2017 Copyright held by the owner/author(s).
PY - 2017/7/24
Y1 - 2017/7/24
N2 - We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k = 2), it is impossible to obtain execution time close to the objects' optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first a.empt to obtain provably fast schedules for distributed transactional memory.
AB - We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k = 2), it is impossible to obtain execution time close to the objects' optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first a.empt to obtain provably fast schedules for distributed transactional memory.
KW - Approximation
KW - Contention
KW - Data-flow model
KW - Distributed systems
KW - Execution time
KW - Scheduling
KW - Transactional memory
UR - http://www.scopus.com/inward/record.url?scp=85027870709&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027870709&partnerID=8YFLogxK
U2 - 10.1145/3087556.3087565
DO - 10.1145/3087556.3087565
M3 - Conference contribution
AN - SCOPUS:85027870709
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 173
EP - 182
BT - SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017
Y2 - 24 July 2017 through 26 July 2017
ER -