Song song chức năng biểu đồ

Question

Tôi đã thực hiện một verion bình thường và song song của một hàm đơn giản để tính toán biểu đồ từ bitmap 32bppArgb. Phiên bản bình thường mất khoảng 0,03 giây trên một hình ảnh 1920x1080 trong khi phiên bản song song mất 0,07 giây.

Luồng trên luồng có thực sự nặng không? Có một số cấu trúc khác ngoài Parallel.For có thể tăng tốc quá trình này? Tôi cần tăng tốc độ này kể từ khi tôi làm việc với video 30fps.

Đây là mã đơn giản:

public sealed class Histogram 
{ 
    public int MaxA = 0; 
    public int MaxR = 0; 
    public int MaxG = 0; 
    public int MaxB = 0; 
    public int MaxT = 0; 

    public int [] A = null; 
    public int [] R = null; 
    public int [] G = null; 
    public int [] B = null; 

    public Histogram() 
    { 
     this.A = new int [256]; 
     this.R = new int [256]; 
     this.G = new int [256]; 
     this.B = new int [256]; 

     this.Initialize(); 
    } 

    public void Initialize() 
    { 
     this.MaxA = 0; 
     this.MaxR = 0; 
     this.MaxG = 0; 
     this.MaxB = 0; 
     this.MaxT = 0; 

     for (int i = 0; i < this.A.Length; i++) 
      this.A [i] = 0; 
     for (int i = 0; i < this.R.Length; i++) 
      this.R [i] = 0; 
     for (int i = 0; i < this.G.Length; i++) 
      this.G [i] = 0; 
     for (int i = 0; i < this.B.Length; i++) 
      this.B [i] = 0; 
    } 

    public void ComputeHistogram (System.Drawing.Bitmap bitmap, bool parallel = false) 
    { 
     System.Drawing.Imaging.BitmapData data = null; 

     data = bitmap.LockBits 
     (
      new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height), 
      System.Drawing.Imaging.ImageLockMode.ReadOnly, 
      System.Drawing.Imaging.PixelFormat.Format32bppArgb 
     ); 

     try 
     { 
      ComputeHistogram(data, parallel); 
     } 
     catch 
     { 
      bitmap.UnlockBits(data); 

      throw; 
     } 

     bitmap.UnlockBits(data); 
    } 

    public void ComputeHistogram (System.Drawing.Imaging.BitmapData data, bool parallel = false) 
    { 
     int stride = System.Math.Abs(data.Stride); 

     this.Initialize(); 

     if (parallel) 
     { 
      unsafe 
      { 
       System.Threading.Tasks.Parallel.For 
       (
        0, 
        data.Height, 
        new System.Threading.Tasks.ParallelOptions() { MaxDegreeOfParallelism = System.Environment.ProcessorCount }, 
        y => 
        { 
         byte* pointer = ((byte*) data.Scan0) + (stride * y); 

         for (int x = 0; x < stride; x += 4) 
         { 
          this.B [pointer [x + 0]]++; 
          this.G [pointer [x + 1]]++; 
          this.R [pointer [x + 2]]++; 
          this.A [pointer [x + 3]]++; 
         } 
        } 
       ); 
      } 
     } 
     else 
     { 
      unsafe 
      { 
       for (int y = 0; y < data.Height; y++) 
       { 
        byte* pointer = ((byte*) data.Scan0) + (stride * y); 

        for (int x = 0; x < stride; x += 4) 
        { 
         this.B [pointer [x + 0]]++; 
         this.G [pointer [x + 1]]++; 
         this.R [pointer [x + 2]]++; 
         this.A [pointer [x + 3]]++; 
        } 
       } 
      } 
     } 

     for (int i = 0; i < this.A.Length; i++) 
      if (this.MaxA < this.A [i]) this.MaxA = this.A [i]; 
     for (int i = 0; i < this.R.Length; i++) 
      if (this.MaxR < this.R [i]) this.MaxR = this.R [i]; 
     for (int i = 0; i < this.G.Length; i++) 
      if (this.MaxG < this.G [i]) this.MaxG = this.G [i]; 
     for (int i = 0; i < this.B.Length; i++) 
      if (this.MaxB < this.B [i]) this.MaxB = this.B [i]; 

     if (this.MaxT < this.MaxA) this.MaxT = this.MaxA; 
     if (this.MaxT < this.MaxR) this.MaxT = this.MaxR; 
     if (this.MaxT < this.MaxG) this.MaxT = this.MaxG; 
     if (this.MaxT < this.MaxB) this.MaxT = this.MaxB; 
    } 
} 

Answer 1

Vâng, trước hết, bạn đã có một lỗi rất lớn trong vòng lặp song song của bạn:

Bạn sẽ có nhiều đề truy cập, incrementing, và cập nhật các mảng chia sẻ - chỉ cần chạy mã mẫu của bạn trên cùng hình ảnh nhiều lần dẫn đến kết quả cực kỳ khác nhau do các điều kiện chủng tộc vốn có.

