source: trunk/platforms/caba-xxx-ccxcachemulti-mipsel/soft/main.c @ 7

Last change on this file since 7 was 3, checked in by nipo, 15 years ago

Import platforms

  • Property svn:eol-style set to native
  • Property svn:executable set to *
  • Property svn:keywords set to "Author Date Id Rev URL Revision"
  • Property svn:mime-type set to text/plain
File size: 6.8 KB
Line 
1#include "system.h"
2#include "stdio.h"
3#include "stdlib.h"
4#include "matrice.h"
5
6#include "../segmentation.h"
7
8#define NPROCS 4
9#define SIZE 1000
10#define SORT_TYPE 0 // shellSort
11
12volatile int nprocs=NPROCS;
13
14/*
15unsigned int gQSortNum0[200] = {
16  251,  24, 113, 170, 215,  60,  83,  30, 115,  48, 169, 210,  49,  92, 101,  58,  21, 184, 225,   6,
17  199, 244, 227, 146,  99,  96,  25, 222,  65, 140, 213,  22, 219, 136, 175, 182,  73,  36, 141, 190,
18   83, 112, 137, 114, 175, 188, 187, 102,  53, 168, 193, 154, 167, 172,   3, 242,  67,  64, 144, 137,
19  142, 175, 188,  69, 102,  53, 168, 193, 102,  89, 172, 253, 242,  67, 192,   7,  62, 159,  20, 181,
20  182, 187, 216, 207,  22, 105, 132, 109, 162, 205,  16, 151,  18, 113, 228,  37,   6,  85,   8, 161,
21   58, 135,  76,  35, 174,  35, 224,  39, 158, 127, 180, 149,  86, 155, 200, 239, 118, 119,  28,  77,
22  254,  19, 176, 183,  78, 145, 132,   5,  90, 117, 152, 127, 218, 153,  20,  67, 178,   3, 128, 185,
23  254,  95, 172, 139, 246, 123, 104,  15,  42, 169,  68, 211,  98, 243,  80,  41, 174,  79,  36,  27,
24  186, 149,  86, 155, 200, 239, 118, 119,  28,  77, 254,  19, 176, 183,  78, 145, 132,   5,  90, 117,
25  152, 127, 218, 153,  20,  67, 178,   3, 128, 185, 254,  95, 172, 139, 246, 123, 104,  15,  42, 169 };
26*/
27
28unsigned int SortArr0[NPROCS*(SIZE+200)];
29
30void SORT(unsigned int *base, unsigned int n, int type);
31void insertion_sort(unsigned int *base, unsigned int n); // type 2
32void selection_sort(unsigned int *base, unsigned int n); // type 1
33void bubble_sort(unsigned int *base, unsigned int n);    // type 3
34void shellSortPhase(unsigned int a[],unsigned int length, int gap);
35void shellSort(unsigned int *base, unsigned int n);     // type 0
36
37int main()
38{
39  register int p;
40
41  int beg_cycle, end_cycle;
42
43  beg_cycle = cpu_cycles();
44
45  p=procnum();
46
47  puts("Hello from processor ");
48  putchar(p+'0');
49  putchar('\n');
50
51  int i;
52  int j;
53  unsigned int* SortArray;
54
55  if(p+1 <= nprocs)
56  {
57        i=1;
58        puts("Memory copy \n");
59        SortArray = SortArr0 + p*(SIZE+200);
60        memcpy(SortArray, gQSortNum0 + p*SIZE,SIZE*4);
61        //memcpy(SortArray, gQSortNum0,SIZE*4);
62
63        puts("Sort... \n");
64        SORT((unsigned int *) (SortArray), (unsigned int) SIZE, SORT_TYPE);
65
66        for (j = 1; j < SIZE; j++)
67        {
68          if (SortArray[j] < SortArray[j-1])
69                {
70                        puts("ucbqsort: failed\n");
71                        while(1);
72                }
73
74        }
75
76        puts("ucbqsort: success\n");
77        end_cycle = cpu_cycles();
78//      printf( "nombre cycles cpu : %i\n", end_cycle-beg_cycle);
79        printf( "begin time        : %i\n", beg_cycle);
80        printf( "end time          : %i\n", end_cycle);
81  }
82
83 
84// puts("Display the sorted array : \n");
85// for(j = 0; j < SIZE; j++)
86// {
87//   puti(SortArray[j]);
88//   putchar('\n');
89// }
90
91//  printf( "------------------------------ \n");
92//  printf( "nombre cycles cpu : %i\n", end_cycle-beg_cycle);
93//  printf( "------------------------------ \n");
94
95
96  while(1);
97}
98
99
100//---- insertion sort : non adapté pour tableaux de grande taille (> 100) --
101void insertion_sort(unsigned int *base, unsigned int n)
102{
103    /* Spécifications externes : Tri du tableau base par insertion séquentielle */
104    int i,p,j;
105    int x;
106
107    puts("Insertion Sort\n");
108
109    for (i = 1; i < n; i++)
110    {
111
112        putchar('-'); // added for debug
113
114        /* stockage de la valeur en i */
115        x = base[i];
116 
117        /* recherche du plus petit indice p inférieur à i tel que base[p] >= base[i] */
118        for(p = 0; base[p] < x; p++);
119        /* p pointe une valeur de base supérieure à celle en i */
120 
121        /* décalage avant des valeurs de base entre p et i */         
122        for (j = i-1; j >= p; j--) {
123            base[j+1] = base[j];
124        }   
125 
126        base[p] = x; /* insertion de la valeur stockée à la place vacante */
127
128        putchar('+'); // added for debug
129
130    }
131}
132
133//------ simple_sort -------------------------------
134void selection_sort(unsigned int *base, unsigned int n)
135{
136     int i, min, j , x;
137     puts("Selection Sort\n");
138
139     for(i = 0 ; i < n - 1 ; i++)
140     {
141
142         putchar('-'); // added for debug
143
144         min = i;
145
146         
147         for(j = i+1 ; j < n ; j++)
148         {
149       
150            if(base[j] < base[min])
151                  min = j;
152           
153         }
154
155         if(min != i)
156         {
157             x = base[i];
158             base[i] = base[min];
159             base[min] = x;
160         }
161
162         putchar('+'); // added for debug
163
164     }
165}
166//-------------------------------
167void bubble_sort(unsigned int *base, unsigned int n)
168{
169        int i   = 0; /* Indice de répétition du tri */
170        int j   = 0; /* Variable de boucle */
171        int tmp = 0; /* Variable de stockage temporaire */
172        int en_desordre = 1; /* Booléen marquant l'arrêt du tri si le tableau est ordonné */
173
174        puts("Bubble Sort\n");
175
176        /* Boucle de répétition du tri et le test qui arrête le tri dès que le tableau est ordonné */
177        for(i = 0 ; (i < n) && en_desordre; i++)
178        {
179                putchar('-'); // added for debug
180
181                /* Supposons le tableau ordonné */
182                en_desordre = 0;
183                /* Vérification des éléments des places j et j-1 */
184                for(j = 1 ; j < n - i ; j++)
185                {
186                        /* Si les 2 éléments sont mal triés */
187                        if(base[j] < base[j-1])
188                        {
189                                /* Inversion des 2 éléments */
190                                tmp = base[j-1];
191                                base[j-1] = base[j];
192                                base[j] = tmp;
193 
194                                /* Le tableau n'est toujours pas trié */
195                                en_desordre = 1;
196                        }
197                }
198
199                putchar('+'); // added for debug
200        }
201
202}
203//------------------------------------------------------
204/*
205 * Exécute un tri par insertion avec la séparation donnée
206 * If gap == 1, on fait un tri ordinaire.
207 * If gap >= length, on ne fait rien.
208 */
209void shellSortPhase(unsigned int a[],unsigned int length, int gap) {
210    int i;
211 
212    puti(gap);
213    for (i = gap; i < length; ++i) {
214        unsigned int value = a[i];
215        int j;
216        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
217            putchar('+');
218            a[j + gap] = a[j];
219            putchar('-');
220        }
221        a[j + gap] = value;
222    }
223}
224 
225void shellSort(unsigned int *base, unsigned int n) {
226    /*
227     * gaps[] doit approximer une Série géométrique.
228     * La sequence suivante est la meilleure connue en terme
229     * de nombre moyen de comparaisons. voir:
230     * http://www.research.att.com/~njas/sequences/A102549
231     */
232    static const int gaps[] = {
233        1, 4, 10, 23, 57, 132, 301, 701
234    };
235    int sizeIndex;
236 
237    puts("Shell Sort\n");
238    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
239               sizeIndex >= 0;
240               --sizeIndex)
241        shellSortPhase(base, n, gaps[sizeIndex]);
242}
243
244//-------------------------------------*/
245void SORT(unsigned int *base, unsigned int n, int type)
246{
247  switch(type)
248  {
249  case 0:
250    shellSort(base, n);
251    break;
252  case 1:
253    selection_sort(base, n);
254    break;
255  case 2:
256    insertion_sort(base, n);
257    break;
258  case 3:
259    bubble_sort(base, n);
260    break;
261  default:
262    break;
263  }
264}
Note: See TracBrowser for help on using the repository browser.