Gå til innhold

C#: Hvordan bruke Parallell.For til å finne max i 2D array?

Mr Burns

Anbefalte innlegg

Mr Burns

Mr Burns

Skrevet
Skrevet

Jeg har et bilde, lagret som 2D array. En del av operasjonene jeg skal ta på bildet trenger å vite maxverdien. Nå kjører jeg bare gjennom alle elementene, og lagrer den høyeste jeg finner med en foreach.

 

double m = im[0, 0];
foreach (double d in im)
{
  if (d > m)
  m = d;
}

Lenke til kommentar

Videoannonse

Videoannonse
Annonse
GeirGrusom

GeirGrusom

Skrevet
Skrevet

Du kan dele det opp i et to-lags tre:

 

la oss si fire tråder:

 

Hver tråd tar (for eksempel) en linje, og finner maks verdien på den linjen, og returnerer det til en samle-tråd. Samle tråden finner så maksverdien av de, og starter fire nye tråder, og fortsetter til alle pikslene er vurdert.

Lenke til kommentar
Mr Burns

Mr Burns

Skrevet
  • Forfatter
Skrevet

Testet litt nå, od ser at en dobbel for loop er raskere en foreach loop. Hvis jeg bruker en Parallell.For loop ytterst er det fremdeles raskere med dobbel for-loop. I dette tilfellet er parallellisering bortkastet. En mer krevende operasjon, som å beregne standardavvik vil nok tjene på parallellisering.

 

MailMan, det ser ikke ut til at SelectMany virker på 2D-array.

Lenke til kommentar
Mr Burns

Mr Burns

Skrevet
  • Forfatter
Skrevet (endret)

Her er et lite benchmark av ulike måter å søke etter max i en 10000x10000 2D array eller jagged array, i de fire siste er det brukt jagged arrays:

ForEach:	2005, 	max: 254,999998337589
For:		1479, 	max: 254,999998337589
ParallellFor:	2180, 	max: 254,999998337589
jForEach:	839, 	max: 254,999998337589
jFor:		866, 	max: 254,999998337589
jParallellFor:	1831, 	max: 254,999998337589
jAsParallell:	3470, 	max: 254,999998337589

Jagged arrays er tydeligvis veien å gå. Parallellisering er bortkastet på en så liten arbeidsmengde. Dette kjørte på en Win7 64bit, Xeon E5405 2GHz maskin.

Endret av Mr Burns
Lenke til kommentar
GeirGrusom

GeirGrusom

Skrevet
Skrevet (endret)

Fullt lovlig å bruke unsafe på arrays også, men vet ikke helt om det har noe for seg. Kanskje verd å prøve?

 

fixed(int* ptr = bilde)
{
}

Funker forøvrig også på arrays som ikke er jagged også, som gjør at du kan unslippe oversetningen fra to- til en-dimensjonal indeks.

Endret av GeirGrusom
Lenke til kommentar
MailMan13

MailMan13

Skrevet
Skrevet (endret)
Parallellisering er bortkastet på en så liten arbeidsmengde. Dette kjørte på en Win7 64bit, Xeon E5405 2GHz maskin.

Hvis du starter tråder i thread poolen hver gang så er det kanskje meningsløst.

 

Det er mulig å starte trådene du trenger i oppstart av programmet så ha dem stående på en AutoResetEvent til dem trengs. Det er mye raskere å invokere en AutoResetEvent enn det er å hente en tråd i ThreadPool. Kan kanskje være en mulighet hvis det er noe som kjøres ofte? Disclaimer: Usikker på hva kostnaden ved å ha tråder stående slik er...

 

 

"Kode til det virker-eksempel": - (ie, mye kode som bør pakkes pent inn ;) )

 

 

 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;


namespace ConsoleApplication2
{

   static class Program
   {
       private static AutoResetEvent[] blocker = new AutoResetEvent[4];
       private static AutoResetEvent[] done = new AutoResetEvent[4];
       private static Func<int>[] work = new Func<int>[4];
       private static int[] result = new int[4];

       static void Main(string[] args)
       {
           // random testdata, 10k x 10k
           var rnd = new Random();
           var numbers = Enumerable.Range(0, 10000).Select(x => Enumerable.Range(0, 10000).Select(y => rnd.Next()).ToArray()).ToArray();


           // sett opp signaler og start tråder
           for (int i = 0; i < 4; i++)
           {
               var index = i;
               blocker[i] = new AutoResetEvent(false);
               done[i] = new AutoResetEvent(false);
               Action worker = () => DoWork(index);
               worker.BeginInvoke(null, null);
           }

           var st = new Stopwatch();
           st.Start();
           var res = numbers.GetMax();
           st.Stop();
           Console.WriteLine(String.Format("Time spent {0}ms, max: {1}", st.ElapsedMilliseconds, res  ));
           Console.ReadLine();
       }

