| 1 : |
jhr |
5597 |
## Strand arrays
|
| 2 : |
|
|
|
| 3 : |
|
|
Strand arrays provide a standard interface to the underlying representation of strand
|
| 4 : |
|
|
status and state information. There are four different implementations of the
|
| 5 : |
|
|
`strand_array` struct type (for the sequential target) and the compiler picks the one
|
| 6 : |
|
|
best suited to the particular Diderot program being compiled.
|
| 7 : |
|
|
|
| 8 : |
|
|
### Strand array operations
|
| 9 : |
|
|
|
| 10 : |
|
|
There are several different functions for querying the number of strands:
|
| 11 : |
|
|
```cpp
|
| 12 : |
|
|
// return the number of active strands (includes stabilizing and dying strands)
|
| 13 : |
|
|
uint32_t num_active () const;
|
| 14 : |
|
|
// return the current number of active strands (not including stabilizing and dying strands)
|
| 15 : |
|
|
uint32_t current_active () const;
|
| 16 : |
|
|
// return the number of stable strands
|
| 17 : |
|
|
uint32_t num_stable () const;
|
| 18 : |
|
|
// return the number of alive strands (active + stable)
|
| 19 : |
|
|
uint32_t num_alive () const;
|
| 20 : |
|
|
```
|
| 21 : |
|
|
All of these functions, except `current_active` return the number of strands as of the
|
| 22 : |
|
|
*beginning* of the current superstep. The `current_active` function returns the number
|
| 23 : |
|
|
of currently active strands after accounting for any strands that have stabilized or
|
| 24 : |
|
|
died. The `current_active` function is used to implement the `kill_all` and
|
| 25 : |
|
|
`stabilize_all` functions in the `world` struct.
|
| 26 : |
|
|
|
| 27 : |
|
|
There are two ways to address a strand: a strand's ID (`sid_t`), which is invariant
|
| 28 : |
|
|
over the life of a strand, and a strand's index (`index_t`), which may change between
|
| 29 : |
|
|
supersteps. Strand indices are used to provide a fast iteration over strands by status
|
| 30 : |
|
|
(*i.e.*, stable, active, or alive). The `strands_array` struct provides various methods
|
| 31 : |
|
|
to access the strand status and state:
|
| 32 : |
|
|
```cpp
|
| 33 : |
|
|
// return the strand ID for the given strand index
|
| 34 : |
|
|
sid_t id (index_t ix) const;
|
| 35 : |
|
|
// return a pointer to the strand with the given strand ID
|
| 36 : |
|
|
STRAND_strand *id_to_strand sid_t id) const;
|
| 37 : |
|
|
// return the status of the strand with the given index
|
| 38 : |
|
|
diderot::strand_status status (index_t ix) const;
|
| 39 : |
|
|
// return the status of the strand with the given index
|
| 40 : |
|
|
STRAND_strand *strand (index_t ix) const;
|
| 41 : |
|
|
// return a pointer to the local (non-shared) state of the strand with the
|
| 42 : |
|
|
// given index
|
| 43 : |
|
|
STRAND_local *local_state (index_t ix) const;
|
| 44 : |
|
|
// return a pointer to the local (non-shared) state of the strand with the
|
| 45 : |
|
|
// given strand ID
|
| 46 : |
|
|
STRAND_local *id_to_local_state (sid_t id) const;
|
| 47 : |
|
|
```
|
| 48 : |
|
|
|
| 49 : |
|
|
#### Iterators
|
| 50 : |
|
|
|
| 51 : |
|
|
```cpp
|
| 52 : |
|
|
// iteration over the active strands in the array
|
| 53 : |
|
|
index_t begin_active () const;
|
| 54 : |
|
|
index_t end_active () const;
|
| 55 : |
|
|
index_t next_active (index_t &ix);
|
| 56 : |
|
|
```
|
| 57 : |
|
|
|
| 58 : |
|
|
```cpp
|
| 59 : |
|
|
// iteration over the stable strands in the array
|
| 60 : |
|
|
index_t begin_stable () const;
|
| 61 : |
|
|
index_t end_stable () const;
|
| 62 : |
|
|
index_t next_stable (index_t &ix);
|
| 63 : |
|
|
```
|
| 64 : |
|
|
|
| 65 : |
|
|
```cpp
|
| 66 : |
|
|
// iteration over the alive strands in the array
|
| 67 : |
|
|
index_t begin_alive () const;
|
| 68 : |
|
|
index_t end_alive () const;
|
| 69 : |
|
|
index_t next_alive (index_t &ix);
|
| 70 : |
|
|
```
|
| 71 : |
|
|
|
| 72 : |
|
|
#### Dual-state functions
|
| 73 : |
|
|
|
| 74 : |
|
|
Some functions are specific to the *dual-state* implementations of the `strand_array` type.
|
| 75 : |
|
|
|
| 76 : |
|
|
The dual-state implementations maintain two copies of the shared mutable strand state:
|
| 77 : |
|
|
the *in-state*, which is the strand's state at the beginning of the super step, and
|
| 78 : |
|
|
the *out-state*, which is the state that is updated during the super step.
|
| 79 : |
|
|
|
| 80 : |
|
|
There are two functions for managing the two copies of the mutable state.
|
| 81 : |
|
|
```cpp
|
| 82 : |
|
|
// for dual-state implementations, return the index of the shared input state.
|
| 83 : |
|
|
uint32_t in_state_index () const;
|
| 84 : |
|
|
// swap in and out states
|
| 85 : |
|
|
void swap ();
|
| 86 : |
|
|
```
|
| 87 : |
|
|
These functions are present, but no-ops, in the single-state implementations.
|
| 88 : |
|
|
|
| 89 : |
|
|
There are also functions for accessing the in and out states of a strand:
|
| 90 : |
|
|
```cpp
|
| 91 : |
|
|
// return a pointer to the shared input state of the strand with the
|
| 92 : |
|
|
// given index [DUAL-STATE only]
|
| 93 : |
|
|
const STRAND_shared *in_state (index_t ix) const;
|
| 94 : |
|
|
// return a pointer to the shared input state of the strand with the
|
| 95 : |
|
|
// given strand ID
|
| 96 : |
|
|
const STRAND_shared *id_to_in_state (sid_t id) const;
|
| 97 : |
|
|
// return a pointer to the shared output state of the strand with the
|
| 98 : |
|
|
// given index
|
| 99 : |
|
|
STRAND_shared *out_state (index_t ix) const;
|
| 100 : |
|
|
```
|
| 101 : |
|
|
|
| 102 : |
|
|
#### Strand operations
|
| 103 : |
|
|
|
| 104 : |
|
|
```cpp
|
| 105 : |
|
|
// initialize the first nStrands locations as new active strands
|
| 106 : |
|
|
void create_strands (uint32_t nStrands);
|
| 107 : |
|
|
// invoke strand's start method
|
| 108 : |
|
|
diderot::strand_status strand_start (..., index_t ix);
|
| 109 : |
|
|
// invoke strand's update method
|
| 110 : |
|
|
diderot::strand_status strand_update (..., index_t ix);
|
| 111 : |
|
|
// invoke strand's stabilize method
|
| 112 : |
|
|
index_t strand_stabilize (..., index_t ix);
|
| 113 : |
|
|
// record that the specified strand is dying
|
| 114 : |
|
|
index_t kill (index_t ix);
|
| 115 : |
|
|
// allocate a new strand
|
| 116 : |
|
|
index_t new_strand ();
|
| 117 : |
|
|
// finish a step by updating the strand statuses and the various counters
|
| 118 : |
|
|
void finish_step ();
|
| 119 : |
|
|
```
|
| 120 : |
|
|
|
| 121 : |
|
|
#### Other operations
|
| 122 : |
|
|
|
| 123 : |
|
|
```cpp
|
| 124 : |
|
|
// allocate space for at least nItems
|
| 125 : |
|
|
bool alloc (uint32_t nItems);
|
| 126 : |
|
|
// deallocate space reserved for strands
|
| 127 : |
|
|
void dealloc ();
|
| 128 : |
|
|
```
|
| 129 : |
|
|
|
| 130 : |
|
|
### Implementations
|
| 131 : |
|
|
|
| 132 : |
|
|
There are four implementations of the `strand_array` type for the sequential target.
|
| 133 : |
|
|
These are defined in four different source-fragment files, which are located in the
|
| 134 : |
|
|
directory `src/compiler/target-cpu/fragments`.
|
| 135 : |
|
|
|
| 136 : |
|
|
* `seq-sarr.in` -- the basic implementation for the no-BSP scheduler with direct
|
| 137 : |
|
|
access to the state and no shared state. In this implementation a strand's `sid_t`
|
| 138 : |
|
|
and `index_t` IDs are the same.
|
| 139 : |
|
|
* `seq-sarr-indirect.in` -- the implementation for programs that have dynamic thread
|
| 140 : |
|
|
operations (*e.g.*, ``die``). This implementation adds a level of indirection
|
| 141 : |
|
|
to the strand's state to support the dynamically changing number of strands.
|
| 142 : |
|
|
* `seq-sarr-dual.in` -- the implementation for programs that have strand communication,
|
| 143 : |
|
|
but not `new` or `die`. Two copies of any mutable strand state that is accessed
|
| 144 : |
|
|
by other strands is duplicated into an *in-state* and *out-state*.
|
| 145 : |
|
|
* `seq-sarr-dual-indirect.in` -- the implementation for programs that have both
|
| 146 : |
|
|
strand communication and dynamically varying numbers of strands.
|
| 147 : |
|
|
|
Parent Directory
| 
Revision Log
