Параллельное программирование для ускорения обработки информации

[Dimarik_1]

Мне необходимо выполнить бинаризацию изображения с использованием k-means на 2 кластера.
Делаю я следующим образом:
1. сначала я подготавливаю массив массивов. Чтобы каждая ячейка соответствовала своему потоку. и в каждой ячейке содержались только те данные, которые будет своё ядро обрабатывать. Для оптимизации так сделал.
вот таким образом я раскидываю. Тут вроде ничего интересного. Всё правильно вроде. Просто так код приложил

public void IdentifyPointsArray(int iSize, int iThreadCount)
        {
            iPointPointer = 0; // указатель на текущую точку
             _iPointsInEveryThread = iSize / iThreadCount;
             _iDivThread = iSize % iThreadCount;
            _dPointsArrayParallel = new double[iThreadCount][][];//сюда нужно раскидать точки изображения _dPoints[][]
            for (int i = 0; i < iThreadCount; i++)
            {
                if (iThreadCount - i > 1)
                {
                    _dPointsArrayParallel[i] = new double[_iPointsInEveryThread][];
                }
                else
                {
                    _dPointsArrayParallel[i] = new double[_iPointsInEveryThread + _iDivThread][];
                }


                int iPointsInThread = _dPointsArrayParallel[i].Length;
                for (int j = 0; j < iPointsInThread; j++)
                {
                    _dPointsArrayParallel[i][j] = new double[3];
                     //раскидать точки по ячейкам массива точек для потоков
                    _dPointsArrayParallel[i][j][0] = _dPoints[iPointPointer][0];
                    _dPointsArrayParallel[i][j][1] = _dPoints[iPointPointer][1];
                    _dPointsArrayParallel[i][j][2] = _dPoints[iPointPointer][2];
                    iPointPointer++;
                }
            }
    
        }

Затем я выполняю бинаризацию изображения (все точки изображения делю на 2 класса). Приложил код. Вдруг я меряю время неправильно. Мне нужно замерять время выполнения GetBarycentresParallel

Stopwatch stMy = new Stopwatch();
                    stMy.Reset();   
                    stMy.Start();
                    kMeansObject.GetBarycentresParallel(j);
                    stMy.Stop();
                    dTime[i] = stMy.Elapsed.TotalSeconds;
                    dSumTime += dTime[i];

