Przedziały równoliczne

ranges.upc

/* 
 * autor: Maciej Ciemborowicz
 * Uniwersytet Jagielloński
 * PRIR 2011/2012
 * kompilacja: /usr/local/berkeley_upc/bin/upcc ranges.upc -fupc-threads-N
 *                                                                (gdzie N to ilość procesów)
 * uruchomienie: /usr/local/berkeley_upc/bin/upcrun a.out ILOSC_PRZEDZIALOW
 */

#include <upc_relaxed.h>
#include <upc_collective.h>
#include <stdio.h>
#include <stdlib.h>

////////////////////////////////////////////////////////////////////////////

static
shared void *
Asub (shared void *A, int i, size_t elem_size, size_t blk_size)
// Compute &A[i] given &A[0] and the element and block sizes of A.
{
  shared char *base;
  int j, k, r, p, q;

  base = (shared char *) A - upc_threadof (A);	// corres. addr on thr 0
  p = upc_phaseof (A);		// phase of A
  j = i + p + upc_threadof (A) * blk_size;	// j is i relative to base
  k = (j / blk_size) % THREADS;	// element j is on thread k
  r = j - k * blk_size;		// r is corres. index on thr 0
  q = r / (blk_size * THREADS);	// number of blocks preceding r

  return base + (q * blk_size + j % blk_size - p) * elem_size * THREADS + k;
}

////////////////////////////////////////////////////////////////////////////

void
sort (shared void *A,
	      size_t elem_size,
	      size_t nelems,
	      size_t blk_size,
	      int (*func) (shared void *, shared void *),
	      upc_flag_t sync_mode)
{
  const int nelems_m1 = (int)nelems - 1;
  int i, j;
  shared char *Aj, *Ajp1, *tmp;

#ifdef _UPC_COLL_CHECK_ARGS
  upc_coll_err (A, NULL, NULL, elem_size, sync_mode, blk_size,
		nelems, 0, UPC_SORT);
#endif

  // Synchronize using barriers in the cases of MYSYNC and ALLSYNC.

  if (UPC_IN_MYSYNC & sync_mode || !(UPC_IN_NOSYNC & sync_mode))

    upc_barrier;

  if (MYTHREAD == 0)
#ifdef __UPC_VERSION__		// UPC version 1.1 or higher
    tmp = upc_alloc (elem_size);
#else // deprecated version is used
    tmp = upc_local_alloc (1, elem_size);
#endif

  // Thread 0 does a bubble sort.
  if (MYTHREAD == 0)
    for (i = 0; i < nelems_m1; ++i)
      for (j = 0; j < nelems_m1 - i; ++j)
	{
	  // compute addresses of A[j] and A[j+1]

	  Aj = (shared char *) Asub (A, j, elem_size, blk_size);
	  Ajp1 = (shared char *) Asub (A, j + 1, elem_size, blk_size);

	  if (func ((shared void *) Aj, (shared void *) Ajp1) > 0)

	    {			// swap array elements
	      upc_memcpy (tmp, (shared const void *) Aj, elem_size);
	      upc_memcpy (Aj, (shared const void *) Ajp1, elem_size);
	      upc_memcpy (Ajp1, (shared const void *) tmp, elem_size);
	    }
	}

  if (MYTHREAD == 0)
    upc_free (tmp);

  // Synchronize using barriers in the cases of MYSYNC and ALLSYNC.

  if (UPC_OUT_MYSYNC & sync_mode || !(UPC_OUT_NOSYNC & sync_mode))
    upc_barrier;
}

////////////////////////////////////////////////////////////////////////////

/* za dokumentacją UPC, wykorzystywane w upc_sort_all */
int lt_int( shared void *x, shared void *y ) {
  float x_val = *(shared float *)x, 
        y_val = *(shared float *)y;
  return x_val > y_val ? -1 : x_val < y_val ? 1 : 0;
}

/* ilość liczb */
shared int size = 0;
  
int main(int argc, char* argv[]) {

  /* pobranie argumentu określającego ilość przedziałów równolicznych */
  int ranges_number = atoi(argv[1]);

  FILE *f;
  int i=0;
  
  /* pobranie ilości rekordów w pliku */
  if (MYTHREAD == 0) {
    f = fopen ("dane.dat", "r");
    float o; 
    while ((i=fscanf(f,"%f",&o)) != EOF) {
      size += i;
    }
    fclose(f);
  }

  /* alokacja pamięci współdzielonej */
  upc_barrier;
  shared [] float *array = upc_all_alloc(size*THREADS, sizeof(float));
  upc_barrier;

  /* wczytanie danych z pliku */
  if (MYTHREAD == 0) {
    int current=0;
    float temp;
    int i=0;
      f = fopen ("dane.dat", "r");
      float o; 
      while ((i=fscanf(f,"%f\n",&temp)) != EOF) {
        array[current] = temp;
        current += i;
      }
  }

  /* posortowanie tablicy z wykorzystaniem funkcji wbudowanej UPC */
  upc_barrier;
  sort(array, sizeof(float), size*THREADS, size, lt_int, UPC_IN_ALLSYNC);
  upc_barrier;

  if (MYTHREAD == 0) {

/*
  for(int i=size-1; i>=0; --i) {
    printf("%f\n", array[i]);
  }
  
  printf("======\n");
*/
    
    /* wypisanie granic przedziałów
     * każdy przedział ma size/ranges_number elementów
     * granica przedziałów jest jest obliczana z wykorzystaniem średniej sąsiednich elementów
     */
    for (i = size-1-(size/ranges_number); i>=(size/ranges_number) - 1; i-=size/ranges_number) {
      printf("%f\n", array[i]-((array[i]-array[i+1])/2));
    }
  }
  
  return 0;
}