Skip to Content
Find More Like This
Return to Search

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

United States Patent

September 16, 2014
View the Complete Patent at the US Patent & Trademark Office
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.
Chen; Dong (Yorktown Heights, NY), Gara; Alana (Yorktown Heights, NY), Heidelberger; Philip (Yorktown Heights, NY), Kumar; Sameer (White Plains, NY), Ohmacht; Martin (Yorktown Heights, NY), Steinmacher-Burow; Burkhard (Boeblingen, DE), Wisniewski; Robert (Yorktown Heights, NY)
International Business Machines Corporation (Armonk, NY)
12/ 564,535
September 22, 2009
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT This invention was made with Government support under Contract No.: B554331 awarded by Department of Energy. The Government has certain rights in this invention.