       private static int  GetMax(this int[][] numbers)
       {
           var count = numbers.Count();

           //sett opp arbeid
           for (int i = 0; i < 4; i++)
           {
               var index = i;
               var n = numbers.Skip(index * count / 4).Take(count / 4);
               work[i] = () => FindMax(n);
           }


           // start arbeidere            
           foreach (var b in blocker)
               b.Set();
           // vent til alle er ferdig
           foreach (var d in done)
               d.WaitOne();

           return  result.Max(x => x);
       }

       private static int FindMax(IEnumerable<int[]> numbers)
       {
           int max = 0;
           foreach (var ns in numbers)
               foreach (var n in ns)
                   max = Math.Max(n, max);
           return max;
       }

       public static void DoWork(int index)
       {
           while (true)
           {
               blocker[index].WaitOne();
               result[index] = work[index]();
               done[index].Set();
           }
       }
   }
}

 

 

 

Jeg vet, ikke det mest elegante eksempelet jeg har sett...

 

Fire tråder:

Time spent 43ms, max: 2147483599

 

For-loop tar ca 110ms på min maskin (Xeon X3540).

 

Edit: redudant ToArray-kall tok 10ms ekstra...

Endret av MailMan13
Lenke til kommentar
GeirGrusom

GeirGrusom

Skrevet
Skrevet (endret)

Her er en som bruker unsafe:

 

 

 

class Program
   {
       public static void Main2(string[] args)
       {

           int[,] img = new int[10000, 10000];
           Random rnd = new Random();
           for (int i = 0; i < 10000; i++)
           {
               for (int j = 0; j < 10000; j++)
               {
                   img[i, j] = rnd.Next() % 0x00ffffff;
               }
           }
           Stopwatch sw = new Stopwatch();

           sw.Start();
           int max = FindImageMax(img);

           sw.Stop();

           Console.WriteLine(string.Format("(Unsafe)Finished in {0} ms; max = {1}", sw.ElapsedMilliseconds, max));
           Console.ReadLine();

       }

       static IEnumerable<int> Range(int count)
       {
           while (--count >= 0)
               yield return count;
       }

       static int FindImageMax(int[,] image)
       {
           unsafe
           {
               fixed(int* ptr = image)
               {
               // Store vertical indices wghich will be dispathed to threads
                   int horizontal_size = image.GetLength(0);
                   int vertical_size = image.GetLength(1);

                   var vertical_indices = Range(vertical_size).ToArray();

                   var vertical_values = new int[vertical_size];

                   IntPtr pointer = new IntPtr(ptr);
                   vertical_indices.AsParallel().ForAll((index) =>
                       {
                           vertical_values[index] = FindArrayMax(pointer, index, horizontal_size);
                       });

                   int value = int.MinValue;

                   for (int i = 0; i < vertical_size; i++)
                       if (vertical_values[i] > value)
                           value = vertical_values[i];
                   return value;

               }
           }
       }

       static unsafe int FindArrayMax(IntPtr start, int index, int count)
       {
           int current = int.MinValue;
           int* ptr = (int*)start.ToPointer();
           int* end = ptr + count;

           while(ptr < end)
           {
               if (*ptr > current)
                   current = *ptr;
               ++ptr;
           }
           return current;

       }
   }

 

135 vs 185 ms (MailMan sin mer trygge versjon)

Så litt raskere, men koden må kompileres med unsafe.

 

edit: litt formatering

 

edit2: litt snodig, men jeg fikk vesentlig dårligere hvis jeg kjørte i 64-bit... da gikk den opp til 170ms, og MailMan sin gikk opp til 300... som var ganske uventet.

Endret av GeirGrusom
Lenke til kommentar
MailMan13

MailMan13

Skrevet
Skrevet (endret)

Du har forsåvidt optimalisert bort et annet problem da, så dem ekskluderer ikke hverandre (mulig å få det ned en del mer...) ;)

 

Men jeg får 84ms på din og 43ms på min... Mulig du starter med debugger attatched? Managed varianten tar ca 3 ganger lenger tid når den starter med debugger tilkoblet hos meg... (tipper det er noe bounds-checking som ikke blir riktig optimalisert bort)

 

 

Edit:

Skejr rare ting når jeg endrer build target, ca 35-40 på begge med X64...

Endret av MailMan13
Lenke til kommentar
GeirGrusom

