Parallellisere radix sortering

[jonny]

Nedenfor er en implementasjon av radix sortering. Noen som har tips til hvordan denne kan parallelliseres for å øke hastigheten ved bruk av flere kjerner? Jeg har prøvd og har klart å forbedre hastigheten litt (ved sortering av 10 mill. elementer, færre elementer reduserer hastigheten...), dette gjorde jeg ved å dele opp lista i X antall blokker og la hver tråd håndtere sin blokk, for så til slutt å 'merge' blokkene. Sortering av 100 mill. elementer med koden nedenfor tar ca 1500 ms, med den parallelliserte koden tar det ca 1333 ms på min maskin (i5 3570K @ 4.2 GHz).
 
Dette er ifm. en oppgave ved UiO som skal leveres i dag, men jeg er forsåvidt ferdig med den, så det er ikke viktig med raske svar - dette er kun for interessens skyld :-)

   public static void sort(int[] a) {
      int[] b = new int[a.length];
      radixSort(a, b,  0, false);
      radixSort(b, a,  8, false);
      radixSort(a, b, 16, false);
      radixSort(b, a, 24, true);
   }

   private static void radixSort(
         int[] a, int[] b, int shift, boolean signed)
   {
      int[] count = new int[0x100];
      for (int i = 0; i < a.length; i++)
         count[getRadixValue(a[i], shift, signed)]++;

      for (int i = 0, sum = 0; i < count.length; i++) {
         int j = count[i];
         count[i] = sum;
         sum += j;
      }

      for (int i = 0; i < a.length; i++)
         b[count[getRadixValue(a[i], shift, signed)]++] = a[i];
   }
   
   private static int getRadixValue(int value, int shift, boolean signed) {
      int result = (value >> shift) & 0xFF;
      return (signed ? result ^ 0x80 : result);
   }

Edit: Tallene brukt ved testing er tilfeldig genererte tall fra 0..n-1, hvor n er antall elementer i lista.

Endret 8. mai 2015 av jonny

[Joachim Hansen]

Du kan bruke lambda og parallel streams for å gjøre denne jobben for deg

private static long testParallel(Collection<String> names)
  {
    return names.parallelStream()
                .filter(name -> name.startsWith("A"))
                .count();
  }

eksempel  tatt fra :

http://www.javaworld.com/article/2461744/java-language/java-language-iterating-over-collections-in-java-8.html?page=2

[jonny]

Du kan bruke lambda og parallel streams for å gjøre denne jobben for deg

private static long testParallel(Collection<String> names)
  {
    return names.parallelStream()
                .filter(name -> name.startsWith("A"))
                .count();
  }

eksempel  tatt fra :

http://www.javaworld.com/article/2461744/java-language/java-language-iterating-over-collections-in-java-8.html?page=2

 

Hvordan da, mener du? Verdiene jeg skal sortere ligger i en int-array, og de skal sorteres med radix-algoritmen jeg postet ovenfor. Spørsmålet er altså om noen har tips til hvordan denne algoritmen kan parallelliseres, ikke om sortering generelt kan parallelliseres, slik det virker som du prøver å si? Mulig jeg misforstår deg...

[Persn]

dette gjorde jeg ved å dele opp lista i X antall blokker og la hver tråd håndtere sin blokk, for så til slutt å 'merge' blokkene.

 

På hvilken måte bestemmer du x og hvordan merger du blokkene?

[jonny]

 

dette gjorde jeg ved å dele opp lista i X antall blokker og la hver tråd håndtere sin blokk, for så til slutt å 'merge' blokkene.

 

På hvilken måte bestemmer du x og hvordan merger du blokkene?

 

 

X = Runtime.getRuntime().availableProcessors()

 

Jeg merger blokkene ved å la hver tråd ta to naboblokker og merge dem, dette gjøres om og om igjen helt til det kun er en blokk igjen. Dette er ikke helt optimalt, med 4 kjerner vil kun 2 tråder merge (så 4 blokker blir til 2), deretter vil en tråd merge de to gjenværende blokkene til sist.

[Persn]

Fra den lyn-researchen jeg har gjort om radix-sort så ville jeg nok antageligvis gjort det på samme måte som deg. Men på mergingen så burde du kjøre x/2 tråder istedenfor x. Å lage ekstra tråder som kjører og venter på tur vil lage overhead som igjen vil øke kjøretiden din.

 

Det som eventuelt står igjen da er å optimalisere single-thread performance, altså pass på at hver individuelle tråd ikke gjør mer enn nødvendig, om du ikke har gjort det allerede.

[jonny]

Fra den lyn-researchen jeg har gjort om radix-sort så ville jeg nok antageligvis gjort det på samme måte som deg. Men på mergingen så burde du kjøre x/2 tråder istedenfor x. Å lage ekstra tråder som kjører og venter på tur vil lage overhead som igjen vil øke kjøretiden din.

 