Nhưng đó không phải là những gì bạn đã hỏi. Đối với lý do tại sao bạn thấy hiệu suất giảm khi thực hiện song song, câu trả lời đơn giản là bạn có thể không làm đủ công việc trong từng tác vụ song song để bù đắp "chi phí spinup" của việc tạo tác vụ mới Lập kế hoạch, vv ..

Có lẽ điều quan trọng hơn là tôi tin rằng bạn đang đẩy địa ngục ra khỏi bộ nhớ cache L1/L2 với tất cả việc nhảy xung quanh trong bộ nhớ - mỗi chuỗi nhiệm vụ sẽ cố gắng tải những gì nó nghĩ sẽ cần vào bộ nhớ cache, nhưng khi bạn đang lập chỉ mục trên toàn bộ địa điểm, bạn không còn tạo ra mẫu truy cập nhất quán, vì vậy bạn có thể sẽ bị nhớ cache mỗi khi bạn cố gắng truy cập bộ đệm bitmap hoặc mảng nội bộ .

Ngoài ra còn có một cách bình đẳng performant nhận ở các dữ liệu chỉ đọc của bitmap mà không sử dụng mã không an toàn ... thực sự, chúng ta hãy làm điều đó đầu tiên:

Vì vậy, bạn có, bằng cách gọi LockBits, một con trỏ tới bộ nhớ không được quản lý . Hãy tạo một bản sao của nó:

System.Drawing.Imaging.BitmapData data = null; 
data = bitmap.LockBits 
(
    new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height), 
    System.Drawing.Imaging.ImageLockMode.ReadOnly, 
    System.Drawing.Imaging.PixelFormat.Format32bppArgb 
); 

// For later usage 
var imageStride = data.Stride; 
var imageHeight = data.Height; 

// allocate space to hold the data 
byte[] buffer = new byte[data.Stride * data.Height]; 

// Source will be the bitmap scan data 
IntPtr pointer = data.Scan0; 

// the CLR marshalling system knows how to move blocks of bytes around, FAST. 
Marshal.Copy(pointer, buffer, 0, buffer.Length); 

// and now we can unlock this since we don't need it anymore 
bitmap.UnlockBits(data); 

ComputeHistogram(buffer, imageStride, imageHeight, parallel); 

Bây giờ, như đối với tình trạng chủng tộc - bạn có thể khắc phục điều này một cách hợp lý performant bằng Interlocked cuộc gọi đến bump lên đếm (LƯU Ý !!! lập trình đa luồng là HARD, và nó hoàn toàn có thể giải pháp của tôi ở đây không phải là hoàn hảo!)

public void ComputeHistogram (byte[] data, int stride, int height, bool parallel = false) 
{ 
    this.Initialize(); 

    if (parallel) 
    { 
     System.Threading.Tasks.Parallel.For 
     (
      0, 
      height, 
      new ParallelOptions() { MaxDegreeOfParallelism = Environment.ProcessorCount }, 
      y => 
      { 
       int startIndex = (stride * y); 
       int endIndex = stride * (y+1); 
       for (int x = startIndex; x < endIndex; x += 4) 
       { 
        // Interlocked actions are more-or-less atomic 
        // (caveats abound, but this should work for us) 
        Interlocked.Increment(ref this.B[data[x]]); 
        Interlocked.Increment(ref this.G[data[x+1]]); 
        Interlocked.Increment(ref this.R[data[x+2]]); 
        Interlocked.Increment(ref this.A[data[x+3]]); 
       } 
      } 
     ); 
    } 
    else 
    { 
     // the original way is ok for non-parallel, since only one 
     // thread is mucking around with the data 
    } 

    // Sorry, couldn't help myself, this just looked "cleaner" to me 
    this.MaxA = this.A.Max(); 
    this.MaxR = this.R.Max(); 
    this.MaxG = this.G.Max(); 
    this.MaxB = this.B.Max(); 
    this.MaxT = new[] { this.MaxA, this.MaxB, this.MaxG, this.MaxR }.Max(); 
} 

Vì vậy, điều này làm gì với hành vi thời gian chạy?

Không phải là toàn bộ, nhưng ít nhất là ngã ba song song tính toán kết quả chính xác ngay bây giờ.:)

Sử dụng một giàn khoan thử nghiệm thực sự cheapo:

void Main() 
{  
    foreach(var useParallel in new[]{false, true}) 
    { 
     var totalRunTime = TimeSpan.Zero; 
     var sw = new Stopwatch(); 
     var runCount = 10; 
     for(int run=0; run < runCount; run++) 
     { 
      GC.Collect(); 
      GC.WaitForPendingFinalizers(); 
      GC.Collect(); 
      sw.Reset(); 
      sw.Start(); 
      var bmp = Bitmap.FromFile(@"c:\temp\banner.bmp") as Bitmap; 
      var hist = new Histogram(); 
      hist.ComputeHistogram(bmp, useParallel); 
      sw.Stop(); 
      totalRunTime = totalRunTime.Add(sw.Elapsed); 
     } 
     Console.WriteLine("Parallel={0}, Avg={1} ms", useParallel, totalRunTime.TotalMilliseconds/runCount); 
    } 
} 

