Fast concurrent array-based stacks, queues and deques using fetch-and-increment-bounded, fetch-and-decrement-bounded and store-on-twin synchronization primitives

US8838944B2 · kind B2 · utility

Assignee

• International Business Machines Corporation · US

Inventors

• Dong Chen · Scarsdale, US
• Alana Gara · Yorktown Heights, US
• Philip Heidelberger · Somers, US
• Sameer Kumar · White Plains, US
• Martin Ohmacht · Yorktown Heights, US
• Burkhard Steinmacher-Burow · Eßlingen, DE
• Robert W. Wisniewski · Ossining, US

Key dates

• Filing date: Sep 22, 2009
• Grant date: Sep 16, 2014
• Expiry date: Mar 19, 2033

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F9/546
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Implementation primitives for concurrent array-based stacks, queues, double-ended queues (deques) and wrapped deques are provided. In one aspect, each element of the stack, queue, deque or wrapped deque data structure has its own ticket lock, allowing multiple threads to concurrently use multiple elements of the data structure and thus achieving high performance. In another aspect, new synchronization primitives FetchAndIncrementBounded (Counter, Bound) and FetchAndDecrementBounded (Counter, Bound) are implemented. These primitives can be implemented in hardware and thus promise a very fast throughput for queues, stacks and double-ended queues.