Всю функцию GetBarycentresParallel не стал приводить, приведу наиболее значимый её кусок (во этого объявления переменных и прочая ерунда, не сильно нагружающая процессор

while (true)
            {
                iCountSteps++;
                //занулить суммы
                _dPointsSum[0, 0] = 0;
                _dPointsSum[0, 1] = 0;
                _dPointsSum[0, 2] = 0;
                _dPointsSum[1, 0] = 0;
                _dPointsSum[1, 1] = 0;
                _dPointsSum[1, 2] = 0;
                
               _iPointsIn0 = 0;
             _iPointsIn1 = 0;
                ////////////////////////////////////////////////////////////////////
                //1. определить кластеры по текущим центрам
             Parallel.For(0, iThreadsCount, options, IdentifyPointIntoClusterByThreadArray);
                dPointsInclust[0] = _iPointsIn0;
                dPointsInclust[1] = _iPointsIn1;
                //2. Определить новые центры кластеров

                //сохранить значения центров кластеров на предыдущем шаге
             _dBaryCentresPrevious[0][0] = _dBaryCentres[0][0];
             _dBaryCentresPrevious[0][1] = _dBaryCentres[0][1];
             _dBaryCentresPrevious[0][2] = _dBaryCentres[0][2];
             _dBaryCentresPrevious[1][0] = _dBaryCentres[1][0];
             _dBaryCentresPrevious[1][1] = _dBaryCentres[1][1];
             _dBaryCentresPrevious[1][1] = _dBaryCentres[1][2];
             for (int i = 0; i < 2; i++)
             {
                 for (int j = 0; j < 3; j++)
                 {
                     //сохраняем значение
                     _dBaryCentresPrevious[i][j] = _dBaryCentres[i][j];
                     _dBaryCentres[i][j] = _dPointsSum[i, j] / dPointsInclust[i];
                 }
             }

             dTotalSum = EvclidDistance(_dBaryCentres[0], _dBaryCentresPrevious[0]);
             dTotalSum += EvclidDistance(_dBaryCentres[1], _dBaryCentresPrevious[1]);
             if (iCountSteps > 10)
             {
                 break;
             }

            }

Самое интересное - эта строчка. От неё все и зависит.
Вот код функции

public void IdentifyPointsArray(int iSize, int iThreadCount)
        {
            iPointPointer = 0; // указатель на текущую точку
             _iPointsInEveryThread = iSize / iThreadCount;
             _iDivThread = iSize % iThreadCount;
            _dPointsArrayParallel = new double[iThreadCount][][];//сюда нужно раскидать точки изображения _dPointe[][]
            for (int i = 0; i < iThreadCount; i++)
            {
                if (iThreadCount - i > 1)
                {
                    _dPointsArrayParallel[i] = new double[_iPointsInEveryThread][];
                }
                else
                {
                    _dPointsArrayParallel[i] = new double[_iPointsInEveryThread + _iDivThread][];
                }


                int iPointsInThread = _dPointsArrayParallel[i].Length;
                for (int j = 0; j < iPointsInThread; j++)
                {
                    _dPointsArrayParallel[i][j] = new double[3];
                     //раскидать точки по ячейкам массива точек для потоков
                    _dPointsArrayParallel[i][j][0] = _dPoints[iPointPointer][0];
                    _dPointsArrayParallel[i][j][1] = _dPoints[iPointPointer][1];
                    _dPointsArrayParallel[i][j][2] = _dPoints[iPointPointer][2];
                    iPointPointer++;
                }
            }
    
        }

Вроде бы самое сложное место распараллелил. Логично, что если 1 ядря, то выполняется, например, 100 секунд, если 2 ядра то 50 секунд, если 3 то 30 и так далее. Естественно, 50 и 30 это идеальные варианты и вполне неплохо было бы, если бы было 60 и 40, как пример. Но у меня совсем не то что надо получается. вот мои результаты. Распараллеливание даже отрицательный эффект по скорости дало почему-то:

Size image {Width=3976, Height=3299} time 34,45929 processors 1
Size image {Width=3976, Height=3299} time 52,25169305 processors 2
Size image {Width=3976, Height=3299} time 49,773416025 processors 3
Size image {Width=3976, Height=3299} time 44,0997120125 processors 4
Size image {Width=3976, Height=3299} time 38,79137545625 processors 5
Size image {Width=3976, Height=3299} time 34,887025578125 processors 6
Size image {Width=3976, Height=3299} time 31,8754485390625 processors 7
Size image {Width=3976, Height=3299} time 29,6087524195313 processors 8
Size image {Width=3976, Height=3299} time 27,7327576597656 processors 9
Size image {Width=3976, Height=3299} time 26,4133148798828 processors 10
Size image {Width=3976, Height=3299} time 25,2272720399414 processors 11
Size image {Width=3976, Height=3299} time 24,6323545199707 processors 12

Процессор i7-3930k. Количество ядер процессора 6, количество потоков процессора 12.
Почему так печально у меня получается со скоростью?

[New man]

Ну, на создание и синхронизацию потоков отводится время. Я не помню формулу, которую нам в универе давали но там нужно было что-то вроде T = t/core_number + latency

Ну, в общем неважно.

У тебя же на 10 секунд лучше стало, чем недоволен?

И да, я вообще нифига не понял, что за магия у тебя в сохранении предыдущих центроидов. Заведи для этого лучше какой-то отдельный список.

А так, вангую, что проблема в том, что ты в каждый цикл работы KMeans в каждом потоке выделяешь память. Это очень накладная операция.

Я бы так сделал (это что-то вроде псевдокода):

int[] pointClusterIndex = new int[points];
point[] lastClusterCentroids = new point[clusterCount];
List<point[]> oldCentroids = new List<>();
initRandomPointsAsCenters // как-то выбираем из точек случайные два
// Вообще, лучше юзать ThreadPool, но я хз, как там синхронизацию делать, так как сам вообще на Java пишу обычно
      // С ним будет меньше расходов на обработку потоков
      Thread[] threads = new Thread[threadNum];
      for (int i = 0..threadNum)
            {
                  threads[i]= new Thread((i)={
                        for(pointIndex in i*(points/threadNum) + (i+1)*(points/threadNum))
{
                                    pointClusterIndex[pointIndex] = chooseCluster(point[pointIndex], lastClusterCentroids);
                              }
                  })
            }
for (int i = 0; < 300; i++){
      foreach(thread in Threads){
            thread.start(); // Хз, мне кажется, так делать нельзя. Если нельзя, то надо executorService вместо массива тредов заюзать
// И вытастивать инфу чем-то вроде FutureCallable.
      }
      foreach(thread in threads) thread.join();
      Сохраняем инфу.
}

Фишка в том, что надо бы избежать выделения памяти и создания потоков в цикле работы алгоритма, так как это жутко долго и сводит на нет пользу от распарраллелирования.

UPD: А вообще да, попробуй вынести создание массивов за пределы цикла, может этого уже будет достаточно для тебя.

[Dimarik_1]

Решил накидать простенькую задачу: выполнить какие-нибудь операции над большим блоком данных. И это все распараллелить. Это можно сделать 2мя способами:
1. Параллелить вызов коротеньких процедур. Но тогда будет очень много времени тратиться на то, чтобы передать управление другому ядру. Ведь так? ну нет смысла параллелить операцию 2+2.
2. Параллелить обработку блоков данных. Логично предположить. что когда параллельно запускаться будут тяжелые процедуруы, эффект от параллельности будет гораздо выше.
Однако оказались весьма странные результаты. Почему-то первоначальный эффект от параллельности отрицательный.
Вот код простой программки, которая наглядно всё демонстрирует:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Diagnostics;
using System.Threading;
namespace WindowsFormsApplication2
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        double [] _dArray = new double[10000000];
        double[] _dArray2 = new double[10000000];
        int _iThreads = 8;
        int _iSizeBlock;
  
        private void button1_Click(object sender, EventArgs e)
        {
            _iSizeBlock = _dArray.Length / _iThreads;//размер блока
            
            //заполним массив случайно
            Random r = new Random();
            for (int i = 0; i < _dArray.Length; i++)
            {
                _dArray[i] = r.NextDouble();
                _dArray2[i] = _dArray[i];
            }
             richTextBox1.Text = "1 итерация:\r\n";
             for (int i = 1; i <= 8; i++)
             {
                 ParallelOptions options = new ParallelOptions
            {
                MaxDegreeOfParallelism = i
            };
                 Stopwatch st1 = new Stopwatch();
                 st1.Start();
                 Parallel.For(0, _dArray.Length, options, parallelOne);
                 st1.Stop();
                 richTextBox1.Text += i.ToString() + " поток, время: " + st1.Elapsed.TotalSeconds.ToString() + "\r\n";
             }

             richTextBox1.Text += "Блок итераций:\r\n";
             for (int i = 1; i <= 8; i++)
             {
                 ParallelOptions options = new ParallelOptions
                 {
                     MaxDegreeOfParallelism = i
                 };
                 Stopwatch st1 = new Stopwatch();
                 st1.Start();
                 Parallel.For(0, i, options, ParallelBlock);
                 st1.Stop();
                 richTextBox1.Text += i.ToString() + " поток, время: " + st1.Elapsed.TotalSeconds.ToString() + "\r\n";
             }
           
        }
        
        private void ParallelBlock(int iIndex)
        {
            int iStart = iIndex * _iSizeBlock;
            int iEnd = iStart + _iSizeBlock;
            //iIndex - номер блока
            for (int i = iStart; i < iEnd; i++)
            {
                _dArray[i] = Someoperations(_dArray[i]);
            }
        }
        private void parallelOne(int iIndex)
        {
            _dArray[iIndex] = Someoperations(_dArray[iIndex]);
        }
        private double Someoperations(double dInput)
        {
            double Result = Math.Sin(dInput) * Math.Log(dInput + 10);
            Result = Math.Pow(Result, 10);
            Result += Math.Abs(Math.Cos(Result));
            Result += Math.Sqrt(Result);
            Result = Math.Pow(Result, 2);
            return Result;
        }
    }
}

А вот результат.
1 итерация:
1 поток, время: 2,5947303
2 поток, время: 1,5046816
3 поток, время: 1,2435103
4 поток, время: 1,1743574
5 поток, время: 1,8177255
6 поток, время: 1,8564871
7 поток, время: 1,7038264
8 поток, время: 1,7404472
Блок итераций:
1 поток, время: 1,2824387
2 поток, время: 1,2592897
3 поток, время: 1,3303499
4 поток, время: 1,3710368
5 поток, время: 1,4195757
6 поток, время: 1,4460356
7 поток, время: 1,5213963
8 поток, время: 1,6072681

Как видно, во втором случае результат очень плохой. То есть распараллеливание медленно отрабатывает. Почему так? Ведь по логике второй способ распараллеливания должен быть лучше первого?