queue.c 8.22 KB
Newer Older
1
/*******************************************************************************
2
 * This file is part of SWIFT.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 * Coypright (c) 2012 Pedro Gonnet (pedro.gonnet@durham.ac.uk)
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * 
 ******************************************************************************/

/* Config parameters. */
#include "../config.h"

/* Some standard headers. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Local headers. */
#include "cycle.h"
#include "lock.h"
#include "task.h"
#include "cell.h"
#include "queue.h"
34
35
#include "error.h"
#include "inline.h"
36
37
38

/* Define the timer macros. */
#ifdef TIMER_VERBOSE
39
40
41
    #ifndef TIMER
        #define TIMER
    #endif
42
43
44
45
46
47
#endif
#ifdef TIMER
    #define TIMER_TIC ticks tic = getticks();
    #define TIMER_TOC(t) timer_toc( t , tic )
    #define TIMER_TIC2 ticks tic2 = getticks();
    #define TIMER_TOC2(t) timer_toc( t , tic2 )
48
    INLINE static ticks timer_toc ( int t , ticks tic ) {
49
50
51
52
53
54
55
        ticks d = (getticks() - tic);
        __sync_add_and_fetch( &queue_timer[t] , d );
        return d;
        }
#else
    #define TIMER_TIC
    #define TIMER_TOC(t)
Pedro Gonnet's avatar
Pedro Gonnet committed
56
57
    #define TIMER_TIC2
    #define TIMER_TOC2(t)
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#endif


/* Counter macros. */
#ifdef COUNTER
    #define COUNT(c) ( __sync_add_and_fetch( &queue_counter[ c ] , 1 ) )
#else
    #define COUNT(c)
#endif


/* The timers. */
ticks queue_timer[ queue_timer_count ];

/* The counters. */
int queue_counter[ queue_counter_count ];

        

Pedro Gonnet's avatar
Pedro Gonnet committed
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * @brief Insert a used tasks into the given queue.
 *
 * @param q The #queue.
 * @param t The #task.
 */
 
void queue_insert ( struct queue *q , struct task *t ) {

    /* Lock the queue. */
    if ( lock_lock( &q->lock ) != 0 )
        error( "Failed to get queue lock." );
        
90
91
92
93
94
95
96
97
98
99
100
101
102
    /* Does the queue need to be grown? */
    if ( q->count == q->size ) {
        int *temp;
        q->size *= queue_sizegrow;
        if ( ( temp = (int *)malloc( sizeof(int) * q->size ) ) == NULL )
            error( "Failed to allocate new indices." );
        memcpy( temp , q->tid , sizeof(int) * q->count );
        free( q->tid );
        q->tid = temp;
        }
        
    /* Drop the task at the end of the queue. */
    q->tid[ q->count ] = ( t - q->tasks );
Pedro Gonnet's avatar
Pedro Gonnet committed
103
    q->count += 1;
104
105
    
    /* Shuffle up. */
106
107
    for ( int k = q->count - 1 ; k > 0 ; k = (k-1)/2 )
        if ( q->tasks[ q->tid[k] ].weight > q->tasks[ q->tid[(k-1)/2] ].weight ) {
108
            int temp = q->tid[k];
109
110
            q->tid[k] = q->tid[(k-1)/2];
            q->tid[(k-1)/2] = temp;
111
112
113
            }
        else
            break;
114
115
116
117
118
            
    /* Verify queue consistency. */
    /* for ( int k = 1 ; k < q->count ; k++ )
        if ( q->tasks[ q->tid[(k-1)/2] ].weight < q->tasks[ q->tid[k] ].weight )
            error( "Queue not heaped." ); */
Pedro Gonnet's avatar
Pedro Gonnet committed
119
120
121
122
123
124
125
    
    /* Unlock the queue. */
    if ( lock_unlock( &q->lock ) != 0 )
        error( "Failed to unlock queue." );
    }


126
127
128
129
130
131
132
133
/** 
 * @brief Initialize the given queue.
 *
 * @param q The #queue.
 * @param size The maximum size of the queue.
 * @param tasks List of tasks to which the queue indices refer to.
 */
 
134
void queue_init ( struct queue *q , struct task *tasks ) {
135
    
136
    /* Allocate the task list if needed. */
137
138
139
    q->size = queue_sizeinit;
    if ( ( q->tid = (int *)malloc( sizeof(int) * q->size ) ) == NULL )
        error( "Failed to allocate queue tids." );
140
141
        
    /* Set the tasks pointer. */
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
    q->tasks = tasks;
        
    /* Init counters. */
    q->count = 0;
    
    /* Init the queue lock. */
    if ( lock_init( &q->lock ) != 0 )
        error( "Failed to init queue lock." );

    }


/**
 * @brief Get a task free of dependencies and conflicts.
 *
 * @param q The task #queue.
 * @param blocking Block until access to the queue is granted.
 * @param keep Remove the returned task from this queue.
 */
 
162
struct task *queue_gettask ( struct queue *q , int qid , int blocking ) {
163

Pedro Gonnet's avatar
Pedro Gonnet committed
164
    int k, i, temp, qcount, *qtid, type;
165
    lock_type *qlock = &q->lock;
166
167
    struct task *qtasks, *res = NULL;
    struct cell *ci, *cj;
168
169
170
    TIMER_TIC
    
    /* If there are no tasks, leave immediately. */
171
    if ( q->count == 0 ) {
172
173
174
175
176
        TIMER_TOC(queue_timer_gettask);
        return NULL;
        }

    /* Main loop, while there are tasks... */
177
    while ( q->count > 0 ) {
178
179
    
        /* Grab the task lock. */
180
181
        if ( lock_lock( qlock ) != 0 )
            error( "Locking the qlock failed.\n" );
182
            
183
184
185
        /* Set some pointers we will use often. */
        qtid = q->tid;
        qtasks = q->tasks;
186
        qcount = q->count;
187
            
188
        /* Loop over the remaining task IDs. */
189
        for ( k = 0 ; k < qcount ; k++ ) {
Pedro Gonnet's avatar
Pedro Gonnet committed
190
191
192
        
            /* Put a finger on the task. */
            res = &qtasks[ qtid[k] ];
193
194
195
            ci = res->ci;
            cj = res->cj;
            type = res->type;
Pedro Gonnet's avatar
Pedro Gonnet committed
196
197
198
199
200
            
            /* Is this task blocked? */
            if ( res->wait )
                continue;
                
201
            /* Try to lock ci. */
202
203
204
205
            if ( type == task_type_self || 
                 type == task_type_sort || 
                 (type == task_type_sub && cj == NULL) ) {
                if ( cell_locktree( ci ) != 0 )
Pedro Gonnet's avatar
Pedro Gonnet committed
206
207
                    continue;
                }
208
209
            else if ( type == task_type_pair || (type == task_type_sub && cj != NULL) ) {
                if ( ci->hold || cj->hold || ci->wait || cj->wait )
Pedro Gonnet's avatar
Pedro Gonnet committed
210
                    continue;
211
                if ( cell_locktree( ci ) != 0 )
Pedro Gonnet's avatar
Pedro Gonnet committed
212
                    continue;
213
214
                if ( cell_locktree( cj ) != 0 ) {
                    cell_unlocktree( ci );
Pedro Gonnet's avatar
Pedro Gonnet committed
215
216
217
                    continue;
                    }
                }
218
            
Pedro Gonnet's avatar
Pedro Gonnet committed
219
            /* If we made it this far, we're safe. */
220
            break;
Pedro Gonnet's avatar
Pedro Gonnet committed
221
222
223
224
        
            } /* loop over the task IDs. */
            
        /* Did we get a task? */
225
        if ( k < qcount ) {
Pedro Gonnet's avatar
Pedro Gonnet committed
226
        
227
            /* Another one bites the dust. */
228
            qcount = q->count -= 1;
Pedro Gonnet's avatar
Pedro Gonnet committed
229
230
        
            /* Own the cells involved. */
231
232
233
            ci->super->owner = qid;
            if ( cj != NULL )
                cj->super->owner = qid;
234
                
235
            /* Swap this task with the last task and re-heap. */
236
237
238
239
240
241
242
243
244
245
            if ( k < qcount ) {
                qtid[ k ] = qtid[ qcount ];
                while ( qtasks[ qtid[k] ].weight > qtasks[ qtid[(k-1)/2] ].weight ) {
                    int temp = q->tid[k];
                    q->tid[k] = q->tid[(k-1)/2];
                    q->tid[(k-1)/2] = temp;
                    k = (k-1)/2;
                    }
                while ( ( i = 2*k+1 ) < qcount ) {
                    if ( i+1 < qcount && qtasks[ qtid[i+1] ].weight > qtasks[ qtid[i] ].weight )
246
                        i += 1;
247
                    if ( qtasks[ qtid[i] ].weight > qtasks[ qtid[k] ].weight ) {
248
                        temp = qtid[i];
249
250
251
252
253
254
                        qtid[i] = qtid[k];
                        qtid[k] = temp;
                        k = i;
                        }
                    else
                        break;
255
                    }
Pedro Gonnet's avatar
Pedro Gonnet committed
256
                }
Pedro Gonnet's avatar
Pedro Gonnet committed
257
                
258
259
260
261
262
            /* Verify queue consistency. */
            /* for ( k = 1 ; k < q->count ; k++ )
                if ( q->tasks[ q->tid[(k-1)/2] ].weight < q->tasks[ q->tid[k] ].weight )
                    error( "Queue not heaped." ); */
    
Pedro Gonnet's avatar
Pedro Gonnet committed
263
            }
Pedro Gonnet's avatar
Pedro Gonnet committed
264
265
        else
            res = NULL;
Pedro Gonnet's avatar
Pedro Gonnet committed
266
267
268
    
        /* Release the task lock. */
        if ( lock_unlock( qlock ) != 0 )
269
            error( "Unlocking the qlock failed.\n" );
Pedro Gonnet's avatar
Pedro Gonnet committed
270
271
            
        /* Leave? */
272
        if ( res != NULL || !blocking )
273
274
275
276
            break;
    
        } /* while there are tasks. */
        
Pedro Gonnet's avatar
Pedro Gonnet committed
277
    /* Take the money and run. */
278
    TIMER_TOC(queue_timer_gettask);
279
    return res;
280
281
282
283

    }