Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /branches/cuda/doc/implementation/strand-arrays.md
ViewVC logotype

Annotation of /branches/cuda/doc/implementation/strand-arrays.md

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5597 - (view) (download)

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 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0