DESunordered Class Reference
#include <DESunordered.h>
Classes | |
| struct | process |
| contains the loop body, called by More... | |
Private Types | |
| typedef Galois::GAccumulator< int > | PerCPUcounter |
| typedef Galois::GReduceMax < size_t > | ReduceMax |
Private Member Functions | |
| virtual void | runLoop (const SimInit &simInit) |
| Run loop. | |
| virtual bool | isSerial () const |
| return true in serial versions and false in Galois versions | |
Member Typedef Documentation
typedef Galois::GAccumulator<int> DESunordered::PerCPUcounter [private] |
typedef Galois::GReduceMax<size_t> DESunordered::ReduceMax [private] |
Member Function Documentation
| virtual bool DESunordered::isSerial | ( | ) | const [inline, private, virtual] |
return true in serial versions and false in Galois versions
Implements DESabstractMain.
| virtual void DESunordered::runLoop | ( | const SimInit & | simInit | ) | [inline, private, virtual] |
Run loop.
Galois worklists, currently, do not support set semantics, therefore, duplicates can be present on the workset. To ensure uniqueness of items on the worklist, we keep a list of boolean flags for each node, which indicate whether the node is on the worklist. When adding a node to the worklist, the flag corresponding to a node is set to True if it was previously False. The flag reset to False when the node is removed from the worklist. This list of flags provides a cheap way of implementing set semantics.
Normally, one would use a vector<bool>, but std::vector<bool> uses bit vector implementation, where different indices i!=j share a common memory word. To protect against concurrent accesses, we would need to acquire abstract locks corresponding to the memory word rather than acquiring locks on locations iand j. This requires knowledge of std::vector<bool> implementation. Instead, we use a std::vector<unsigned int> so that each index i!=j is stored in a separate word and we can acquire lock on i safely.
Implements DESabstractMain.
The documentation for this class was generated from the following file:
