source: proiecte/swift/trunk/test/qsort_ws.c @ 176

/*
 * swift_context.c
 *
 * (c) 2009 Ionut Rosoiu <ionut.rosoiu@gmail.com>
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include "swift.h"

int limit;

extern void read_array(char *filename, int **arr, int *n);
extern void free_array(int *arr);
extern void check_array(int *arr, int n);

typedef struct qs_data {
        int *a;
        int l;
        int r;

        char _pad1[SWIFT_CACHE_LINE_SIZE - sizeof(swift_size_t)];

        swift_size_t sync_frames_remaining;

        char _pad2[SWIFT_CACHE_LINE_SIZE - sizeof(swift_size_t)];
} qs_data_t;

/* forward declaration for the fibo() */
void qs(swift_thread_t *thread, swift_frame_t *frame);


inline
void swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

inline
int partition(int *a, int l, int r)
{
        int pivot = a[l];
        int i = l;
        int j = r + 1;

        while (1) {
                do {
                        ++i;
                } while (a[i] <= pivot && i <= r);

                do {
                        --j;
                } while (a[j] > pivot);

                if (i >= j) {
                        break;
                }

                swap(&a[i], &a[j]);
        }

        swap(&a[l], &a[j]);
        return j;
}

void qs_ws(swift_thread_t *thread, swift_frame_t *frame)
{
        qs_data_t *data = frame->private_data;
        swift_status_t status;
        int pivot, n;

        SWIFT_LOG(INFO, "\n[%d] qs() c=%d f=%c.%d-%d (%d)\n", thread->id,
                                                                SWIFT_PROC(frame->info), SWIFT_FRAME_NAME(frame->info),
                                                                ((frame->dbg >> 16) & 0xFF), (frame->dbg & 0xFF),
                                                                SWIFT_FRAME_ID(frame->info));

        if (data->l < data->r) {
                swift_frame_t frame1;
                qs_data_t data1;

                swift_frame_t frame2;
                qs_data_t data2;

#ifdef LOGGING_ON
                int i;
#endif

                pivot = partition(data->a, data->l, data->r);

#ifdef LOGGING_ON
                for (i=data->l; i<=data->r; i++) {
                        if (i == pivot) {
                                fprintf(stderr, "%d<%d> ", i, data->a[i]);
                        } else {
                                fprintf(stderr, "%d(%d) ", i, data->a[i]);
                        }
                }
                fprintf(stderr, "\n");
#endif

                // ---------- left ---------
                frame1.closure = qs_ws;
                frame1.flags = 0;
#ifdef LOGGING_ON
                frame1.creator_id = thread->id;
                frame1.dbg = ((data->l & 0xFF) << 16) | ((pivot - 1) & 0xFF);
#endif
                data1.a = data->a;
                data1.l = data->l;
                data1.r = pivot - 1;

                frame1.private_data = &data1;

                SWIFT_WRITE_FRAME_INFO((&frame1), thread->id, 'q', thread->frame_no++);

                frame1.dependencies_frame = NULL;
                frame1.sync_frames_remaining = &data->sync_frames_remaining;

                // ---------- right ---------
                frame2.closure = qs_ws;
                frame2.flags = 0;
#ifdef LOGGING_ON
                frame2.creator_id = thread->id;
                frame2.dbg = (((pivot + 1) & 0xFF) << 16) | (data->r & 0xFF);
#endif
                data2.a = data->a;
                data2.l = pivot + 1;
                data2.r = data->r;

                frame2.private_data = &data2;

                SWIFT_WRITE_FRAME_INFO((&frame2), thread->id, 'q', thread->frame_no++);

                frame2.dependencies_frame = NULL;
                frame2.sync_frames_remaining = &data->sync_frames_remaining;

                // ------------------------
                // wait for 1&2 to finish
                data->sync_frames_remaining = 2;

                // put it into the workqueue
                swift_deque_push(&thread->workque, &frame1, &status);
                swift_deque_push(&thread->workque, &frame2, &status);

                // sync
                while ((n = SWIFT_ATOMIC_READ(data->sync_frames_remaining))) {
                        SWIFT_LOG(INFO, "[%d] %s rem=%d c=%d f=%c.%d-%d (%d)\n", thread->id, "@sync", n,
                                                        SWIFT_PROC(frame->info), SWIFT_FRAME_NAME(frame->info),
                                                        ((frame->dbg >> 16) & 0xFF), (frame->dbg & 0xFF),
                                                        SWIFT_FRAME_ID(frame->info));
                        swift_scheduler_execute(thread);
                }

                SWIFT_LOG(INFO, "[%d] __qs(%d, %d)\n", thread->id, data->l, data->r);

                if (SWIFT_FRAME_IS_END_PARALLEL(frame)) {
                        SWIFT_LOG(INFO, "[%d] END_PARALLEL!!!\n", thread->id);
                        thread->stop = 1;
                }
        }

        swift_signal_frame_done(thread, frame);
        swift_frame_done(thread->context, thread, frame);
}

void* thread_start(void *arg) {
        swift_thread_t *thread = arg;
        int i = 0;

        SWIFT_LOG(INFO, "_____started thread %d\n", thread->id);

        while(!thread->stop) {
                swift_scheduler_execute(thread);
        }

        // inform all other threads that they must stop
        for (i=0; i<thread->context->thread_num; i++) {
                thread->context->threads[i].stop = 1;
        }


        SWIFT_LOG(INFO, "_____finished thread %d: %d frames processed\n", thread->id, thread->stats);
        printf("_____finished thread %d: %d frames processed\n", thread->id, thread->stats);

        return arg;
}

int quicksort(int *a, int size, int nthreads)
{
        swift_context_t context;
        swift_frame_t frame;
        qs_data_t data;
        swift_status_t status;
        int i;

        SWIFT_LOG(INFO, "Started nthreads=%d\n", nthreads);

        /* initialize the context */
        swift_context_init(&context, nthreads);

        /* push the first frame */
        SWIFT_FRAME_SET_END_PARALLEL(&frame);
        frame.closure = qs_ws;
#ifdef LOGGING_ON
        frame.dbg = size & 0xFF;
        frame.creator_id = 0;
#endif

        data.a = a;
        data.l = 0;
        data.r = size - 1;
        frame.private_data = &data;

        SWIFT_WRITE_FRAME_INFO((&frame), 0, 'q', context.threads[0].frame_no++);
        SWIFT_LOG_FRAME_INFO((&context.threads[0]), (&frame));

        frame.dependencies_no = 0;
        frame.dependencies_frame = NULL;
        frame.sync_frames_remaining = &data.sync_frames_remaining;

        swift_deque_push(&context.threads[0].workque, &frame, &status);
        SWIFT_LOG(INFO, "pushed first frame\n");


        /* start the threads */
        for (i=0; i<nthreads; i++) {
                swift_thread_start(&context.threads[i], thread_start);
        }

        /* wait for the threads to finish */
        for (i=0; i<nthreads; i++) {
                SWIFT_LOG(INFO, "_____waiting %d\n", i);
                swift_thread_wait(&context.threads[i]);
                SWIFT_LOG(INFO, "_____waiting %d done\n", i);
        }

        /* check the result */
        printf("done with the first frame.\n");
        swift_context_destroy(&context);
        return 0;
}

int main(int argc, char **argv)
{
        int n, *a, nthreads;

        if (argc != 4) {
                fprintf(stderr, "usage: %s <input_file> <nthreads> <serial_limit>\n", argv[0]);
                abort();
        }

        read_array(argv[1], &a, &n);

        nthreads = strtol(argv[2], NULL, 10);
        limit = strtol(argv[3], NULL, 10);

        quicksort(a, n, nthreads);

        check_array(a, n);

        free_array(a);

        printf("done.\n");
        return 0;
}