DistributedDeque¶

Summary¶

A parallel-safe scalable distributed deque. A deque is a double-ended queue that supports insertion and removal from both ends of the queue, effectively supporting both FIFO, LIFO, and a Total ordering, where the order in which you add them will be the exact order you remove them in; for emphasis, a Deque can be used as a Queue, a Stack, and a List respectively.

Usage¶

First, the DistDeque must be initialized before use by calling its constructor.

var deque = new DistDeque(int, cap=maxElem, targetLocales=ourLocales);

The deque can be used as a queue by using the enqueue and dequeue convenience methods or inserting from one end to remove from another...

deque.enqueue(1);
var (hasElem, elem) = deque.dequeue();

The deque can be used as a stack by using the push and pop convenience methods, or insertion and removing from the same ends...

deque.push(1);
var (hasElem, elem) = deque.pop();

The deque can be used as a list by using the pushBack, pushFront, popBack, and popFront methods. While the deque is not indexable, the ability to append or prepend is powerful enough to allow a total ordering, allowing the user to define the order by letting them insert and remove at whichever ends they so choose.

var deque = new DistDeque(int);
forall i in 1 .. N {
  if i % 2 == 0 then deque.pushFront(i);
  else deque.pushBack(i);
}

The deque supports both serial and parallel iteration, and a means to iterate in a particular order (currently only FIFO and LIFO) using the Ordering enumerator.

for elt in deque.these(Ordering.FIFO) {
  // ...
}

for elt in deque.these(Ordering.LIFO) {
  // ...
}

The deque can also be used in a reduction, although currently reduction only used parallel-iteration, hence reduction will be performed in an unordered fashion. In the future, a specific function may be created to allow reduction in a certain ordering...

deque.addBulk(1..100);
var result = + reduce deque;

Bugs and Known Issues¶

1. It is not safe to call other methods while iterating, as it will lead to deadlock. It is an open question whether using a snapshot approach is better to allow concurrent operations at the expense of elevated memory consumption, and iterating directly over elements while holding locks, which strangles potential concurrency.
2. Reduction cannot be performed in any ordered way. This may be fixed in the near future, either by adding pseudo-parallel iterators that merely yield sequentially in order, or by creating a method to perform reduction for the user in a specified ordering.
3. This data structure requires network atomic support for scalability, and without it will result in degrading performance. It is another open question whether a specific implementation that is more friendly for remote-execution atomic operations should be provided.
4. The ordered serial iterators currently do not work when the globalHead or globalTail are negative, which is a result of iteration being an after-thought. This will be improved upon soon, but for now if you use pushBack or pushFront methods, I would advise against using them for now.

Planned Improvements¶

1. Double the size of each successor up to some maximum, similar to DistributedBag for unroll blocks. Currently they are fixed-sized, but it can benefit from improved locality if a lot of elements are added at once.

Methods¶

config param distributedDequeBlockSize = 8¶

Size of each unroll block for each local deque node.

enum Ordering { NONE, FIFO, LIFO }¶

The ordering used for serial iteration. NONE, the default, is the most performant and is algorithmically similar to parallel iteration.

record DistDeque¶

A parallel-safe scalable distributed double-ended queue that supports both insertion and removal from either end of the queue. Can be used as a Queue, Stack, or even a List.

type eltType¶

var _impl: DistributedDequeImpl(eltType)¶

The implementation of the Deque is forwarded. See DistributedDequeImpl for documentation.

proc init(type eltType, cap = -1, targetLocales = Locales)¶

proc forwarding_expr4__value()¶

class DistributedDequeImpl: CollectionImpl¶

var cap: int¶

Capacity, the maximum number of elements a Deque can hold. A cap of -1 is considered unbounded.

var targetLocales: [targetLocDom] locale¶

Locales to distribute the Deque across.

proc init(type eltType, cap: int = -1, targetLocales: [?locDom] locale = Locales)¶

proc add(elt: eltType): bool¶

Syntactic sugar for pushBack.

proc remove(): (bool, eltType)¶

Syntactic sugar for popFront.

proc enqueue(elt: eltType): bool¶

Syntactic sugar for pushBack.

proc dequeue(): (bool, eltType)¶

Syntactic sugar for popFront.

proc push(elt: eltType): bool¶

Syntactic sugar for pushBack.

proc pop(): (bool, eltType)¶

Syntactic sugar for popBack.

proc pushBack(elt: eltType): bool¶

Appends the element to the tail.

proc popBack(): (bool, eltType)¶

Removes the element at the tail.

proc pushFront(elt: eltType): bool¶

Appends the element to the head.

proc popFront(): (bool, eltType)¶

Removes the element at the head.

proc getSize(): int¶

Obtains the number of elements held by this queue.

proc contains(elt: eltType): bool¶

Performs a lookup for the element in the data structure.

iter these(param order: Ordering = Ordering.NONE): eltType¶

Iterate over all elements in the deque in the order specified.

iter these(param order: Ordering = Ordering.NONE): eltType

iter these(param order: Ordering = Ordering.NONE): eltType

iter these(param order: Ordering = Ordering.NONE, param tag: iterKind)

iter these(param order: Ordering = Ordering.NONE, param tag: iterKind, followThis)