source: trunk/platforms/caba-ring-ccxcachev1_memcachev3-mipsel/soft/main.c @ 324

Last change on this file since 324 was 137, checked in by simerabe, 14 years ago

replacing old ring versions with new one

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