GeirGrusom

Skrevet
Skrevet (endret)

Under release får jeg samme som deg ja ^^

 

(Unsafe)Finished in 73 ms; max = 2147286367

(Safe)Time spent 55ms, max: 2147483642

 

Men i x86 er det ikke lenger tilfelle:

(Unsafe)Finished in 60 ms; max = 2147463918

(Safe)Time spent 71ms, max: 2147483632

Endret av GeirGrusom
Lenke til kommentar
Mr Burns

Mr Burns

Skrevet
  • Forfatter
Skrevet

Hva med double, det er det jeg bruker?

 

Jeg får 504 ms med MailMan sin kode tilpasset til double, i forhold til "min" foreach på jagged array som bruker 850 ms.

        public double jmaxForEach()
       {
           double m = jim[0][0];
           foreach (double[] d in jim)
           {
               foreach (double dd in d)
               {
                   if (dd > m)
                       m = dd;
               }
           }
           return m;
       }

Lenke til kommentar
MailMan13

MailMan13

Skrevet
Skrevet (endret)

Burde ikke være vesensforskjell. Fysiske størrelsen på dataene blir dobbelt så stor, og det blir en annen sammenligningsoperator, ellers mye det samme.

 

Kombinere en lettvekts worker/thread pool implementasjon med unsafe enumerering/sammenligning er kanskje tingen, det er ingenting i dem som ekskluderer hverandre.

Endret av MailMan13
Lenke til kommentar
GeirGrusom

GeirGrusom

Skrevet
Skrevet (endret)

Er det masse arbeid med prosessering av flyttall, så vil kanskje OpenCL være verdt å ta en titt på. Flyttall i parallell er generelt noe prosessoren er relativt dårlig egnet til i forhold til GPU-en (flere nyere prosessorer har færre FPU-er enn heltallsenheter også). Har du en GPU for OpenGL 4 eller DirectX 11, så skal oppløsningen være 64-bit også. OpenCL er tilgjengelig gjennom OpenTK biblioteket for .NET.

 

Edit: selvsagt også DirectCompute under DirectX 11, som er tilgjengelig gjennom SlimDX.

Endret av GeirGrusom
Lenke til kommentar
GeirGrusom

GeirGrusom

Skrevet
Skrevet (endret)

Kanskej jeg gjør det feil, men med OpenCL får jeg rundt 70 ms på et 2048x2048 array med 32-bit float på GeForce 210. Og det er jo mildt sagt elendig.

 

 

            string ProgramCode = @"
kernel void VectorMax(
   global read_only float* vec,
   int scanline_len,
   global write_only float* output )
{
   int index = get_global_id(0);
   int offset = index * scanline_len;
   int end = offset + scanline_len;
   float current = 0;
   int i;
   for(int i = offset; i < end; i++)
   {
     if(vec[i] > current)
       current = vec[i];
   }
   output[index] = current;    
}";

           int size = 2048;
           Stopwatch sw = new Stopwatch();
           Random rnd = new Random();
           var data = new float[size * size];
           var result = new float[size];

           for (int i = 0; i < data.Length; i++)
           {
               data[i] = (float)rnd.NextDouble();
           }

           var image_buffer = new ComputeBuffer<float>(context,  ComputeMemoryFlags.CopyHostPointer | ComputeMemoryFlags.ReadOnly, data);
           var result_buffer = new ComputeBuffer<float>(context, ComputeMemoryFlags.UseHostPointer | ComputeMemoryFlags.WriteOnly, result);

           var program = new ComputeProgram(context, ProgramCode);
           program.Build(null, null, null, IntPtr.Zero);



           var kernel = program.CreateKernel("VectorMax");


           kernel.SetMemoryArgument(0, image_buffer);
           kernel.SetValueArgument<int>(1, result.Length);
           kernel.SetMemoryArgument(2, result_buffer);

           ComputeEventList events = new ComputeEventList();

           ComputeCommandQueue commands = new ComputeCommandQueue(context, context.Devices[0], ComputeCommandQueueFlags.None);

           sw.Start();
           commands.Execute(kernel, null, new long[] { result.LongLength }, null, events);

           commands.Finish();

           commands.ReadFromBuffer(result_buffer, ref result, true, events);

           double max = -1;

           for (int i = 0; i < result.Length; i++)
               if (result[i] > max)
                   max = result[i];

           sw.Stop();

           log.WriteLine(string.Format("Max value = {0:0.000} completed in {1} ms", max, sw.ElapsedMilliseconds));

 

Endret av GeirGrusom
Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
Gå til emneliste
×
×
  • Opprett ny...