tôi nhận được kết quả như thế này:

Parallel=False, Avg=1.69777 ms 
Parallel=True, Avg=5.33584 ms 

Như bạn có thể thấy, chúng ta vẫn chưa giải quyết câu hỏi ban đầu của bạn. :)

Vì vậy, chúng ta hãy xem một đâm vào làm cho công việc song song "nhiều hơn":

Hãy xem những gì "cho công việc nhiều hơn" với nhiệm vụ thực hiện:

if (parallel) 
{ 
    var batchSize = 2; 
    System.Threading.Tasks.Parallel.For 
    (
     0, 
     height/batchSize, 
     new ParallelOptions() { MaxDegreeOfParallelism = Environment.ProcessorCount }, 
     y => 
     { 
      int startIndex = (stride * y * batchSize); 
      int endIndex = startIndex + (stride * batchSize); 
      for (int x = startIndex; x < endIndex; x += 4) 
      { 
       // Interlocked actions are more-or-less atomic 
       // (caveats abound, but this should work for us) 
       Interlocked.Increment(ref this.B[data[x]]); 
       Interlocked.Increment(ref this.G[data[x+1]]); 
       Interlocked.Increment(ref this.R[data[x+2]]); 
       Interlocked.Increment(ref this.A[data[x+3]]); 
      } 
     } 
    ); 
} 

Kết quả:

Parallel=False, Avg=1.70273 ms 
Parallel=True, Avg=4.82591 ms 

Ooh, có vẻ đầy hứa hẹn ... Tôi tự hỏi điều gì xảy ra khi chúng tôi thay đổi batchSize?

Hãy thay đổi giàn khoan thử nghiệm của chúng tôi thusly:

void Main() 
{  
    foreach(var useParallel in new[]{false, true}) 
    { 
     for(int batchSize = 1; batchSize < 1024; batchSize <<= 1) 
     { 
      var totalRunTime = TimeSpan.Zero; 
      var sw = new Stopwatch(); 
      var runCount = 10; 
      for(int run=0; run < runCount; run++) 
      { 
       GC.Collect(); 
       GC.WaitForPendingFinalizers(); 
       GC.Collect(); 
       sw.Reset(); 
       sw.Start(); 
       var bmp = Bitmap.FromFile(@"c:\temp\banner.bmp") as Bitmap; 
       var hist = new Histogram(); 
       hist.ComputeHistogram(bmp, useParallel, batchSize); 
       sw.Stop(); 
       totalRunTime = totalRunTime.Add(sw.Elapsed); 
      } 
      Console.WriteLine("Parallel={0}, BatchSize={1} Avg={2} ms", useParallel, batchSize, totalRunTime.TotalMilliseconds/runCount); 
     }   
    } 
} 

Kết quả: (chỉ hiển thị song song = true, vì không song song sẽ không thay đổi)

Parallel=True, BatchSize=1 Avg=5.57644 ms 
Parallel=True, BatchSize=2 Avg=5.49982 ms 
Parallel=True, BatchSize=4 Avg=5.20434 ms 
Parallel=True, BatchSize=8 Avg=5.1721 ms 
Parallel=True, BatchSize=16 Avg=5.00405 ms 
Parallel=True, BatchSize=32 Avg=4.44973 ms 
Parallel=True, BatchSize=64 Avg=2.28332 ms 
Parallel=True, BatchSize=128 Avg=1.39957 ms 
Parallel=True, BatchSize=256 Avg=1.29156 ms 
Parallel=True, BatchSize=512 Avg=1.28656 ms 

Chúng tôi dường như được tiếp cận một tiệm cận của các loại khi chúng tôi crest phạm vi 64-128 trong kích thước hàng loạt, mặc dù tất nhiên mileage của bạn có thể khác nhau tùy thuộc vào kích thước bitmap của bạn, vv

Tôi hy vọng điều này sẽ giúp! Đó là một sự phân tâm thú vị từ ngày tôi chờ đợi để xây dựng sản phẩm hoàn thành! :)

Answer 2

đề Tạo đã có khá một trên không đáng kể. Việc thực hiện có thể chạy nhanh hơn đáng kể so với phiên bản luồng đơn, nhưng hoàn thành quá nhanh để bù đắp cho chi phí ban đầu này.

Nếu bạn làm điều này mỗi khung hình, nó sẽ chỉ làm chậm bạn xuống.

Tuy nhiên, nếu bạn tạo thủ công một threadpool, gán thủ công công việc và sử dụng lại các chuỗi cho mỗi khung, bạn có thể thấy rằng bằng khung hai hoặc ba tên mã của bạn qua phiên bản luồng đơn.