DistributedDeque

Usage

use DistributedDeque;

or

import DistributedDeque;

Implements a parallel-safe scalable distributed deque.

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.

Note

This module is a work in progress and may change in future releases.

Usage

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

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

The deque can be used as a queue by using the DistributedDequeImpl.enqueue and DistributedDequeImpl.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 DistributedDequeImpl.push and DistributedDequeImpl.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 DistributedDequeImpl.pushBack, DistributedDequeImpl.pushFront, DistributedDequeImpl.popBack, and DistributedDequeImpl.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 DistributedDequeImpl.pushBack or DistributedDequeImpl.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.

enum constant NONE

enum constant FIFO

enum constant LIFO

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: unmanaged DistributedDequeImpl(eltType)?

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

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

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)

override proc add(elt: eltType): bool

Syntactic sugar for pushBack.

override 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.

override proc getSize(): int

Obtains the number of elements held by this queue.

override proc contains(elt: eltType): bool

Performs a lookup for the element in the data structure.

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

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

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

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

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

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