Det som eventuelt står igjen da er å optimalisere single-thread performance, altså pass på at hver individuelle tråd ikke gjør mer enn nødvendig, om du ikke har gjort det allerede.

 

Vet ikke helt om jeg skjønner hva du mener... slik jeg har gjort det, oppretter jeg en ExecutorService (en 'fixed threadpool') som så benyttes først for sorteringen (en del av array'en til hver tråd), og deretter brukes den samme threadpool'en til merging etterpå (men på min maskin med 4 tråder vil det jo kun bli to av trådene som får en jobb i første steg (2 tråder sammenfletter 2 blokker hver, som tilsammen blir 4), deretter kun en tråd i andre (og siste) steg av mergingen. Trådene i threadpool'en som ikke benyttes lager ikke nevneverdig overhead såvidt jeg vet.

[Persn]

Beklager, jeg så for meg en litt mer manuel håndtering av threads. Jeg skulle likt å brukt litt mer tid på dette, morsom nøtt, men det er desverre eksamenstid.

[quantum]

 

Hvordan da, mener du? Verdiene jeg skal sortere ligger i en int-array, og de skal sorteres med radix-algoritmen jeg postet ovenfor. Spørsmålet er altså om noen har tips til hvordan denne algoritmen kan parallelliseres, ikke om sortering generelt kan parallelliseres, slik det virker som du prøver å si? Mulig jeg misforstår deg...

 

 

Han mener vel at lambda-funksjoner og streams automatiserer paralelliseringen for deg, men det tar jo moroa ut av det ...

[jonny]

Ikke bare moroa, men effektiviteten også... jeg har prøvd å bruke IntStream til dette, koden for sorteringsmetoden ser slik ut:

   public void sort(int[] values) {
      IntStream stream = IntStream.of(values).sequential().sorted();
      PrimitveIterator.OfInt it = stream.iterator();
      for (int i = 0; i < values.length; i++)
         values[i] = it.nextInt();
   }

Den parallelle versjonen bytter ut .sequential() med .parallel() i koden ovenfor.
 
Testresultater, sammenlignet med Arrays.sort()-metoden (en quicksort-algoritme) og koden i første post (begge disse algoritmene er sekvensielle):

        Sort algorithm  1000  10000  100000  1000000  10000000  100000000
 
        IntQuickSorter  0.04   0.43    5.36    64.69    755.14    8651.61
 
       IntRadix4Sorter  0.01   0.08    0.88     9.70    105.34    1062.54
             (speedup)  2.91   5.07    6.07     6.67      7.17       8.14
 
       IntStreamSorter  0.08   0.68    7.98    93.48   1080.52   14488.87
             (speedup)  0.47   0.63    0.67     0.69      0.70       0.60
 
     IntMTStreamSorter  0.20   0.57    4.29    45.15    489.17    5329.65
             (speedup)  0.20   0.75    1.25     1.43      1.54       1.62

Tallene i første linje sier hvor mange elementer array'en som sorteres har (tilfeldige verdier fra Integer.MIN_VALUE til Integer.MAX_VALUE), tallene etter hver IntXXXSorter er i antall millisekunder, mens (speedup)-linjene viser hvor rask algoritmen i linjen over er i forhold til algoritmen øverst (IntQuickSorter). Testene er kjørt 9 ganger, og median-verdien av tidsmålingene er brukt. Alle algoritmene får de samme dataene å jobbe med i hver iterasjon (seed-verdi for generering av tall endres kun hver gang en ny test-iterasjon begynner).

Endret 10. mai 2015 av jonny

[jonny]

Jeg har fortsatt ikke klart å forbedre kjøretida til sorteringa merkbart. Metoden for å 'merge' sorterte data er viktig, jeg poster koden min her - fint om noen har noen forslag til forbedringer.

   /**
    * Merge two adjacent sorted parts of an array into one sorted part.
    * If the subarrays are not sorted (ascending), the result are
    * undefined.
    * 
    * @param a      array where to merge two adjacent, sorted subarrays
    * @param from1  start index of first subarray
    * @param from2  start index of second subarray ('from2'-1 is last
    *   index of first subarray)
    * @param to2    end index (exclusive) of the second subarray
    */
   public static void mergeSubArrays(
         int a[], int from1, int from2, int to2)
   {
      // skip all values on left side which are smaller than the
      // leftmost value in the right subarray
      for (int i = from1; i < from2 && a[i] <= a[from2]; i++, from1++);
      if (from1 == from2) return;
      // skip all values on right side which are larger than the
      // rightmost value in the left subarray
      for (int i = to2-1; i >= from2 && a[i] >= a[from2-1]; i--, to2--);
      if (to2 == from2) return;

      int leftLen = from2-from1, rightLen = to2-from2;
      if (leftLen <= rightLen) {
         // left subarray is smaller, make a copy and start merging
         int i = from1, j = 0, k = from2;
         int[] firstPart = Arrays.copyOfRange(a, from1+j, from2);
         while (j < firstPart.length && k < to2) {
            if (firstPart[j] <= a[k])
               a[i++] = firstPart[j++];
            else
               a[i++] = a[k++];
         }
         // all of either the left or right subarray is done, copy
         // the rest of 'firstPart' to the end of the two subarrays
         while (j < firstPart.length)
            a[i++] = firstPart[j++];
      }
      else {
         // right subarray is smaller, make a copy and start merging
         int i = to2-1, j = rightLen-1, k = from2-1;
         int[] lastPart = Arrays.copyOfRange(a, from2, from2+rightLen);
         while (j >= 0 && k >= from1) {
            if (lastPart[j] >= a[k])
               a[i--] = lastPart[j--];
            else
               a[i--] = a[k--];
         }
         // all of either the left or right subarray is done, copy
         // the rest of 'lastPart' to the start of the two subarrays
         while (j >= 0)
            a[i--] = lastPart[j--];
      }
   }

Endret 12. mai 2015 av jonny

[jonny]

I mangel av idéer på hvordan jeg kan øke hastigheten til radix-algoritmen ved bruk av flere tråder, har jeg lagt til funksjonalitet i programmet slik at det er mulig å få en visuell sammenligning av sorteringsalgoritmene. Hvis noen er interessert, ligger programmet vedlagt. OBS: Jeg er ikke en GUI-designer, så programmet er ikke veldig brukervennlig... bare spør om det skulle være noe!

 

Hvordan kjøre programmet:

- endre navnet til 'SortTester.jar' (er ikke lov til å laste opp .jar-filer her...)

- kjør kommandoen 'java -jar SortTester.jar -g'

 

Noen tips:

- vinduet som dukker opp har fire knapper for oppsett før sorteringen starter:

  - 'm' gir deg mulighet til å velge hvilke algoritmer du vil teste (bare skriv inn deler av navnet på algoritmene, adskilt med mellomrom, f.eks. vil 'quick' matche 'IntQuickSorter'). Det er mulig å dele opp elementene som skal sorteres i blokker på X antall elementer, slik at hver blokk sorteres separat med algoritmen du velger for deretter å 'merges' etterpå, dette gjøres ved å skrive inn 'bX:' foran navnet på algoritmen (f.eks. vil 'b8:ins' resultere i at IntInsertSorter sorterer 8 og 8 elementer før disse blokkene merges)

  - 'n' gir deg mulighet til å oppgi hvor mange elementer som skal sorteres

  - 'r' gir deg mulighet til å si hvor tilfeldige verdiene som skal sorteres skal være, 0 er ikke tilfeldig i det hele tatt (gir deg en ferdig sortert liste), mens 100 gir en liste hvor alle tallene er tilfeldig trukket

  - 'v' gir deg mulighet til å si hvilket tallområde tallene som genereres skal være i, du må her oppgi dette på formatet 'min..max' der 'min' og 'max' kan være heltall, 'n' (for hvor mange tall som genereres) og de regneoperasjonene +, -, *, /

- når sorteringen starter kan du senke og øke hastigheten ved å trykke '-'- og '+'-knappene, og velge om du vil vise lese-operasjoner eller ikke ved å trykke 'W'/'RW'-knappen

 

Når sorteringen er i gang, vises verdiene som søylediagram (svarte), leseoperasjoner er gule og skriveoperasjoner er røde. Hvis algoritmene allokerer ekstra minne (f.eks. ved 'merging') vises dette som søylediagram under (det øverste diagrammet er alltid den listen med tall som sorteres, og der resultatet vil havne)

 

 

Her er noen eksempler på hvordan ting ser ut:

 

 

Edit: Har gjort noen endringer på programmet:

- lagt til flere sorteringsalgoritmer (bubble sort, cycle sort, "dobbel" selection sort og heap sort)

- fikset radix sort slik at den takler negative tall (algoritmen kommer opprinnelig fra UiO (INF2440), og taklet ikke negative tall slik den ble levert derfra)

- genereringen av tilfeldige tall endret, slik at 'randomness' sier hvor mye hvert tall kan avvike fra standard verdi, isteden for å si ca. hvor mange tall som blir tilfeldig generert

SortTester.zip

Endret 22. mai 2015 av jonny

[Matsemann]

Stilig visualisering!

 

Er koden tilgjengelig noen plass? Gjør det lettere å teste ut alternative approaches.

[jonny]

Stilig visualisering!

 

Er koden tilgjengelig noen plass? Gjør det lettere å teste ut alternative approaches.

 

Jeg har ikke lagt ut koden noe sted. En ting er at enkelte deler av koden er veldig dårlig kommentert, spesielt GUI-delen. En annen ting som gjør at jeg er usikker på om det er lurt, er at dette kun er tillegg (påbygg) til en obligatorisk oppgave ved UiO. Kan selvfølgelig fjerne den delen som er mest sentral ifm. den oppgaven (flertrådet radix-sortering), men...