pu.pi

Class DFSonDAGs<V>

java.lang.Object

pu.pi.ParIteratorAbstract<V>

pu.pi.DFSonDAGs<V>

All Implemented Interfaces:

java.util.Iterator<V>, ParIterator<V>

public class DFSonDAGs<V>
extends ParIteratorAbstract<V>

Date created: 9 September 2009 Last modified: 22 September 2009 This class represents a Parallel DFS Iterator which works on Directed Acyclic Graphs (DAGs). It returns nodes in DFS order from top to buttom (i.e. in case of a tree, root nodes are returned before leaves). It supports work-stealing when threads get idle.

Author:

Lama Akeila

Nested Class Summary

Nested classes/interfaces inherited from interface pu.pi.ParIterator

ParIterator.Schedule

Field Summary

Fields inherited from class pu.pi.ParIteratorAbstract

chunkSize, collection, data, exceptions, flags, ignoreBarrier, numOfThreads, reclaimedElements, threadID

Fields inherited from interface pu.pi.ParIterator

DEFAULT_CHUNKSIZE

Constructor Summary

Constructors

Constructor and Description
DFSonDAGs(GraphAdapterInterface graph, V root, int numOfThreads)

Method Summary

Modifier and Type	Method and Description
void	forEachRemaining(java.util.function.Consumer<? super V> action)
void	globalBreak() Causes all threads to stop processing elements at the next iteration boundary.
boolean	hasNext() Checks to see if any elements remain for the current thread.
boolean	localBreak() Attempts to excuse the current thread from continuing to iterate (and re-distribute all unprocessed elements to the other threads).
V	next() Returns an element for the current thread to process.

Methods inherited from class pu.pi.ParIteratorAbstract

allOtherThreadsHaveLocalBreaked, getAllExceptions, getID, register, register, remove, reset

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DFSonDAGs

public DFSonDAGs(GraphAdapterInterface graph,
                 V root,
                 int numOfThreads)

Method Detail

hasNext

public boolean hasNext()

Description copied from interface: ParIterator

Checks to see if any elements remain for the current thread. If such an element exists, true is returned and the current thread must follow up with a binding call to next(). A thread must continue to obtain elements in this fashion until this method returns false.

Note that this method involves an implicit barrier for the last call to hasNext() in order to ensure all threads finish at the same time.

Returns:

true if at least one element has been reserved for the calling thread (in which case it must follow up with a call to next()).
false otherwise (in such a case, the calling thread blocks until all the other threads have completed their iterations).

See Also:

ParIterator.next()

next

public V next()

Description copied from interface: ParIterator

Returns an element for the current thread to process. A thread must not call this method unless it has previously called hasNext() (and received true).

Note that calls to hasNext() (that return true) only allow for one corresponding and binding call to hasNext(). Therefore, multiple calls to hasNext() have no effect until the corresponding call to next() takes place.

See Also:

ParIterator.hasNext()

globalBreak

public void globalBreak()

Description copied from interface: ParIterator

Causes all threads to stop processing elements at the next iteration boundary. Therefore, even if there were any unprocessed elements, they will not be processed. In such a case, false is returned to every thread at the next call to hasNext(). Therefore, all the threads safely stop iterating when they call hasNext() (includes an implicit barrier to ensure all threads stop at the same time).

Specified by:

globalBreak in interface ParIterator<V>

Overrides:

globalBreak in class ParIteratorAbstract<V>

See Also:

ParIterator.localBreak()

localBreak

public boolean localBreak()

Description copied from interface: ParIterator

Attempts to excuse the current thread from continuing to iterate (and re-distribute all unprocessed elements to the other threads). This is only successful if the the elements previously assigned to this thread are successfully allocated to the other thread(s). If the elements cannot be assigned to another thread (because the other threads have already stopped processing), then this attempt to local break will fail.

Therefore, (as opposed to globalBreak()) this method guarantees that even if all threads attempt to localBreak(), at least one will fail and is left to traverse the remaining elements. Note that in many cases, calling localBreak() will break the original scheduling policy.

Returns:

true if the attempt is successful, false otherwise.

See Also:

ParIterator.globalBreak()

forEachRemaining

public void forEachRemaining(java.util.function.Consumer<? super V> action)